Stenobird

Episode

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

Podcast
Heavy Networking
Published
May 1, 2026
Duration seconds
3283
Processing state
processed
Canonical source
https://packetpushers.net/podcasts/heavy-networking/hn825-faster-than-dijkstra-exploring-a-new-shortest-path-algorithm-with-bruce-davie/
Audio
https://feeds.packetpushers.net/link/12486/17330395/HN825.mp3
JSON
/v1/public/podcasts/heavy-networking/episodes/hn825-faster-than-dijkstra-exploring-a-new-shortest-path-algorithm-with-bruce-davie
Markdown
/podcast/heavy-networking/hn825-faster-than-dijkstra-exploring-a-new-shortest-path-algorithm-with-bruce-davie.md

Actions

  • POST https://stenobird.com/v1/public/podcasts/heavy-networking/episodes/hn825-faster-than-dijkstra-exploring-a-new-shortest-path-algorithm-with-bruce-davie/transcription-requests
    Idempotently request low-priority transcript generation for this episode.
  • GET https://stenobird.com/podcast/heavy-networking/hn825-faster-than-dijkstra-exploring-a-new-shortest-path-algorithm-with-bruce-davie.md
    Read the agent-friendly Markdown representation of this episode resource.

Summary

Dr. Bruce Davie evaluates whether a new, theoretically faster shortest-path algorithm can realistically replace Dijkstra's algorithm in modern routing. The discussion explores why algorithmic complexity matters less than the systemic delays in failure detection and propagation.

Topics

  • Dijkstra's Algorithm
  • Link State Routing
  • Network Convergence
  • MPLS
  • BFD
  • Network Engineering
  • Algorithm Complexity
  • Systems Approach

Highlights

  • Main idea: Theoretical algorithmic improvements often fail to impact real-world performance due to the overhead of failure detection and packet propagation
  • Practical takeaway: Optimizing the SPF calculation is less impactful than reducing the time it takes to detect a link failure and propagate link-state advertisements
  • Failure mode: Implementing overly complex algorithms increases the risk of unhandled corner cases and implementation bugs in production routers
  • Systemic view: Network convergence is a multi-stage process involving physical layer detection, BFD, LSA flooding, and hardware forwarding table updates
  • Lesson: When evaluating new technologies, determine if the 'juice is worth the squeeze' by looking at the entire system rather than isolated metrics

Chapters

  1. 1:00 Introduction to Dr. Bruce Davie: Dr. Bruce Davie discusses his background in networking, including his work on MPLS at Cisco and his current role at Systems Approach.
  2. 5:00 The Hacker News Debate: A look at the reaction to new shortest-path research and the challenges of presenting complex algorithmic shifts to the community.
  3. 9:05 The Mechanics of Link State Routing: An explanation of how routers calculate the lowest cost path based on throughput and link state packets.
  4. 13:20 The SPF Calculation Process: A deep dive into the tentative and confirmed lists used during the Shortest Path First (SPF) calculation process.
  5. 17:40 The Risks of Algorithmic Complexity: Discussing why simple, proven algorithms like Dijkstra's are preferred over complex alternatives to avoid implementation errors.
  6. 25:55 The Bottleneck: Failure Detection: Why fast failure detection (like BFD) is more critical to convergence than the speed of the underlying path algorithm.
  7. 38:30 Evaluating New Algorithms: Comparing the theoretical benefits of new research against the practical realities of modern router hardware and software.