第5章 网络层：控制平面

5.1 路由问题与算法分类

5.1.1 路由问题的本质

路由（routing）解决“从源到目的走哪条路更好”的问题。路径被抽象为一系列路由器（router）组成的序列，路径“好”通常意味着代价最小、延迟最小或拥塞最小。

5.1.2 图模型与链路代价

网络通常被抽象为图 G=(N,E)：

• N：路由器集合
• E：链路集合
• c(x,y)：链路代价，可能与带宽、时延、负载相关

5.1.3 路由算法的分类

• 全局（global）：掌握完整拓扑与链路代价，如链路状态（link-state）。
• 分布式（decentralized）：只知道邻居信息，如距离向量（distance-vector）。
• 静态（static）：变化慢，人工配置多。
• 动态（dynamic）：周期或事件驱动更新。

5.2 链路状态路由算法（LS Algorithm）

5.2.1 算法思想

链路状态（Link State, LS）算法是一种全局式路由算法。

• 全局信息：每个路由器都拥有整个网络的完整拓扑结构和所有链路的代价信息。
• 信息获取：通过链路状态广播（Link State Broadcast），每个节点向全网发送自己与邻居的链路状态。
• 计算核心：每个节点独立运行 Dijkstra 算法，计算从自己到所有其他节点的最短路径树（Shortest Path Tree），进而生成转发表。

🔬

实验：Dijkstra 算法可视化

点击前往交互式实验 →

5.2.2 Dijkstra 算法实例

设源节点为 $u$，$D(v)$ 表示从 $u$ 到 $v$ 的当前最短路径代价，$p(v)$ 表示 $v$ 的前驱节点，$N^{\prime }$ 为已找到最短路径的节点集合。 步骤：

1. 初始化：$N^{\prime }=\{u\}$，对于所有 $v$，若 $u,v$ 相邻则 $D(v)=c(u,v)$，否则 $D(v)=\mathrm{\infty }$。
2. 循环：
   • 在不在 $N^{\prime }$ 中的节点中，找到 $D(w)$ 最小的节点 $w$。
   • 将 $w$ 加入 $N^{\prime }$。
   • 更新邻居：对于 $w$ 的所有邻居 $v$（且 $v\notin N^{\prime }$），更新 $D(v)=min(D(v),D(w)+c(w,v))$。
3. 结束：直到所有节点都在 $N^{\prime }$ 中。

实例演示： 考虑节点 u, x, y, z, w, v。u 为源点。

步骤	N'	D(v), p(v)	D(x), p(x)	D(y), p(y)	D(w), p(w)	D(z), p(z)
0	u	7, u	5, u	$\mathrm{\infty }$	3, u	$\mathrm{\infty }$
1	uw	6, w	5, u	11, w	3, u	$\mathrm{\infty }$
2	uwx	6, w	5, u	11, w		14, x
3	uwxv	6, w		11, w		14, x
4	uwxvy			10, y		12, y
5	uwxvyz					12, y
(注：表中数据仅为示意，实际计算需依据具体拓扑图)

5.2.3 路由振荡（Routing Oscillation）

若链路代价与拥塞程度（流量）相关，LS 算法可能导致路由振荡。

• 场景：路由器总是选择负载最小的路径。
• 过程：所有流量涌向低负载路径 $\to$ 该路径变拥塞（代价变大） $\to$ 路由算法重新计算，所有流量切向另一条路径 $\to$ 原路径空闲，新路径拥塞 $\to$ 再次切换。
• 结果：流量在两组路径间反复横跳，导致网络不稳定。
• 解决：不让所有路由器同时运行算法（引入随机延迟）。

5.3 距离矢量路由算法（DV Algorithm）

5.3.1 算法思想

距离矢量（Distance Vector, DV）算法是一种分布式、迭代、异步的算法。

• 局部信息：每个节点只知道自己到邻居的代价，以及邻居到目的地的距离估计。
• Bellman-Ford 方程：核心状态方程。$$d_x(y)=\underset{v}{min}\{c(x,v)+d_v(y)\}$$其中 $d_x(y)$ 是 $x$ 到 $y$ 的最低代价，$v$ 是 $x$ 的邻居。
• 交互：节点定期向邻居发送自己的距离向量（Distance Vector）。收到邻居的 DV 后，利用 BF 方程重新计算自己的 DV，若有变化则通知邻居。

