Conference Program

Program At A Glance   Tutorials Program  Technical Program  Outrageous Opinions Session  
Social Events

Technical Program

SRR: An 0(1) Time Complexity Packet Scheduler for Flows in Multi-Service Packet Networks Chuanxiong Guo (Institute of Communications Engineering, China)

In this paper, we present a novel fair queueing scheme, which we call Smoothed Round Robin (SRR). Ordinary round robin schedulers are well known for their burstiness in the scheduling output. In order to overcome this problem, SRR codes the weights of the flows into binary vectors to form a Weight Matrix, then uses a Weight Spread Sequence (WSS), which is specially designed to distribute the output more evenly, to schedule packets by scanning the Weight Matrix. By using the WSS and the Weight Matrix, SRR can emulate the Generalized Processor Sharing (GPS) well. It possesses better short-term fairness and schedule delay properties in comparison with various round robin schedulers. At the same time, it preserves O(1) time complexity by avoiding the time-stamp maintenance employed in various Fair Queueing schedulers. Simulation and implementation experiments show that SRR can provide good average end-to-end delay for soft real-time services. SRR can also be implemented in high-speed networks to provide QoS for its simplicity and low time complexity.
 

Papers are provided as a service to all by the members of ACM SIGCOMM.