Dijkstra’s algorithm won’t be replaced in production routers • The Register

Methods Method Final yr a few individuals forwarded to me the identical article on a new method of finding shortest paths in networks.

The underlying research claims to enhance on the basic method pioneered by Dijkstra that’s taught in most networking textbooks (together with ours). I used to be initially a bit skeptical, a lot as I’d be if I learn that the Riemann Hypothesis had been proved.

Dijkstra is a legend in pc science and his algorithm, which he printed in 1959, predates packet switching by a couple of years. The specification for OSPF (Open Shortest Path First (OSPF), one in every of two dominant link-state routing protocols (Intermediate System-to-Intermediate System, aka IS-IS, is the opposite).

Steerage to implementors of OSPF is unusually detailed and principally tells them to make use of Dijkstra’s algorithm. And that’s what most implementations have accomplished for many years, with a couple of minor enhancements by the years to hurry up the implementation however no actual change to the basics.

The brand new algorithm is not any minor tweak to Dijkstra’s however a considerably totally different method. Its headline declare is that, whereas Dijkstra requires a sorting operation, and thus is barely in a position to carry out in addition to the perfect sorting algorithm, this new method “breaks the sorting barrier”. That’s, it avoids the necessity for sorting and is ready to ship higher bounds on efficiency than Dijkstra.

Whereas I don’t take into account myself certified to guage the paper that describes the brand new algorithm, it has handed peer-review at a top-tier convention (ACM Symposium on the Theory of Computing) and acquired sufficient scrutiny that I don’t doubt that the idea works. The query I wish to focus on right here is: does it matter?

Two major points got here instantly to thoughts once I tried to evaluate the implications of a theoretical enchancment in algorithmic efficiency. The primary is, what are the precise scaling limits that we have to tackle in an actual routing system. For instance, the working time of Dijkstra’s algorithm is on the order of (n log n + m) for a community of n vertices (routers) and m edges (hyperlinks). The brand new method claims order  (m log^2/3 n) which is clearly going to be much less for giant sufficient n. (I needed to take a refresher course on log notation earlier than I might even write that sentence with any confidence.) The issue with assessing the scaling properties of something is it’s a must to surprise how large n should get earlier than it makes a distinction. There are fixed components that may differ between the 2 approaches; at small n, a “much less scalable” method may really show higher efficiency.

What scaling restrict?

One among my first jobs was a part of the workforce constructing a scalable packet switch primarily based on arrays of small switching components. (That is the place I bought to construct the accidental SmartNIC). We had papers to indicate that we might construct switches with hundreds of ports at 155 Mbps, in an period when shared Ethernet ran at 10 Mbps and had not but been overtaken by switched Ethernet.

Whereas we at Bellcore have been investing numerous money and time to place collectively a set of 32-port prototype switches, FORE systems delivered commercially profitable 16-port switches.  Nearly definitely they weren’t as scalable as our design, however it turned out that n=16 was a reasonably helpful capability for switches with 155 Mbps hyperlinks within the Nineteen Nineties. We felt fairly unhappy that our analysis appeared to have been overtaken by industrial merchandise. My takeaway was that scalability was factor to try for however that typically you may obtain outcome with a much less scalable resolution. One among my favourite textual content books, “Principles of Computer Systems Design”, makes use of the instance of stopping a supertanker to show the scaling limits of a system. The truth that supertankers have a scaling restrict doesn’t forestall them from being the spine of oil transport. You simply must keep away from making them too large.

What’s a big worth for n in SPF calculations? I checked in with a few colleagues to replace my recollection of what number of routers you may discover in a giant OSPF or IS-IS spine. In my reminiscence it was within the tons of; for the biggest service supplier networks right now it appears to be within the small variety of hundreds. In order that’s not tiny however it’s small in comparison with, say, the variety of prefixes carried in BGP.

And it doesn’t appear to be restricted by the efficiency of the SPF calculation, as I’ll clarify beneath.

The numerous sides of efficiency

One other reminiscence I’ve from my time working for Huge Router was an evaluation of all of the issues that go into the efficiency of routing protocols. I used to be engaged on MPLS in its early days, and we have been fairly excited a couple of know-how known as “quick reroute” (FRR) which makes use of MPLS to divert packets round a failed hyperlink with out ready for routing to converge after the failure. However on the similar time, the individuals accountable for routing protocol growth have been onerous at work bettering routing convergence instances. Some of the vital issues, it seems, for each MPLS and customary routing, was merely detecting failure sooner. For instance, if it’s a must to look forward to tens of seconds of lacking OSPF Hiya packets earlier than you declare a hyperlink down, it doesn’t actually matter if you happen to can calculate the shortest path in a fraction of a second. This was the reasoning behind the creation of BFD (Bidirectional Forwarding Detection): a quick mechanism, unbiased of routing, by which hyperlink failures might be detected for any sort of hyperlink.

Past quick failure detection, different components taking part in into routing convergence embody: the time to ship a brand new hyperlink state packet out a hyperlink and propagation delay throughout the community; time to obtain such a packet and dispatch it to the best course of within the working system; SPF time; time to replace the routing info base; time to calculate the influence on the forwarding desk; time to push any forwarding desk updates out to the road playing cards (on large routers which have such issues); time to flood the hyperlink state packet out to neighbors. All of those steps have been analyzed and optimized through the years, to the purpose the place sub-second routing convergence is now routine. As early as 2003 the enhancements to all of the steps above had enabled sub-second convergence, as this NANOG presentation exhibits. Sure, you couldn’t afford to spend 10 seconds doing an SPF calculation if you happen to wished quick convergence, however that was already a solved challenge by then. Optimizing all the opposite components was not less than as vital as bettering the SPF calculation time.

Lastly, I chatted with one other colleague about this subject and he jogged my memory of a purpose that Dijkstra’s algorithm stays the implementation methodology of alternative: it may be understood by the individuals who have to put in writing code. Dijkstra himself places it properly in a 2001 interview:

In different phrases, Keep It Simple, Stupid. I will surely slightly level an engineer on the OSPF spec than ship them off to know the hybrid Bellman-Ford/Dijkstra method that may shave a couple of milliseconds off the non-bottleneck a part of routing convergence. Possibly at some point somebody will write the reason of the novel SPF method that’s as clear as Dijkstra’s paper and the OSPF spec. And the hybrid algorithm could be nice for giant mapping purposes. However I don’t see Dijkstra’s algorithm being changed in manufacturing routers any time quickly. ®

Larry Peterson and Bruce Davie are the authors behind Computer Networks: A Systems Approach and the associated Systems Approach sequence of books. All their content material is open supply and out there free of charge on GitHub. Yow will discover them on Mastodon, their e-newsletter right here, and previous The Register columns here.