本文翻译自 Faster than Dijkstra?，原载于 Hacker News。
去年，有好几位朋友给我转发了一篇关于网络最短路径查找新方法的文章。这项研究声称改进了Dijkstra开创的经典算法——这个算法几乎出现在所有网络教材中（包括我们自己写的那本）。
说实话，我一开始是持怀疑态度的。这种感觉就像看到有人声称证明了黎曼猜想一样。Dijkstra是计算机科学界的传奇人物，他在1959年发表的这个算法甚至比分组交换技术的诞生还要早几年。OSPF（开放式最短路径优先协议）作为目前主流的链路状态路由协议之一（另一个是IS-IS），其规范文档对实现者的指导异常详细，基本就是告诉他们：用Dijkstra算法。几十年来，大多数实现都是这样做的，虽然有一些小的改进来加速实现，但基本原则从未改变。
而这个新算法不是对Dijkstra的小修小补，而是一种截然不同的方法。它的核心宣称是：Dijkstra算法需要进行排序操作，因此其性能受限于最优排序算法的性能；而这个新方法”打破了排序壁垒”——它避免了排序的需求，能够提供比Dijkstra更好的性能界限。
虽然我自认没有资格评估描述这个新算法的论文，但它已经在顶级会议（ACM计算理论研讨会）上通过了同行评审，也接受了足够的审查，所以我不怀疑理论上是行得通的。我想在这里讨论的问题是：这重要吗？
理论改进 vs 实际需求
当我尝试评估算法性能的理论改进有何影响时，立刻想到了两个主要问题。
首先是：在一个真实的路由系统中，我们实际需要解决的扩展性限制是什么？
举个例子，对于一个有 n 个顶点（路由器）和 m 条边（链路）的网络，Dijkstra算法的运行时间复杂度是 O(n log n + m)。新方法的复杂度是 O(m log^(2/3) n)，当 n 足够大时，确实会更小。（说实话，我在写这句话之前不得不复习了一下对数记法。）
评估任何东西的扩展性时的问题在于：你必须思考 n 要多大才能产生差异。两种方法之间可能存在不同的常数因子；在 n 较小时，一个”扩展性较差”的方法实际上可能表现更好。
扩展性的实际限制
我早年在Bellcore工作时，我们团队正在构建一个基于小型交换元件阵列的可扩展分组交换机。我们有论文证明可以构建数千个端口、155 Mbps速率的交换机——在那个共享以太网只有10 Mbps、还未被交换式以太网超越的年代。当我们还在投入大量时间和金钱组装32端口的原型交换机时，FORE Systems公司已经成功交付了商用的16端口交换机。
几乎可以肯定，他们的设计没有我们的可扩展，但事实证明在1990年代，对于155 Mbps链路的交换机来说，n=16 是一个相当实用的容量。我们感到很沮丧，我们的研究似乎被商业产品超越了。
我的收获是：可扩展性是值得追求的，但有时用一个扩展性较差的解决方案也能取得好结果。我最喜欢的教材之一《计算机系统设计原理》用超大型油轮的例子来演示系统的扩展限制。超大型油轮存在扩展限制这一事实，并不妨碍它们成为石油运输的中坚力量。你只需要避免把它们造得太大。
SPF计算中的 n 有多大？
那么，在SPF（最短路径优先）计算中，n 的值有多大呢？我问了几位同事，更新了我对大型OSPF或IS-IS骨干网中可能有多少路由器的记忆。
在我的印象中是几百个；对于当今最大的服务提供商网络来说，似乎是小几千个。所以这个数字不算小，但与BGP中承载的前缀数量相比，还是小得多。
而且，正如我将在下面解释的，这似乎并不是受限于SPF计算的性能。
性能的多维度考量
我在大型路由器公司工作时，还有一段关于路由协议性能分析的记忆。那时我正在研究早期的MPLS，我们对一种叫做”快速重路由”（Fast Reroute, FRR）的技术感到非常兴奋——它使用MPLS在链路故障后将数据包绕道传输，而不需要等待路由收敛。
与此同时，负责路由协议开发的同事们正在努力改进路由收敛时间。事实证明，对于MPLS和标准路由来说，最重要的一件事就是更快地检测故障。
例如，如果你需要等待几十秒的OSPF Hello包丢失才能声明链路断开，那么你是否能在几分之一秒内计算出最短路径就不重要了。这正是创建BFD（双向转发检测）的原因：一种独立于路由的快速机制，可以检测任何类型链路的故障。
除了快速故障检测，影响路由收敛的其他因素还包括：
- 通过链路发送新的链路状态包的时间和网络传播延迟
- 接收这样的包并将其分派给操作系统中正确进程的时间
- SPF计算时间
- 更新路由信息库（RIB）的时间
- 计算对转发表影响的时间
- 将转发表更新推送到线卡的时间（在有这种东西的大型路由器上）
- 将链路状态包泛洪给邻居的时间
所有这些步骤多年来都经过了分析和优化，以至于亚秒级路由收敛现在已经成为常态。早在2003年，上述所有步骤的改进就已经实现了亚秒级收敛，正如这个NANOG演讲所示。
是的，如果你想快速收敛，你不能花10秒钟做SPF计算，但那时这已经是一个解决的问题了。优化所有其他部分与改进SPF计算时间同样重要。
为什么Dijkstra仍然是首选？
最后，我和另一位同事聊到这个话题，他提醒我Dijkstra算法仍然是首选实现方法的一个原因：它能够被必须编写代码的人理解。
Dijkstra本人在2001年的一次采访中说得很精彩：
这篇论文现在仍然可读，事实上，它相当不错。它之所以如此不错的原因之一是我在设计它时没有用纸笔。我后来学到，不用纸笔设计的一个好处是你几乎被迫避免所有可避免的复杂性。
换句话说，保持简单，傻瓜（KISS原则）。
我当然更愿意让工程师去读OSPF规范，而不是让他们去理解那种可能只能把非瓶颈部分的路由收敛时间减少几毫秒的混合Bellman-Ford/Dijkstra方法。
也许有一天，会有人写出和新颖SPF方法一样清晰的解释，就像Dijkstra的论文和OSPF规范那样。这种混合算法可能非常适合大型地图应用。但我不认为Dijkstra算法会在不久的将来被生产路由器取代。
小结
这篇文章讨论了一个有趣的话题：理论突破 vs 工程实践。
Dijkstra算法自1959年以来一直屹立不倒，不仅因为它的理论优雅，更因为：
- 足够好用：在实际的网络规模下，它的性能完全可以接受
- 简单可理解：工程师能够理解和正确实现它
- 整个系统优化：路由收敛是一个系统工程问题，SPF计算只是其中一环
这让我想起了计算机科学中的许多类似情况：理论上的最优解不一定是最实用的选择。工程实践中，简单性、可理解性和”足够好”往往比理论最优更重要。
新算法可能在大规模地图应用等领域找到用武之地，但在生产路由器领域，Dijkstra算法的地位短期内恐怕难以撼动。这也是对”过早优化”这一经典建议的又一次印证。