QUEUING IN HIGH-PERFORMANCE PACKET SWITCHING

The authors study the performance of four different approaches for providing the queuing necessary to smooth fluctuations in packet arrivals to a high-performance packet switch. They are 1) input queuing, where a separate buffer is provided at each input to the switch; 2) input smoothing, where a frame of b packets is stored at each of the input lines to the switch and simultaneously launched into a switch fabric of size Nb × Nb; 3) output queuing, where packets are queued in a separate first-in first-out (FIFO) buffer located at each output of the switch; and 4) completely shared buffering, where all queuing is done at the outputs and all buffers are completely shared among all the output lines. Input queues saturate at an offered load that depends on the service policy and the number of inputs N, but is approximately 0.586 with FIFO buffers when N is large. At the expense of an increase in the switch fabric size and latency, the lost packet rate for input smoothing can be made small by increasing the frame size b. Output queuing and completely shared buffering both achieve the optimal throughput-delay performance for any packet switch. However, compared to output queuing, completely shared buffering requires less buffer memory at the expense of an increase in switch fabric size.