More Web Proxy on the site http://driver.im/

Article

Bandwidth and latency analysis of modified deficit round robin scheduling algorithms

Authors:

Luciano Lenzini,

Giovanni SteaAuthors Info & Claims

valuetools '06: Proceedings of the 1st international conference on Performance evaluation methodolgies and tools

Pages 41 - es

https://doi.org/10.1145/1190095.1190147

Published: 11 October 2006 Publication History

Abstract

Deficit Round Robin (DRR) is a scheduling algorithm which provides fair queuing at O(1) complexity. However, due to its round robin structure, its latency properties are not adequate for latency-critical applications, such as voice. For this reason, router manufacturers implement variants of the DRR algorithm which guarantee lower latencies to one (or a subset of) queue(s). In this paper we evaluate the performance of two such variants, both of which are known as Modified Deficit Round Robin, currently implemented in commercial routers. The comparison is carried out analytically, by deriving the latency and bandwidth sharing properties of both algorithms, and by simulation.

References

[1]

H. Zhang "Service Disciplines for Guaranteed Performance Service in Packet-Switching Networks", Proceedings of the IEEE, vol. 83, No. 10, pp. 1374--1396, October 1995.

[2]

D. Stiliadis and A. Varma, "Latency-Rate Servers: A General Model for Analysis of Traffic Scheduling Algorithms," IEEE/ACM Transactions on Networking, vol. 6, pp. 675--689, October 1998.

Digital Library

[3]

A. K. Parekh and R. G. Gallager, "A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: the Single Node Case," IEEE/ACM Transactions on Networking, vol. 1, pp. 344--357, June 1993.

Digital Library

[4]

S. J. Golestani, "A Self-Clocked Fair Queueing Scheme for Broadband Applications," in Proc. of IEEE INFOCOM'94, pp. 636--646, Jun. 14--16, 1994, Toronto, Canada.

[5]

M. Shreedhar and G. Varghese, "Efficient Fair Queueing Using Deficit Round Robin," IEEE/ACM Transactions on Networking, vol. 4, pp. 375--385, June 1996.

Digital Library

[6]

S. Suri, G. Varghese, and G. Chandranmenon "Leap Forward Virtual Clock: A New Fair Queueing Scheme With Guaranteed Delay and Throughput Fairness," in Proc. of IEEE INFOCOM'97, Apr. 7--11, 1997, Kobe, Japan.

Digital Library

[7]

P. Goyal, H. M. Vin and H. Cheng, "Start-Time Fair Queueing: A Scheduling Algorithm for Integrated Services Packet Switching Networks", IEEE/ACM Transactions on Networking, Vol. 5, No. 5, pp. 690--704, October 1997.

Digital Library

[8]

J. Bennett and H. Zhang: "Hierarchical Packet Fair Queueing Algorithms", IEEE/ACM Trans. on Networking, Vol. 5, No. 5, pp. 675--689, October 1997.

Digital Library

[9]

F. Toutain, "Decoupled Generalized Processor Sharing: A Fair Queuing Principle for Adaptive Multimedia Applications", Proc. of IEEE INFOCOM'98, San Francisco, CA, USA, March, April 1998

[10]

D. Saha, S. Mukherjee, K. Tripathi: "Carry-Over Round Robin: A Simple Cell Scheduling Mechanism for ATM Networks". IEEE/ACM Transactions. on Networking, Vol. 6, No. 6, pp. 779--796, December 1998.

Digital Library

[11]

S.-C. Tsao and Y.-D. Lin, "Pre-Order Deficit Round Robin: a new scheduling algorithm for packet switched networks," Computer Networks, vol. 35, pp. 287--305, February 2001.

Digital Library

[12]

G. Chuanxiong, "SRR: An O(1) Time Complexity Packet Scheduler for Flows in Multi-Service Packet Networks," in Proc. of ACM SIGCOMM'01, pp. 211--222, Aug. 27--31, 2001, San Diego, CA, USA.

Digital Library

[13]

A. Francini, F. M. Chiussi, R. T. Clancy, K. D. Drucker, and N. E. Idirene, "Enhanced Weighted Round Robin Schedulers For Accurate Bandwidth Distribution in Packet Networks", Computer Networks, vol. 37, pp. 561--578, Nov. 2001.

Digital Library

[14]

S. S. Kanhere, H. Sethu, A. B. Parekh, "Fair and Efficient Packet Scheduling Using Elastic Round-Robin", IEEE Trans. on Parallel and Distributed Systems, vol. 13, no. 3, pp. 324--336, March 2002.

Digital Library

[15]

L. Lenzini, E. Mingozzi, G. Stea, "A unifying service discipline for providing rate-based guaranteed and fair queueing services based on the Timed Token Protocol", IEEE Trans, on Computers, vol. 51, no. 9, pp. 1011--1025, Sept. 2002.

Digital Library

[16]

L. Lenzini, E. Mingozzi, G. Stea, "Packet Timed Token Service Discipline: a scheduling algorithm based on the dual-class paradigm for providing QoS in integrated services networks", Computer Networks 31/4, pp. 363--384, July 2002.

[17]

L. Lenzini, E. Mingozzi, G. Stea, "Design and Performance Analysis of the Generalized Timed Token Service Discipline" IEEE Transactions on Computers, Vol. 53, No. 7, pp. 879--891, July 2004.

Digital Library

[18]

"Understanding and Configuring MDRR/WRED on the Cisco 12000 Series Internet Router", doc. ID 18841, <http://www.cisco.com/warp/public/63/mdrr_wred_overview.html>

[19]

