Chapter 5-2:距离向量路由、Bellman-Ford 方程与路由环路

Chapter 5-2:距离向量路由、Bellman-Ford 方程与路由环路

引言:没有全网地图,路由器还能找到路径吗?

链路状态路由的思路是让每台路由器获得完整的网络拓扑,再运行 Dijkstra 算法计算最短路径。这种方式相当于让每台路由器都拥有一张全网地图。

距离向量路由采用了另一种思路:

路由器不掌握完整拓扑,只询问相邻路由器到各个目的地的距离,再根据邻居提供的信息计算自己的路径。

假设路由器 x 想前往目的地 y,而 x 有多个邻居。对于每个邻居 vx 都可以计算:

1
2
3
经过 v 到达 y 的总代价
= x 到 v 的直接链路代价
+ v 声称的到 y 的代价

然后,x 从所有邻居中选择总代价最小者作为下一跳。

这一过程不要求路由器知道目的地位于网络的哪个方向,也不要求它知道完整路径经过哪些节点。它只需要反复与邻居交换信息,就能逐渐形成到各目的地的路由。

❗核心主线: 距离向量路由不建立全网拓扑,而是通过邻居之间反复交换距离信息,利用 Bellman-Ford 方程逐步收敛到较优路径。


1. 距离向量中的“距离”与“向量”

1.1 “距离”是路径代价

距离向量中的 distance 并不一定表示物理距离。它表示路由协议定义的路径代价。

路径代价可以采用不同指标:

  • 经过的链路数量,即跳数;
  • 链路时延;
  • 队列长度或拥塞程度;
  • 带宽对应的代价;
  • 管理员配置的策略性开销。

因此,一条物理距离较长的路径,可能因为带宽更高而具有更低的路由代价。

1.2 “向量”是目的地代价列表

距离向量中的 vector 也不是几何学中的方向向量。它可以理解为路由器维护的一组距离估计:

1
2
3
4
5
到 A 的代价:2
到 B 的代价:5
到 C 的代价:7
到 D 的代价:∞
……

如果网络中存在多个目的地,路由器就为每个目的地保存一个当前代价。这一整组代价构成该路由器的距离向量。

例如,路由器 x 的距离向量可以写成:

1
Dₓ = [Dₓ(A), Dₓ(B), Dₓ(C), Dₓ(D), ...]

其中,Dₓ(y) 表示路由器 x 当前估计的到目的地 y 的最低代价。


❗本节核心结论:

距离向量就是“本路由器到所有目的地的当前代价估计表”。距离表示路径成本,向量表示一组面向不同目的地的距离值。


2. 距离向量路由表保存什么

距离向量协议通常为每个目的地维护以下核心信息:

字段 含义
To 目的地网络或目的节点
Next 前往该目的地时选择的下一跳
Cost 从当前路由器到目的地的总代价

例如:

To Next Cost
A B 3
C D 5
E B 8

其中,“到 A,下一跳为 B,总代价为 3”表示:

  • 当前路由器最终想把分组送到 A
  • 当前这一跳先把分组交给邻居 B
  • 按照当前路由信息,经由 B 到达 A 的总代价为 3

2.1 下一跳不是完整路径

下一跳是:

当前路由器应该将分组交给的直接相邻路由器。

例如,完整路径为:

1
u → x → y → z

u 的视角看:

  • 最终目的地是 z
  • 下一跳是 x
  • u 不需要在转发时一次性控制后面的 yz

x 收到分组后,它会查询自己的路由表,再决定下一跳 y。随后,y 再决定把分组交给 z

这种方式称为逐跳转发。每台路由器只负责当前的一跳,而不直接控制完整端到端路径。

2.2 下一跳必须是直接邻居

路由表中的下一跳不能随意填写一个远端路由器。当前路由器必须能够通过某条直接链路将分组交给下一跳。

因此:

  • 目的地可以是远端网络;
  • 下一跳通常是直接连接的相邻路由器;
  • 输出接口是通向该下一跳的本地接口。

❗本节核心结论:

路由表不一定保存完整路径。它只需要保存“到这个目的地,下一步交给哪个邻居”,完整路径由沿途路由器逐跳共同完成。


3. Bellman-Ford 方程

距离向量路由的数学核心是 Bellman-Ford 方程:

