Group Round Robin: Improving the Fairness and Complexity of Packet Scheduling

Bogdan Caprita, Jason Nieh, Wong Chun Chan

Proceedings of the 1st ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS 2005), Princeton, NJ, October 26-28, 2005, pp. 29-40


We present Group Round-Robin (GRR) scheduling, a hybrid fair packet scheduling framework based on a grouping strategy that narrows down the traditional trade-off between fairness and com- putational complexity. GRR combines its grouping strategy with a specialized round-robin scheduling algorithm that utilizes the prop- erties of GRR groups to schedule flows within groups in a man- ner that provides O(1) bounds on fairness with only O(1) time complexity. Under the practical assumption that GRR employs a small constant number of groups, we apply GRR to popular fair queuing scheduling algorithms and show how GRR can be used to achieve constant bounds on fairness and time complexity for these algorithms. We also present and prove new results on the fairness bounds for several of these fair queuing algorithms using a consistent fairness measure. We analyze the behavior of GRR and present experimental results that demonstrate how GRR can be combined with existing scheduling algorithms to provide much lower scheduling overhead and more than an order of magnitude better scheduling accuracy in practice than scheduling algorithms without GRR.



Columbia University Department of Computer Science