5.3.2 DV 算法实例

以 3 个节点 x, y, z 为例，链路代价 $c(x,y)=2,c(y,z)=1,c(x,z)=7$。

1. 初始化：各节点只知直接邻居代价。$x$ 知道 $D_x=[0,2,7]$。
2. 更新：
   • $y$ 计算到 $z$ 的距离：直接是 1。
   • $x$ 收到 $y$ 的向量（$y$ 到 $z$ 是 1）。
   • $x$ 更新到 $z$ 的距离：$min(c(x,z),c(x,y)+d_y(z))=min(7,2+1)=3$。
   • $x$ 的新向量变为 $[0,2,3]$，并通告给邻居。

5.3.3 路由环路与无穷计数

距离矢量算法的一个主要问题是收敛慢，且容易产生路由环路 (Routing Loop) 和 无穷计数 (Count-to-Infinity) 问题。

• 好消息传得快：某个链路代价变小，很快传播全网。

• 坏消息传得慢（无穷计数问题）：

  • 场景：$x-y-z$，链路代价 $c(x,y)=4,c(y,z)=1,c(x,z)=50$。此时 $y$ 到 $x$ 走直接链路 (4)，$z$ 到 $x$ 经过 $y$ (1+4=5)。
  • 故障：若 $x-y$ 链路断开（代价变为 $\mathrm{\infty }$）。
  • 循环：
    1. $y$ 检测到链路断开，查找路由表。发现邻居 $z$ 说“我到 $x$ 距离是 5”（其实是 $z\to y\to x$）。
    2. $y$ 误以为可以通过 $z$ 到达 $x$，于是更新 $D_y(x)=c(y,z)+D_z(x)=1+5=6$。
    3. $y$ 告诉 $z$ “我到 $x$ 距离变为 6”。
    4. $z$ 收到后更新自己的距离：$D_z(x)=c(z,y)+D_y(x)=1+6=7$。
    5. 如此反复，$y$ 和 $z$ 的距离相互推高，直到无穷大（Count-to-Infinity）。在此期间，数据包在 $y$ 和 $z$ 之间循环转发，形成路由环路。

• 毒性逆转（Poisoned Reverse）：

  • 机制：如果 $z$ 是通过 $y$ 到达 $x$ 的，那么 $z$ 在通告给 $y$ 时，必须谎称 $d_z(x)=\mathrm{\infty }$（即“我到 $x$ 不可达”）。
  • 作用：防止 $y$ 误以为 $z$ 有一条独立的路径到达 $x$，从而避免两个节点间的直接路由环路。
  • 局限：无法解决涉及 3 个或更多节点的复杂环路。

🔬

实验：距离向量 (DV) 模拟

点击前往交互式实验 →

5.4 LS 与 DV 的比较

特性	链路状态 (LS)	距离矢量 (DV)
报文复杂性	高（需向全网广播）	低（仅与邻居交换）
收敛速度	快（$O(n^2)$ 算法，广播快）	慢（可能遇到无穷计数）
健壮性	较好（节点计算错误只影响局部）	较差（错误会传播全网）
路径计算	每个节点拥有完整拓扑	仅知道邻居和下一跳
代表协议	OSPF, IS-IS	RIP, BGP (Path Vector)

5.4 自治系统与域内/域间路由

5.4.1 自治系统（AS）概念

自治系统（Autonomous System, AS）是由单一管理机构控制的一组网络。AS 之间通过网关路由器相连。

5.4.2 域内与域间的区别

• 域内路由（intra-AS）：性能优先，协议统一。
• 域间路由（inter-AS）：策略优先，管理控制重要。

5.4.3 选择不同协议的原因

• 域内：一个管理者，强调效率
• 域间：多个管理者，强调策略与商业控制

5.5 OSPF 域内路由协议

5.5.1 OSPF 概述

OSPF (Open Shortest Path First) 是一种基于链路状态的域内路由协议（IGP），广泛应用于企业网和 ISP 内部网络。

