第 20 讲：路由算法——链路状态与距离向量

一、图抽象

        5
   u ────────  v
   │╲         │╲
  2│ ╲2      2│ ╲1
   │  ╲       │  ╲
   x ── w ─── y ── z
      3    1     2

G = (N, E)
   N = 路由器集合 {u, v, w, x, y, z}
   E = 链路集合
   c(x, y) = 链路 (x,y) 的开销；若不直接相连则为 ∞

开销可以是什么：

常数 1（此时最短路 = 最少跳数）
与带宽成反比（OSPF 默认：开销 = 参考带宽 / 链路带宽）
与拥塞程度相关（动态，但会导致震荡，见第三节）
由管理员任意指定（策略）

路由的目标：找出从源到目的的最小开销路径。

分类的三个维度

维度	选项 A	选项 B
信息范围	⭐ 全局（link-state）：每个节点知道完整拓扑	⭐ 分布式（distance-vector）：只知道邻居
变化频率	静态：路由很少改变	动态：定期或事件驱动地更新
是否感知负载	负载敏感：开销随拥塞变化	⭐ 负载不敏感：今天的互联网基本都是这一类

二、链路状态算法（Dijkstra）

2.1 前提

每个节点都知道完整的网络拓扑和所有链路开销。

怎么知道的？通过链路状态广播：每个节点向全网泛洪自己与邻居的连接信息。所有节点因此拥有相同的拓扑数据库，各自独立运行 Dijkstra。

2.2 算法

初始化:
   N' = {u}                      ← 已确定最短路的节点集合
   对所有节点 v:
       若 v 是 u 的邻居: D(v) = c(u,v),  p(v) = u
       否则:            D(v) = ∞

循环:
   从 N' 之外找出 D(w) 最小的节点 w
   把 w 加入 N'
   ⭐ 对 w 的每个不在 N' 中的邻居 v:
       D(v) = min( D(v),  D(w) + c(w,v) )
       若更新了，则 p(v) = w
直到 N' 包含所有节点

核心思想（贪心）：每一步都把当前已知距离最小的节点"确定下来"，然后用它去松弛它的邻居。

2.3 完整手算示例 ⭐

用上面那张图，从 u 出发。

链路开销：

c(u,v)=5  c(u,x)=2  c(u,w)=2(经x路径)  实际直连：u-v=5, u-x=2
c(x,w)=3  c(v,w)=2  c(v,y)=1  c(w,y)=1  c(y,z)=2

为清晰起见，重列直连关系：

u–v: 5     u–x: 2
v–w: 2     v–y: 1
x–w: 3
w–y: 1
y–z: 2

迭代表：

步	N'	D(v),p(v)	D(w),p(w)	D(x),p(x)	D(y),p(y)	D(z),p(z)
0	{u}	5,u	∞	2,u	∞	∞
1	{u,x}	5,u	5,x		∞	∞
2	{u,x,v}		5,x		6,v	∞
3	{u,x,v,w}				6,v	∞
4	{u,x,v,w,y}					8,y
5	全部

逐步解释：

步 0: 初始化。u 的邻居 v(5)、x(2)，其余 ∞
      ⭐ 最小的是 x(2) → 加入 N'

步 1: 用 x 松弛它的邻居 w:
         D(w) = min(∞, D(x)+c(x,w)) = min(∞, 2+3) = 5, p(w)=x
      ⭐ 现在 N' 外最小的是 v(5) 和 w(5)，任选 v

步 2: 用 v 松弛邻居 w 和 y:
         D(w) = min(5, D(v)+c(v,w)) = min(5, 5+2) = 5  （不变）
         D(y) = min(∞, D(v)+c(v,y)) = min(∞, 5+1) = 6, p(y)=v
      ⭐ 最小的是 w(5)

步 3: 用 w 松弛邻居 y:
         D(y) = min(6, D(w)+c(w,y)) = min(6, 5+1) = 6  （不变）
      ⭐ 最小的是 y(6)

步 4: 用 y 松弛邻居 z:
         D(z) = min(∞, 6+2) = 8, p(z)=y
      ⭐ 最小的是 z(8)

步 5: 全部完成

从前驱指针回溯出最短路径树：

   u
   ├── x (2)
   │   └── w (5)
   └── v (5)
       └── y (6)
           └── z (8)

u 的转发表：

