Weighted random matching: a simple scheduling algorithm for achieving 100% throughput

Input-queuing is preferred to output-queuing in high-speed switches because it can be implemented with slower memories. Existing schedulers for input-queued switches that achieve 100% throughput without any speedup have extremely high time complexity and require significant hardware. It is known that a scheduler using maximal matches achieves 100% throughput with a speedup of 2. However, computing even maximal matches at line-speed is nontrivial. Most existing scheduling algorithms for input-queued switches require variable sized packets to be segmented into fixed size cells leading to significant overhead in both bandwidth and hardware. We present an extremely simple randomized algorithm, weighted random matching, for scheduling variable length packets in an input-queued switch. The amount of work that our scheduler does is less than a single iteration of parallel iterative matching (PIM). We show that our algorithm is guaranteed to achieve 100% throughput under any admissible traffic, with a speedup of 2.