Article

Free access

SRR: An O(1) time complexity packet scheduler for flows in multi-service packet networks

Author:

Guo ChuanxiongAuthors Info & Claims

SIGCOMM '01: Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications

Pages 211 - 222

https://doi.org/10.1145/383059.383076

Published: 27 August 2001 Publication History

Abstract

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.

References

[1]

J. Bennet, and H. Zhang, "WF 2 Q: worst case fair weighted fair queueing," in Proc. Infocom'96, 1996.

[2]

J. Bennett, and H. Zhang, "Hierarchical Packet Fair Queueing Algorithms," in Proc. SIGCOMM'96, 1996.

Digital Library

[3]

S. Blake, et. al. "An Architecture for Differentiated Services," RFC 2475, Dec. 1998.

Digital Library

[4]

J. Bolot, and T. Turletti, "Experience with Control Mechanisms for Packet Video," in Proc. SIGCOMM'97, 1997.

[5]

Guo Chuanxiong, "A SRR packet scheduler for flows in multi-service packet networks," Ph.D. thesis, Inst. of Comm. Eng. of China, April, 2000.

[6]

D. Clark, and Wenjia Fang, "Explicit Allocation of Best- Effort Packet Delivery Service," IEEE/ACM Trans. Networking, vol. 6, Aug. 1998.

Digital Library

[7]

D. Clark, "The Design Philosophy of the DARPA Internet Protocols," in Proc. SIGCOMM'88, 1988.

Digital Library

[8]

D. Clark, S. Shenker, and L. Zhang, "Supporting Realtime Applications in an Integrated Services Packet Network: Architecture and Mechanism," in Proc. SIGCOMM'92, 1992.

Digital Library

[9]

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

Digital Library

[10]

J. A. Cobb, and M. G. Gouda, "Flow Theory," IEEE/ACM Trans. Networking, vol.5, Oct. 1997.

Digital Library

[11]

A. Demers, S. Keshav, and S. Shenker, "Analysis and Simulation of a Fair Queueing Algorithm," in Proc. SIGCOMM'89, 1989.

Digital Library

[12]

S. Floyd, and V. Jacobson, "Random Early Detection Gateways for Congestion Avoidance," IEEE/ACM Trans. Networking, vol. 1, Aug. 1993.

Digital Library

[13]

S. Floyd, and V. Jacobson, "Link-share and Resource Management Models for Packet Networks," IEEE/ACM Trans. Networking, vol. 3, Aug. 1995.

Digital Library

[14]

S. Floyd, and K. Fall, "Promoting the Use of End-to-End Congestion Control in the Internet," IEEE/ACM Trans. Networking, vol. 7, Aug. 1999.

Digital Library

[15]

L. Georgiadis, R. Guerin, and R. Rajan, "Efficient Support of Delay and Rate Guarantees in an Internet," in Proc. SIGCOMM'96, 1996.

Digital Library

[16]

P. Goyal, H. M. Vin, and H Cheng, "Start-Time Fair Queueing: A Scheduling Algorithm for Integrated Services Packet Switching Networks," IEEE/ACM Trans. Networking, vol. 5, 1997.

Digital Library

[17]

Pawn Goyal, and H. Vin, "Generalized Guaranteed Rate Scheduling Algorithms: A Framework," IEEE/ACM Trans. Networking, vol. 5, 1997.

Digital Library

[18]

S. R. McCanne, "Scalable Compression and Transmission of Internet Multicast Video," Ph.D. thesis, UC. Berkeley, Dec. 1996.

Digital Library

[19]

A. Parekh, "A Generalized Processor Sharing Approach to Flow Control in Integrated Services Network," Ph.D. thesis, Dept. Elect. Eng. and Comput. Sci., M.I.T., Feb. 1992.

[20]

V. Paxson, and S. Floyd, "Why we don't know how to simulate the Internet," from: ftp://ftp.ee.lbl.gov/papers/wsc97.ps.

[21]

O. Rose, "Traffic Modeling of Variable Bit Rate MPEG Video and its Impacts on ATM Networks," Ph.D. thesis, Wurezburger, Bericht, 02/97.