1
Dₓ(y) = minᵥ { c(x,v) + Dᵥ(y) }

各符号含义如下:

符号 含义
Dₓ(y) 节点 x 当前估计的到目的地 y 的最低代价
v 节点 x 的某个直接邻居
c(x,v) x 到邻居 v 的直接链路代价
Dᵥ(y) 邻居 v 声称的到目的地 y 的代价
minᵥ 在所有邻居提供的方案中选择总代价最小者

方程表达的是:

x 前往 y,第一步必然要先到达某个邻居 v。因此,只需比较经过不同邻居时的总代价,并选择最小者。

3.1 计算示例

假设路由器 u 有三个邻居 vxw。它们通告的到目的地 z 的代价为:

1
2
3
Dᵥ(z) = 5
Dₓ(z) = 3
D𝑤(z) = 3

路由器 u 到三个邻居的直接链路代价为:

1
2
3
c(u,v) = 2
c(u,x) = 1
c(u,w) = 5

于是,u 分别计算:

选择的邻居 计算 总代价
v 2 + 5 7
x 1 + 3 4
w 5 + 3 8

最小值为 4,因此:

1
2
Dᵤ(z) = 4
下一跳 = x

路由器 u 的路由表中将记录:

To Next Cost
z x 4

3.2 Bellman-Ford 的本质

当前路由器并不直接验证邻居后面的完整路径。它只能知道:

  • 自己到邻居的链路代价;
  • 邻居通告的到目的地的距离。

因此,Bellman-Ford 方程是一种基于邻居信息的局部最优计算。

这既是距离向量算法能够分布式运行的原因,也是它可能受到错误或过期信息影响的原因。


❗本节核心结论:

Bellman-Ford 方程把一个全局路径问题分解为多个局部选择:比较“先到哪个邻居,再由邻居前往目的地”的总代价。


4. DV 为什么不需要全局拓扑图

在链路状态算法中,每台路由器最终会获得:

  • 全部路由器节点;
  • 路由器之间的连接关系;
  • 各条链路的代价。

因此,LS 路由器逻辑上维护一张全局拓扑图,并在图上运行 Dijkstra 算法。

距离向量路由器不维护这样的全局图。它通常只掌握:

  • 自己有哪些直接邻居;
  • 自己到各邻居的链路代价;
  • 各邻居通告的距离向量;
  • 自己计算出的目的地、下一跳和总代价。
信息 LS 路由器 DV 路由器
自己的直接邻居 知道 知道
本地链路代价 知道 知道
完整网络拓扑 知道 不知道
所有链路的代价 知道 不知道
邻居到各目的地的距离 可由全图计算 由邻居直接通告
典型算法 Dijkstra Bellman-Ford

可以使用一个直观类比:

  • LS: 每个人都拿到完整地图,自己规划路线;
  • DV: 每个人没有完整地图,只询问邻居“你到那里还有多远”。

4.1 DV 知道目的地,但不知道完整路径

DV 路由器虽然不掌握拓扑图,仍然需要知道有哪些目的地,并维护到这些目的地的距离。

它可能知道:

1
到 A 的代价为 4,下一跳是 B

但它未必知道 B 后面究竟经过哪些节点才能到达 A

这种信息压缩减少了拓扑维护成本,却也隐藏了路径内部结构。


❗本节核心结论:

DV 路由器不维护全网图。它保存的是邻居信息和距离估计,而不是网络中所有节点与链路之间的完整连接关系。


5. 距离向量算法的运行过程

5.1 初始化

算法开始时,每台路由器首先建立初始距离:

  • 到自己的代价为 0
  • 到直接邻居的代价为本地链路代价;
  • 到其他未知目的地的代价为

例如,路由器 xab 直接相连:

1
2
3
4
Dₓ(x) = 0
Dₓ(a) = c(x,a)
Dₓ(b) = c(x,b)
Dₓ(y) = ∞,如果暂时不知道如何到达 y

5.2 向邻居发送距离向量

每台路由器将自己到各目的地的当前距离估计发送给直接邻居。

需要注意,它通常通告的是:

1
2
3
我到 A 的代价是多少
我到 B 的代价是多少
我到 C 的代价是多少

而不是完整说明:

1
我到 A 要经过哪些路由器

5.3 接收邻居的距离向量

