距离向量路由与失效传播

路由器可以只向邻居问一件事：“你认为到目的地还有多远？”把到邻居的链路成本加上这个回答，就得到一个经该邻居的候选。但回答来自过去的一张表；链路已经断开时，邻居可能仍在转述自己最早提供的旧消息。

形式陈述

每个目的分别维护距离和下一跳

IP转发需要前缀对应的出口与下一跳。距离向量协议负责生成或更新这些候选路由；转发查表本身不等于运行一次路由协议。

对目的 $x$ ，路由器 $u$ 保存当前估计 $D_u(x)$ 、下一跳 $N_u(x)$ ，以及各邻居最近收到的通告 $A_{u,v}(x)$ 。链路成本 $c(u,v)>0$ 。若 $u=x$ ，距离固定为0；否则按当前可用邻居重新计算

D_u(x)=\min_v\{c(u,v)+A_{u,v}(x)\}.

空候选集取无穷。直连目的网络可另作一个固定成本候选。选择取得最小值的邻居作下一跳，平局按固定邻居ID处理。收到新通告就替换该邻居的旧缓存，再重算；路由器改变结果后可通告邻居，也可周期性重发当前结果。

本页首先用数学无穷；讨论RIP式故障时改用饱和值 $I=16$ ，加法和最小值均限制到16。值16表示不可用，不安装一个“成本16的可达下一跳”。未到期的缓存只是最近收到的估计，并不证明邻居此刻真的拥有一条无环路径。

成本恶化也必须接受

Bellman–Ford松弛提供路径长度递推工具。在固定图、从无穷初始化的求短路过程中，距离只需改善；动态路由却必须允许提高距离或撤回路由。若当前下一跳通知“我已经到不了”，仍保留旧小值，就会永久引用失效路径。

完整协议还要规定邻居失效检测、缓存过期和消息发送规则。本文用明确事件序列计算状态，不把集中式算法的 $O(n+nm)$ 运算次数当成网络的收敛秒数，也不把一轮未收到消息直接解释为邻居死亡。

直觉

固定图上的一轮，多看一条边

暂取同步模型：所有路由器在一轮中读取上一轮距离，轮末同时写新结果。起初只有目的自身为0，其他为无穷。第 $k$ 轮的估计是至多 $k$ 条边路径的最小成本；末条选择邻居的递推正好枚举这些路径。

正成本使最短路径不需要重复顶点，因此含 $n$ 个顶点的固定图，在至多 $n-1$ 轮后得到可达顶点的距离。不可达者保持无穷。这里的轮数结论要求新鲜初始化和轮同步；带旧消息的故障恢复不满足这两个条件。

丢掉完整路径，节省了信息，也丢掉了依赖关系

距离通告只说“我这里是2”，没有说明这个2是否沿途经过接收者自己。当原出口断开，接收者可能把自己的旧信息绕一圈听回来，误以为找到了替代路线。不断加上正成本会使错误估计越来越大，却不会立即揭示它们都依赖同一个已经消失的出口。

例子与边界

正常收敛先算两轮

R1—R2成本1，R2—R3成本1，R1—R3成本4，以R3为目的。重置所有非目的距离为无穷：

轮	R1	R2
0	∞	∞
1	4，经R3	1，经R3
2	2，经R2	1，经R3
3	2，经R2	1，经R3

R1第一轮还看不到R2刚算出的1，第二轮才有候选 $1+1=2$ 。若在第一轮中就使用已经更新的R2，那是另一种原地事件顺序，不能把两张轨迹表混用。

断开的出口怎样被旧消息“接回来”

另开故障快照：A到目的网络X的直连成本为1，A—B成本1。原来A=1直达X，B=2经A；没有毒性逆转。断开A—X后，A仍缓存B此前通告的2，于是选择B，得到3。B听到A的3，改为4经A；A听到4，再改为5经B。

A和B把彼此的旧距离当作新出口，成本逐次增加；毒性逆转使经A的B向A报告不可达 — 数字增加不能证明出口仍然存在

在这一交替传递顺序下，结果继续为6、7、8，直到饱和16，最后双方均不可达。数据在A、B之间循环，IP的TTL可以限制一份包的寿命，却不能修复控制面的错误下一跳。

毒性逆转阻止的是哪一种互指

简单水平分割不向学来路线的方向通告该路线；毒性逆转则明确向该方向通告无穷。例如B经A到X时，B对A报16，而对其他邻居仍可报2。若A缓存到的已经是这份毒性通告，断开A—X后就不会把B作为替代出口。

这不要求A的实际数据包改发16，也不从转发表删除B对其他目的的路由；改变的是某一目的、某一通告方向的距离字段。省略路线与明确报不可达的区别，还影响接收者是否必须等待旧缓存超时。

三个路由器仍能把依赖绕开

下面使用允许定向成本的教学网络，所有邻接均能双向交换控制消息。A→B、B→A、B→C、C→B、A→C的成本都为1，C→A成本10；A直连X成本1。初始稳定路由是A=1直达，B=2经A，C=3经B。

采用毒性逆转，B对A报16、对C报2；C对B报16、对A报3。断开A—X后，按A、B、C轮流处理并立即向邻居提供新通告：

更新者	采用的非毒性候选	新状态
A	从C收到3，链路成本1	A=4，经C
B	从A收到4，链路成本1	B=5，经A
C	从B收到5，链路成本1	C=6，经B
A	从C收到6，链路成本1	A=7，经C

A向C报16，B向A报16，C向B报16；但循环实际为A→C→B→A，每个路由器仍从另一方向收到有限通告。正成本与饱和规则最终会结束这次计数，却没有在第一步排除三节点依赖环。这个定向成本例是协议原理的构造，不宣称所有RIP部署都采用这种链路配置。

推论与应用

短的无穷，换来有限的网络尺度

取16为无穷能让坏消息停止在一个有限数字，但也使真实最短成本为16的目的被表示为不可达。不能既保留该饱和值，又声称支持任意大的真实路径成本。RIP的选择以及水平分割、触发更新，是对协议开销和收敛行为的具体取舍。

触发更新使变化较快传播，但旧的周期性通告仍可能与它交错。判断一个“不会成环”的说法时，需问它是否包含在途旧消息、三节点循环和链路失效，而不只检查最终距离满足某个方程。

链路状态路由改为传播本地拓扑事实，再在各处计算路径；路径向量路由携带AS路径并加入策略。这些额外信息解决不同问题，也各自带来版本不一致或策略不收敛的边界。

参考资料

Gary Malkin，1998，RFC2453：RIP Version 2，§3.4距离向量递推、§3.4.1失效、§3.4.2计数到无穷、§3.4.3水平分割、§3.4.4触发更新；本文两节点和定向三节点轨迹独立构造
Richard Bellman，On a Routing Problem，Quarterly of Applied Mathematics 16(1)，1958，pp.87–90，原论文书目信息与正文入口：固定路径长度递推的来源，动态消息恢复条件见上述RFC

形式陈述 ​

每个目的分别维护距离和下一跳 ​

成本恶化也必须接受 ​

固定图上的一轮，多看一条边 ​

丢掉完整路径，节省了信息，也丢掉了依赖关系 ​

正常收敛先算两轮 ​

断开的出口怎样被旧消息“接回来” ​

毒性逆转阻止的是哪一种互指 ​

三个路由器仍能把依赖绕开 ​

短的无穷，换来有限的网络尺度 ​

反向链接