Scaling Internet Routers

In two papers from McKeown and others, "A Fast Switched Backplane for a Gigabit Switched Router" and "Scaling Internet Routers Using Optics", the authors explain how router technology can be scaled well beyond its current needs and close to its theoretic limits. One of the papers discusses how to scale routers for gigabit while the other one shows an impressive design for 100 terabit!

McKeown discusses how, in most routers then (circa 1995), datagrams are transmitted out of a first-come-first-served (FIFO) queue (which is crazy considering the numerous router/gateway algorithms that I have discussed in this blog). He does acknowledge "more advanced routers", but does not seem to imply that many of them actually perform many, if any, of the advanced algorithms such as Fair Queuing.

Both sets of authors describe the basic design of the router, including its parallel design, crossbar switch and use of virtual output queuing (VOQ). The VOQ discussion is especially interesting because it shows how traumatic head-of-line blocking can be (nearly 50% of performance).

McKeown describes how VOQ + iSlip (a crossbar scheduling algorithm) can achieve close to the theoretical maximum of performance. They compare this with a crossbar like router but one which uses FIFO (and variable-length datagrams ...). Ironically, when we relate this work to other work discussed on this blog it becomes apparent that none of the gateway algorithms are actually being used ...

Another rather interesting relation between this work and previous work discussed is its attention to "controlling delay". Specifically, to deal with traffic that needs to have low latency they employ two mechanisms: priority levels and speedup (the latter I think is much more fascinating!). Priority levels are what they sound like, but speedup is kind of clever: operate the crossbar switch twice as fast as the external line! That way, with sufficient speedup one could actually guarantee that every datagram is immediately transferred to its output port, where a departure time can be precisely scheduled (which will eliminate the non-determinism inherent in the router otherwise, which screws up ones ability to reason about delay). They go on to discuss how in theory one would need a speedup of N (where N is the number of ports) to actually achieve the guarantee, but how in practice one can actually get away pretty well with a speedup of just two.

Scaling of routers for gigabit was published sometime in the mid '90s (it was actually a description of the work McKeown did at Cisco for the Cisco 12000 router). The later paper (2003) discusses the terabit routing work, and emphasizes the need to use optics versus electornics (at least in some parts). I would be curious to know how necessary terabit routing really is today ...