Improved Smoothed Round Robin Schedulers for High-Speed Packet Networks

  • Chuanxiong Guo

IEEE Infocom |

Published by IEEE Communications Society

Smoothed Round Robin (SRR) packet scheduler is attractive to high-speed networks due to its very low time complexity, but it is not suitable for real-time applications since it cannot provide tight delay bound. In this paper, we present two improvements of SRR, namely SRR^+ and SRR^#, which are based on novel matrix transform techniques. By transforming the irregular Weight Matrix of SRR into triangular and diagonal ones, SRR^+ and SRR^# are able to interleave the flows evenly according to their reserved rates even for skewed weight distributions. SRR^+ and SRR^# provide bounded delay, whereas are still of low space and time complexities and are simple to implement in high-speed networks. The properties of SRR^+ and SRR^# are addressed in detail by analysis and simulations. SRR^+ and SRR^#, together with SRR and the recently developed G-3 scheduler form a full spectrum of schedulers that provide tradeoffs among delay, space complexity, and time complexity.