Stable and practical scheduling algorithms for high speed virtual output queuing switches

High-performance input queued switches achieve good performance with low cost. However, with the appearance of optical techniques, the line rate is much higher than before. Scheduling algorithms require not only good performance in delay and stability but fast speed and simple implementation as well. A variety of scheduling algorithms for virtual output queuing (VOQ) packet switching architecture are proposed. Round-robin scheduling algorithms are fast and simple to implement in hardware. In particular, a group of fully desynchronized round-robin scheduling algorithms - SRR (static round robin matching), proposed recently, achieve pretty good delay performance while easy to implement. However, they are not stable under non-uniform traffic. Randomized algorithms are stable under any admissible traffic, however, their delay is high and hardware implementation is complex. Based on the concept of randomized algorithms and SRR, we propose a group of new scheduling algorithms, DRDSRR, the improved version of DRDSRR, ARDSRR and the variations of ARDSRR. They not only ensure stability but also have good performance and simple implementation. We have proved stability in the paper.