路由算法：距离矢量与链路状态

上一篇我们看清了路由表怎么用——拿目标 IP 查表、最长前缀匹配选下一跳。但有个问题被我们暂时跳过了：路由表里那些条目到底是怎么来的？ 小网络可以人工一条条配，可到了运营商骨干网、数据中心、企业核心网，成百上千台路由器、链路随时可能抖动或断掉，靠人手维护根本不可能。于是路由器之间必须能自动交换信息、自己算出路，这就是动态路由算法要解决的事。

教科书里最经典的是两类思路：距离矢量和链路状态。很多人学这块只背下「RIP 是距离矢量、OSPF 是链路状态」就过了，却说不清它们各自怎么算、信息怎么传、为什么一个收敛慢一个收敛快。这一篇我们反过来：先把两种算法的运转机制一步步拆开——谁告诉谁什么、收到后怎么更新自己的表——看清机制之后，再回答它们的差异和取舍从何而来。

不要把路由算法当成纯数学题。它本质上在回答一个工程问题：网络变化之后，每台设备怎样尽快、尽量正确地知道「路该怎么走」。

一、先明确：算法到底在算什么

在拆算法之前，先统一目标。每台路由器要算出的，是一张「到各个目标网络，下一跳该交给哪个邻居、代价多少」的表。这里的**代价（cost / metric）**可能是跳数、带宽、延迟等度量。算法的任务就是：在一张由路由器和链路构成的图上，为每个目标找出代价最小的路径，并据此确定下一跳。

区别只在于「靠什么信息、用什么方式」算出这个最小代价。距离矢量和链路状态给了两种截然不同的答案：一种是「只信邻居转告的结论」，一种是「先拿到全图自己算」。

二、距离矢量的机制：向邻居打听，再更新自己

距离矢量（Distance Vector）的核心想法，像极了问路：你不知道全程，但你可以问身边每个邻居「你到目的地多远」，再加上「我到你多远」，就能估出「我经你到目的地多远」。

它的运转机制是这样的：

  1. 每台路由器维护一个矢量：记录自己到每个已知目标网络的「最短代价」和「对应的下一跳邻居」。初始时只知道自己的直连网络（代价为 0 或链路代价）。

  2. 周期性地把整张矢量发给所有直连邻居：注意——它发的不是拓扑，而是自己算出的结论：「我到 A 要 3，到 B 要 5，到 C 要 2……」

  3. 收到邻居的矢量后，做更新：对每个目标网络，用 Bellman-Ford 思想算一遍：

    1
    我经邻居 N 到目标 D 的代价 = 我到 N 的链路代价 + N 声称它到 D 的代价

    把所有邻居都这么算一遍，取最小值作为我到 D 的新代价，并把下一跳记成那个最优邻居。

  4. 如果表变了，再扩散给邻居，如此反复，直到全网不再变化——这就叫收敛。

举个具体例子：路由器 A 直连 B（代价 1），B 告诉 A「我到网络 D 代价是 4」。A 一算：经 B 到 D = 1 + 4 = 5。如果 A 当前没有更好的路，就把「到 D：代价 5，下一跳 B」写进表。这就是距离矢量最核心的一次更新。

距离矢量的精髓：每台设备只看得到「邻居转告的结论」，看不到全网长什么样。它靠一轮轮交换结论，让正确的代价像涟漪一样从目标处扩散到全网。RIP 是典型代表。

三、距离矢量的软肋：坏消息传得慢

机制看懂了，它的毛病也就藏在机制里。距离矢量有个著名问题——计数到无穷（count to infinity），根源在于「每台设备只信邻居的结论，却不知道这个结论是不是绕回了自己」。

设想 A 通过 B 到达网络 D。某刻 D 断了，B 知道到不了 D 了。但就在 B 要扩散这个坏消息前，它先收到了 A 的旧矢量——A 还在说「我到 D 代价 5（其实是经 B）」。B 一看：「哦，我可以经 A 到 D，代价 5+1=6」，于是 B 把到 D 改成「经 A，代价 6」。可 A 的那条路本来就是经 B 的！现在形成了 A→B→A 的来回指认，两边代价你加一我加一，缓慢爬向无穷，直到达到协议设的上限（RIP 里是 16 跳算作不可达）才停。