目的	最短路径	⭐ 输出链路（第一跳）
v	u→v	(u,v)
w	u→x→w	(u,x)
x	u→x	(u,x)
y	u→v→y	(u,v)
z	u→v→y→z	(u,v)

⚠️ 注意转发表只记录第一跳，不记录整条路径——因为转发是逐跳的（第 2 讲）。

2.4 复杂度

朴素实现：每轮扫描找最小值 O(n) ，共 n 轮  →  O(n²)
用优先队列（堆）：                          →  O(E log n)

2.5 震荡问题 ⭐

如果链路开销随负载变化（负载敏感路由），会发生什么？

初始：三条流分别从 x、y、z 流向目的地 w，链路开销 = 承载的流量

      1        1
  x ────▶ w ◀──── y
      ╲       ╱
       ╲ 0   ╱ 1        （数字为当前开销）
        ╲   ╱
          z

① 所有人发现顺时针方向拥塞 → 全部切到逆时针
② 逆时针路径现在拥塞了，顺时针空了 → 全部切回来
③ ⭐ 无限震荡，流量在两条路径间来回摆动

后果：路由不稳定、分组大量乱序、TCP 性能崩溃。

缓解手段：

⭐ 不用负载敏感的开销（今天互联网的实际做法——OSPF 开销基于带宽而非负载）
让各路由器的更新时刻去同步化（加随机抖动）
平滑开销变化（EWMA）

📌 一个重要的工程结论：**「让路由自动避开拥塞」听起来很美，但在实践中会引入正反馈震荡。**互联网选择了让路由保持稳定，把拥塞问题交给传输层的拥塞控制（第 15、16 讲）——又一次「智能在边缘」。

三、距离向量算法（Bellman-Ford）

3.1 Bellman-Ford 方程

⭐ d_x(y) = min over v { c(x,v) + d_v(y) }

  d_x(y) = 从 x 到 y 的最小开销
  v 遍历 x 的所有邻居

含义：「我到 y 的最短距离，等于（我到某个邻居的开销 + 那个邻居到 y 的最短距离）在所有邻居上取最小。」

⚠️ 注意 x 并不知道整个拓扑，它只知道：

到各邻居的直连开销 c(x,v)
各邻居告诉它的距离向量 D_v = [d_v(y) for all y]

3.2 算法特点：分布式、异步、自终止

每个节点:
   等待某个事件（邻居的距离向量变了 / 自己的链路开销变了）
   ↓
   用 Bellman-Ford 方程重算自己的距离向量
   ↓
   ⭐ 若自己的距离向量【发生了变化】，通知所有邻居
   ↓
   回到等待

三个性质：

迭代（iterative）：反复进行直到没有变化
异步（asynchronous）：⭐ 节点之间不需要同步，各干各的
自终止（self-terminating）：没有变化时自然停止，不需要"结束"信号

📌 这是一个非常优雅的分布式算法：没有中央协调，没有全局时钟，没有终止检测，但它会收敛到正确答案。

3.3 手算示例

      2        1
  x ─────  y ─────  z
   ╲              ╱
    ╲──── 7 ─────╱

初始（每个节点只知道直连邻居）：

x 的表:  d_x(x)=0  d_x(y)=2  d_x(z)=7
y 的表:  d_y(x)=2  d_y(y)=0  d_y(z)=1
z 的表:  d_z(x)=7  d_z(y)=1  d_z(z)=0

第 1 轮交换后，x 收到 y 和 z 的向量：

d_x(z) = min{ c(x,y) + d_y(z),   c(x,z) + d_z(z) }
       = min{ 2 + 1,             7 + 0 }
       = min{ 3, 7 }
       = 3   ⭐ 从 7 降到 3，下一跳改为 y

同理 z 也会发现经 y 到 x 更近：

d_z(x) = min{ c(z,y) + d_y(x),   c(z,x) + d_x(x) }
       = min{ 1 + 2,             7 + 0 }
       = 3   ⭐

第 2 轮：没有节点的向量发生变化 → 收敛。

最终：

x: d(y)=2 [下一跳 y]   d(z)=3 [下一跳 y]
y: d(x)=2 [下一跳 x]   d(z)=1 [下一跳 z]
z: d(x)=3 [下一跳 y]   d(y)=1 [下一跳 y]

3.4 链路开销变化

