Dijkstra最短路径算法短期内不会被生产路由器替换

去年有几个人向我转发了同一篇关于网络中寻找最短路径新方法的文章。

这项基础研究声称改进了由Dijkstra开创的经典方法，该方法在大多数网络教科书中都有教授。我最初有点怀疑，就像我读到黎曼猜想被证明时的感觉一样。

Dijkstra是计算机科学的传奇人物，他在1959年发表的算法比分组交换技术还要早几年。OSPF（开放最短路径优先协议）是两个主要链路状态路由协议之一（另一个是中间系统到中间系统协议IS-IS）。

对OSPF实现者的指导异常详细，基本上告诉他们使用Dijkstra算法。几十年来，大多数实现都是这样做的，多年来只有一些小的改进来加速实现，但核心算法没有真正改变。

新算法并非对Dijkstra的小幅调整，而是一种截然不同的方法。其主要声称是，Dijkstra需要排序操作，因此性能只能达到最佳排序算法的水平，而这种新方法"突破了排序障碍"。也就是说，它避免了排序需求，能够提供比Dijkstra更好的性能边界。

虽然我不认为自己有资格评估描述新算法的论文，但它已经通过了顶级会议（ACM计算理论研讨会）的同行评议，并经过了足够的审查，我不怀疑理论的有效性。我想在这里讨论的问题是：这重要吗？

算法性能的理论改进带来的影响

当我试图评估算法性能理论改进的影响时，立即想到了两个主要问题。首先是，在真实路由系统中我们需要解决的实际扩展限制是什么。例如，Dijkstra算法在具有n个顶点（路由器）和m条边（链路）的网络中的运行时间为(n log n + m)数量级。新方法声称为(m log2/3 n)数量级，对于足够大的n显然会更少。评估任何东西扩展性的问题在于，你必须思考n必须达到多大才能产生影响。两种方法之间可能存在不同的常数因子；在小n值时，"可扩展性较低"的方法实际上可能显示更好的性能。

我的第一份工作之一是参与构建基于小型交换元件阵列的可扩展分组交换机团队。我们有论文显示可以构建具有数千个155 Mbps端口的交换机，而当时共享以太网运行速度为10 Mbps，尚未被交换式以太网超越。

当我们在贝尔核心投入大量时间和金钱组装32端口原型交换机时，FORE系统交付了商业上成功的16端口交换机。它们几乎肯定不如我们的设计可扩展，但在1990年代，n=16对于155 Mbps链路的交换机来说是相当有用的容量。我们感到很遗憾，我们的研究似乎被商业产品超越了。我的收获是，可扩展性是值得追求的好事，但有时你可能通过可扩展性较低的解决方案获得好结果。

SPF计算中n的大值是什么？我咨询了几位同事，更新了对大型OSPF或IS-IS骨干网中可能找到多少路由器的回忆。在我的记忆中是数百个；对于今天最大的服务提供商网络，似乎是数千个的小数量级。这不算微小，但与BGP中携带的前缀数量相比还是很小的。

而且似乎不受SPF计算性能的限制。

路由协议性能的多个因素

我在大型路由器公司工作时的另一个记忆是对影响路由协议性能的所有因素的分析。我在早期从事MPLS工作，我们对一种叫做"快速重路由"（FRR）的技术很兴奋，它使用MPLS在不等待故障后路由收敛的情况下将数据包绕过故障链路转移。但同时，负责路由协议开发的人员正在努力改进路由收敛时间。事实证明，对于MPLS和标准路由来说，最重要的事情之一就是更快地检测故障。例如，如果你必须等待数十秒的OSPF Hello数据包丢失才能宣告链路故障，那么你能否在几分之一秒内计算最短路径并不重要。这就是创建BFD（双向转发检测）的原因：一种独立于路由的快速机制，可以检测任何类型链路的故障。

除了快速故障检测，影响路由收敛的其他因素还包括：在链路上发送新链路状态数据包的时间和跨网络的传播延迟；接收此类数据包并将其分派给操作系统中正确进程的时间；SPF时间；更新路由信息库的时间；计算对转发表影响的时间；将任何转发表更新推送到线卡的时间（在有这种设备的大型路由器上）；将链路状态数据包泛洪到邻居的时间。多年来，所有这些步骤都经过了分析和优化，以至于亚秒级路由收敛现在已成为常规。早在2003年，对上述所有步骤的改进就已经实现了亚秒级收敛。是的，如果你想要快速收敛，你不能花10秒钟做SPF计算，但这在当时已经是一个解决的问题。优化所有其他部分至少与改进SPF计算时间同样重要。

实现复杂性的考虑

最后，我与另一位同事讨论了这个话题，他提醒我Dijkstra算法仍然是首选实现方法的一个原因：它可以被必须编写代码的人理解。Dijkstra本人在2001年的采访中说得很好：换句话说，保持简单。我当然宁愿让工程师研究OSPF规范，也不愿让他们去理解可能在路由收敛的非瓶颈部分节省几毫秒的混合Bellman-Ford/Dijkstra方法。也许有一天会有人写出像Dijkstra论文和OSPF规范一样清晰的新型SPF方法解释。混合算法可能对大型映射应用很有用。但我不认为Dijkstra算法会很快在生产路由器中被替换。

Q&A

Q1：新的最短路径算法相比Dijkstra算法有什么优势？

A：新算法声称能够"突破排序障碍"，避免了Dijkstra算法需要的排序操作，在理论上能够提供更好的性能边界，运行时间复杂度为(m log2/3 n)，在网络规模足够大时会比Dijkstra的(n log n + m)更优。

Q2：为什么新算法短期内不会替代Dijkstra算法？

A：主要有三个原因：首先，实际网络规模（数千个路由器）下性能差异不明显；其次，路由收敛的瓶颈不在SPF计算，而在故障检测、数据包传播等其他环节；最后，Dijkstra算法更容易理解和实现，工程师更容易掌握。

Q3：影响路由协议收敛时间的主要因素有哪些？

A：包括故障检测时间、链路状态数据包发送和传播延迟、数据包接收和分派时间、SPF计算时间、路由信息库更新时间、转发表计算和推送时间等。其中故障检测通常是最大瓶颈，这也是为什么会开发BFD等快速检测机制的原因。