[22]

D. Saha, S. Mukherjee, and S. Tripathi, "Carry-Over Round Robin: A Simple Cell Scheduling Mechanism for ATM Networks," IEEE/ACM Trans. Networking, vol.6, Dec. 1998.

Digital Library

[23]

M. Shreedhar and G. Varghese, "Efficient Fair Queuing using Deficit Round Robin," in Proc. SIGCOMM'95, 1995.

Digital Library

[24]

D. Stiliadis, and A. Varma, "Rate-Proportional Servers: A Design Methodology for Fair Queueing Algorithms," IEEE/ACM Trans. Networking, vol. 6, Apr. 1998.

Digital Library

[25]

D. Stiliadis, and A. Varma, "Efficient Fair Queueing Algorithms for Packet-Switched Networks, " IEEE/ACM Trans. Networking, vol. 6, Apr. 1998.

Digital Library

[26]

A. Varma, and D. Stiliadis, "Hardware Implementation of Fair Queuing Algorithms for Asynchronous Transfer Mode Networks," IEEE Com. Mag., vol. 35, Dec. 1997.

Digital Library

[27]

W. Weiss, "QoS with differentiated services," Bell-labs Technical Journal, oct-dec 1998.

[28]

W. Willingers, and V. Paxson, "Where Mathematics meets the Internet," Notes of the American Mathematical Society, vol.45, Aug.1998.

[29]

L. Zhang, "A New Architecture for Packet Switching Network Protocols," Ph.D. thesis, Dept. Elect. Eng. and Comput Sci., M.I.T., Aug. 1989.

[30]

L. Zhang, S. Deering, D. Estrin, S. Shenker and D. Zappala, "RSVP: A New Resource ReServation Protocol," IEEE Network, 1993.

[31]

The VINT Project, "ns Notes and Documentation", from http://www-mash.cs.berkeley.edu/ns/nsDoc.ps.gz.

Cited By

Khamse-Ashari JKesidis GLambadaris IUrgaonkar BZhao Y(2016)Max-min Fair scheduling of variable-length packet-flows to multiple servers by deficit round-robin2016 Annual Conference on Information Science and Systems (CISS)10.1109/CISS.2016.7460534(390-395)Online publication date: Mar-2016
https://doi.org/10.1109/CISS.2016.7460534
Eberle HOlesinski W(2012)Classes of service for daisy chain interconnects2012 IEEE 13th International Conference on High Performance Switching and Routing10.1109/HPSR.2012.6260842(147-153)Online publication date: Jun-2012
https://doi.org/10.1109/HPSR.2012.6260842
Eberle HOlesinski W(2012)Weighted Differential SchedulerProceedings of the 2012 IEEE 20th Annual Symposium on High-Performance Interconnects10.1109/HOTI.2012.12(33-39)Online publication date: 22-Aug-2012
https://dl.acm.org/doi/10.1109/HOTI.2012.12
Show More Cited By

Index Terms

SRR: An O(1) time complexity packet scheduler for flows in multi-service packet networks
1. Computer systems organization
  1. Architectures
    1. Distributed architectures
2. Networks

Recommendations

SRR: An O(1) time complexity packet scheduler for flows in multi-service packet networks
Proceedings of the 2001 SIGCOMM conference

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 ...
SRR: an O(1) time-complexity packet scheduler for flows in multiservice packet networks

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 the burstiness of their scheduling output. In order to overcome this problem, SRR codes the weights of ...
Real-Time Traffic Scheduling and Routing in Packet-Switched Networks Using a Least-Laxity-First Strategy

In this paper, we address the problem of transmission scheduling and buffer management at a switch in a high-speed packet-switched network. Future computer networks are expected to carry bursty real-time multimedia traffic with specific time-delay ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGCOMM '01: Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications

August 2001

298 pages

ISBN:1581134118

DOI:10.1145/383059

Chairmen:
Rene Cruz
Unvi. of California, San Diego
,
George Varghese
Unvi. of California, San Diego