好消息传得快（Good news travels fast）

      4              1
  x ─────  y ─────  z

若 c(x,y) 从 4 降到 1：

t0: y 检测到变化，更新自己的表，通知邻居
t1: z 收到 y 的更新，更新自己的表
t2: 收敛完成
⭐ 只用了 2 轮

坏消息传得慢（Bad news travels slow）—— 无穷计数问题 ⭐⭐

      4              1
  x ─────  y ─────  z
      ↑
   开销从 4 涨到 60

初始状态：d_y(x) = 4（直连），d_z(x) = 5（经 y）。

t0: y 检测到 c(y,x) 变成 60
    y 计算: d_y(x) = min{ 60 + 0,  1 + d_z(x) }
                   = min{ 60,      1 + 5 }
                   = 6  ⭐ 经 z 走！

    ⚠️ 但 z 到 x 的路径【本来就是经过 y 的】！
       y 不知道这一点 —— 它只看到一个数字 5

t1: z 收到 y 说"我到 x 是 6"
    z 计算: d_z(x) = min{ 50+0,  1 + 6 } = 7

t2: y 收到 z 说 7
    d_y(x) = min{ 60,  1 + 7 } = 8

t3: z → 9
t4: y → 10
    ...
⭐ 一直数到 d = 51 时，y 才发现直接走 60 的链路更划算
   （因为 1 + 50 = 51 > ... 实际到 y 算出 60 < 1+d_z(x) 时才停）

⚠️ 需要【44 轮迭代】才收敛

根本原因：⭐ y 不知道 z 到 x 的路径是经过 y 自己的。这叫路由环路，而 DV 算法的信息是「一个距离数字」，丢失了路径信息。

3.5 毒性逆转（Poisoned Reverse）

做法：

⭐ 如果 z 到 x 的路径要经过 y，
   那么 z 就告诉 y：「我到 x 的距离是 ∞」

这样 y 就永远不会试图经 z 到 x。

回到上面的例子：

z 告诉 y: d_z(x) = ∞
t0: y 计算 d_y(x) = min{ 60,  1 + ∞ } = 60  ⭐ 立刻正确
t1: y 通知 z，z 更新为 61
⭐ 2 轮收敛

⚠️ 但毒性逆转不能解决所有环路！

它只能消除两个节点之间的环路。三个或更多节点构成的环路仍然会产生无穷计数：

    x ─── y
     ╲   ╱
      ╲ ╱
       z

若 A→B→C→A 形成环，毒性逆转无能为力。

其他缓解手段：

手段	说明
定义"无穷"为一个小数	RIP 中 16 跳即视为不可达，把收敛时间上限压到可接受范围
水平分割（Split Horizon）	不把从某接口学到的路由再从该接口通告出去
触发更新	变化时立即通告，不等周期定时器
抑制计时器（Holddown）	收到坏消息后一段时间内不接受更好的路由

📌 RIP 的最大跳数是 15，正是为了限制无穷计数的持续时间——这也直接限制了 RIP 只能用在小型网络里。

四、LS 与 DV 全面对比

	链路状态（LS）	距离向量（DV）
知道什么	⭐ 完整拓扑	⭐ 只知道邻居和它们报的距离
算法	Dijkstra	Bellman-Ford
通信方式	向全网泛洪链路状态	只与邻居交换距离向量
报文复杂度	O(nE)，每个节点广播	只在邻居间，但收敛前轮数可能很多
收敛速度	O(n²) 或 O(E log n)，快且确定	可能很慢（无穷计数）
健壮性 ⭐	节点只广播自己链路的开销，一个节点出错影响有限，各节点独立算	⭐ 一个节点报错的距离会被传播和放大，因为每个节点的计算依赖邻居的结果
内存	需存完整拓扑	只需存距离向量
代表协议	OSPF、IS-IS	RIP、EIGRP、BGP（路径向量）

⭐ 健壮性差异是最重要的一条：

LS: 若某路由器广播了错误的链路开销，其他节点会看到这个错误，
    但它们【各自独立】计算，错误的影响局限在涉及该链路的路径上

DV: 若某路由器报告了错误的距离，邻居会基于它计算，
    然后把结果再传给下一层邻居 —— ⭐ 错误会像病毒一样扩散全网

