article

Free access

Efficient fair queueing algorithms for packet-switched networks

Editor: Simon S. Lam Authors:

Dimitrios Stiliadis,

Anujan VarmaAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 6, Issue 2

Pages 175 - 185

https://doi.org/10.1109/90.664266

Published: 01 April 1998 Publication History

PDF eReader

References

[1]

A, K, Parekh and R, G, Gallager, "A generalized processor sharing npproach to flow control--The single node case," in Prec. IEEE INFO- COM'92, vol, 2, May 1992, pp. 915-924.

Crossref

Google Scholar

[2]

A, Demers, S, Keshav, and S, Shenker, "Analysis and simulation of a fair queueJng algorithm," hatemetworkh~g: Research and Experience, vol, 1, no, 1, pp, 3-26, 1990.

Google Scholar

[3]

L, Zhang, "VirtualClock: A new traffic control algorithm for packet wJtchJng networks," ACM Trans. Comput. Syst., vol. 9, pp. 101-124, May 1991,

Crossref

Google Scholar

[4]

D, Ferrarj and D. Verma, "A scheme for real-time channel establishment ill wide-area networks," IEEE J. Select. Areas Commun., vol. 8, pp. 368-379, Apr. 1990.

Google Scholar

[5]

M, Katevenis, S. Sidiropoulos, and C. Courcoubetis, "Weighted roundrobin cell multiplexing in a general-purpose ATM switch chip," IEEE 3, &,ieet. Areas Commun., vol. 9, pp. 1265-1279, Oct. 1991.

Google Scholar

[6]

M, Shreedhar and G. Varghese, "Efficient fair queueing using deficit round robin," in Proc, ACM SIGCOMM'95, Cambridge, MA, Sept. 1995, pp, 231-242.

Crossref

Google Scholar

[7]

C, Kalmanek, H. Kanakia, and S, Keshav, "Rate-controlled servers for very lligh-speed networks," in Prec. IEEE Global Telecommunications Cot~, San Diego, CA, Dec. 1990, pp. 300.3.1-300.3.9.

Google Scholar

[8]

S, Golet~tani, "A framing strategy for congestion management," IEEE J. Select, Areas Commun., vol. 9, pp. 1064-1077, Sept. 1991.

Google Scholar

[9]

H, Zhang, "Service disciplines for guaranteed performance service in packet-switching networks," Prec. IEEE, vol. 83, pp. 1374-1396, Oct. 1995,

Google Scholar

[10]

D, Stlltadis and A. Varma, "Latency-rate servers: A general model for analysis of traffic scheduling algorithms," in Prec. IEEE INFOCOM'96, San Francisco, CA, Mar. 1996, pp. 111-119.

Crossref

Google Scholar

[11]

.----, "Rate-proportional servers: A design methodology for fair quetteJng algorithms," IEEE/ACM Trans. Neavorking, this issue, pp. 164-174,

Crossref

Google Scholar

[12]

J, Davjn and A. Heybcy, "A simulation study of fair queueing and policy enforcement," Comput. Commun. Rev., vol. 20, pp. 23-29, Oct. 1990,

Crossref

Google Scholar

[13]

S, Golestani, "A self-clocked fair queueing scheme for broadband applications," in Prec. IEEE INFOCOM'94, Toronto, Ont., Canada, Apr. 1994, pp, 636-646.

Google Scholar

[14]

"Network delay analysis of a class of fair queueing algorithms," IEEE J. Select. Areas Commun., vol. 13, pp. 1057-1070, Aug, 1995,

Crossref

Google Scholar

[15]

P. Goyal, H. M. Vin, and H. Chen, "Start-time fair queueing: A scheduling algorithm for integrated services packet switching networks," in Proc. ACM SIGCOMM'96, Stanford, CA, Sept. 1996, pp, 157-169.

Crossref

Google Scholar

[16]

D. Stiliadis, "Traffic scheduling in packet switched ne~vorks: Analysis, design, and implementation," Ph.D. thesis, Comput. Eng. Dep., Univ, California, Santa Cruz, June 1996.

Crossref

Google Scholar

[17]

D. Stiliadis and A. Varma, "A reconfigurable hardware approach to network simulation," A CM Trans. Modeling Comput, Simulation, vol. 7, no. 1, pp. 131-156, Jan. 1997.

Crossref

Google Scholar

[18]

A. Varma and D. Stiliadis, "FAST: An FPGA-based simulation testbed for ATM switching systems," in Proc. ICC'96, vol. 1, Dallas, 'IX, June 1996, pp. 374-378.

Crossref

Google Scholar

[19]

P.V.E. Boas, "Preserving order in a forest in less than logarithmic time and linear space," Inform. Processing Lett., vol. 6, pp. 80-82, Apr. 1977,

Google Scholar

[20]

P. V. E. Boas, R. Kaas, and E. Zijlstra, "Design and implementation of an efficient priority queue," Mathemat. Syst. Theory, vol. 10, pp, 99-127, 1977.

Google Scholar

[21]

K. Mehlhorn, Data Structures and Algoritlzms. New York: Springer- Verlag, 1984.

Crossref

Google Scholar

[22]

D. Johnson, "A priority queue in which initialization and queue operations take O(log log d) time," Math. Syst. Theory, vol. 15, pp. 295--309, 1982.

Google Scholar

[23]