当路由器收到邻居的新通告后,就获得了新的候选路径信息。

例如,邻居 v 通告:

1
Dᵥ(y) = 5

当前路由器 x 知道:

1
c(x,v) = 2

于是可以得到一条候选路径:

1
2
x → v → …… → y
总代价 = 2 + 5 = 7

5.4 使用 Bellman-Ford 重新计算

对于每个目的地 y,路由器比较所有邻居提供的方案:

1
Dₓ(y) = minᵥ { c(x,v) + Dᵥ(y) }

如果最优代价发生变化,就更新:

  • 到目的地的代价;
  • 对应的下一跳。

5.5 变化后继续通知邻居

如果本路由器的距离向量发生变化,就把新的结果发送给邻居。

邻居收到后也会重新计算。如果邻居的结果再次变化,它们还会继续向外传播。

5.6 收敛

如果网络拓扑保持稳定,信息经过多轮传播后,各路由器的距离向量将不再变化。此时称网络路由已经收敛。

收敛并不意味着网络从此永久不变。当链路代价变化、链路断开或新路由器加入时,算法会再次开始更新。


❗本节核心结论:

DV 不是一次性计算,而是“交换—计算—更新—再次交换”的循环过程。路由结果通过多轮局部互动逐渐形成。


6. 为什么 DV 是分布式、异步、迭代的

6.1 分布式

DV 没有统一的中央计算节点。

每台路由器分别:

  • 保存自己的距离向量;
  • 接收邻居信息;
  • 执行自己的 Bellman-Ford 更新;
  • 将变化通知邻居。

全网结果由大量局部计算共同形成。

6.2 异步

路由器不必按照统一时钟同时执行第 1 轮、第 2 轮和第 3 轮计算。

路由器通常在以下事件发生时重新计算:

  • 本地链路代价发生变化;
  • 收到邻居发送的新距离向量;
  • 周期性更新时间到达。

因此,一台路由器可能已经完成更新,而另一台路由器还没有收到最新消息。

6.3 迭代

一次邻居交换通常不能让所有路由器立刻知道远端变化。

如果某项变化发生在节点 A

  • 第一次传播影响一跳外邻居;
  • 第二次传播影响两跳外节点;
  • 第三次传播继续影响更远节点。

信息通过多轮交换逐跳扩散,直到全网重新稳定。


❗本节核心结论:

分布式表示各节点独立计算,异步表示节点不必同时更新,迭代表示正确结果需要经过多轮信息交换才能形成。


7. 更新前和更新后的路由表,哪一个是正确的?

距离向量算法不会先判断:

1
旧表一定正确

或者:

1
邻居的新表一定正确

它所做的是:

根据当前掌握的最新信息,重新计算当前最优估计。

因此:

  • 更新前的路由表,是旧信息条件下的最优估计;
  • 更新后的路由表,是新信息条件下的最优估计;
  • 二者都不一定立刻等于网络当前的真实最短路径。

7.1 邻居的信息可能是过期的

假设链路刚刚断开,但邻居还没有收到故障消息。它可能继续通告一条已经失效的路径。

当前路由器收到后,可能暂时将错误信息写入自己的路由表。

这不是 Bellman-Ford 公式本身算错了,而是公式的输入已经过期。

7.2 邻居的信息可能依赖当前路由器

更危险的情况是:

  • 邻居说自己能够到达目的地;
  • 但邻居原来的路径实际上要经过当前路由器。

当前路由器不知道完整路径,就可能反过来把邻居选作下一跳。于是两台路由器相互依赖,形成环路。

7.3 正确性来自最终收敛

在网络拓扑稳定、通告能够可靠传播的条件下,后续更新会逐渐纠正旧信息,距离向量最终收敛到正确的最短路径代价。

因此,DV 的正确性不是建立在“每一次局部更新都立即反映全网真相”之上,而是建立在:

  • 路由信息持续交换;
  • 各节点持续重新计算;
  • 网络状态保持足够长时间稳定;
  • 算法最终收敛。

❗关键判断: DV 路由表记录的是当前估计,不是路由器能够独立验证的绝对真相。邻居信息错误时,本节点也可能暂时被带错。


8. 链路代价变化:为什么好消息传播快

假设网络中新出现一条更短路径。

邻居一旦通告更小的代价,当前路由器就会立即比较:

