THE INHERENT QUEUING DELAY OF PARALLEL PACKET SWITCHES (Extended Abstract)
Hagit Attiya, David A. Hay · 2004
The parallel packet switch (PPS) is extensively used as the core of con- temporary commercial switches. This paper investigates the inherent queuing delay and delay jitter introduced by the PPS's demultiplexing algorithm, relative to an optimal work-conserving switch. We show that the inherent queuing delay and delay jitter of a sym- metric and fault-tolerant N N PPS, where every demultiplexing algo- rithm dispatches cells to all the middle-stage switches is ( N), if there are no buers in the PPS input-ports. If the demultiplexing algorithms dispatch cells only to part of the middle-stage switches, the queuing delay and delay jitter are ( N=S), where S is the PPS speedup. These lower bounds hold unless the demultiplexing algorithm has full and im- mediate knowledge of the switch status. When the PPS has buers in its input-ports, an ( N=S) lower bound holds if the demultiplexing algo- rithm uses only local information, or the input buers are small relative to the time an input-port needs to learn the switch global information.