前面讨论 IP 地址、子网、IPv4/IPv6 数据报时路由器似乎只要“查表转发”即可。但转发表不是凭空出现的当链路故障、路由器新增或开销变化时网络中的路由器需要重新判断到达各个目的网络的下一跳应该是谁。这就是路由选择算法要解决的问题。本篇仍位于 TCP/IP 五层模型的网络层。我们先建立一个共同的问题模型再比较两类最经典的动态路由选择思路拥有全网地图的链路状态算法以及只与邻居交换距离估计的距离向量算法。下一篇会在此基础上进入 OSPF 与 BGP 等具体协议。一、路由算法、路由协议与转发表不是一回事这三个概念经常一起出现但职责不同路由选择算法根据已知网络信息计算较优路径核心目标是找出到各目的地的下一跳路由选择协议除了采用某种算法还规定路由器交换什么信息、何时交换、如何处理更新转发表或路由表算法和协议收敛后的结果供路由器在收到数据报时快速查找并转发。因此路由器在转发一个具体 IP 数据报时通常不会重新运行一遍完整算法它使用已经建立好的转发表。算法和协议属于控制平面的工作查表转发属于数据平面的工作。路由选择主要发生在跨网络、跨路由器的通信中。同一局域网内的主机若在同一子网通常先通过 ARP 获取目标 MAC 地址再由交换机按二层规则转发并不需要为这一次局域网通信计算路由路径。二、把网络抽象成带权图为了讨论算法可以把路由网络抽象为一张图路由器是图中的节点两台路由器之间的链路是图中的边链路的开销是边的权值。从源路由器到目的路由器的“最佳”路径常指总开销最小的路径。开销可以按跳数、带宽、时延、管理策略等定义本篇为理解算法默认只讨论“总开销最小”。真实网络的路由选择还可能受到安全、商业关系和流量工程策略约束所以“最短”不一定等于物理距离最近。算法计算出的路径最终要落实为转发表中的下一跳。例如一条记录通常会关联目的网络前缀、下一跳地址或出接口以及路由开销。三、两类动态路由选择思路动态路由算法会随拓扑或可用链路变化更新路由表。按路由器掌握的信息范围可分为两类类别核心问题代表算法链路状态LS怎样让每台路由器获得一致的全网拓扑Dijkstra 最短路径算法距离向量DV怎样只靠邻居通告逐步得出最短距离Bellman-Ford 的分布式版本静态路由由管理员手工配置简单且没有动态协议开销适合非常稳定的小网络本篇讨论的 LS 与 DV 都属于动态路由选择算法。四、链路状态先获得全网地图再独立算最短路所谓“链路状态”指一个路由器直接连接了哪些邻居以及每条直接链路的开销。链路状态算法的目标是让每台路由器都持有一致的全网拓扑数据库。1. 先收集并洪泛链路状态每台路由器先检测自己的直接邻居与链路开销并产生链路状态通告。通告只描述“我和谁直接相连、开销是多少”而不是替所有路由器计算完整路径。随后通过洪泛把通告扩散到整个路由域路由器把新通告发送给相邻路由器邻居再转发给其他邻居避免立即发回刚来的方向和重复传播。最终每台路由器都能拼出相同的网络拓扑图。洪泛并不是简单使用某个局域网广播地址把信息发遍互联网广播本身受本网范围限制。它是由路由协议控制、沿邻接关系逐跳扩散的过程。2. 每台路由器各自运行 Dijkstra得到全网图后每台路由器把自己作为源点独立运行 Dijkstra 算法计算到所有其他节点的最低费用路径。算法不断选择当前开销最小、且尚未确定的节点再用它松弛相邻边最终得到前驱关系和下一跳。链路状态变化后路由器更新拓扑数据库并重新计算。所有设备使用相同的拓扑信息独立计算因此通常收敛较快也更容易从通告内容定位某条链路或某个节点的异常。典型的链路状态路由协议是 OSPF。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 的开销为 2A 就会比较经 B 到 D1 4 5 经 C 到 D2 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 的跳数限制能限制一个数据报无限循环但不能替代路由协议本身的收敛机制。常见缓解手段手段核心做法水平分割不把从某个邻居学到的路由再原样通告给该邻居毒性逆转若到目的地的下一跳是邻居就向该邻居声明该目的地不可达最大跳数或无穷大上限用有限上限尽快表示“不可达”例如 RIP 将 16 跳视为不可达触发更新与超时机制在故障时尽快传播变化并清理长期失效的路由毒性逆转对两个节点之间的简单环路特别有效但不能解决所有多节点环路实际协议通常结合多种机制降低风险。七、链路状态与距离向量对比对比维度链路状态LS距离向量DV初始掌握的信息通过洪泛获得全网拓扑与链路开销只知道直接邻居和邻居通告的距离路径计算各节点本地运行 Dijkstra各节点按 Bellman-Ford 关系迭代更新信息交换范围链路状态通告扩散到整个路由域仅与直接邻居交换距离向量收敛特点通常较快但需维护拓扑数据库与洪泛逐步传播坏消息可能较慢环路风险依赖一致拓扑和计算仍需防止异常更新更容易出现临时环路与无穷计数典型协议OSPFRIP两者没有脱离场景的绝对优劣。链路状态适合需要较快收敛、能够维护完整拓扑信息的路由域距离向量实现和信息交换相对直接但需要谨慎处理故障传播和环路问题。八、总结路由选择算法把路由器和链路抽象为带权图并为每个目的地求出合适的下一跳。链路状态算法先通过洪泛让所有路由器获得一致的全网地图再各自运行 Dijkstra距离向量算法则让每台路由器只与邻居交换距离估计依据 Bellman-Ford 关系异步迭代更新。理解这两种基本思路后再看具体协议就更清楚了OSPF 如何在自治系统内部用链路状态建立路由BGP 又为什么在自治系统之间更强调策略而非单纯最短路将是下一篇的重点。如果这篇文章对你有帮助欢迎点赞、评论、关注、收藏。你们的支持是我前进的动力
【计算机网络 | 网络层9：路由选择算法：距离向量与链路状态算法】
前面讨论 IP 地址、子网、IPv4/IPv6 数据报时路由器似乎只要“查表转发”即可。但转发表不是凭空出现的当链路故障、路由器新增或开销变化时网络中的路由器需要重新判断到达各个目的网络的下一跳应该是谁。这就是路由选择算法要解决的问题。本篇仍位于 TCP/IP 五层模型的网络层。我们先建立一个共同的问题模型再比较两类最经典的动态路由选择思路拥有全网地图的链路状态算法以及只与邻居交换距离估计的距离向量算法。下一篇会在此基础上进入 OSPF 与 BGP 等具体协议。一、路由算法、路由协议与转发表不是一回事这三个概念经常一起出现但职责不同路由选择算法根据已知网络信息计算较优路径核心目标是找出到各目的地的下一跳路由选择协议除了采用某种算法还规定路由器交换什么信息、何时交换、如何处理更新转发表或路由表算法和协议收敛后的结果供路由器在收到数据报时快速查找并转发。因此路由器在转发一个具体 IP 数据报时通常不会重新运行一遍完整算法它使用已经建立好的转发表。算法和协议属于控制平面的工作查表转发属于数据平面的工作。路由选择主要发生在跨网络、跨路由器的通信中。同一局域网内的主机若在同一子网通常先通过 ARP 获取目标 MAC 地址再由交换机按二层规则转发并不需要为这一次局域网通信计算路由路径。二、把网络抽象成带权图为了讨论算法可以把路由网络抽象为一张图路由器是图中的节点两台路由器之间的链路是图中的边链路的开销是边的权值。从源路由器到目的路由器的“最佳”路径常指总开销最小的路径。开销可以按跳数、带宽、时延、管理策略等定义本篇为理解算法默认只讨论“总开销最小”。真实网络的路由选择还可能受到安全、商业关系和流量工程策略约束所以“最短”不一定等于物理距离最近。算法计算出的路径最终要落实为转发表中的下一跳。例如一条记录通常会关联目的网络前缀、下一跳地址或出接口以及路由开销。三、两类动态路由选择思路动态路由算法会随拓扑或可用链路变化更新路由表。按路由器掌握的信息范围可分为两类类别核心问题代表算法链路状态LS怎样让每台路由器获得一致的全网拓扑Dijkstra 最短路径算法距离向量DV怎样只靠邻居通告逐步得出最短距离Bellman-Ford 的分布式版本静态路由由管理员手工配置简单且没有动态协议开销适合非常稳定的小网络本篇讨论的 LS 与 DV 都属于动态路由选择算法。四、链路状态先获得全网地图再独立算最短路所谓“链路状态”指一个路由器直接连接了哪些邻居以及每条直接链路的开销。链路状态算法的目标是让每台路由器都持有一致的全网拓扑数据库。1. 先收集并洪泛链路状态每台路由器先检测自己的直接邻居与链路开销并产生链路状态通告。通告只描述“我和谁直接相连、开销是多少”而不是替所有路由器计算完整路径。随后通过洪泛把通告扩散到整个路由域路由器把新通告发送给相邻路由器邻居再转发给其他邻居避免立即发回刚来的方向和重复传播。最终每台路由器都能拼出相同的网络拓扑图。洪泛并不是简单使用某个局域网广播地址把信息发遍互联网广播本身受本网范围限制。它是由路由协议控制、沿邻接关系逐跳扩散的过程。2. 每台路由器各自运行 Dijkstra得到全网图后每台路由器把自己作为源点独立运行 Dijkstra 算法计算到所有其他节点的最低费用路径。算法不断选择当前开销最小、且尚未确定的节点再用它松弛相邻边最终得到前驱关系和下一跳。链路状态变化后路由器更新拓扑数据库并重新计算。所有设备使用相同的拓扑信息独立计算因此通常收敛较快也更容易从通告内容定位某条链路或某个节点的异常。典型的链路状态路由协议是 OSPF。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 的开销为 2A 就会比较经 B 到 D1 4 5 经 C 到 D2 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 的跳数限制能限制一个数据报无限循环但不能替代路由协议本身的收敛机制。常见缓解手段手段核心做法水平分割不把从某个邻居学到的路由再原样通告给该邻居毒性逆转若到目的地的下一跳是邻居就向该邻居声明该目的地不可达最大跳数或无穷大上限用有限上限尽快表示“不可达”例如 RIP 将 16 跳视为不可达触发更新与超时机制在故障时尽快传播变化并清理长期失效的路由毒性逆转对两个节点之间的简单环路特别有效但不能解决所有多节点环路实际协议通常结合多种机制降低风险。七、链路状态与距离向量对比对比维度链路状态LS距离向量DV初始掌握的信息通过洪泛获得全网拓扑与链路开销只知道直接邻居和邻居通告的距离路径计算各节点本地运行 Dijkstra各节点按 Bellman-Ford 关系迭代更新信息交换范围链路状态通告扩散到整个路由域仅与直接邻居交换距离向量收敛特点通常较快但需维护拓扑数据库与洪泛逐步传播坏消息可能较慢环路风险依赖一致拓扑和计算仍需防止异常更新更容易出现临时环路与无穷计数典型协议OSPFRIP两者没有脱离场景的绝对优劣。链路状态适合需要较快收敛、能够维护完整拓扑信息的路由域距离向量实现和信息交换相对直接但需要谨慎处理故障传播和环路问题。八、总结路由选择算法把路由器和链路抽象为带权图并为每个目的地求出合适的下一跳。链路状态算法先通过洪泛让所有路由器获得一致的全网地图再各自运行 Dijkstra距离向量算法则让每台路由器只与邻居交换距离估计依据 Bellman-Ford 关系异步迭代更新。理解这两种基本思路后再看具体协议就更清楚了OSPF 如何在自治系统内部用链路状态建立路由BGP 又为什么在自治系统之间更强调策略而非单纯最短路将是下一篇的重点。如果这篇文章对你有帮助欢迎点赞、评论、关注、收藏。你们的支持是我前进的动力