B. Dixon, "Concurrency in an O(log log n) priority queue:" in Proc. Parallel and Distributed Computing, Theory and Practice, First Canada-France Conference, Montreal, P.Q., Canada, 1994, pp. 59-71,

Crossref

Google Scholar

[24]

J. C. R. Bennett and H. Zhang, "Hierarchical packet fair queueing algorithms," in Proc, A CM SIGCOMM'96, Stanford, CA, Sept. 1996, pp. 143-156.

Crossref

Google Scholar

[25]

D. Stiliadis and A. Varma, "A general methodology for designing efficient traffic scheduling and shaping algorithms," in Proc. IEEE INFOCOM'97, San Francisco, CA, Apr. 1997, pp. 326-335.

Crossref

Google Scholar

Cited By

View all

Kulkarni SZhang WHwang JRajagopalan SRamakrishnan KWood TArumaithurai MFu X(2017)NFVniceProceedings of the Conference of the ACM Special Interest Group on Data Communication10.1145/3098822.3098828(71-84)Online publication date: 7-Aug-2017
https://dl.acm.org/doi/10.1145/3098822.3098828
Blenk ABasta AReisslein MKellerer W(2016)Survey on Network Virtualization Hypervisors for Software Defined NetworkingIEEE Communications Surveys & Tutorials10.1109/COMST.2015.248918318:1(655-685)Online publication date: 27-Jan-2016
https://dl.acm.org/doi/10.1109/COMST.2015.2489183
Kim SKim J(2016)Channel-independent throughput-based fair queueing in wireless packet networksOperations Research Letters10.1016/j.orl.2016.06.00244:4(563-567)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1016/j.orl.2016.06.002
Show More Cited By

Index Terms

Efficient fair queueing algorithms for packet-switched networks
1. Networks
  1. Network types
    1. Packet-switching networks
2. 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

Rate-proportional servers: a design methodology for fair queueing algorithms
On the application of forking nodes to product-form queueing networks

We define a ‘forking node’ as a service centre with one input feeding two outputs (each served by its own queue) under the control of an internal path-selection (PS) policy. We assume that both outputs lead to paths through which a packet reaches its ...
Hierarchical packet fair queueing algorithms
SIGCOMM '96: Conference proceedings on Applications, technologies, architectures, and protocols for computer communications

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 6, Issue 2

April 1998

120 pages

ISSN:1063-6692

Editor:
Simon S. Lam
Univ. Texas, Austin

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 April 1998

Published in TON Volume 6, Issue 2

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

48
Total Citations
View Citations
907
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)6

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kulkarni SZhang WHwang JRajagopalan SRamakrishnan KWood TArumaithurai MFu X(2017)NFVniceProceedings of the Conference of the ACM Special Interest Group on Data Communication10.1145/3098822.3098828(71-84)Online publication date: 7-Aug-2017
https://dl.acm.org/doi/10.1145/3098822.3098828
Blenk ABasta AReisslein MKellerer W(2016)Survey on Network Virtualization Hypervisors for Software Defined NetworkingIEEE Communications Surveys & Tutorials10.1109/COMST.2015.248918318:1(655-685)Online publication date: 27-Jan-2016
https://dl.acm.org/doi/10.1109/COMST.2015.2489183
Kim SKim J(2016)Channel-independent throughput-based fair queueing in wireless packet networksOperations Research Letters10.1016/j.orl.2016.06.00244:4(563-567)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1016/j.orl.2016.06.002
Alqahtani S(2015)Token Bucket Fair Scheduling Algorithm with Adaptive Rate Allocations for Heterogeneous Wireless NetworksWireless Personal Communications: An International Journal10.1007/s11277-015-2661-284:2(801-819)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1007/s11277-015-2661-2
Billaud JGulati AHanzálek ZHärtig HCastro MKaashoek M(2013)hClockProceedings of the 8th ACM European Conference on Computer Systems10.1145/2465351.2465382(309-322)Online publication date: 15-Apr-2013
https://dl.acm.org/doi/10.1145/2465351.2465382
Joung JChoi JMin SSon SKim YSong JKim YKim C(2013)A flow admission control in Next Generation Networks with flow aggregate information exchangeTelecommunications Systems10.1007/s11235-011-9444-152:2(363-374)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1007/s11235-011-9444-1
Yousefi LMeghanathan NWozniak M(2012)A fair spectrum sharing approach in Cognitive Radio NetworksProceedings of the Second International Conference on Computational Science, Engineering and Information Technology10.1145/2393216.2393342(753-759)Online publication date: 26-Oct-2012
https://dl.acm.org/doi/10.1145/2393216.2393342
Lee JHwang HPark KLee CLim SGantenbein RKuo T(2011)Delay-bandwidth normalized service sharing with service rate guaranteesProceedings of the 2011 ACM Symposium on Research in Applied Computation10.1145/2103380.2103406(118-123)Online publication date: 2-Nov-2011
https://dl.acm.org/doi/10.1145/2103380.2103406
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
Lee BJohn L(2009)Hardware acceleration for media/transaction applications in network processorsIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2008.200684717:12(1691-1697)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1109/TVLSI.2008.2006847
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

References

Cited By

Index Terms

Recommendations

Rate-proportional servers: a design methodology for fair queueing algorithms

On the application of forking nodes to product-form queueing networks

Hierarchical packet fair queueing algorithms

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations