Faster Than Dijkstra?
A new shortest path algorithm boasts theoretical asymptotic improvements over Dijkstra's, promising to "break the sorting barrier." This post critically examines whether such theoretical gains translate to practical advantages in real-world network routing, arguing that other system-level bottlenecks and implementation complexity often outweigh marginal algorithmic speedups. Hacker News debates the eternal tension between elegant mathematical theory and messy, practical engineering constraints.
The Lowdown
Bruce Davie, a seasoned networking expert, scrutinizes a recently published shortest path algorithm that purports to be "faster than Dijkstra" by sidestepping the sorting bottleneck inherent in classical approaches. While acknowledging the algorithm's academic rigor and peer validation, Davie pivots to question its tangible impact on production network routing.
- Theoretical vs. Practical Speed: The new algorithm offers superior asymptotic complexity (O(m log^(2/3) n) compared to Dijkstra's O(n log n + m)). However, Davie posits that for typical network sizes (a few thousand nodes), the 'n' may not be large enough for these theoretical gains to manifest, with constant factors potentially making Dijkstra more efficient.
- Beyond SPF: The Real Bottlenecks: The article highlights that SPF calculation time is merely one piece of the routing convergence puzzle. Other crucial factors, such as rapid failure detection (e.g., BFD), propagation delays, operating system overhead, and forwarding table updates, are often the dominant bottlenecks, many of which have already been highly optimized to achieve sub-second convergence.
- Simplicity Trumps Complexity: Dijkstra's algorithm, enshrined in specifications like OSPF, is valued for its understandability and ease of implementation. Davie argues that introducing a more complex "hybrid Bellman-Ford/Dijkstra" approach for minimal real-world performance gain in an already non-bottlenecked area would be counterproductive, increasing maintenance burden without significant benefit.
In essence, Davie concludes that while this new algorithm represents a fascinating theoretical advance, Dijkstra's enduring simplicity, coupled with the optimization of other critical routing components, means it's unlikely to be unseated from production routers anytime soon. Its true utility might lie in different domains, such as large-scale mapping applications.
The Gossip
Algorithmic Applicability Quandaries
Commenters extensively debated the practical utility of the new algorithm versus Dijkstra's. Many echoed the author's sentiment that theoretical improvements often fail to translate to real-world networking benefits, especially when graph sparsity assumptions or constant factors are considered. Others, however, felt the author's critique missed the point of a purely mathematical advancement.
Sorting's Shifting Semantics
The article's reference to "breaking the sorting barrier" sparked a deep dive into the definition and boundaries of sorting algorithms. Discussions ranged from the conditions under which O(N) sorting is possible (e.g., specific data types, finite alphabets, transdichotomous models) to broader philosophical points about how computational models influence complexity analysis, especially concerning the inherent O(N log N) lower bound for comparison sorts.
Critiques and Compliments on Commentary
Users offered varied opinions on the author's approach and writing style. Some found the article insightful, appreciating the musing on practical engineering trade-offs. Conversely, others criticized what they perceived as a dismissive tone towards theoretical computer science, suggesting the author spent insufficient effort evaluating the new algorithm before critiquing its real-world relevance.