📌 这解释了为什么大型网络内部普遍使用 OSPF/IS-IS（LS 类）。而 BGP（第 21 讲）虽然是 DV 的变体，但它携带完整的 AS 路径——正是为了解决 DV 丢失路径信息导致环路的问题。

五、例题（Worked Example）

题目：给定网络

        1
   A ────── B
   │╲       │
  4│ ╲2    3│
   │  ╲     │
   D ── C ──┘
      5

链路：A–B=1, A–C=2, A–D=4, B–C=3, C–D=5

(a) 用 Dijkstra 从 A 出发，写出完整迭代表。 (b) 给出 A 的转发表。 (c) 若使用 DV，写出 A 的初始距离向量和收敛后的距离向量。

解答：

(a) Dijkstra 从 A 出发

步	N'	D(B),p(B)	D(C),p(C)	D(D),p(D)
0	{A}	1,A	2,A	4,A
1	{A,B}		2,A	4,A
2	{A,B,C}			4,A
3	{A,B,C,D}

逐步说明：

步 0: D(B)=1, D(C)=2, D(D)=4。最小是 B(1) → 加入
步 1: 用 B 松弛 C:  D(C) = min(2, 1+3) = 2  （不变）
      最小是 C(2) → 加入
步 2: 用 C 松弛 D:  D(D) = min(4, 2+5) = 4  （不变）
      最小是 D(4) → 加入
步 3: 完成

(b) A 的转发表

目的	最短路径	开销	输出链路
B	A→B	1	(A,B)
C	A→C	2	(A,C)
D	A→D	4	(A,D)

⭐ 本例中三条最短路径都是直连——因为直连开销都不大于绕行开销。

(c) DV

A 的初始距离向量（只知道直连）：

D_A = [ A:0, B:1, C:2, D:4 ]

第 1 轮，A 收到邻居的向量：

D_B = [A:1, B:0, C:3, D:∞]
D_C = [A:2, B:3, C:0, D:5]
D_D = [A:4, B:∞, C:5, D:0]

d_A(B) = min{ c(A,B)+0, c(A,C)+3, c(A,D)+∞ } = min{1, 5, ∞} = 1
d_A(C) = min{ c(A,B)+3, c(A,C)+0, c(A,D)+5 } = min{4, 2, 9} = 2
d_A(D) = min{ c(A,B)+∞, c(A,C)+5, c(A,D)+0 } = min{∞, 7, 4} = 4

没有变化 → 已收敛：

D_A = [ A:0, B:1, C:2, D:4 ]      与 Dijkstra 结果一致 ✅

📌 两种算法必然给出相同的最短路径（前提是拓扑稳定且开销一致）。它们的差别不在结果，而在如何得到结果——以及在网络变化和故障时的行为。

六、随堂自测

路由算法的三个分类维度是什么？今天的互联网属于哪一类？
Dijkstra 每一步做什么？为什么它是贪心的？
为什么转发表只记录第一跳而不记录整条路径？
什么是路由震荡？为什么互联网不用负载敏感的路由开销？
写出 Bellman-Ford 方程并解释每一项的含义。
DV 算法的三个性质是什么？「自终止」是什么意思？
⭐ 用一个具体例子说明无穷计数问题的成因。
毒性逆转能解决所有环路吗？为什么？
LS 和 DV 在健壮性上的根本差异是什么？

七、本讲要点回顾

路由 = 在带权图上找最短路径。互联网使用负载不敏感的静态开销（OSPF 按带宽）。
Dijkstra：贪心，每步确定一个最近节点并松弛其邻居。O(n²) 或 O(E log n)。
负载敏感的开销会导致震荡——互联网选择保持路由稳定，把拥塞交给传输层处理。
Bellman-Ford：d_x(y) = min_v { c(x,v) + d_v(y) }，分布式、异步、自终止。
⭐ 好消息传得快，坏消息传得慢：无穷计数的根因是 DV 只传距离、丢失了路径信息。
毒性逆转只能消除两节点环路，三节点以上仍会出问题；RIP 用「16 = 无穷」限制损害。
⭐ LS 更健壮：错误影响局限；DV 的错误会在全网扩散。
代表协议：OSPF/IS-IS 是 LS，RIP 是 DV，BGP 是携带完整路径的 DV 变体。

八、自测答案

1. ① 信息范围：全局（链路状态）vs 分布式（距离向量）；② 变化频率：静态 vs 动态；③ 是否感知负载：负载敏感 vs 负载不敏感。今天的互联网属于分布式/全局混合（域内用 LS，域间用路径向量）、动态、且负载不敏感。

2. 每一步：从尚未确定的节点中选出当前 D 值最小的节点 w，把它加入已确定集合 N’，然后用 w 去松弛它所有还不在 N’ 中的邻居（D(v) = min(D(v), D(w)+c(w,v))）。它是贪心的，因为它假设当前 D 值最小的节点的距离已经是最终答案——这个假设在所有边权非负时可以被证明成立（若存在更短路径，那条路径必须经过某个 D 值更大的节点，加上非负边权后只会更大，矛盾）。

3. 因为转发是逐跳的（第 2 讲）：每台路由器只负责把分组交给下一跳，下一跳会用它自己的转发表继续决策。记录整条路径既无必要（下游路由器不看你的决定），也不可行（会让转发表巨大，且路径变化时要更新所有上游）。

4. 路由震荡指流量在多条路径间来回摆动、路由表反复改变的现象。成因：若链路开销随负载变化，则「所有人避开拥塞路径」会让原本拥塞的路径变空、原本空闲的路径变拥塞，形成正反馈。互联网不用负载敏感开销，是因为震荡会造成路由不稳定、分组大量乱序、TCP 性能崩溃——保持路由稳定、把拥塞交给端系统的拥塞控制处理，是更好的分工。

5. d_x(y) = min over v { c(x,v) + d_v(y) }。d_x(y)：x 到 y 的最小开销；v：遍历 x 的所有直连邻居；c(x,v)：x 到邻居 v 的直连链路开销（x 自己知道）；d_v(y)：邻居 v 到 y 的最小开销（由 v 告诉 x）。整个式子的含义：我到目的地的最短距离，等于「到某个邻居的代价 + 那个邻居到目的地的最短距离」在所有邻居上的最小值。

6. 迭代：反复计算直到不再变化；异步：各节点不需要同步执行，谁收到更新谁就算，没有全局时钟或轮次；自终止：当没有任何节点的距离向量发生变化时，就不再有更新报文发出，算法自然停止——不需要任何"算法结束"的检测或信号。

7. 见正文 x–y–z 例子：c(x,y) 从 4 涨到 60 时，y 计算 d_y(x) = min{60, 1 + d_z(x)} = min{60, 1+5} = 6，选择经 z。但 z 到 x 的路径本来就是经过 y 的——y 看到的只是数字 5，不知道这条路径的具体走法。于是形成环路，两者交替加 1 慢慢往上数，直到数值超过 60 才收敛，共需 44 轮。根因是 DV 报文只携带距离，丢失了路径信息。

8. 不能。毒性逆转只能消除两个节点之间的环路（z 告诉 y「我经过你，所以我到 x 是 ∞」）。当环路涉及三个或更多节点时（A→B→C→A），每一对节点之间的关系都是"我没经过你"，毒性逆转不会触发，无穷计数依然发生。这就是 RIP 必须额外用「16 跳 = 无穷」来兜底、并配合水平分割与抑制计时器的原因。

9. LS：每个节点只广播自己直连链路的状态，所有节点拥有相同的拓扑数据库并各自独立运行 Dijkstra。若某节点广播了错误信息，其他节点会看到这个错误，但错误的影响局限在涉及该链路的路径计算上，且不会被"加工放大"。DV：每个节点的距离向量是基于邻居报告的结果计算出来的，并且这个结果会继续传给下一层邻居。因此一个错误的距离值会被逐级采纳、累加、传播——错误在网络中扩散并放大。这是大型网络内部普遍采用 LS 类协议的核心原因。

一、图抽象#

分类的三个维度#

二、链路状态算法（Dijkstra）#

2.1 前提#

2.2 算法#

2.3 完整手算示例 ⭐#

2.4 复杂度#

2.5 震荡问题 ⭐#

三、距离向量算法（Bellman-Ford）#

3.1 Bellman-Ford 方程#

3.2 算法特点：分布式、异步、自终止#

3.3 手算示例#

3.4 链路开销变化#

3.5 毒性逆转（Poisoned Reverse）#

四、LS 与 DV 全面对比#

五、例题（Worked Example）#

六、随堂自测#

七、本讲要点回顾#

八、自测答案#