G-3: An O(1) Time Complexity Packet Scheduler That Provides Bounded End-to-End Delay
Chuanxiong Guo · 2007
In this paper, we present anO(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 (Chuanxiong Guo, 2004) and RRR (Garg and Xiaoqiang Chen, 1999) 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 achieveO(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 itsO(1) time complexity.