research-article

Stability and fairness of explicit congestion control with small buffers

Authors:

Thomas VoiceAuthors Info & Claims

ACM SIGCOMM Computer Communication Review, Volume 38, Issue 3

Pages 51 - 62

https://doi.org/10.1145/1384609.1384615

Published: 01 July 2008 Publication History

Abstract

Rate control protocols that utilise explicit feedback from routers are able to achieve fast convergence to an equilibrium which approximates processor-sharing on a single bottleneck link, and hence such protocols allow short flows to complete quickly. For a network, however, processor-sharing is not uniquely defined but corresponds with a choice of fairness criteria, and proportional fairness has a reasonable claim to be the network generalization of processor-sharing.

In this paper, we develop a variant of RCP (rate control protocol) that achieves α-fairness when buffers are small, including proportional fairness as the case α = 1. At the level of theoretical abstraction treated, our model incorporates a general network topology, and heterogeneous propagation delays. For our variant of the RCP algorithm, we establish a simple decentralized sufficient condition for local stability.

An outstanding question for explicit congestion control is whether the presence of feedback based on queue size is helpful or not, given the presence of feedback based on rate mismatch. We show that, for the variant of RCP considered here, feedback based on queue size may cause the queue to be less accurately controlled.

A further outstanding question for explicit congestion control is the scale of the step-change in rate that is necessary at a resource to accommodate a new flow. We show that, for the variant of RCP considered here, this can be estimated from the aggregate flow through the resource, without knowledge of individual flow rates.

References

[1]

H. Balakrishnan, N. Dukkipati, N. McKeown and C. Tomlin. Stability analysis of explicit congestion control protocols. IEEE Communications Letters, 11(10): 823--825, 2007.

[2]

S. Ben Fredj, T. Bonald, A. Proutière, G. Régnié and J.W. Roberts. Statistical bandwidth sharing: a study of congestion at flow level. Proceedings of ACM Sigcomm, 2001.

Digital Library

[3]

T. Bonald, L. Massoulié, A. Proutière and J. Virtamo. A queueing analysis of max-min fairness, proportional fairness and balanced fairness. Queueing Systems, 53: 65--84, 2006.

Digital Library

[4]

N. Dukkipati and N. McKeown. Why flow-completion time is the right metric for congestion control. Computer Communication Review, 36(1): 59--62, 2006.

Digital Library

[5]

N. Dukkipati, M. Kobayashi, R. Zhang-Shen and N. McKeown. Processor sharing flows in the Internet. Thirteenth International Workshop on Quality of Service (IWQoS), Passau, Germany, June 2005.

Digital Library

[6]

N. Dukkipati, N. McKeown and A.G. Fraser. RCP-AC: Congestion control to make flows complete quickly in any environment. High-Speed Networking Workshop: The Terabits Challenge (In Conjunction with IEEE Infocom 2006), Barcelona, Spain, April 2006.

[7]

B. Hajek. A queue with periodic arrivals and constant service rate. In F.P. Kelly (ed.) Probability, Statistics and Optimisation: a Tribute to Peter Whittle. Wiley, Chichester. 1994, 147--157.

[8]

J.M. Harrison. Brownian Motion and Stochastic Flow Systems. Krieger, 1985.

[9]

C.V. Hollot, V. Misra, D. Towsley and W. Gong. Analysis and design of controllers for AQM routers supporting TCP flows. IEEE/ACM Transactions on Automatic Control, 47(6):945--959, 2002.

[10]

D. Katabi, M. Handley and C. Rohrs. Internet congestion control for future high bandwidth-delay product environments. Proceedings of ACM Sigcomm, 2002.

Digital Library

[11]

F. Kelly. Fairness and stability of end-to-end congestion control. European Journal of Control, 9:159--176, 2003.

[12]

J.-Y. Le Boudec and B. Radunovic. Rate performance objectives of multihop wireless networks. IEEE Transactions on Mobile Computing, 3:334--349, 2004.

Digital Library

[13]

S.H. Low and D.E. Lapsley. Optimization flow control.I: basic algorithm and convergence. IEEE/ACM Transactions on Networking, 7:861--874, 1999.

Digital Library

[14]

L. Massoulié. Structural properties of proportional fairness: stability and insensitivity. The Annals of Applied Probability, 17(3):809--839, 2007.

