A Fast Switched Backplane for a Gigabit Switched Router

McKeown presents a series of design decisions to allow high throughput between different ports on a network switch. He points to trends in router design towards more hardware, more parallelism, and fewer shared buses to reduce contention, and so argues that a switched backplane will be best because it reduces contention. His design consists of a star topology where each line card is connected to a single switch. The switch can connect pairs of cards, and so the challenge is to quickly form a matching between enqueued messages and receive buffers which minimizes latency and is fair. The algorithm he proposes is called iSLIP, and consists of multiple rounds of proposals after which the switch can choose a conflict-free match.

He is especially interested in reducing block; HOL (head of line) blocking is particularly problematic. To solve that, he introduces the VOQ, or virtual output queue where each card has multiple output queues, one for each other line card. In this scheme, a packet can never become blocked behind a packed destined for a different port. He also notes that a combination of queuing discipline (in the sense of more VOQs + priorities) has the same effect as more speedup (running the switch at a multiple of the line card speed.

This paper outlines the full design of a small switch; I thought it was an interesting read. The techniques he mentioned are probably still valid today, since a 16-way 2.4 Ghz switch is still a reasonable piece of hardware. It was light on details, and parts were confusing; the frequent note that the Cisco 12000 uses some of the techniques didn't actually contribute to the paper, because he does not go into detail other then the general design of that system.