距离矢量的「好消息传得快、坏消息传得慢」就来自这里——它看不到全局拓扑，无法识别「这条路其实绕回了我自己」。

为缓解它，距离矢量协议打了一堆补丁：水平分割（从某邻居学到的路由，不再告诉那个邻居）、毒性逆转（明确告诉邻居「我经你的那条路代价是无穷」）、触发更新（一变就立刻发，不等周期）。这些补丁能减轻问题，但治不了根——根在「只有结论、没有全图」。

四、链路状态的机制：先拿全图，再自己算

链路状态（Link State）换了完全不同的思路：与其听邻居转述结论，不如让每台路由器都先拿到一张完整的全网地图，然后各自独立算最短路径。 OSPF 是典型代表。它的运转分两个清晰的阶段：

阶段一：测量并洪泛链路状态。

  1. 每台路由器先探测自己直连的链路：邻居是谁、这条链路代价多少（通过 Hello 报文发现邻居、检测存活）。
  2. 把这些信息打包成一条 链路状态通告（LSA）：「我是 R1，我直连 R2 代价 1、直连 R3 代价 4」。
  3. 洪泛（flooding）：把自己的 LSA 发给所有邻居，邻居收到后再转发给它们的邻居……每条 LSA 都传遍全网。关键是 LSA 带序列号，重复的会被丢弃，不会无限转。
  4. 结果：每台路由器都收齐了全网所有路由器的 LSA，拼起来就是一张完整的网络拓扑图，存在「链路状态数据库（LSDB）」里。全网的 LSDB 最终是一致的。

阶段二：独立计算最短路径。

每台路由器拿着这张全图，以自己为根，跑一遍 Dijkstra 最短路径算法，算出到每个目标网络的最短路径，进而确定下一跳，填进路由表。

flowchart TD A[探测直连链路<br/>Hello 发现邻居 + 测代价] --> B[生成本机 LSA] B --> C[向全网洪泛 LSA<br/>带序列号去重] C --> D[各路由器收齐所有 LSA<br/>构建一致的 LSDB 全网拓扑] D --> E[以自己为根<br/>跑 Dijkstra 算最短路径] E --> F[得出到各目标的下一跳<br/>填入路由表]

这张图的要点是：前三步是「同步出一张全网一致的地图」，最后两步是「每台设备拿着同一张地图各算各的」。 因为每台设备都基于完整拓扑独立计算，它能一眼看出「这条路是不是绕回了自己」，所以没有计数到无穷的问题，收敛也更快——拓扑一变，新 LSA 洪泛出去，大家更新地图、重算一遍即可。

五、两者的本质差异：信息视野不同

把两套机制并排，差异其实就一句话——它们掌握的信息不一样：

维度 距离矢量 链路状态
每台设备知道什么 只知道「邻居说它到各处多远」 知道全网完整拓扑
交换什么 自己算出的结论矢量 自己的直连链路状态（LSA）
怎么算 Bellman-Ford，依赖邻居结果迭代 各自跑 Dijkstra
传播方式 只发给直连邻居，逐跳扩散 洪泛到全网
收敛速度 慢，有计数到无穷 快，无环路计算问题
资源开销 CPU/内存省，但收敛慢 内存（存全图）和 CPU（算 Dijkstra）开销大
典型协议 RIP OSPF、IS-IS

一句话记牢：距离矢量像「不断向周围人打听路线」，链路状态像「每个人都先拿到同一张地图再自己规划」。打听省事但容易被错误结论误导，拿地图费资源但看得全、判断准。

六、收敛：为什么它是评价路由协议的关键

「收敛」这个词反复出现，单独说清它的分量。收敛指的是：网络发生变化（链路断、设备故障、新增节点）后，所有路由器重新对「路该怎么走」达成一致认识所需的过程和时间。

收敛慢的代价是真金白银的：在没收敛的那段时间里，有的路由器还按旧拓扑转发，可能把包送进一条已经断了的路（黑洞），或者两台设备互相把包推给对方（环路），表现为业务大面积超时、抖动。所以工程上评价一个路由协议，从来不只看「能不能算出路」，而是看：收敛速度、稳定性、资源开销、可扩展性、可维护性。这也是大型网络普遍选 OSPF/IS-IS 而非 RIP 的根本原因——前者收敛快得多。

七、那 BGP 呢：现实里的第三种考量

真实互联网的「主干路由」既不是纯距离矢量也不是纯链路状态，而是 BGP。它常被归为「路径矢量」——是距离矢量的演进：交换的不只是代价，而是到目标要经过的完整 AS 路径列表。

这么设计有两个现实理由：一是靠记录完整路径直接避免环路（看到路径里已有自己就拒绝，根治了计数到无穷）；二是互联网由无数自治系统（AS，各家运营商/机构）组成，路由选择掺杂大量商业策略（走谁的线便宜、和谁有对等协议），而不只是「跳数最少」。OSPF 这类管一个 AS 内部（IGP），BGP 管 AS 之间（EGP）——它们分工协作，撑起了整个互联网的可达性。

八、工程视角：这些知识什么时候用得上

作为后端/SRE，你未必天天配路由协议，但这些理解会在关键时刻救你：

  • 看懂收敛抖动：一次机房链路 flapping（频繁断连），可能引发路由反复重算、业务周期性超时。知道「收敛」这个概念，你才会往路由层去查，而不是死盯应用。
  • 理解云上路由的局限：云厂商的 VPC 路由表大多是「静态 + 受控」的，不跑 OSPF。理解动态路由的代价（资源、收敛复杂度），你就明白云为什么用更简单、可控的模型。
  • 多活/多线路场景：当你的服务接了多条出口线路，流量为什么走这条不走那条、一条断了多久切过去，背后都是路由协议的度量和收敛在起作用。
  • debug 不对称路由：去回路径不一致常源于两端路由策略差异，理解算法有助于定位。

九、学习这一部分最容易踩的坑

1. 只背「RIP 距离矢量、OSPF 链路状态」

名字是结果，机制才是根。说不清「一个交换结论矢量、一个洪泛 LSA 后各跑 Dijkstra」，这个对比就没真懂，遇到变体（IS-IS、EIGRP）就抓瞎。

2. 以为距离矢量「算错了」

计数到无穷不是 bug，是「只有邻居结论、没有全局视野」这一信息局限的必然产物。理解它来自信息不足，才理解为什么链路状态用「拿全图」来根治。

3. 把洪泛当成广播风暴

LSA 洪泛带序列号去重，每条 LSA 在每台设备只被转发有限次，会收敛停止，不是无限循环。这和无控制的二层广播风暴是两码事。

4. 忽视收敛速度的工程分量

「能算出路」只是及格线。生产网络里，收敛慢一秒可能就是一片超时。评价路由方案，收敛、稳定、开销同样关键。

总结

这一篇我们先拆机制、再谈取舍，核心是看清两种算法「信息从哪来、怎么算出路」：

  • 动态路由要解决的是「网络变化后，路径信息如何传播、路由表如何自动更新」；
  • 距离矢量交换「自己算出的代价矢量」，靠 Bellman-Ford 迭代，只知邻居结论，收敛慢、有计数到无穷；
  • 链路状态洪泛「直连链路 LSA」，每台设备拼出全网拓扑后各跑 Dijkstra，收敛快、无环路计算问题；
  • 二者的本质差异是信息视野：一个只信邻居转述，一个先拿全图自己算；
  • 收敛速度、稳定性、资源开销才是工程上评价路由协议的真正标尺；
  • 现实互联网骨干用 BGP（路径矢量），因为既要防环路，又要承载 AS 之间的商业策略。

当你能对着一张小拓扑，分别用距离矢量「一轮轮交换矢量」和链路状态「洪泛 LSA 再跑 Dijkstra」走一遍、并说清各自为什么这样收敛，这部分就真正属于你了。

参考资源：