Stable round-robin scheduling algorithms for high-performance input queued switches
Jing Liu, Hung Chun Kit, Mounir Hamdi, Chi-Ying Tsui · 2003
High-performance input-queued switches require high-speed scheduling algorithms while maintaining good performance. Various round-robin scheduling algorithms for virtual output queuing (VOQ) crossbar-based packet switch architectures have been proposed. It has been demonstrated that they can operate at high speed (e.g., OC192), and are relatively simple to implement in hardware. In particular, a group of fully desynchronized round-robin scheduling algorithms, named SRR (static round robin matching), achieve pretty good delay performance while easy to implement. The main problem with these arbitration algorithms is that they are not stable under non-uniform traffic. In this paper, based on the concept of both randomized algorithms and SRR, we propose a new scheduling algorithm, termed DRDSRR (derandomized rotating double static round-robin), which is shown to be stable under all Bernoulli i.i.d. admissible traffic and performs better than SRR.. In addition, we also propose a novel pipelining scheme for the hardware implementation of these scheduling algorithms which can achieve one more iteration within each cycle time, and hence better performance, when compared with the pipelining schemes used in conventional designs.