1
2
3
旧代价

经过邻居的新代价

只要新代价更小,就可以立即采用新路径,并继续向其他邻居传播更小的距离。

例如:

1
2
3
原来到 A 的代价:10
邻居 B 新通告:B 到 A 的代价为 3
本节点到 B 的代价:1

新的候选代价为:

1
1 + 3 = 4

由于 4 < 10,本节点可以迅速把代价更新为 4

更短的代价通常会像波纹一样向外扩散,因此:

好消息通常传播得比较快。

这里的“好消息”包括:

  • 出现更短路径;
  • 新链路建立;
  • 新目的地变得可达;
  • 某条链路的代价降低。

9. 为什么坏消息传播慢

坏消息包括:

  • 链路断开;
  • 目的地不可达;
  • 路径代价显著增加;
  • 某个路由器停止工作。

当一条路径失效时,邻居可能仍然保存旧信息。各路由器无法立刻知道邻居通告的路径是否已经包含自己,也无法直接看到完整拓扑。

因此,坏消息可能在多个节点之间被反复误解。

9.1 一个典型环路

假设原来的路径为:

1
C → B → A

其中:

  • BA 直接相连;
  • C 通过 B 到达 A
  • C 通告自己到 A 的代价为 2

现在,B-A 链路断开。

但是 C 还没有收到更新,仍然告诉 B

1
我到 A 的代价是 2

B 可能据此计算:

1
2
3
B 到 C 的代价 1
+ C 到 A 的代价 2
= 3

于是 B 认为自己可以通过 C 到达 A

CA 的旧路径原本就是:

1
C → B → A

因此形成:

1
B → C → B → C → …

两台路由器互相把对方当作下一跳,产生路由环路。


❗本节核心结论:

好消息只需提供一个更小的代价就能立即被采用;坏消息则需要证明旧路径已经失效,而 DV 缺少完整路径信息,因此更容易出现延迟与误判。


10. 无穷计算问题

无穷计算问题又称 count-to-infinity。

它表示:

当目的地已经不可达时,路由器仍然可能互相通告错误路径,使到该目的地的代价一轮一轮增加,经过很长时间才达到协议定义的“无穷大”。

继续使用 BC 的例子。假设每条链路代价为 1

  1. C 原来认为到 A 的代价为 2
  2. B-A 断开后,B 根据 C 的旧信息更新为 3
  3. C 收到 B 的新通告后,可能更新为 4
  4. B 再根据 C 更新为 5
  5. 代价继续增加。
1
2
3
4
5
6
7
B:3
C:4
B:5
C:6
B:7
C:8
……

直到代价达到协议规定的无穷值,目的地才最终被判定为不可达。

10.1 为什么叫“计算到无穷”

这里的“无穷”在实际协议中通常不是数学上的无限大,而是一个预先规定的最大值。

只要代价达到该值,协议就将目的地视为不可达。

无穷值过大时,错误路由可能持续较长时间;无穷值较小时,又会限制网络允许的最大路径长度。

10.2 根本原因

无穷计算的根源不是简单的加法错误,而是:

  • 路由器只知道邻居宣称的距离;
  • 不知道邻居的完整路径;
  • 不能发现邻居的路径是否经过自己;
  • 过期信息会被当作新计算的依据;
  • 错误结果会继续向其他节点传播。

❗本节核心结论:

Count-to-infinity 是错误信息自我强化的过程:每个节点都按照局部规则正确计算,但它们依赖的邻居信息彼此循环,导致全局结果错误。


11. 水平分裂与毒性逆转

11.1 水平分裂的基本思想

水平分裂的基本规则是:

如果一条路由是从某个邻居学习到的,就不要再把这条路由原样通告回该邻居。

例如,C 通过 B 到达 A,那么 C 不应该再对 B 宣称:

1
我能以代价 2 到达 A

因为这条路径本来就依赖 B

11.2 毒性逆转

毒性逆转进一步规定:

如果本节点到某目的地的下一跳是邻居 B,那么在向 B 通告该目的地时,故意将距离报告为

例如:

1
2
C 到 A 的真实路由:
下一跳 B,代价 2

C

  • 可以向其他邻居通告到 A 的代价为 2
  • B 通告到 A 的代价为

它表达的不是:

1
我真的完全不能到 A

而是:

1
2
对你 B 来说,不能把我 C 当成前往 A 的替代路径,
因为我到 A 本来就要经过你。

11.3 为什么能够缓解环路

B-A 链路断开时,B 不会从 C 收到一条看似可用的到 A 的路径,因为 CB 通告的是

这能直接阻止:

1
2
B 选择 C
C 又选择 B

形成的两节点环路。

11.4 毒性逆转的局限

毒性逆转主要解决两个节点之间的简单路由环路。

如果环路涉及三个或更多节点,例如:

1
A → B → C → A

单纯的毒性逆转不一定能够识别并阻止所有情况。因为每个节点可能只知道自己的直接下一跳,而无法看到更长的循环结构。

因此,毒性逆转能够缓解无穷计算问题,但不能从根本上消除所有距离向量环路。


❗本节核心结论:

毒性逆转通过“对当前下一跳通告无穷大”阻止邻居反向使用本节点,但它主要防止简单的两节点环路,并非对所有多节点环路都有效。


12. LS 与 DV 的系统比较

12.1 信息传播方式

LS 与 DV 的传播方式几乎相反:

  • LS 传播的是局部链路状态,但传播范围是全网;
  • DV 传播的是到所有目的地的距离,但只发送给直接邻居。
对比维度 LS 链路状态 DV 距离向量
本节点掌握的信息 完整拓扑和全部链路代价 邻居信息与距离向量
主要通告内容 自己与邻居之间的链路状态 自己到各目的地的距离
通告范围 向全网泛洪 只发给直接邻居
典型算法 Dijkstra Bellman-Ford
是否维护全局图
路径计算 在完整图上独立计算 根据邻居通告迭代计算

可以将二者概括为:

1
2
LS:局部信息,全局传播
DV:全局距离,局部传播

这里的“全局距离”是指距离向量中包含到多个目的地的代价,而不是指路由器掌握全局拓扑。

12.2 消息复杂度

DV 只与直接邻居交换距离向量,不必把每项链路状态泛洪到全网。因此,在消息传播范围方面,DV 通常更有优势。

LS 的每项链路状态需要传播到整个网络,控制消息数量较大。

但 DV 的距离向量可能包含大量目的地表项,并且在网络不稳定时需要反复更新,因此实际开销还取决于:

  • 网络规模;
  • 拓扑变化频率;
  • 距离向量大小;
  • 更新方式;
  • 协议实现。

12.3 收敛速度

LS 路由器获得新链路状态后,可以基于完整拓扑重新计算路径,通常收敛较快。

DV 中的信息必须逐跳传播,并可能受到旧信息影响,因此:

  • 更容易收敛缓慢;
  • 可能形成临时环路;
  • 可能出现 count-to-infinity。

12.4 健壮性

在 LS 中,某台路由器发布错误链路信息,会影响其他节点对相应链路的认识,但各节点仍然独立运行最短路径算法。

在 DV 中,一台路由器通告的错误距离可能直接被邻居当作计算依据。邻居计算出的错误结果还可能继续传播,因而错误更容易扩散。

12.5 典型问题

算法 典型风险
LS 控制消息泛洪开销、路由振荡
DV 收敛慢、路由环路、无穷计算

不能简单认为一种算法绝对优于另一种算法。二者是在不同维度上进行权衡:

  • DV 减少了全局拓扑维护;
  • LS 提供了更完整的信息和通常更快的收敛;
  • DV 的局部通信更简单;
  • LS 的错误更容易被限制在具体链路状态上。

❗本节核心结论:

LS 用更高的信息收集成本换取全局视野和较快收敛;DV 用局部交换降低拓扑维护成本,但更依赖邻居信息,也更容易出现环路和慢收敛。


13. 常见误区

13.1 DV 是否完全不进行计算

不是。

路由器收到邻居的距离向量后,必须使用 Bellman-Ford 方程重新计算自己的距离向量和下一跳。

DV 是分布式计算,而不是没有计算。

13.2 邻居说能到达目的地,是否一定安全

不一定。

邻居的路径可能:

  • 已经过期;
  • 已经失效;
  • 原本就经过当前路由器;
  • 依赖另一个错误通告。

因此,邻居信息只是一项当前估计。

13.3 更新后的路由表是否必然正确

