In this paper, we present an O(1) time-complexity packet scheduling algorithm which we call G-3 that provides bounded end-to-end delay for fixed size packet networks. G-3 is built over two round-robin schedulers SRR [10] and RRR [7] and several novel data structures. In G-3, bounded delay is provided by evenly distributing the binary coded weight of a flow into a Square Weight Matrix (SWM) and several Perfect Weighted Binary Trees (PWBTs). In order to achieve O(1) time complexity, the SWM matrix is further spread by a Weight Spread Sequence (WSS) and each PWBT tree is spread by a corresponding Time-Slot Sequence (TSS), respectively. G-3 then performs packet scheduling by sequential scanning the WSS and TSS sequences. G-3 can be implemented in high-speed packet networks to provide bandwidth guarantee, fairness, and bounded delay due to its O(1) time complexity.

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