Last year a couple of people forwarded to me the same article on a new method of finding shortest paths in networks. The underlying research claims to improve on the classic approach pioneered by Dijkstra that is taught in most networking textbooks (including ours). I was initially a bit skeptical, much as I would be if I read that the Riemann Hypothesis had been proved. Dijkstra is a legend in computer science and his algorithm, which he published in 1959, predates packet switching by a few years. The specification for OSPF, one of two dominant link-state routing protocols (IS-IS is the other), is unusually detailed in its guidance to implementors, and it basically tells them to use Dijkstra’s algorithm. And that is what most implementations have done for decades, with a few minor improvements through the years to speed up the implementation but no real change to the fundamentals.
The new algorithm is no minor tweak to Dijkstra’s but a significantly different approach. Its headline claim is that, whereas Dijkstra requires a sorting operation, and thus is only able to perform as well as the best sorting algorithm, this new approach “breaks the sorting barrier”. That is, it avoids the need for sorting, and is able to deliver better bounds on performance than Dijkstra.
While I don’t consider myself qualified to evaluate the paper that describes the new algorithm, it has passed peer-review at a top-tier conference (ACM Symposium on the Theory of Computing) and received enough scrutiny that I don’t doubt that the theory works. The question I want to discuss here is: does it matter?
Two main issues came immediately to mind when I tried to assess the implications of a theoretical improvement in algorithmic performance. The first is, what are the actual scaling limits that we need to address in a real routing system. For example, the running time of Dijkstra’s algorithm is on the order of (n log n + m) for a network of n vertices (routers) and m edges (links). The new approach claims order (m log2/3 n) which is clearly going to be less for large enough n. (I had to take a refresher course on log notation before I could even write that sentence with any confidence.) The problem with assessing the scaling properties of anything is you have to wonder how big n must get before it makes a difference. There are constant factors that might differ between the two approaches; at small n, a “less scalable” approach might actually display better performance.
What scaling limit?
One of my first jobs was part of the team building a scalable packet switch based on arrays of small switching elements. (This is where I got to build the accidental SmartNIC). We had papers to show that we could build switches with thousands of ports at 155 Mbps, in an era when shared Ethernet ran at 10 Mbps and had not yet been overtaken by switched Ethernet. While we at Bellcore were investing lots of time and money to put together a set of 32-port prototype switches, FORE systems delivered commercially successful 16-port switches. Almost certainly they were not as scalable as our design, but it turned out that n=16 was a pretty useful capacity for switches with 155 Mbps links in the 1990s. We felt quite sad that our research seemed to have been overtaken by commercial products. My takeaway was that scalability was a good thing to strive for but that sometimes you might achieve a good result with a less scalable solution. One of my favorite text books, “Principles of Computer Systems Design”, uses the example of stopping a supertanker to demonstrate the scaling limits of a system. The fact that supertankers have a scaling limit doesn’t prevent them from being the backbone of oil shipping. You just need to avoid making them too big.
What’s a large value for n in SPF calculations? I checked in with a couple of colleagues to update my recollection of how many routers you might find in a big OSPF or IS-IS backbone. In my memory it was in the hundreds; for the largest service provider networks today it seems to be in the small number of thousands. So that’s not tiny but it’s small compared to, say, the number of prefixes carried in BGP.
And it doesn’t seem to be limited by the performance of the SPF calculation, as I will explain below.
The many facets of performance
Another memory I have from my time working for Big Router was an analysis of all the things that go into the performance of routing protocols. I was working on MPLS in its early days, and we were pretty excited about a technology called “fast reroute” (FRR) which uses MPLS to divert packets around a failed link without waiting for routing to converge after the failure. But at the same time, the people responsible for routing protocol development were hard at work improving routing convergence times. One of the most important things, it turns out, for both MPLS and standard routing, was simply detecting failure faster. For example, if you have to wait for tens of seconds of missing OSPF Hello packets before you declare a link down, it doesn’t really matter if you can calculate the shortest path in a fraction of a second. This was the reasoning behind the creation of BFD (Bidirectional Forwarding Detection): a fast mechanism, independent of routing, by which link failures could be detected for any type of link.
... continue reading