传输服务

向上层提供的服务

• 传输实体：传输层内部，利用网络层提供的服务，向它的用户提供高效、可靠和性价比合理的服务的硬件/软件
• 传输服务提供者、传输服务用户

网络层的设计要点：

• 存储-转发分组交换
• 向传输层提供服务：独立于路由器技术、路由器数量类型拓扑关系对传输层不可见、跨越多个LAN和WAN进行统一编址
• 无连接服务的实现：数据报、数据报子网
• 面向连接服务的实现：虚电路（VC，virtual circuit）、虚电路子网；要求建立电路、路由器建立表项、分组只含VC号而不需目标和源地址、路由失效将终止、容易实现服务质量和拥塞控制

介质访问控制子层（MAC，medium access control）：用于确定多路访问信道的下一个使用者，属于数据链路层底下部分。用于LAN中，而WAN是用点对点连接（卫星除外）。

设计要点

• 为网络层提供服务：无确认的无连接服务、有确认的无连接服务、有确认的面向连接服务
• 处理传输错误
• 流控制：基于反馈的流控制、基于速率的流控制

数据通信的理论基础

• 傅里叶分析
• 带宽：传输过程中振幅不会明显减弱的一段频率范围
• 尼奎斯特定理：无噪声、有限带宽信道的最大传输率=2Hlog2(V) b/s
• 香农定理：带宽为H，信噪比为S/N的信道最大传输率=Hlog2(1+S/N)

顾名思义，计算机网络是指计算机连接而成的网络。但我们首先还是需要区分一下计算机网络和分布式系统：

• 分布式系统 对于用户是一个统一的整体，只有一个模型或泛型，由操作系统之上的中间件负责实现。 eg. 万维网(world wide web)
• 计算机网络 大量独立的计算机互相连接起来共同完成计算任务。

基本的图算法

图的表示

图 G=(V,E) 可以用两种标准表示方法表示。

1. 邻接链表：由一个包含 |V| 条链表的数组 Adj 构成，每个结点有一条链表。

   权重图：直接将边 (u,v) 的权重值 w(u,v) 存放在 u 的邻接链表里。 邻接链表表示 稀疏图（边的条数|E|远小于$|V|^2$）时非常紧凑。

2. 邻接矩阵：由$|V|\times |V|$的矩阵 $A=(a_{ij})$ 表示： $a_{ij}= \begin{cases} 1,~if~(i,j)\in E\
   0,~other \end{cases} $

   邻接矩阵更适合表示 稠密图、需要快速判断任意两个点是否相连的图。