SW-EDF: A Single-Iteration Algorithm for Combined Input- and Output-Queued Switching

How to design switches (and routers) that provide quality of service (QoS) guarantees, such as low transit (through the switch) delay for packets, has been a long-standing research problem. Output-queued (OQ) switch architecture is perfect for minimizing this transit delay, but is prohibitively expensive to implement "as is" in hardware. In theory, combined input- and output-queued (CIOQ) switch architecture can fully emulate OQ while requiring only a 2× speedup on the crossbar. In practice, however, one last hurdle remains for CIOQ to be practically implementable despite more than a decade of research: This emulation requires using stable marriages (matchings) as crossbar schedules, and each stable marriage takes Ω(N<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>) parallel iterations (N is the number of input/output ports) to compute in the worst case. The contribution of this work is SW-EDF, a novel parallel iterative switching algorithm (PISA) that overcomes this last hurdle: SW-EDF can compute, in a single low-complexity iteration, an "approximate stable marriage" that allows for near-perfect OQ emulation, in terms of tardy (compared to OQ) rates and distribution of tardiness.