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