• 开放性：公有标准（RFC 2328），非私有。
• 承载：直接运行在 IP 之上（协议号 89），不依赖 TCP/UDP。
• 度量：支持多种代价度量（如带宽、延迟），不仅是跳数。
• 特性：支持认证、支持多路径负载均衡、收敛快。

🔬

实验：OSPF 协议可视化

动态演示 OSPF 的邻居发现、DR/BDR 选举、LSA 泛洪与 SPF 计算过程。

点击前往交互式实验 →

5.5.2 OSPF 工作原理

OSPF 的核心是让每个路由器构建并维护一个与全网一致的链路状态数据库 (LSDB)。

1. 邻居发现 (Hello Protocol)：
   • 路由器周期性发送 Hello 报文（默认 10s）来发现和维护邻居关系。
   • 在广播链路（如以太网）上选举 DR (Designated Router) 和 BDR (Backup DR)，减少邻接关系数量。
2. 链路状态通告 (LSA Flooding)：
   • 当链路状态变化（如接口 Up/Down、代价变化）或周期性（30分钟）时，路由器产生 LSA (Link State Advertisement)。
   • LSA 包含路由器直连链路的状态信息。
   • 通过可靠洪泛机制，LSA 被传播到整个区域内的所有路由器。
3. SPF 计算：
   • 每个路由器拥有相同的 LSDB（包含全网拓扑）。
   • 以自己为根，运行 Dijkstra 算法 计算最短路径树。
   • 生成路由表，安装到转发表中。

5.5.3 层次化 OSPF (Hierarchical OSPF)

为了应对大规模网络，OSPF 支持将自治系统划分为多个区域 (Area)。

• 骨干区域 (Backbone Area, Area 0)：
  • 核心区域，连接所有其他区域。
  • 所有区域间流量必须经过 Area 0。
• 非骨干区域 (Area 1, Area 2...)：
  • 只连接到 Area 0。
  • 区域内路由器只维护本区域的完整 LSDB。
• 路由器角色：
  • 区域边界路由器 (ABR)：连接 Area 0 和其他区域，负责在区域间汇总路由信息。
  • 自治系统边界路由器 (ASBR)：连接 OSPF 域和其他 AS（如 BGP），引入外部路由。
• 优势：
  • 减少了 LSDB 的规模。
  • 将洪泛限制在区域内，减少通信开销。

5.6 BGP 域间路由协议

5.6.1 BGP 概述

BGP (Border Gateway Protocol) 是目前互联网唯一的域间路由协议（EGP），用于将互联网中的数千个 ISP 粘合在一起。

• 协议类型：路径向量 (Path Vector) 协议（避免环路，支持策略）。
• 承载：基于 TCP 连接（端口 179），保证可靠传输。
• 核心功能：
  1. 从邻居 AS 获取子网可达性信息。
  2. 向本 AS 内部路由器传播可达性信息。
  3. 基于策略和属性选择最优路由。

🔬

实验：BGP 协议可视化

动态演示 eBGP/iBGP 会话建立及 AS 间的路由传播与路径属性变化。

点击前往交互式实验 →

5.6.2 eBGP 与 iBGP

BGP 会话分为两类：

• eBGP (External BGP)：跨越 AS 边界，在不同 AS 的网关路由器之间建立。用于交换 AS 间的路由。
• iBGP (Internal BGP)：在同一个 AS 内部的路由器之间建立。用于在 AS 内传播从 eBGP 学到的外部路由。
  • 注意：iBGP 不是 IGP（如 OSPF），它不发现拓扑，只搬运外部路由信息。

5.6.3 BGP 路径属性

当 BGP 通告一个前缀（路由）时，会附带一系列属性，用于路由选择：

1. AS-PATH：记录该路由经过的所有 AS 序列（如 AS65001 AS65002）。
   • 防环：若路由器在 AS-PATH 中看到自己的 AS 号，则丢弃该路由。
   • 选路：路径越短越好。
2. NEXT-HOP：通往该前缀的下一跳路由器 IP 地址。
3. LOCAL-PREF：本地偏好。仅在 AS 内部传播，数值越高越优先。用于控制出流量走哪个出口。
4. MED (Multi-Exit Discriminator)：用于建议相邻 AS 如何进入本 AS（数值越小越好）。

