计算机网络 3：网络层

本层……

• 提供主机到主机的包（packet）传输。

• 核心功能是转发（从路由器的输入端口，转移到某个输出端口）和路由（走怎么一条路）

• 两种服务模型：无连接与有连接：

  • 虚电路网络：建立相对可靠的源与目的之间的逻辑连接。典型网络是 ATM。

  • 数据报网络：尽力而为，无连接，靠中间的一层层路由进行转发。Internet 即是此类。

IP 协议（版本 4）

IPv4 包的结构：

其中：

• 版本号为 4。

• 首部长度乘以 4 得到表示此包中「首部」的长度。对于无可选字段的 IPv4 包，此值为 5，因为 5 乘以 4 等于 20，对应整个首部的 20 字节。

• 总长度是整个包的长度，单位是字节。

尽管总长度有 16 位，理论上可以提供到 65535 字节。但由于下层协议往往支持不了这么大的完整载荷——例如，对于以太网，MTU 只有 1500 字节，所以此处最大值也就被限制到了 1500。

也因此，对于更长的数据，如果使用以太网上的 IP 协议传输，就必须分片。

IPv4 分片

对于 MTU=1500 的以太网之上的 IP 协议，假设不使用任何可选数据，则一 IP 包最大只能承载 1480 字节的数据。如果需要传输的数据比这长，就需要分片。假设需要传输的数据长度为 8000 字节。

• 计算 8000 除以 1480，得到 5，余数 600，即需要分成 6 片，最后一片有 600 个字节的数据。

• 对于第 1 片，其偏移为零（因为是开头）；对于之后的 5 片，它们的偏移分别是 185、370、555……这是 1480/8=185 的各整数倍。

• 对于前 5 片，标志位 MF=1；对于第 6 片，MF=0。

如果 MTU 不是 1500，需要特别关注 MTU-20 是否是 8 的倍数。每个 IP 数据包能承载的数据最大长度为（字节）：

\[\lfloor (MTU-20)\div8\rfloor\times8\]

所以出题一般都不用 MTU=1500 这种传统以太网。

IPv4 地址

IP 协议（版本 6）

ICMP 协议

ICMP 是在 IP 之上的协议，和 TCP / UDP 一样，它的段是封装在 IP 包内传输的。但是 ICMP 归网络层。

ICMP 报文可以分为两种：差错报告报文和网络探寻报文。其中，差错报告的 5 种常用类型如下：

DHCP 协议

用于给主机动态地分配 IP 地址。它是基于 UDP 的应用层协议，端口 67（服务器）、68（客户端）。

路由算法

链路状态路由算法

采用 Dijkstra 算法，所有结点掌握整个网络的拓扑结构。

距离向量路由算法

采用 Bellman-Ford 方程，令 \(d_x(y)\) 为「从 \(x\) 到 \(y\) 最小的费用（距离）」，则

\[d_x(y)=\min\limits_v\{c(x, v)+d_v(y)\}\]

其中 \(c(x,v)\) 是 \(x\) 到邻居 \(v\) 的费用。对于每个结点 \(c\)，它知道自己到每个邻居的费用 \(c(x,v)\)，只用知道每个邻居到终点的距离估计 \(D_v(y)\)，就可以实现最优选择。记它所有邻居的 \(D_v(y)\) 组成向量 \(\boldsymbol{D}_v(y)\)，简称 \(\boldsymbol{D}_v\)。

距离向量路由算法的核心思想：

• 每个结点不定时地将自己的 \(D_v\) 估计发送给邻居。

• 每个结点收到邻居发来的 \(D_v\) 估计时，使用上述 BF 方程更新自己的距离向量估计。

在若干次互相通告后，\(D_v\) 会收敛于实际的最优值。

如果某时刻，某链路的「费用」发生了变化，其相邻结点需要重新计算距离向量，如果 \(D_v\) 改变，需要通告自己的邻居。这会造成无穷计数问题。这篇文章介绍了这一问题。

• 好消息（即某链路费用变得更低了）传播是很快的。如果某时刻 X-Y 费用降低为 2，首先 X 检测到这一信息，降低自身到 Y 的距离并通知 Z。Z 收到消息后，降低自己到 Y 的距离并通知 X，X 检测到收敛。

• 坏消息（即某链路费用变得更高了）传播是很慢的。如果某时刻 X-Y 费用变成了 60：

  • 首先 X 检测到变化。此时 X 知道 Z-Y 距离为 5（Z-X-Y），所以重新计算 X-Y 距离为 6（X-Z-Y），但这显然是不正确的。

  • X 将上述新估计发给邻居，Z 收到后，将 Z-Y 距离更新为 7，并进行通告。

  • X 收到 Z 的通告后，又把 X-Y 距离改成了 8。

  • ……

毒性逆转可以避免部分无穷计数问题——如果 X 到达 Z 的最短路径是经过 Y 的，则在通告 Y 自己的 \(D_v\) 时，将自己到 Z 的路径设为无穷大。不能避免 2 个结点以上的环。

路由协议

Internet 采用层次路由。常见的 AS 内部路由协议（IGP）有 RIP 和 OSPF 等，而常见的 AS 间路由协议是 BGP。

RIP 协议

基于距离向量路由算法。

• 使用「跳步数」作为距离度量，最大跳步数为 15（16 表示无穷大），使用毒性逆转技术。

• 每 30 s 交换一次 \(D_v\)。

• 每次通告最多 25 个目的子网。

• 如果 180 s 没有收到通告，认为经过该邻居的链路不可用。

• 使用 UDP。

OSPF 协议

基于链路状态路由算法。

• 每个路由器构造完整的 AS 拓扑图，利用 Dijkstra 算法确定路由。

• 通告在整个 AS 内泛洪。

BGP 协议

一种 AS 间路由协议，采用距离向量路由算法。使用 TCP。