链路状态路由与混合版本转发

同一来源能排序，不同来源没有天然共同快照 ​

“来源R2的12比11新”是局部可检查的版本关系。R2的12与R3的8却没有统一大小关系；它们可能描述不同时间观察到的拓扑。一张LSDB往往是许多来源版本的组合，不是全网共同提交的某一瞬间。

对每个来源保留最大版本，有助于处理重复与乱序，却不能强迫各路由器同时切换转发表。链路状态路由因此可以在稳定后正确，同时在传播期间出现短暂环或丢包。

共同距离函数才能阻止稳定转发环 ​

假设各处都采用同一张固定正成本图，且对目的 $x$ 安装一致最短距离所对应的下一跳。若 $u$ 把包交给 $v$，则

沿每一跳共同距离严格下降，不可能回到原点。平局选不同最短路径仍满足该式；但如果 $u$ 和 $v$ 使用不同图，就没有一个共同的 $d$ 可供整条转发轨迹比较。

一次断线产生两张都“算对了”的本地图 ​

R1—R2成本1，R2—R3成本1，R1—R3成本4，以R3为目的。初始各处LSDB相同：R1选R2、成本2；R2直达R3、成本1。

现在R2—R3断开。R2发布自身版本12，列表只剩R1；它原来的版本11曾列出R1与R3。R2立即采用自己的12并重算；R1暂时仍保存R2的11。其余通告暂不改变，按双端列出才存在边的规则，得到：

R2的5来自R2→R1→R3，成本 $1+4$，在它的新图里完全正确。R1的2来自R1→R2→R3，在旧图里也完全正确。但真正的数据包在R1、R2之间往返，因为下一跳决定取自不同图。

到达顺序比消息名称重要 ​

随后R1收到R2的12，替换旧记录，删除计算图中的R2—R3，改为直达R3、成本4。R2继续经R1、成本5，转发路径恢复为R2→R1→R3。此后迟到的版本11被拒绝，不能把已撤销链路重新添回。

这个例子不要求R3的新版已经到达R1，因为R2这一端的删除足以让双端条件失败。若后来R3也发布撤销，它应作为另一个来源的独立版本处理，不能拿R3的版本号和R2的12比较大小。

序号回退会破坏“更大才新”的前提 ​

若R2重启后从1重新计数，而其他节点仍记着12，它的新事实会被拒绝。若计数器达到最大值后直接回零，也有同一问题。本文通过不回绕、跨重启不倒退排除它们；真实OSPF则结合序号空间、刷新、老化和清除规则处理，不能仅照搬一行整数比较。

RFC2328中，一份LSA由类型、Link State ID及Advertising Router共同标识；新旧比较还包括序号、校验和与年龄，同序号不总意味着同一实例。本文按来源单记录的模型，只保留理解乱序所需的骨架。

收敛条件必须包含故障后的可达性 ​

若拓扑最终固定，幸存控制链路连通，来源的最终版本能通过可靠交换抵达每个节点，且各节点最终完成重算安装，则大家最终得到相同图和相应转发表。分区时只能在各分量内讨论此结论；孤立节点不能靠无限等待获得另一分量的新事实。

数据库一致和转发表一致是两道检查 ​

即使两个路由器已经保存同一组LSA，一个可能尚未完成重算或安装，所以检查LSDB相同还不够。反过来，两份LSDB不同也可能恰好生成同一目的的相同下一跳，不能只看版本差异就宣称必有环。

在图有 $n$ 个顶点、$m$ 条边时，选用合适堆实现的Dijkstra成本按旧算法页的模型计算；这是一次本地计算的成本。泛洪消息量、重传、通告批处理与转发表安装是另外的工作，不能一并塞进最短路的时间界。

距离向量理路距离向量路由与失效传播Distance-vector routing · 距离向量协议 · Count to infinity让相邻路由器交换距离估计，复算稳定路径、坏消息导致的计数到无穷，以及毒性逆转能排除二节点互指却仍允许三节点循环的边界。的坏消息示例提醒我们检查转述的依赖；这里的混合LSDB例提醒我们检查本地图的版本组合。二者都需要把控制消息轨迹与实际包的下一跳轨迹分别列出。