Cooperative Token-Ring Scheduling For Input-Queued Switches

We present a novel distributed scheduling paradigm for Internet routers with input-queued (IQ) switches, called cooperative token-ring (CTR) that provides significant performance improvement over existing scheduling schemes with comparable complexity. Many classical schedulers for IQ switches employ round-robin arbiters, which can be viewed as non-cooperative token-rings, where a separate token is used to resolve contention for each shared resource (e.g., an output port) and each input port acquires a token oblivious of the state of other input ports. Although classical round-robin scheduling schemes achieve fairness and high throughput for uniform traffic, under non-uniform traffic the performance degrades significantly. We show that by using a simple cooperative mechanism between the otherwise non-cooperative arbiters, the performance can be significantly improved. The CTR scheduler dynamically adapts to non-uniform traffic patterns and achieves essentially 100% throughput. The proposed cooperative mechanism is conceptually simple and is supported by experimental results. To provide adequate support for rate guarantees in IQ switches, we present a weighted cooperative token-ring, a simple hierarchical scheduling mechanism. Finally, we analyze the hardware complexity introduced by the cooperative mechanism and describe an optimal hardware implementation for an N times N switch with time complexity of Theta(log N) and circuit size of Theta(N log N) per port.