【计算机网络 | 网络层9：路由选择算法：距离向量与链路状态算法】

前面讨论 IP 地址、子网、IPv4/IPv6 数据报时，路由器似乎只要“查表转发”即可。但转发表不是凭空出现的：当链路故障、路由器新增或开销变化时，网络中的路由器需要重新判断，到达各个目的网络的下一跳应该是谁。这就是路由选择算法要解决的问题。

本篇仍位于 TCP/IP 五层模型的网络层。我们先建立一个共同的问题模型，再比较两类最经典的动态路由选择思路：拥有全网地图的链路状态算法，以及只与邻居交换距离估计的距离向量算法。下一篇会在此基础上进入 OSPF 与 BGP 等具体协议。

一、路由算法、路由协议与转发表不是一回事

这三个概念经常一起出现，但职责不同：

• 路由选择算法：根据已知网络信息计算较优路径，核心目标是找出到各目的地的下一跳；
• 路由选择协议：除了采用某种算法，还规定路由器交换什么信息、何时交换、如何处理更新；
• 转发表或路由表：算法和协议收敛后的结果，供路由器在收到数据报时快速查找并转发。

因此，路由器在转发一个具体 IP 数据报时，通常不会重新运行一遍完整算法；它使用已经建立好的转发表。算法和协议属于控制平面的工作，查表转发属于数据平面的工作。

路由选择主要发生在跨网络、跨路由器的通信中。同一局域网内的主机若在同一子网，通常先通过 ARP 获取目标 MAC 地址，再由交换机按二层规则转发，并不需要为这一次局域网通信计算路由路径。

二、把网络抽象成带权图

为了讨论算法，可以把路由网络抽象为一张图：

• 路由器是图中的节点；
• 两台路由器之间的链路是图中的边；
• 链路的开销是边的权值。

从源路由器到目的路由器的“最佳”路径，常指总开销最小的路径。开销可以按跳数、带宽、时延、管理策略等定义；本篇为理解算法，默认只讨论“总开销最小”。真实网络的路由选择还可能受到安全、商业关系和流量工程策略约束，所以“最短”不一定等于物理距离最近。

算法计算出的路径最终要落实为转发表中的下一跳。例如一条记录通常会关联目的网络前缀、下一跳地址或出接口，以及路由开销。

三、两类动态路由选择思路

动态路由算法会随拓扑或可用链路变化更新路由表。按路由器掌握的信息范围，可分为两类：

静态路由由管理员手工配置，简单且没有动态协议开销，适合非常稳定的小网络；本篇讨论的 LS 与 DV 都属于动态路由选择算法。

四、链路状态：先获得全网地图，再独立算最短路

所谓“链路状态”，指一个路由器直接连接了哪些邻居，以及每条直接链路的开销。链路状态算法的目标，是让每台路由器都持有一致的全网拓扑数据库。

1. 先收集并洪泛链路状态

每台路由器先检测自己的直接邻居与链路开销，并产生链路状态通告。通告只描述“我和谁直接相连、开销是多少”，而不是替所有路由器计算完整路径。

随后通过洪泛把通告扩散到整个路由域：路由器把新通告发送给相邻路由器，邻居再转发给其他邻居，避免立即发回刚来的方向和重复传播。最终，每台路由器都能拼出相同的网络拓扑图。

洪泛并不是简单使用某个局域网广播地址把信息发遍互联网；广播本身受本网范围限制。它是由路由协议控制、沿邻接关系逐跳扩散的过程。

2. 每台路由器各自运行 Dijkstra

得到全网图后，每台路由器把自己作为源点独立运行 Dijkstra 算法，计算到所有其他节点的最低费用路径。算法不断选择当前开销最小、且尚未确定的节点，再用它松弛相邻边，最终得到前驱关系和下一跳。

链路状态变化后，路由器更新拓扑数据库并重新计算。所有设备使用相同的拓扑信息独立计算，因此通常收敛较快，也更容易从通告内容定位某条链路或某个节点的异常。典型的链路状态路由协议是 OSPF。

3. 链路状态的特点

