The inherent queuing delay of parallel packet switches

David Hay, Hagit Attiya
Poster and brief announcement
Switch and router design


The parallel packet switch (PPS) is extensively used as the core of contemporary 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 symmetric and fault-tolerant N x N PPS, where every demultiplexing algorithm dispatches cells to all the middle-stage switches is Ω(N), if there are no buffers 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 immediate knowledge of the switch status. When the PPS has buffers in its input-ports, an Ω(N/S) lower bound holds if the demultiplexing algorithm uses only local information, or the input buffers are small relative to the time an input-port needs to learn the switch global information.

author = {Attiya, Hagit and Hay, David},
title = {The Inherent Queuing Delay of Parallel Packet Switches},
year = {2004},
isbn = {1581138407},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {},
doi = {10.1145/1007912.1007954},
booktitle = {Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures},
pages = {269–270},
numpages = {2},
keywords = {clos networks, packet switching, queuing delay, delay jitter, inverse multiplexing, load balancing, leaky-bucket traffic},
location = {Barcelona, Spain},
series = {SPAA ’04} }