[15]

J. Mo and J. Walrand. Fair end-to-end window-based congestion control. IEEE/ACM Transactions on Networking, 8:556--567, 2000.

Digital Library

[16]

F. Paganini, Z. Wang, J.C. Doyle and S.H. Low. Congestion control for high performance, stability and fairness in general networks. IEEE/ACM Transactions on Networking, 13:43--56, 2005.

Digital Library

[17]

G. Raina and D. Wischik. Buffer sizes for large multiplexers: TCP queueing theory and instability analysis. Proc. EuroNGI Next Generation Internet Networks, Rome, Italy, April 2005.

[18]

G. Raina, D. Towsley and D. Wischik. Part II: Control theory for buffer sizing. Computer Communication Review, 35(3): 79--82, 2005.

Digital Library

[19]

J.W. Roberts (ed.) (1992). Performance Evaluation and Design of Multiservice Networks. Office for Official Publications of the European Communities, Luxembourg.

[20]

J. Roberts and L. Massoulié. Bandwidth sharing and admission control for elastic traffic. ITC specialists seminar, Yokohama, 1998.

[21]

R. Srikant. The Mathematics of Internet Congestion Control. Birkhauser, 2004.

Digital Library

[22]

G. Vinnicombe. On the stability of end-to-end congestion control for the Internet. Cambridge University Engineering Department Technical Report CUED/F-INFENG/TR.398. 2000.

[23]

G. Vinnicombe. On the stability of networks operating TCP-like congestion control. Proceedings of IFAC World Congress, Barcelona, Spain 2002.

[24]

T. Voice. Stability of multi-path dual congestion control algorithms. IEEE/ACM Transactions on Networking, 15: 1231--1239, 2007.

Digital Library

[25]

T. Voice and G. Raina. (2007). Stability analysis of a max-min fair Rate Control Protocol (RCP) in a small buffer regime. Preprint.

[26]

T. Voice and G. Raina. (2008). Rate Control Protocol (RCP): global stability and local Hopf bifurcation analysis. Preprint.

[27]

D. Wischik and N. McKeown. Part I: Buffer sizes for core routers. Computer Communication Review, 35(3): 75--78, 2005.

Digital Library

Cited By

Gao KWang SQian KLi DMiao RLi BZhou YZhai ESun CGao JZhang DFu BKelly FCai DLiu HLi YYang HSun T(2023)Dependable Virtualized Fabric on Programmable Data PlaneIEEE/ACM Transactions on Networking10.1109/TNET.2022.322461731:4(1748-1764)Online publication date: Aug-2023
https://doi.org/10.1109/TNET.2022.3224617
Tang JXu TNguyen CWang XLu SYe B(2022)Tuning Target Delay for RTT-based Congestion Control2022 IEEE 30th International Conference on Network Protocols (ICNP)10.1109/ICNP55882.2022.9940420(1-11)Online publication date: 30-Oct-2022
https://doi.org/10.1109/ICNP55882.2022.9940420
Ting LKoketsu Rodrigues TKato NChuang K(2020)Prediction of Network Traffic Load on High Variability Data Based on Distance Correlation2020 IEEE 92nd Vehicular Technology Conference (VTC2020-Fall)10.1109/VTC2020-Fall49728.2020.9348769(1-5)Online publication date: Nov-2020
https://doi.org/10.1109/VTC2020-Fall49728.2020.9348769
Show More Cited By

Index Terms

Stability and fairness of explicit congestion control with small buffers
1. Networks
  1. Network protocols

Recommendations

TCP and explicit congestion notification

This paper discusses the use of Explicit Congestion Notification (ECN) mechanisms in the TCP/IP protocol. The first part proposes new guidelines for TCP's response to ECN mechanisms (e.g., Source Quench packets, ECN fields in packet headers). Next, ...
Fairness and stability of congestion control mechanisms of TCP

In this paper, we focus on fairness and stability of the congestion control mechanisms adopted in several versions of TCP by investigating their time---transient behaviors through an analytic approach. In addition to TCP Tahoe and TCP Reno, we also ...
Fairness of a Single-Rate Multicast Congestion Control Scheme
IWDC '01: Proceedings of the Thyrrhenian International Workshop on Digital Communications: Evolutionary Trends of the Internet

Recently, a TCP-friendly, single-rate multicast congestion control scheme called pgmcc was introduced by one of the authors. In this paper, we study the fairness of pgmcc in a variety of scenarios in which a multicast transfer session competes with long-...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGCOMM Computer Communication Review

ACM SIGCOMM Computer Communication Review Volume 38, Issue 3

July 2008

96 pages

ISSN:0146-4833

DOI:10.1145/1384609

Issue’s Table of Contents

Copyright © 2008 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2008

Published in SIGCOMM-CCR Volume 38, Issue 3

Check for updates

Author Tag

modeling of communication networks

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
729
Total Downloads

Downloads (Last 12 months)22
Downloads (Last 6 weeks)3

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gao KWang SQian KLi DMiao RLi BZhou YZhai ESun CGao JZhang DFu BKelly FCai DLiu HLi YYang HSun T(2023)Dependable Virtualized Fabric on Programmable Data PlaneIEEE/ACM Transactions on Networking10.1109/TNET.2022.322461731:4(1748-1764)Online publication date: Aug-2023
https://doi.org/10.1109/TNET.2022.3224617
Tang JXu TNguyen CWang XLu SYe B(2022)Tuning Target Delay for RTT-based Congestion Control2022 IEEE 30th International Conference on Network Protocols (ICNP)10.1109/ICNP55882.2022.9940420(1-11)Online publication date: 30-Oct-2022
https://doi.org/10.1109/ICNP55882.2022.9940420
Ting LKoketsu Rodrigues TKato NChuang K(2020)Prediction of Network Traffic Load on High Variability Data Based on Distance Correlation2020 IEEE 92nd Vehicular Technology Conference (VTC2020-Fall)10.1109/VTC2020-Fall49728.2020.9348769(1-5)Online publication date: Nov-2020
https://doi.org/10.1109/VTC2020-Fall49728.2020.9348769
Voice TAbdulrahman ARaina G(2020)Global stability of the Rate Control Protocol (RCP) and some implications for protocol designPerformance Evaluation10.1016/j.peva.2020.102164(102164)Online publication date: Nov-2020
https://doi.org/10.1016/j.peva.2020.102164
Abuthahir AMalangadan NRaina G(2020)Effect of two forms of feedback on the performance of the Rate Control Protocol (RCP)Communications in Nonlinear Science and Numerical Simulation10.1016/j.cnsns.2020.105225(105225)Online publication date: Feb-2020
https://doi.org/10.1016/j.cnsns.2020.105225
. ARaina GVoice T(2019)Do we need two forms of feedback in the Rate Control Protocol (RCP)?ACM SIGMETRICS Performance Evaluation Review10.1145/3374888.337489147:2(3-5)Online publication date: 4-Dec-2019
https://dl.acm.org/doi/10.1145/3374888.3374891
Li YMiao RLiu HZhuang YFeng FTang LCao ZZhang MKelly FAlizadeh MYu MWu JHall W(2019)HPCCProceedings of the ACM Special Interest Group on Data Communication10.1145/3341302.3342085(44-58)Online publication date: 19-Aug-2019
https://dl.acm.org/doi/10.1145/3341302.3342085
Wang JGuo JWang QDuan ZChen G(2019)Necessary and sufficient condition for non-concave network utility maximisationInternational Journal of Control10.1080/00207179.2019.1599419(1-9)Online publication date: 25-Mar-2019
https://doi.org/10.1080/00207179.2019.1599419
Gao YYang YChen TZheng JMao BChen G(2018)DCQCN+: Taming Large-Scale Incast Congestion in RDMA over Ethernet Networks2018 IEEE 26th International Conference on Network Protocols (ICNP)10.1109/ICNP.2018.00021(110-120)Online publication date: Sep-2018
https://doi.org/10.1109/ICNP.2018.00021
Bahnasy MElbiaze HBoughzala B(2018)Zero-queue ethernet congestion control protocol based on available bandwidth estimationJournal of Network and Computer Applications10.1016/j.jnca.2017.12.016105(1-20)Online publication date: Mar-2018
https://doi.org/10.1016/j.jnca.2017.12.016
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.

Figures

Tables

Media

View Issue’s Table of Contents