• Calendar

December 18, Thursday
12:00 – 14:00

The parallel packet switch (PPS), an extension of the inverse multiplexing architecture, is extensively used as the core of contemporary commercial switches. This talk discusses the inherent queuing delay introduced by the PPS's demultiplexing algorithm, responsible for dispatching cells to the middle-stage switches, relative to an output-queued switch. We show that the inherent queuing delay of a symmetric and fault-adaptive PPS without buffers in its input-ports is $\Omega(N)$, where N is the number of external ports. A lower-bound of $\Omega(N/S)$ is proved for an asymmetric PPS, where S is the speedup of the PPS. These lower bounds hold unless the demultiplexing algorithm has full and immediate knowledge of the switch state. Since demultiplexing algorithms with full and immediate knowledge cannot be implemented in real switches, it implies that $\Omega(N/S)$ (and sometimes even $\Omega(N)$) queuing delay is inherent in practical demultiplexing algorithms. When the PPS has buffers in its input-ports, an $\Omega(N/S)$ lower-bound holds if the demultiplexing algorithm has only local information, or the input-buffers are small relative to the time an input-port needs to learn the switch state.

This is joint work with David Hay.