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

Understand

In an input-queued switch, a crossbar schedule, or a matching between the input ports and the output ports needs to be computed in each switching cycle, or time slot.

• Designing switching algorithms with very low computational complexity, that lead to high throughput and small delay is a challenging problem.
• There appears to be a fundamental tradeoff between the computational complexity of the switching algorithm and the resultants throughput and delay.
• Parallel maximal matching algorithms (adapted for switching) appear to have stricken a sweet spot in this tradeoff, and prior work has shown the following performance guarantees.