Improved Smoothed Round Robin Schedulers for High-Speed Packet Networks

Smoothed Round Robin (SRR) \cite{GuoSRR} 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 \cite{guo07} form a full spectrum of schedulers that provide tradeoffs among delay, space complexity, and time complexity.

PDF file

In  IEEE Infocom

Publisher  IEEE Communications Society
Copyright © 2007 IEEE. Reprinted from IEEE Communications Society. This material is posted here with permission of the IEEE. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to By choosing to view this document, you agree to all provisions of the copyright laws protecting it.


> Publications > Improved Smoothed Round Robin Schedulers for High-Speed Packet Networks