Article

Group round robin: improving the fairness and complexity of packet scheduling

Authors:

Bogdan Caprita,

Wong Chun ChanAuthors Info & Claims

ANCS '05: Proceedings of the 2005 ACM symposium on Architecture for networking and communications systems

Pages 29 - 40

https://doi.org/10.1145/1095890.1095896

Published: 26 October 2005 Publication History

Abstract

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 computational complexity. GRR combines its grouping strategy with a specialized round-robin scheduling algorithm that utilizes the properties of GRR groups to schedule flows within groups in a manner 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.

References

[1]

J. Bennett and H. Zhang, "WF2Q: Worst-case Fair Weighted Fair Queuing," in Proceedings of INFOCOM '96, San Francisco, CA, Mar. 1996.

Digital Library

[2]

J. Bennett and H. Zhang, "Hierarchical Packet Fair Queuing Algorithms," in Proceedings of ACM SIGCOMM '96, Aug. 1996.

Digital Library

[3]

B. Caprita, W. Chan and J. Nieh, "Group Round Robin: Improving the Fairness and Complexity of Packet Scheduling." Tech. Rep. CUCS-018-03, Department of Computer Science, Columbia University, June 2003.

[4]

B. Caprita, W. C. Chan, J. Nieh, C. Stein, and H. Zheng, "Group-Ratio Round Robin: O(1) Proportional Share Scheduling for Uniprocessor and Multiprocessor Systems," in Proceedings of the 2005 USENIX Annual Technical Conference, USENIX, Anaheim, CA, April 2005.

Digital Library

[5]

W. Chan and J. Nieh, "Group ratio round-robin: An O(1) proportional share scheduler." Tech. Rep. CUCS-012-03, Department of Computer Science, Columbia University, April 2003.

[6]

S. Cheung and C. Pencea, "BSFQ: Bin Sort Fair Queuing," in Proceedings of INFOCOM ' 02, New York, NY, June 2002.

[7]

G. Chuanxiong, "SRR: An 0(1) Time Complexity Packet Scheduler for Flows in Multi-Service Packet Networks," in Proceedings of ACM SIGCOMM '01, Aug. 2001.

Digital Library

[8]

J. Cobb, M. Gouda, and A. El-Nahas, "Time-Shift Scheduling - Fair Scheduling of Flows in High-Speed Networks," in IEEE/ACM Transactions on Networking, June 1998.

Digital Library

[9]

A. Demers, S. Keshav, and S. Shenker, "Analysis and Simulation of a Fair Queuing Algorithm," in Proceedings of ACM SIGCOMM '89, Austin, TX, Sept. 1989.

Digital Library

[10]

S. J. Golestani, " A Self-Clocked Fair Queuing Scheme for Broadband applications," in Proceedings of IEEE INFOCOM '94, Apr. 1994.

[11]

P. Goyal, S. Lam, and H. Vin, "Determining End-to-End Delay Bounds in Heterogeneous Networks," in Proceedings NOSSDAV, Apr. 1995.

Digital Library

[12]

P. Goyal, H. Vin, and H. Cheng, "Start-Time Fair Queuing: A Scheduling Algorithm for Integrated Services Packet Switching Networks," in IEEE/ACM Transactions on Networking, Oct. 1997.

Digital Library

[13]

L. Kleinrock, Queuing Systems, Volume II: Computer Applications. New York: John Wiley & Sons, 1976.

[14]

A. Parekh and R. Gallager, "A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case," in IEEE/ACM Transactions on Networking, 1(3), June 1993.

Digital Library

[15]

S. Ramabhadran and J. Pasquale, "Stratified Round Robin: A Low Complexity Packet Scheduler with Bandwidth Fairness and Bounded Delay," in Proceedings of ACM SIGCOMM '03, Karlsruhe, Germany, August 2003.

Digital Library

[16]

M. Shreedhar and G. Varghese, "Efficient Fair Queuing Using Deficit Round-Robin," in Proceedings of ACM SIGCOMM '95, 4(3), Sept. 1995.

Digital Library

[17]

D. Stiliadis, and A. Varma, "Efficient Fair Queuing Algorithms for Packet-Switched Networks," in IEEE/ACM Transactions on Networking, Apr. 1998.

Digital Library

[18]

I. Stoica, H. Abdel-Wahab, and K. Jeffay, "On the Duality between Resource Reservation and Proportional Share Resource Allocation," in Multimedia Computing and Networking Proceedings, SPIE Proceedings Series, 3020, Feb. 1997.

Digital Library

[19]

C. Waldspurger, "Lottery and Stride Scheduling: Flexible Proportional-Share Resource Management". PhD thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Sept. 1995.

Digital Library

[20]

J. Xu and R. Lipton, "On Fundamental Tradeoffs between Delay Bounds and Computational Complexity in Packet Scheduling Algorithms," in Proceedings of ACM SIGCOMM '02, Pittsburgh, PA, August 2002.

Digital Library

[21]

X. Yuan and Z. Duan, "FRR: a Proportional and Worst-Case Fair Round Robin Scheduler," in Proceedings of INFOCOM '05, Miami, FL, Mar. 2005.

[22]

L. Zhang, "Virtual Clock: A New Traffic Control Algorithm for Packet Switched Networks," in ACM Transactions on Computer Systems, 9(2), May 1991.

Digital Library

Cited By

