HN825: Faster Than Dijkstra? Exploring a New Shortest-Path Algorithm with Bruce Davie
Bruce Davie joins Heavy Networking to discuss a new shortest-path algorithm claimed to be faster than Dijkstra's, which has been foundational to link-state routing protocols since 1959. While the academic breakthrough is legitimate, Davie argues it has negligible practical impact on network routing because the SPF calculation represents only a tiny fraction of total convergence time. The real bottlenecks are failure detection, packet propagation at the speed of light, and forwarding table updates.
Summary
The episode begins with host Ethan Banks introducing Bruce Davie, a veteran networking engineer who worked at Bellcore, Cisco (where he helped develop MPLS), Nicira, and VMware, and now runs Systems Approach, a nonprofit educational organization co-founded with Larry Peterson that publishes open-source networking textbooks.
Davie was motivated to write about a new shortest-path algorithm after a Quanta Magazine article drew attention to academic research presented at the ACM STOC conference, which reportedly won best paper. The research claims to have found an algorithm asymptotically faster than Dijkstra's for computing shortest paths in graphs.
The hosts walk through Dijkstra's algorithm in detail: routers flood link-state advertisements containing direct neighbor costs, then each router builds a confirmed list and tentative list, iteratively moving the lowest-cost node from tentative to confirmed while updating neighbor costs. This sorting operation — finding the minimum-cost node on the tentative list — is a core computational step with a theoretical complexity of approximately O(n log n).
The new algorithm reportedly eliminates the sorting requirement by incorporating elements of Bellman-Ford and working through node neighborhoods differently, achieving complexity closer to O(m log^(2/3) n). However, Davie is candid that the theoretical details exceed his expertise.
The central argument of the episode is that even if the new algorithm is faster, it doesn't meaningfully improve real-world routing convergence. Davie references a 2003 Cisco presentation by Fellow Clarence Filsfils that decomposed all the steps in convergence: physical failure detection, generating and transmitting link-state packets, flooding across the network at the speed of light, OS dispatch, SPF calculation, forwarding table generation, and hardware table updates. The SPF calculation itself already runs in milliseconds on modern hardware and represents a small fraction of total convergence time.
Davie highlights that the biggest historical improvement came from fast failure detection via BFD (Bidirectional Forwarding Detection), which replaced slow hello-based detection that could take 30 seconds. MPLS Fast Reroute and segment routing-based local protection further reduced convergence to near-detection-time by making local rerouting decisions without requiring network-wide propagation.
Additionally, Davie raises the asymptotic complexity caveat: a new algorithm being faster for very large N doesn't mean it's faster for practical routing topologies of thousands of nodes, especially when constant factors are unknown. The existing Dijkstra implementation is also decades-hardened, well-understood, and relatively simple to implement correctly — qualities the new algorithm lacks.
Davie suggests the new algorithm may find practical use in domains requiring millions of nodes, such as mapping, chip layout, or other graph problems — but not in routing protocols. The episode closes with discussion of Systems Approach's ongoing work on the seventh edition of their textbook and their mission to make networking education freely accessible globally.
Key Insights
- Davie argues that even though the new algorithm is a legitimate academic breakthrough that won best paper at STOC, its practical impact on network routing is negligible because the SPF calculation already runs in milliseconds on modern hardware.
- Davie points out that Dijkstra's algorithm has persisted for decades in part because of its implementation simplicity — it's simple enough that coders can read the OSPF RFC and correctly implement it, reducing the risk of corner-case bugs.
- Davie contends that the biggest historical improvement to routing convergence was not a faster SPF algorithm but the introduction of BFD (Bidirectional Forwarding Detection), which replaced slow hello-based failure detection that could take up to 30 seconds.
- Davie references a 2003 Cisco analysis by Clarence Filsfils showing that convergence time is distributed across many steps — failure detection, packet generation, flooding, OS dispatch, SPF calculation, FIB generation, and hardware table updates — and optimizing only the SPF step yields diminishing returns.
- Davie argues that speed-of-light propagation across wide-area networks represents a fundamental, irreducible limit to convergence time that cannot be improved by any algorithmic optimization.
- Davie suggests that MPLS Fast Reroute and segment routing local protection achieve faster convergence than any SPF improvement because they enable purely local rerouting decisions that avoid the need to propagate topology changes network-wide.
- Davie notes that asymptotic complexity improvements only matter at very large values of N, and that routing topologies of thousands of nodes likely fall in the regime where constant factors dominate, making the new algorithm's theoretical advantage practically irrelevant.
- Davie suggests the new shortest-path algorithm is more likely to find practical applications in domains like geographic mapping or chip layout design, where graph sizes reach millions of nodes, rather than in network routing protocols.
Topics
Full transcript available for MurmurCast members
Sign Up to Access