链路状态把“发现变化”和“计算路径”分开：变化的链路信息被通告到全网，而最短路计算在每台路由器本地进行。它的代价是需要维护拓扑数据库、洪泛控制和计算资源。

如果把实时负载或瞬时拥塞直接作为链路开销，路由器可能同时改选看似更便宜的路径，反而把新路径压拥堵，随后又一起切回，形成路由振荡。因此工程中通常对开销变化进行平滑、设置切换阈值或限制更新传播范围，而不是让每个短暂流量波动立刻改变全网路径。

五、距离向量：只和邻居“传话”，逐步逼近最短路

距离向量算法不要求路由器保存完整全网图。每台路由器只知道：

1. 自己到直接邻居的链路开销；
2. 自己到各目的地的当前距离估计，也就是距离向量；
3. 从每个邻居收到的距离向量。

路由器定期或在更新时把自己的距离向量发送给直接邻居。收到邻居 v 的向量后，路由器 x 对每个目的地 y 比较“当前距离”和“先到邻居 v、再由 v 到 y”的距离：

x 到 y 的新估计 = min(当前估计, x 到 v 的开销 + v 到 y 的估计)

这就是 Bellman-Ford 最短路径思想在网络中的分布式、异步版本。若新的距离向量发生改变，路由器再把更新通知邻居；反复交换，直到没有节点继续更新为止，称为收敛。

一个直观场景

路由器 A 只与 B、C 直接相连。A 并不知道远端网络 D 的完整拓扑，但 B 告诉它“我到 D 的开销是 4”，C 告诉它“我到 D 的开销是 7”。若 A 到 B 的开销为 1、到 C 的开销为 2，A 就会比较：

经 B 到 D：1 + 4 = 5 经 C 到 D：2 + 7 = 9

于是 A 把到 D 的下一跳选为 B。A 不需要知道 B 到 D 中间经过了哪些路由器，只需相信邻居给出的距离估计。这正是距离向量“局部交换、逐步传播”的特点。

典型的距离向量协议是 RIP；它采用跳数作为距离度量。不过要注意：**距离向量算法不等于 RIP。**不同协议可以使用距离向量思路，却采用不同的开销定义和不可达规则。

六、距离向量的难点：坏消息传播慢

距离向量在链路变好或出现新路径时，较小的开销很容易逐步传播；但链路断开或开销突然增大时，邻居可能还保存着旧的“可达”信息。

例如，Y 原本经 Z 到达目的 X，而 Z 原本也经 Y 到达 X。Y 到 X 的直连链路断开后，Y 可能误以为 Z 仍有通往 X 的好路径；Z 又可能误以为 Y 有。两者把数据报彼此转发，形成临时路由环路，并在后续通告中把到 X 的距离一点点增大。

这种距离逐步增加、迟迟才认识到不可达的现象称为无穷计数或“坏消息传播慢”。它会带来无效更新、收敛延迟和数据报在环路中绕行。IPv4 的 TTL 或 IPv6 的跳数限制能限制一个数据报无限循环，但不能替代路由协议本身的收敛机制。

常见缓解手段

毒性逆转对两个节点之间的简单环路特别有效，但不能解决所有多节点环路；实际协议通常结合多种机制降低风险。

七、链路状态与距离向量对比

两者没有脱离场景的绝对优劣。链路状态适合需要较快收敛、能够维护完整拓扑信息的路由域；距离向量实现和信息交换相对直接，但需要谨慎处理故障传播和环路问题。

八、总结

路由选择算法把路由器和链路抽象为带权图，并为每个目的地求出合适的下一跳。链路状态算法先通过洪泛让所有路由器获得一致的全网地图，再各自运行 Dijkstra；距离向量算法则让每台路由器只与邻居交换距离估计，依据 Bellman-Ford 关系异步迭代更新。

理解这两种基本思路后，再看具体协议就更清楚了：OSPF 如何在自治系统内部用链路状态建立路由，BGP 又为什么在自治系统之间更强调策略而非单纯最短路，将是下一篇的重点。

如果这篇文章对你有帮助，欢迎点赞、评论、关注、收藏。你们的支持是我前进的动力！