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

Article

Free access

Hierarchical packet fair queueing algorithms

Authors:

Jon C. R. Bennett,

Hui ZhangAuthors Info & Claims

SIGCOMM '96: Conference proceedings on Applications, technologies, architectures, and protocols for computer communications

Pages 143 - 156

https://doi.org/10.1145/248156.248170

Published: 28 August 1996 Publication History

Abstract

Hierarchical Packet Fair Queueing (H-PFQ) algorithms have the potential to simultaneously support guaranteed real-time service, rate-adaptive best-effort, and controlled link-sharing service. In this paper, we design practical H-PFQ algorithms by using one-level Packet Fair Queueing (PFQ) servers as basic building blocks, and develop techniques to analyze delay and fairness properties of the resulted H-PFQ servers. We demonstrate that, in order to provide tight delay bounds in a H-PFQ server, it is essential for the one-level PFQ servers to have small Worst-case Fair Indices (WFI). We propose a new one-level PFQ algorithm called WF²Q+ that is the first to have all the following three properties: (a) providing the tightest delay bound among all PFQ algorithms; (b) having the smallest WFI among all PFQ algorithms; and (c) having a relatively low implementation complexity of O(log N). We show that practical H-PFQ algorithms can be implemented by using WF²Q+ as the basic building block and prove that the resulting H-WF²Q+ algorithms provide similar delay bounds and bandwidth distribution as those provided by a H-GPS server. Simulation experiments are presented to evaluate the proposed algorithm.

References

[1]

J. Bennett and H. Zhang. Worst-case fair packet fair queueing algorithms. Technical report, 1996. Submitted for publication.

[2]

J.C.R. Bennett and H. Zhang. WFJQ: Worst-case fair weighted fair queueing. In Proceedings of IEEE IN- FOCOM'96, pages 120-128, San Francisco, CA, March 1996.

Digital Library

[3]

D. Clark, S. Shenker, and L. Zhang. Supporting realtime applications in an integrated services packet network: Architecture and mechanism. In Proceedings of A CM SIGCOMM'92, pages 14-26, Baltimore, Maryland, August 1992.

Digital Library

[4]

R. Cruz. Service burstiness and dynamic burstiness measures: A framework. Journal of High Speed Networks, 1(2):105-127, 1992.

Digital Library

[5]

J. Davin and A. Heybey. A simulation study of fair queueing and policy enforcement. Computer Communication Review, 20(5):23-29, October 1990.

Digital Library

[6]

A. Demers, S. Keshav, and S. Shenker. Analysis and simulation of a fair queueing algorithm. In Journal of Internetworking Research and Experience, pages 3- 26, October 1990. Also in Proceedings of ACM SIG- COMM~89, pp 3-12.

Digital Library

[7]

D. Ferrari and D. Verma. A scheme for real-time channel establishment in wide-area networks. IEEE Journal on Selected Areas in Communications, 8(3):368-379, April 1990.

Digital Library

[8]

S. Floyd and V. Jacobson. Link-sharing and resource management models for packet networks. IEEE/A CM Transactions on Networking, 3(4), August 1995.

Digital Library

[9]

S. Golestani. A self-clocked fair queueing scheme for broadband applications. In Proceedings of IEEE IN- FOCOM'9J, pages 636-646, Toronto, CA, June 1994.

[10]

P. Goyal, S. Lam, and H. Vin. Determining end-to-end delay bounds in heterogeneous networks. In Proceedings of the 5th International Workshop on Network and Operating System Support For Digital Audio and Video, pages 287-298, Durham, New Hampshire, April 1995.

Digital Library

[11]

S. Keshav. A control-theoretic approach to flow control. In Proceedings of A CM SIGCOMM'91, pages 3- 15, Zurich, Switzerland, September 1991.

Digital Library

[12]

P. McKenney. Stochastic fair queueing. In Proceedings of IEEE INFOCOM'90, San Francisco, CA, June 1990.

[13]

O. Ndiaye. An efficient implementation of a hierarchical weighted fair queue packet scheduler. Master's thesis, Massachusetts Institute of Technology, May 1994.

[14]

A. Parekh and R. Gallager. A generalized processor sharing approach to flow control- the single node case. A CM/IEEE Transactions on Networking, 1(3):344- 357, June 1993.

Digital Library

[15]

S. Shenker. Making greed work in networks: A game theoretical analysis of switch service disciplines. In Proceedings of A CM SIGCOMM'9J, pages 47-57, London, UK, August 1994.

Digital Library

[16]

S. Shenker, D. Clark, and L. Zhang. A scheduling service model and a scheduling architecture for an integrated services network, 1993. preprint.

[17]

M. Shreedhar and G. Varghese. Efficient fair queueing using deficit round robin. In Proceedings of SIG- COMM'95, pages 231-243, Boston, MA, September 1995.

Digital Library

[18]

D. Stilliadis and A. Verma. Frame-based fair queueing: A new traffic scheduling algorithm for packet-switched networks. Technical Report USCS-CRL-95-39, University of California at Santa Cruz, July 1995.

Digital Library

[19]

J. Turner. New directions in communications(or which way to the information age?). IEEE Communication Magazine, 24(10), October 1986.

Digital Library

[20]

H. Zhang and S. Keshav. Comparison of rate-based service disciplines. In Proceedings of A CM SlGCOMM'91, pages 113-122, Zurich, Switzerland, September 1991.

Digital Library

Cited By

MacDavid RChen XRexford J(2024)Scalable Real-Time Bandwidth Fairness in SwitchesIEEE/ACM Transactions on Networking10.1109/TNET.2023.331717232:2(1423-1434)Online publication date: Apr-2024
https://doi.org/10.1109/TNET.2023.3317172
Guo FSun SHu JZhang NLv Z(2024)CIPO: Efficient, lightweight and programmable packet schedulingComputer Networks10.1016/j.comnet.2024.110355245(110355)Online publication date: May-2024
https://doi.org/10.1016/j.comnet.2024.110355
Mohan ALiu YFoster NKappé TKozen D(2023)Formal Abstractions for Packet SchedulingProceedings of the ACM on Programming Languages10.1145/36228457:OOPSLA2(1338-1362)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622845
Show More Cited By

Index Terms

Hierarchical packet fair queueing algorithms

Recommendations

Hierarchical packet fair queueing algorithms

Hierarchical Packet Fair Queueing (H-PFQ) algorithms have the potential to simultaneously support guaranteed real-time service, rate-adaptive best-effort, and controlled link-sharing service. In this paper, we design practical H-PFQ algorithms by using ...
Deterministic Time-Varying Packet Fair Queueing for Integrated Services Networks

In integrated services networks, the provision of Quality of Service (QoS) guarantees depends critically upon the scheduling algorithm employed at the network layer. In this work we review fundamental results on scheduling, and we focus on Packet Fair ...
A minimum-work weighted fair queuing algorithm for guaranteed end-to-end quality-of-service in packet networks

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGCOMM '96: Conference proceedings on Applications, technologies, architectures, and protocols for computer communications

August 1996

330 pages

ISBN:0897917901

DOI:10.1145/248156

Chairmen:
Deborah Estrin
Univ. of Southern California, Los Angeles
,
Sally Floyd
Lawrence Berkeley National Laboratory, Berkeley, CA
,
Craig Partridge
BBN Systems and Technologies
,
Editor:
Martha Steenstrup
BBN, USA

ACM SIGCOMM Computer Communication Review Volume 26, Issue 4
Oct. 1996
335 pages
ISSN:0146-4833
DOI:10.1145/248157
Editor:
Martha Steenstrup
BBN Corporation, Cambridge, MA
Issue’s Table of Contents

Copyright © 1996 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: 28 August 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

COMM96

Sponsor:

SIGCOMM

COMM96: ACM SIGCOMM '96

August 28 - 30, 1996

California, Palo Alto, USA

Acceptance Rates

SIGCOMM '96 Paper Acceptance Rate 27 of 162 submissions, 17%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

203
Total Citations
View Citations
1,817
Total Downloads

Downloads (Last 12 months)329
Downloads (Last 6 weeks)56

Reflects downloads up to 27 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

MacDavid RChen XRexford J(2024)Scalable Real-Time Bandwidth Fairness in SwitchesIEEE/ACM Transactions on Networking10.1109/TNET.2023.331717232:2(1423-1434)Online publication date: Apr-2024
https://doi.org/10.1109/TNET.2023.3317172
Guo FSun SHu JZhang NLv Z(2024)CIPO: Efficient, lightweight and programmable packet schedulingComputer Networks10.1016/j.comnet.2024.110355245(110355)Online publication date: May-2024
https://doi.org/10.1016/j.comnet.2024.110355
Mohan ALiu YFoster NKappé TKozen D(2023)Formal Abstractions for Packet SchedulingProceedings of the ACM on Programming Languages10.1145/36228457:OOPSLA2(1338-1362)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622845
MacDavid RChen XRexford J(2023)Scalable Real-Time Bandwidth Fairness in SwitchesIEEE INFOCOM 2023 - IEEE Conference on Computer Communications10.1109/INFOCOM53939.2023.10228997(1-10)Online publication date: 17-May-2023
https://doi.org/10.1109/INFOCOM53939.2023.10228997
Ursu RPapa AKellerer W(2022)Experimental Evaluation of Downlink Scheduling Algorithms using OpenAirInterface2022 IEEE Wireless Communications and Networking Conference (WCNC)10.1109/WCNC51071.2022.9771597(84-89)Online publication date: 10-Apr-2022
https://doi.org/10.1109/WCNC51071.2022.9771597
Saeed AZhao YDukkipati NAmmar MZegura EHarras KVahdat ALorch JYu M(2019)EiffelProceedings of the 16th USENIX Conference on Networked Systems Design and Implementation10.5555/3323234.3323237(17-31)Online publication date: 26-Feb-2019
https://dl.acm.org/doi/10.5555/3323234.3323237
Shrivastav VWu JHall W(2019)Fast, scalable, and programmable packet scheduler in hardwareProceedings of the ACM Special Interest Group on Data Communication10.1145/3341302.3342090(367-379)Online publication date: 19-Aug-2019
https://dl.acm.org/doi/10.1145/3341302.3342090
Zhao YSuo KWu XRao JWu SJin HWeissman JButt ASmirni E(2019)Preemptive Multi-Queue Fair QueuingProceedings of the 28th International Symposium on High-Performance Parallel and Distributed Computing10.1145/3307681.3326605(147-158)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3307681.3326605
Addanki VLinguaglossa LRoberts JRossi D(2018)Controlling software router resource sharing by fair packet dropping2018 IFIP Networking Conference (IFIP Networking) and Workshops10.23919/IFIPNetworking.2018.8696549(1-9)Online publication date: May-2018
https://doi.org/10.23919/IFIPNetworking.2018.8696549
Ousterhout APerry JBalakrishnan HLapukhov PAkella AHowell J(2017)FlexplaneProceedings of the 14th USENIX Conference on Networked Systems Design and Implementation10.5555/3154630.3154666(437-451)Online publication date: 27-Mar-2017
https://dl.acm.org/doi/10.5555/3154630.3154666
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

Media

Figures

Other

Tables

View Table of Contents