Head-of-line blocking

An EthernetSwitch connects a number N of input ports to a number M of output ports (usually N = M) by some sort of SwitchingFabric. Arriving packets need to be buffered somewhere in the system when there is contention until they can be transmitted on the desired output ports. In a typical design, these buffers are located at the input ports. Head-of-line blocking occurs when these buffers are implemented as FIFOs and packets from different input queues are destined for the same output port


The process that removes packets from the input queue and feeds them into the switching fabric during a working cycle of the switch (called the arbiter, which must run at N times the input rate) can only select one of these queues. Due to the nature of a FIFO, the packets at the head of the other queues effectively block the packets behind them even if there is enough capacity to switch them onto their (uncongested) output ports. This effect limits the throughput of the switch to 58% of its capacity when the input traffic is randomly distributed.

Head-of-line blocking can be avoided, for example, by placing the buffers at the output ports or using shared memory rather than FIFOs for the input buffers. However, shared memory is expensive and buffering at the output requires the SwitchingFabric to run at M times the output rate. Therefore, cheap devices usually don't have these features.


-- AlexGall - 05 Sep 2007

Edit | Attach | Watch | Print version | History: r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r2 - 2007-09-05 - AlexGall
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2004-2009 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.