HN825: Faster Than Dijkstra? Exploring a New Shortest-Path Algorithm with Bruce Davie

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.