5.6.4 BGP 路由选择策略 (Decision Process)

BGP 不仅仅寻找“最短路径”，而是基于策略 (Policy)。当路由器收到去往同一目的地的多条路由时，按顺序执行以下规则（直到选出一条）：

1. 最高 Local Preference（管理员策略优先）。
2. 最短 AS-PATH（经过最少的 AS）。
3. 最近的 NEXT-HOP（热土豆路由：尽快将包扔出本 AS）。
4. 其他规则（如 MED、Router ID 等）。

5.6.5 为什么区分域内和域间路由？

• 策略 (Policy)：
  • 域间：管理员需要控制流量如何进出 AS（例如：不帮竞争对手转发流量）。BGP 提供了丰富的策略控制。
  • 域内：都在同一管理下，无需策略，只求高效。
• 规模 (Scale)：
  • 域间：路由表巨大（互联网核心路由表 > 90万条），需可扩展性，路径向量能有效防环。
  • 域内：规模相对小，可以使用复杂的链路状态算法计算最短路。
• 性能 (Performance)：
  • 域内：追求收敛快、延迟低。
  • 域间：策略优先，性能次之。

5.7 Internet 控制报文协议 (ICMP)

5.7.1 ICMP 功能

ICMP (Internet Control Message Protocol) 是主机和路由器用来彼此沟通网络层信息的协议。它被认为是网络层的一部分，但实际上承载在 IP 数据报中（协议号 1）。

• 差错报告：当路由器无法处理数据报（如 TTL=0、无路由、MTU 过大）时，向源主机发送错误报告。
• 网络探测：查询网络状态（如 Ping）。

5.7.2 ICMP 报文类型

ICMP 报文由 Type（类型）和 Code（代码）字段标识。常见类型：

• Type 8 / Type 0：Echo Request / Echo Reply。用于 Ping 命令，测试连通性。
• Type 3：Destination Unreachable（目的不可达）。
  • Code 1: Host Unreachable
  • Code 3: Port Unreachable（UDP 端口未打开）
• Type 11：Time Exceeded（TTL 超时）。
  • Code 0: TTL expired in transit（用于 Traceroute）。

5.7.3 应用：Traceroute

Traceroute 利用 ICMP 报文跟踪路径：

1. 源主机向目的主机发送一系列 UDP 报文（目的端口号设为一个不可能使用的端口，如 33434）。
2. 第 1 组报文 TTL=1：到达第 1 个路由器，TTL 减为 0，丢弃，返回 ICMP Time Exceeded（记录第 1 跳 IP）。
3. 第 2 组报文 TTL=2：到达第 2 个路由器，TTL 减为 0，丢弃，返回 ICMP Time Exceeded（记录第 2 跳 IP）。
4. ...
5. 最终报文到达目的主机：TTL 足够，但端口不可达，返回 ICMP Port Unreachable。
6. 源主机停止发送。

5.8 IP 组播 (Multicast)

5.8.1 组播概念

• 单播 (Unicast)：一对一。
• 广播 (Broadcast)：一对所有（局域网内）。
• 组播 (Multicast)：一对多。源主机发送一份数据，网络层负责将其复制并分发给所有加入该组播组的成员。适用于视频直播、在线会议、IPTV。

5.8.2 IP 组播地址

使用 D 类 IP 地址 标识组播组。

• 范围：224.0.0.0 ~ 239.255.255.255。
• 保留地址：
  • 224.0.0.1：本子网内所有主机。
  • 224.0.0.2：本子网内所有组播路由器。
• MAC 地址映射：
  • 组播 IP 需要映射到以太网组播 MAC 地址，以便在链路层过滤。
  • 映射规则：MAC 前 24 位固定为 01-00-5E，后 24 位由 IP 地址的后 23 位填充（第 25 位固定为 0）。这导致 32 个 IP 组播地址可能映射到同一个 MAC 地址。

5.8.3 IGMP 协议

IGMP (Internet Group Management Protocol) 运行在主机和本地组播路由器之间。

• 功能：让路由器知道本子网内是否有主机加入了某个组播组。
• 机制：
  • 主机发送 Membership Report 加入组。
  • 路由器周期性发送 Membership Query 确认组成员是否还存在。