Abstract :
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 (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 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.
Keywords :
communication complexity; delays; matrix algebra; packet radio networks; scheduling; spread spectrum communication; trees (mathematics); G-3 packet scheduling; bounded end-to-end delay; fixed size packet network; perfect weighted binary trees; round-robin scheduling; square weight matrix; time complexity; time-slot sequence; weight spread sequence; Bandwidth; Binary trees; Communications Society; Data structures; Delay effects; Internet telephony; Processor scheduling; Round robin; Scheduling algorithm; Video sharing;