不一定。

更新后的路由表只是新信息条件下的最优估计。在拓扑变化期间,路由器之间可能暂时不一致。

只有网络状态稳定并完成多轮信息传播后,算法才可能重新收敛。

13.4 下一跳是否等于最终目的地

通常不是。

下一跳是当前路由器的直接邻居;最终目的地可能还要经过多个中间路由器。

只有当目的地与当前路由器直接相连时,下一跳才可能就是目的地本身。

13.5 DV 路由器是否维护全局图

不维护。

DV 路由器知道自己的邻居和邻居通告的距离,但不知道全网所有链路如何连接。

13.6 毒性逆转是否属于错误通告

它是一种有意设计的协议行为,而不是随机错误。

的含义是:

1
2
不要通过我来选择这条路径,
因为我前往该目的地本来就依赖你。

13.7 毒性逆转是否能消除所有环路

不能。

它能有效防止部分简单环路,尤其是两个相邻节点互相把对方当作下一跳的情况,但不能保证消除所有多节点环路。


14. 知识结构总览

这张图反映了距离向量路由的完整逻辑:

  • 路由器只掌握局部信息;
  • 路由器根据邻居通告进行 Bellman-Ford 更新;
  • 多个节点异步、迭代地交换结果;
  • 信息不完整可能导致路由环路;
  • 水平分裂和毒性逆转用于缓解部分问题。

15. 复习清单

完成本章学习后,应能够回答以下问题:

  • 距离向量中的“距离”表示什么?
  • 距离向量中的“向量”为什么可以理解为一张列表?
  • DV 路由表中的 ToNextCost 分别表示什么?
  • 下一跳与完整路径有什么区别?
  • 为什么下一跳通常必须是当前路由器的直接邻居?
  • Bellman-Ford 方程中 Dₓ(y)c(x,v)Dᵥ(y) 分别表示什么?
  • 为什么 DV 只比较经过各邻居的总代价就能选择下一跳?
  • DV 路由器是否维护完整的网络拓扑?
  • LS 与 DV 在信息掌握范围上有什么区别?
  • DV 算法初始化时,到自己、邻居和未知节点的代价分别是多少?
  • 路由器在什么情况下会重新计算距离向量?
  • 为什么说 DV 是分布式、异步和迭代的?
  • 更新前和更新后的路由表为什么都只能称为当前估计?
  • 邻居的路由信息错误时,会怎样影响当前路由器?
  • 为什么出现更短路径时,好消息通常传播较快?
  • 为什么链路断开后,坏消息可能传播较慢?
  • 路由环路是怎样形成的?
  • Count-to-infinity 的根本原因是什么?
  • 水平分裂的基本规则是什么?
  • 毒性逆转为什么要向特定邻居通告
  • 毒性逆转能够防止哪些环路?
  • 为什么毒性逆转不能保证消除所有多节点环路?
  • 为什么消息传播方面 DV 可能更有优势?
  • 为什么收敛速度和健壮性方面 LS 通常更有优势?

结论

距离向量路由提供了一种不依赖完整网络地图的分布式路径计算方法。

每台路由器只需要知道直接邻居、到邻居的链路代价,以及邻居通告的距离向量。它通过 Bellman-Ford 方程比较经过不同邻居的总代价,选择最优下一跳,并在结果变化后继续通知邻居。

整个网络的路由结果不是由某个中心节点一次算出,而是在许多路由器之间通过异步、迭代的信息交换逐渐形成。

这种局部性降低了全局拓扑维护成本,却也带来了明显代价:路由器无法检查邻居通告背后的完整路径,因而可能被过期或循环依赖的信息误导,产生路由环路与无穷计算问题。

水平分裂和毒性逆转可以阻止部分错误的反向路由,但不能消除所有多节点环路。

距离向量路由的完整逻辑可以压缩为:

1
2
3
4
5
6
7
8
9
10
11
掌握直接邻居

接收邻居的距离向量

使用 Bellman-Ford 比较候选路径

选择最低代价与下一跳

结果变化后通知邻居

经过多轮交换逐渐收敛

❗最终结论: DV 像是在没有全局地图的情况下不断向邻居问路。它以较少的拓扑信息完成分布式路由计算,但也必须承担邻居信息不可靠、坏消息传播慢以及路由环路等风险。