Switched backplane with centralized scheduler

Nick McKeown, "Fast Switched Backplane for a Gigabit Switched Router"

Basic Observations:

• A router has to forward traffic from every port to every other port
• The total traffic is the product of the traffic at one port times the number of ports N
  
• A structure where all traffic is going through one central structure has to fail because it has to be so much faster
• A N-to-N connection scheme can be used so that the speed needed at each N-to-N crosspoint doesn't exceed the speed of a port
• Because the number of N-to-N crosspoints is O(N^2), these crosspoints have to be cheap, i.e. they cannot do routing decisions, should be only on-off-switches which are on a scheduling scheme, this is called "crossbar"
• Scheduler closes N of the N^2 crosspoints at a time, so we have maximal throughput
  

Basic concepts:

• 1 Line card per port, backplane connecting all line cards
  
• Components: forwarding decision (next-hop MAC, TTL decrement, IP checksum), backplane (forward to output linecard, queue or drop packets), output link scheduling (FIFO or QoS scheduling)
• dataplane (per packet) versus control plane
• specific hardware (ASIC) for dataplane
• parallelism
• shared versus switched backplane
• fixed packet length through splitting into fixed size chunks (cells, around 64Bytes)

Problems with switched backplanes:

• head-of line (packet in line card has to wait until the crossbar switched to the right output) is solved by queues (one per output) between line card and crossbar, queues are called virtual ouput queues (VOQ)
  
• input and output blocking (e.g. several line cards want to use the same output), cause delay, need prioritization or speed-up for QoS
  

Scheduling algorithm:

• Goals: high throughput, starvation free, fast, simple to implement
• iSLIP is iterative 3-step algorithm, underlying is a fixed round-robin priority scheme, the algorithm matches input to outputs to fullfill those requests with highest priority

Other features:

• Unicast and multicast support
• QoS

Scale (as of 1997):

• CISCO 12000 had 16 2.4Gb/s ports
• maximal shared bus capacity 20Gb/s
• forwarding decision (Ip prefix lookup, ...) can be done in 2ns
• scheduler reconfigures crossbar every 40ns