Jiang YLuo J(2018)Name Weighted Round Robin (NWRR) Algorithm for Named Data Networking2018 1st IEEE International Conference on Hot Information-Centric Networking (HotICN)10.1109/HOTICN.2018.8606018(94-99)Online publication date: Aug-2018
https://doi.org/10.1109/HOTICN.2018.8606018
Raheja S(2017)Intuitionistic Fuzzy Set Theory with Fair Share CPU SchedulerFuzzy Systems10.4018/978-1-5225-1908-9.ch015(321-346)Online publication date: 2017
https://doi.org/10.4018/978-1-5225-1908-9.ch015
Raheja S(2017)Intuitionistic Fuzzy Set Theory with Fair Share CPU SchedulerTheoretical and Practical Advancements for Fuzzy System Integration10.4018/978-1-5225-1848-8.ch006(126-153)Online publication date: 2017
https://doi.org/10.4018/978-1-5225-1848-8.ch006
Show More Cited By

Index Terms

Group round robin: improving the fairness and complexity of packet scheduling
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

Grouped distributed queues: distributed queue, proportional share multiprocessor scheduling
PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing

We present Grouped Distributed Queues (GDQ), the first proportional share scheduler for multiprocessor systems that scales well with a large number of processors and processes. GDQ uses a distributed queue architecture, and achieves accurate ...
The efficiency-fairness balance of Round Robin scheduling
Abstract
Round Robin is a widely used scheduling policy, used primarily because it is intuitively fair, splitting the resources evenly among the jobs. Little is known, however, of its fairness with respect to completion times for the jobs, ...
Group ratio round-robin: O(1) proportional share scheduling for uniprocessor and multiprocessor systems
ATEC '05: Proceedings of the annual conference on USENIX Annual Technical Conference

We present Group Ratio Round-Robin (GR³), the first proportional share scheduler that combines accurate proportional fairness scheduling behavior with O(1) scheduling overhead on both uniprocessor and multiprocessor systems. GR³ uses a simple grouping ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ANCS '05: Proceedings of the 2005 ACM symposium on Architecture for networking and communications systems

October 2005

230 pages

ISBN:1595930825

DOI:10.1145/1095890

General Chair:
Alan Berenbaum
SMSC
,
Program Chairs:
Kai Li
Princeton University, Princeton, NJ
,
Jonathan Turner
Washington University in St. Louis

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 October 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ANCS05

Sponsor:

ANCS05: Symposium on Architecture for Networking and Communications Systems 2005

October 26 - 28, 2005

NJ, Princeton, USA

Acceptance Rates

Overall Acceptance Rate 88 of 314 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
595
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Jiang YLuo J(2018)Name Weighted Round Robin (NWRR) Algorithm for Named Data Networking2018 1st IEEE International Conference on Hot Information-Centric Networking (HotICN)10.1109/HOTICN.2018.8606018(94-99)Online publication date: Aug-2018
https://doi.org/10.1109/HOTICN.2018.8606018
Raheja S(2017)Intuitionistic Fuzzy Set Theory with Fair Share CPU SchedulerFuzzy Systems10.4018/978-1-5225-1908-9.ch015(321-346)Online publication date: 2017
https://doi.org/10.4018/978-1-5225-1908-9.ch015
Raheja S(2017)Intuitionistic Fuzzy Set Theory with Fair Share CPU SchedulerTheoretical and Practical Advancements for Fuzzy System Integration10.4018/978-1-5225-1848-8.ch006(126-153)Online publication date: 2017
https://doi.org/10.4018/978-1-5225-1848-8.ch006
Cheng LRao JLau FCadar CPietzuch PKeeton KRodrigues R(2016)vScaleProceedings of the Eleventh European Conference on Computer Systems10.1145/2901318.2901321(1-14)Online publication date: 18-Apr-2016
https://dl.acm.org/doi/10.1145/2901318.2901321
Raheja SDadhich RRajpal S(2015)Designing of Vague Logic Based Fair-Share CPU SchedulerInternational Journal of Fuzzy System Applications10.4018/IJFSA.20150701034:3(25-49)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.4018/IJFSA.2015070103
Wang WLiang BLi B(2014)Low complexity multi-resource fair queueing with bounded delayIEEE INFOCOM 2014 - IEEE Conference on Computer Communications10.1109/INFOCOM.2014.6848131(1914-1922)Online publication date: Apr-2014
https://doi.org/10.1109/INFOCOM.2014.6848131
Zhang JChen XLi JLi X(2012)Task mapper and application-aware virtual machine scheduler oriented for parallel computingJournal of Zhejiang University SCIENCE C10.1631/jzus.C110021713:3(155-177)Online publication date: 6-Mar-2012
https://doi.org/10.1631/jzus.C1100217
Wang PChen SHu H(2011)Bandwidth Guaranteed Multicast Scheduling for Buffered CrossbarKey Engineering Materials10.4028/www.scientific.net/KEM.474-476.1819474-476(1819-1824)Online publication date: Apr-2011
https://doi.org/10.4028/www.scientific.net/KEM.474-476.1819
Yang MWang PLi XZhu S(2011)A High-Performance Scheduling Algorithm for Buffered Crossbar SwitchAdvanced Materials Research10.4028/www.scientific.net/AMR.268-270.2101268-270(2101-2107)Online publication date: Jul-2011
https://doi.org/10.4028/www.scientific.net/AMR.268-270.2101
Karsten M(2010)Approximation of generalized processor sharing with interleaved stratified timer wheelsIEEE/ACM Transactions on Networking10.1109/TNET.2009.203305918:3(708-721)Online publication date: 1-Jun-2010
https://dl.acm.org/doi/10.1109/TNET.2009.2033059
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents