The inherent queuing delay of parallel packet switches

David Hay, Hagit Attiya
IFIP Conference on Theoretical Computer Science (TCS),
Conferences & Workshops
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×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       = {Hagit Attiya and
                  David Hay},
  editor       = {Jean{-}Jacques L{\'{e}}vy and
                  Ernst W. Mayr and
                  John C. Mitchell},
  title        = {The Inherent Queuing Delay of Parallel Packet Switches},
  booktitle    = {Exploring New Frontiers of Theoretical Informatics, {IFIP} 18th World
                  Computer Congress, {TC1} 3rd International Conference on Theoretical
                  Computer Science (TCS2004), 22-27 August 2004, Toulouse, France},
  series       = {{IFIP}},
  volume       = {155},
  pages        = {139--152},
  publisher    = {Kluwer/Springer},
  year         = {2004},
  url          = {\_13},
  doi          = {10.1007/1-4020-8141-3\_13},
  timestamp    = {Fri, 27 Sep 2019 10:35:17 +0200},
  biburl       = {},
  bibsource    = {dblp computer science bibliography,}