ACM SIGCOMM Computer Communication Review Volume 31, Issue 4
Proceedings of the 2001 SIGCOMM conference
October 2001
275 pages
ISSN:0146-4833
DOI:10.1145/964723
Issue’s Table of Contents

Copyright © 2001 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

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 August 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGCOMM01

Sponsor:

SIGCOMM

SIGCOMM01: Annual ACM SIGCOMM Conference

California, San Diego, USA

Acceptance Rates

SIGCOMM '01 Paper Acceptance Rate 23 of 252 submissions, 9%;

Overall Acceptance Rate 462 of 3,389 submissions, 14%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

55
Total Citations
View Citations
1,303
Total Downloads

Downloads (Last 12 months)114
Downloads (Last 6 weeks)14

Reflects downloads up to 27 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Khamse-Ashari JKesidis GLambadaris IUrgaonkar BZhao Y(2016)Max-min Fair scheduling of variable-length packet-flows to multiple servers by deficit round-robin2016 Annual Conference on Information Science and Systems (CISS)10.1109/CISS.2016.7460534(390-395)Online publication date: Mar-2016
https://doi.org/10.1109/CISS.2016.7460534
Eberle HOlesinski W(2012)Classes of service for daisy chain interconnects2012 IEEE 13th International Conference on High Performance Switching and Routing10.1109/HPSR.2012.6260842(147-153)Online publication date: Jun-2012
https://doi.org/10.1109/HPSR.2012.6260842
Eberle HOlesinski W(2012)Weighted Differential SchedulerProceedings of the 2012 IEEE 20th Annual Symposium on High-Performance Interconnects10.1109/HOTI.2012.12(33-39)Online publication date: 22-Aug-2012
https://dl.acm.org/doi/10.1109/HOTI.2012.12
Dwekat ZRouskas G(2011)Worst-Case Fair Bin Sort Queuing (WBSQ): An O(1) Worst-Case Fair Scheduler2011 IEEE International Conference on Communications (ICC)10.1109/icc.2011.5963218(1-5)Online publication date: Jun-2011
https://doi.org/10.1109/icc.2011.5963218
Jin DNicol DYücesan E(2010)Fast simulation of background traffic through fair queueing networksProceedings of the Winter Simulation Conference10.5555/2433508.2433873(2935-2946)Online publication date: 5-Dec-2010
https://dl.acm.org/doi/10.5555/2433508.2433873
Olesinski WEberle HLin BMogul JIyer R(2010)Simple two-priority, low-jitter schedulerProceedings of the 6th ACM/IEEE Symposium on Architectures for Networking and Communications Systems10.1145/1872007.1872048(1-2)Online publication date: 25-Oct-2010
https://dl.acm.org/doi/10.1145/1872007.1872048
Martinez-Morais RAlfaro-Cortes FSanchez J(2010)Providing QoS with the Deficit Table SchedulerIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2009.7521:3(327-341)Online publication date: 1-Mar-2010
https://dl.acm.org/doi/10.1109/TPDS.2009.75
Dong Jin Nicol DCaesar M(2010)Efficient Gigabit Ethernet Switch Models for Large-Scale SimulationProceedings of the 2010 IEEE Workshop on Principles of Advanced and Distributed Simulation10.1109/PADS.2010.5471659(122-131)Online publication date: 17-May-2010
https://dl.acm.org/doi/10.1109/PADS.2010.5471659
He ZLiu XLiu XZhou J(2010)Link-16 model architecture for multiple nets simulation in NS-22010 IEEE International Conference on Industrial Engineering and Engineering Management10.1109/IEEM.2010.5674291(1645-1649)Online publication date: Dec-2010
https://doi.org/10.1109/IEEM.2010.5674291
Yin YPoo G(2010)User-oriented hierarchical bandwidth scheduling for ethernet passive optical networksComputer Communications10.1016/j.comcom.2010.01.01833:8(965-975)Online publication date: 1-May-2010
https://dl.acm.org/doi/10.1016/j.comcom.2010.01.018
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Figures

Tables

Media

View Table of Conten