Conventional Wisdom of Routing

System design involves tradeoffs, and there is a natural tendency for improvements to be incremental instead of revolutionary. Although it's true that radical changes are often more difficult to implement, it's important to have people who challenge the conventional wisdom. I recently read ROFL: Routing on Flat Labels, which proposes a peer-to-peer-inspired routing architecture. Instead of merely separating location from identity, the paper explores a routing algorithm where location is completely unnecessary. The authors modestly write of ROFL, "While its scaling and efficiency properties are far from ideal, our results suggest that the idea of routing on flat labels cannot be immediately dismissed." In fact, the authors' preliminary algorithm has an attractive scalable design, and its performance seems acceptable given its benefits.

ROFL basically casts the Internet as a big hierarchical DHT. Since there is no lower network layer on which to overlay the DHT, each system keeps a cache of source routes which are sufficient to ensure that every host is reachable. Each packet contains a source route to a host whose ID does not exceed the ID of the destination. Each router, if possible, replaces this route with a new source route to a host whose ID is closer to the destination ID. In the spirit of DHTs, routers keep "fingers" (in this cased, memorized source routes) to routers that are physically nearby but logically distant on the ring.

At first glance, this sounds inefficient: routers blindly send packets based on the structure of the ring, which is completely unrelated to the structure of the network. However, as the cache sizes increase, the stretch approaches 1 (stretch is the worst case ratio of actual path length to optimal path length). Of course, if ROFL needs huge caches to get good performance, then it doesn't seem to be much of an improvement over BGP's huge routing tables, but there is an important difference: BGP needs huge tables to work, ROFL uses huge caches as an optimization. In other words, some routers can have large caches while others have small caches, and the algorithm will still work.

The one thing ROFL needs is a really good animation that shows how it works and the effect of caching on performance. In any case, after reading the paper, thinking about the algorithm, and trying to understand the results section, I am convinced that ROFL is worth exploring. It might be difficult to implement in an IP world, but it is a refreshingly novel approach.