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 pubs-permissions@ieee.org. By choosing to view this document, you agree to all provisions of the copyright laws protecting it.

Details