QPS-r: A Cost-Effective Crossbar Scheduling Algorithm and Its Stability and Delay Analysis.

Parallel iterative maximal matching algorithms (adapted for switching) has long been recognized as a cost-effective family for crossbar scheduling. On one hand, they provide the following Quality of Service (QoS) guarantees: Using maximal matchings as crossbar schedules results in at least 50% switch throughput and order-optimal (i.e., independent of the switch size $N$) average delay bounds for various traffic arrival processes. On the other hand, using $N$ processors (one per port), their per-port computational complexity can be as low as $O(\log^2 N)$ (more precisely $O(\log N)$ iterations that each has $O(\log N)$ computational complexity) for an $N\times N$ switch. In this work, we propose QPS-r, a parallel iterative switching algorithm that has the lowest possible computational complexity: $O(1)$ per port. Yet, the matchings that QPS-r computes have the same quality as maximal matchings in the following sense: Using such matchings as crossbar schedules results in exactly the same aforementioned provable throughput and delay guarantees as using maximal matchings, as we show using Lyapunov stability analysis. Although QPS-r builds upon an existing add-on technique called Queue-Proportional Sampling (QPS), we are the first to discover and prove this nice property of such matchings. We also demonstrate that QPS-3 (running 3 iterations) has comparable empirical throughput and delay performances as iSLIP (running $\log_2 N$ iterations), a refined and optimized representative maximal matching algorithm adapted for switching.