Randomization does not reduce the average delay in parallel packet switches

David Hay, Hagit Attiya
Conferences & Workshops
Switch and router design


Switching cells in parallel is a common approach to build switches with very high external line rate and a large number of ports. A prime example is the parallel packet switch (in short, PPS) in which a demultiplexing algorithm sends cells, arriving at rate R on N input-ports, through one of K intermediate slower switches, operating at rate r<R.This paper presents lower bounds on the average queuing delay introduced by the PPS relative to an optimal work-conserving FCFS switch, for demultiplexing algorithms that does not have full and immediate information about the switch status. The bounds hold even if the algorithm is randomized.These lower bounds are shown to be asymptotically optimal through a new methodology for analyzing the maximal relative queuing delay; this clearly upper bounds their average relative queuing delay. The methodology is used to devise a new algorithm that relies on slightly out-dated global information on the switch status. It is also used to provide, for the first time, a complete proof of the maximum relative queuing delay provided by the fractional traffic dispatch [19, 22] algorithm.

author = {Attiya, Hagit and Hay, David},
title = {Randomization Does Not Reduce the Average Delay in Parallel Packet Switches},
year = {2005},
isbn = {1581139861},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1073970.1073973},
doi = {10.1145/1073970.1073973},