Readings for Lecture Sep 23, 2008

Scaling Internet Routers Using Optics

The Internet is widely reported to have a glut of capacity with average link utilization below 10% and a large fraction of installed but unused link capacity. Thus, the capacity of routers should grow since the demand for network capacity continues to double every year while doubling the number of router each year is impractical.

Current multi-rack systems suffer from unpredictable performance and poor scalability. This causes problems to operators since they do not know what utilization they should apply to their routers then they cannot full exploit their long-haul links. The paper explains how they can use optics with almost zero power consumption to design architectures with predictable throughput and scalable capacity.

The load-balanced switch consists of a single stage buffer sandwiched by two identical switching stages. The buffer at each intermediate input is partitioned into N separate FIFO queues, one per output, hence called Virtual Output Queue (VOQ). There are total N x N such queues. Both the switching stages walk through a fixed sequence of configuration.

The sequence of the switch configurations is pre-determined regardless of the traffic or the state of the queues. The load-balanced switch has 100% throughput even for non-uniform traffic. The two switches at rate R/N then can be replaced by a single switch running twice as fast. The Full Order Frames First (FOFF) can be used to bound the number of mis-sequenced packets in the switch to at most N^2 + 2.

This router architecture, which can guarantee throughput, can be useful to design routers for real-time Internet protocols.

A Fast Switched Backplane for a Gigabit Switched Router

Router functions can be separated in two types Datapath functions often implemented in
hardware and Control functions often implemented in software. There are three trends in designing high performance routers: 1) Datapath is implemented more in hardware; 2) Parallelism is employed more; 3) The most important one is the trend to more away from shared buses since buses are shared between multiple functions can be congested.

Early routers built around conventional computer architecture with a shared central bus, a
central CPU, memory and line cards have the main limitation is that the central CPU has to process every packet, thus limiting the throughput of the system. The improved architecture with multiple CPUs with local forward decision, however, is still limited since the forward decisions is made in software can be outperformed by careful design ASIC in forwarding decisions, managing queues and arbitrating access to the bus. The shared bus in this architecture could be the second limiting factor since one packet can traverse the bus at a time.

By replacing local CPUs with hardware forwarding engines on line card and replacing the bus with a crossbar switch can solve the problem. The performance is further boosted using multiple crossbar switches or slices in parallel to form a switch core. The packet length is chosen to be fixed so the ease and efficiency in design. The head of line blocking problem is fixed by using virtual output queueing (VOQ).

The scheduling algorithm has to satisfy the following properties: high throughput, starvation free, fast, and simple to implement. The iSLIP algorithm is chosen. The priority packet-scheduling scheme can make this architecture suitable for the RSVP protocol.