V. Ananthakrishnan, B. Kelly, "Operation of Modified Deficit Round Robin in M-Series Routers", Juniper Networks, <http://www.juniper.net/solutions/literature/app_note/>

[20]

L. Lenzini, E. Mingozzi, G. Stea, "Tradeoffs between Low Complexity, Low Latency and Fairness with Deficit Round Robin Schedulers", IEEE/ACM Transactions on Networking, pp. 681--693, August 2004.

Digital Library

[21]

M. H. McGregor and W. Shi: "Deficits for Bursty Latency-critical Flows: DRR++", Proc. of ICON'00, Singapore, September 5--8, 2000.

[22]

The Network Simulator - ns2 <http://www.isi.edu/nsnam/ns/>.

[23]

Agilent Website, <http://advanced.comms.agilent.com/ insight/2001-08/Questions/traffic_gen.htm>, 2004

[24]

http://www.isi.edu/nsnam/ns/ns-contributed.html

Cited By

Khalid SAbidin HMazalan LAbdullah S(2023)Optimising Video Transmission Performance in 5G New Radio Technology for Vehicle-to-Network (V2N) Application: A Comprehensive Analysis2023 11th International Conference on Information and Communication Technology (ICoICT)10.1109/ICoICT58202.2023.10262660(487-492)Online publication date: 23-Aug-2023
https://doi.org/10.1109/ICoICT58202.2023.10262660
Ali MAli M(2020)A Priority-Based Deficit Weighted Round Robin Queuing for Dynamic Bandwidth Allocation Algorithm in Gigabit Passive Optical NetworkIntelligent Energy Management Technologies10.1007/978-981-15-8820-4_6(65-71)Online publication date: 2-Dec-2020
https://doi.org/10.1007/978-981-15-8820-4_6
Alsahag AAli BNoordin NMohamad H(2011)Fair bandwidth assignment in hierarchical scheduling for mobile WiMAX systemThe 17th Asia Pacific Conference on Communications10.1109/APCC.2011.6152905(743-747)Online publication date: Oct-2011
https://doi.org/10.1109/APCC.2011.6152905
Show More Cited By

Index Terms

Bandwidth and latency analysis of modified deficit round robin scheduling algorithms

Recommendations

Performance analysis of Modified Deficit Round Robin schedulers

Deficit Round Robin (DRR) is a scheduling algorithm which provides fair queuing at O(1) complexity. However, due to its round robin structure, its latency properties are not adequate for latency-critical applications, such as voice. For this reason, ...
On the latency and fairness characteristics of pre-order deficit round Robin

In the emerging high-speed packet-switched networks, fair packet scheduling algorithms in switches and routers will form an important component of the mechanisms that seek to satisfy the Quality of Service (QoS) requirements of various applications. The ...
Proportional Nested Deficit Round Robin: Improving the Latency of Packet Scheduler with an O(1) Complexity
AAA-IDEA '05: Proceedings of the First International Workshop on Advanced Architectures and Algorithms for Internet Delivery and Applications

In recent years, many fair Packet scheduling algorithms have been proposed for switches and routers to provide the Quality of Service (QoS) guarantees required by many applications. In addition to the fairness and low end-to-end delay that these ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

valuetools '06: Proceedings of the 1st international conference on Performance evaluation methodolgies and tools

October 2006

638 pages

ISBN:1595935045

DOI:10.1145/1190095

General Chairs:
Luciano Lenzini
University of Pisa, Italy
,
Rene Cruz
UCSD, US

Copyright © 2006 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 October 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 90 of 196 submissions, 46%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
914
Total Downloads

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

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Khalid SAbidin HMazalan LAbdullah S(2023)Optimising Video Transmission Performance in 5G New Radio Technology for Vehicle-to-Network (V2N) Application: A Comprehensive Analysis2023 11th International Conference on Information and Communication Technology (ICoICT)10.1109/ICoICT58202.2023.10262660(487-492)Online publication date: 23-Aug-2023
https://doi.org/10.1109/ICoICT58202.2023.10262660
Ali MAli M(2020)A Priority-Based Deficit Weighted Round Robin Queuing for Dynamic Bandwidth Allocation Algorithm in Gigabit Passive Optical NetworkIntelligent Energy Management Technologies10.1007/978-981-15-8820-4_6(65-71)Online publication date: 2-Dec-2020
https://doi.org/10.1007/978-981-15-8820-4_6
Alsahag AAli BNoordin NMohamad H(2011)Fair bandwidth assignment in hierarchical scheduling for mobile WiMAX systemThe 17th Asia Pacific Conference on Communications10.1109/APCC.2011.6152905(743-747)Online publication date: Oct-2011
https://doi.org/10.1109/APCC.2011.6152905
Alparslan OAkar NKarasan E(2011)TCP flow aware adaptive path switching in diffserv enabled MPLS networksEuropean Transactions on Telecommunications10.1002/ett.146822:5(185-199)Online publication date: 4-Mar-2011
https://doi.org/10.1002/ett.1468
Miaji YHassan S(2009)A comparative survey of scheduling mechanisms in the internetTENCON 2009 - 2009 IEEE Region 10 Conference10.1109/TENCON.2009.5396190(1-6)Online publication date: Nov-2009
https://doi.org/10.1109/TENCON.2009.5396190
Lenzini LMingozzi EStea G(2007)Performance analysis of Modified Deficit Round Robin schedulersJournal of High Speed Networks10.5555/2692164.269216916:4(399-422)Online publication date: 1-Oct-2007
https://dl.acm.org/doi/10.5555/2692164.2692169

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