路由算法

路由算法计算数据包通过网络所遵循的路径，通常通过使用全局链路状态视图或分布式、逐跳距离向量计算，在路由器和链路图中找到成本最低的路径。

Definition

路由算法是一种程序，它确定通过建模为加权图的网络中成本最低（或以其他方式优先）的路径，从而生成路由器用于将数据包转发到其目的地的转发决策。

Scope

本主题涵盖了填充转发表的算法：具有链路成本的网络图模型；使用Dijkstra最短路径算法和全局共享拓扑的链路状态路由；使用分布式Bellman-Ford计算和邻居交换的距离向量路由；它们的收敛行为和病态，例如“计数到无穷大”问题；以及用于可扩展性的分层路由。它抽象地处理这些算法，将具体的协议（OSPF、RIP、BGP）及其域内/域间组织留给路由协议主题。

Core questions

• 网络如何建模为加权图以进行路由？
• 链路状态算法如何从完整的拓扑视图计算最短路径？
• 距离向量算法如何仅通过邻居交换实现收敛？
• 收敛和稳定性问题（例如“计数到无穷大”）是什么，以及如何缓解它们？
• 为什么路由要分层，以及这如何影响路径最优性？

Key concepts

• 加权网络图
• 成本最低路径
• 链路状态路由
• Dijkstra算法
• 距离向量路由
• Bellman-Ford方程
• 计数到无穷大问题
• 水平分割和毒性反转
• 分层路由

Key theories

链路状态路由 (Dijkstra)

每个路由器泛洪其链路成本，以便所有路由器共享完整的拓扑，然后独立运行Dijkstra算法来计算最短路径；这种方法收敛快速且可预测，但需要全局信息交换。

距离向量路由 (Bellman-Ford)

路由器与其邻居交换到每个目的地的当前最低成本估计，并通过Bellman-Ford方程进行更新；该计算是分布式的，仅使用本地信息，但收敛可能缓慢并遭受“计数到无穷大”问题。

分层路由

由于扁平路由无法扩展到整个互联网，路由器被分组到区域（自治系统），路由在每个区域内部本地处理，并在区域之间进行汇总，以牺牲部分路径最优性来换取可扩展性和管理自治。

Clinical relevance

路由算法决定了流量的传输效率和可靠性：链路状态算法是OSPF等内部协议的基础，这些协议在故障后能快速收敛，而距离向量思想则出现在RIP和BGP的路径向量方法中。理解它们的收敛行为对于设计稳定的网络以及诊断链路或路由器故障后的路由环路和缓慢恢复至关重要。

History

路由核心的最短路径算法早于计算机网络：Bellman和Ford在1950年代后期关于路由问题的工作以及Dijkstra在1959年的最短路径算法。随着分组网络的发展，这些算法被改编为距离向量和链路状态路由，分层结构化为自治系统使路由扩展到全球互联网。

Debates

链路状态路由与距离向量路由

链路状态路由收敛快，避免“计数到无穷大”问题，但要求每个路由器保存完整的拓扑并进行更多计算；而距离向量路由更简单、更局部，但收敛可能缓慢并形成瞬时环路；实际网络在不同尺度上结合了这两种思想。

Key figures

• Edsger W. Dijkstra
• Richard Bellman
• Lester Ford

Seminal works

• dijkstra1959
• bellman1958
• kurose2021

Frequently asked questions

什么是“计数到无穷大”问题？

这是一种距离向量病态，在链路故障后，路由器通过交换陈旧信息，缓慢增加其到不可达目的地的距离估计，错误地认为彼此之间仍然存在路径。缓解措施包括水平分割、毒性反转和限制最大距离。

为什么链路状态和距离向量都被使用？

它们适用于不同的范围。OSPF等链路状态协议在单个管理域内提供快速、无环路的收敛，其中共享完整拓扑是可接受的。距离向量和路径向量方法在跨域时具有更好的可扩展性并揭示更少的内部细节，这就是BGP在网络之间使用路径向量设计的原因。