路由协议

路由协议为路由器建立下一跳表。距离向量交换“到 C 的代价是 X”这样的数值，过期通告可能让两个邻居互相转发。链路状态先泛洪网络拓扑，再由各路由器运行 Dijkstra；在本课的三节点链路断开、拓扑更新完成后，查表会丢包。

可以把两种方法看作问路：一种只问邻居“到面包店要几分钟”，另一种交换街道地图。面包店的路断了，旧时间可能让两个邻居互相指路；更新后的地图则能指出没有通路。数据包不携带地图，只按当前路由器的下一跳前进。

Dijkstra 和 Bellman–Ford 假设计算方已掌握所需输入。本课解释这些信息如何在路由器之间传播，以及过期信息如何形成环路。

路由协议如何工作

转发表回答“目标是 C，该交给哪个邻居”。路由协议写表，转发过程读表。数据卡片只写 dest C，不写完整的 A—B—C 路径。

距离向量是分布式 Bellman–Ford。邻居 nbr 通告 nbr_cost，本机计算 cand = nbr_cost + link_cost。候选代价更小，或该邻居本来就是当前下一跳时，都要更新。第二个条件意味着也接受来自当前下一跳的变差消息。若删掉它，路由器会保留旧的低代价，仍可能形成环路，却不再增加代价。有了它，代价会向 RIP 的无穷大 16 递增，最终让路由失效。

RIP 的水平分割和毒性逆转可以阻止这里的双节点环路，但不能保证消除三节点等更长环路。本课展示朴素算法，不演示这些改进；测验会问它们如何改变当前线路。

链路状态采用类似 OSPF 的方式。路由器发送 LSA，描述“我有哪些可用邻接链路”，而非“到 C 的代价”。通告经过泛洪组成 LSDB。地图完整后，执行 table = dijkstra(lsdb, dest)。链路断开时，新 LSA 删除边；没有路径的节点得到 ∞，查表后丢包。

这个结论只适用于本课三节点直线在新 LSA 安装完成之后。真实链路状态协议也可能在 LSDB 尚未同步时形成暂态环路。画布用一份共享地图简化了这个过程。

路由协议逐步演示

默认选择 Distance Vector、Contrast，拓扑为 A —1— B —1— C，目标为 C。先从空表收敛并交付一个包，再断开 B—C，对比距离向量的环路与链路状态的丢包。

1. A 有发往 C 的包，却无下一跳。 A、B 的表为 ∞，C 为 0 / local。dest C 卡片等待，尚无可显示的有效代价。
2. C 向 B 通告 C: 0。 通告携带代价，不携带路径。
3. B 写入 1 via C。 cand = 0 + 1 = 1 < ∞。
4. B 向 A 通告 C: 1。 表项变化触发通告。
5. A 写入 2 via B。 cand = 1 + 1 = 2，顶部显示 A = 2 via B。
6. 路由稳定。 下一跳为 A → B → C。独立的 Converge 场景还会让 A 向 B 通告 C: 2，B 忽略该较差候选；Contrast 省略这次往返。
7. A 出现数据包。 卡片为 dest C，A 查到下一跳 B。
8. A 转发给 B。 forward 只读取下一跳。
9. B 转发给 C。
10. 到达 C。 目标匹配，交付。包内从未存放 A—B—C 路径。
11. B—C 断开。 最后一跳出现红叉。
12. B 写入 ∞。 下一跳邻居不可达，on_link_down 安排一次 advertise。
13. 展示消息顺序。 1 A:C2 已在线路上，2 B: pending 排在后面。B 的更新在发送时才读取自己的表。先到的旧通告决定后续结果。
14. A 的周期通告 C: 2 先到 B。 内容已经过期。
15. B 写入 3 via A。 cand = 2 + 1 = 3 < ∞，但 A 的 2 本来就是经 B 得到的。
16. B 向 A 通告 C: 3。
17. A 写入 4 via B。 因为 nbr == route.next，接受当前下一跳发来的更差代价。
18. A 出现新包。 A 指向 B，B 现在指向 A。
19. A 转发给 B。
20. B 转发回 A。 环路形成。
21. 代价递增。 检查面板合并展示 3/4 → 5/6 → … → 15/16，表跳到 B = 15 via A、A = ∞。RIP 把 16 作为不可达；环路早在 3/4 时就已发生。
22. 转到链路状态。 左侧固定显示距离向量环路，当前表改由拓扑计算。同样以 C 为目标，B—C 同样断开。
23. B 泛洪 LSA B {A:1}。 消息描述邻居，而非到 C 的代价。
24. LSDB 删除 B—C。 地图只剩一条边，没有通往 C 的路径。
25. Dijkstra 给 A、B 写入 ∞。 不需要逐次计数。
26. A 出现数据包。 下一跳为 None。
27. next is None → drop。 目标仍是刚才发生环路的 C。
28. 保留两种结局。 距离向量定格在 A=4 via B、B=3 via A 的环路时刻；链路状态两者均为 ∞，包在 A 丢弃。

在 Contrast 中把 Protocol 改为 Link State，会先演示地图：两个 LSA、一次 Dijkstra、交付一个包，再断链丢包；距离向量环路作为静态对照。Converge 与 Link down 分别重放单种协议。

排查路由问题时看什么

最后一跳已断，RIP 风格路由表却仍有有限代价时，要检查下一跳。两个路由器若互指，控制面还在计数期间，数据包会循环直到 TTL 耗尽。

OSPF 收到撤销 LSA 后路由消失，应查看 LSDB 与邻接日志。地图无路时，丢包符合预期；不同路由器地图不一致时，则要检查泛洪延迟、SPF 调度或尚未安装的路由。这些暂态不在动画中。

路由写表，转发读表。表中有有限代价并不能排除环路；没有下一跳导致的丢包也不必然是转发器故障。

代价不等于地图

Dijkstra 需要图，路由协议负责收集图或距离信息。距离向量只声明代价，不说明代价如何得来；A 的旧 2 仍经 B，B 却从通告中看不到这个依赖。

LSA 声明邻接关系。各邻接信息汇入 LSDB 后，每台路由器才能运行已学过的最短路算法。这里新增的机制是泛洪，而非 Dijkstra 本身。

数据包的处理更简单：在 A 只读取 next = B。两个本地查表结果都合法，组合起来仍可成为 A ↔ B 环路。

边界情况

• 收敛时的较差候选。 Converge 中 A 把 C: 2 通告给 B，B 已有直接到 C 的代价 1，因此 < 条件拒绝更新。
• 目标的自身路由。 C 始终保留 0 / local，不会被通告覆盖。
• 断链竞态。 B 确实安排了更新，但 A 的旧周期消息已在途中并先到达。raceOrder 先展示队列；B 的更新发送时读表，因此通告 3 而非 ∞。
• 数到 16。 3/4 → … → 15/16 压缩后续交换。A 到 16 时删除下一跳，但包在代价 4 时已经循环。
• 没有备用路径。 本例没有 A—C 链路。B—C 断开后 C 不可达，不存在“增加到某个值后备用路由胜出”。
• 空下一跳。 LSDB 更新后，forward 在 nxt is None 处分支丢包。
• 未演示水平分割。 A 不把经 B 的路由通告回 B，就可阻止这里的双节点计数；更长环路仍可能存在。

常见错误

• 把路由协议当成 Dijkstra。 距离向量不建立全图；链路状态先建图，再调用 Dijkstra。
• 认为包携带整条路径。 暂停在首个 fwdHop，卡片只有 dest C，下一跳来自 A 的表。
• 删掉 nbr == route.next。 A 会在 B 通告 3 后仍保留 2 via B，环路照旧，只是不再计数。
• 认为水平分割能消除所有无穷计数。 它能处理本例的双节点环路，不能保证处理三节点环路。
• 认为链路状态永不成环。 这里只展示三节点直线在 LSA 安装后的结果。真实地图不同步时可能形成暂态环路。
• 混淆 ∞ 与可用代价。 代码用 RIP 的整数 16 表示不可达，表格画成 ∞，与最短路中的不可达记号一致。

模型的简化

距离向量使用朴素 Bellman–Ford，没有水平分割、毒性逆转、抑制定时器或 RIP invalid/flush 定时器，无穷大为 16。链路状态只展示类似 OSPF 的泛洪与一次 Dijkstra，不包含区域、指定路由器、LSA 类型、hello/dead 间隔。

本课只有一个目的地。画面显示共享 LSDB，代码仍保存每台路由器的 lsdb[node]，靠泛洪使副本一致。C 的 LSA 没有增加新的无向边，因此省略。BGP、路由策略和最长前缀匹配不在本课范围内。