article

End-to-end congestion control schemes: utility functions, random losses and ECN marks

Authors:

Srisankar Kunniyur,

R. SrikantAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 11, Issue 5

Pages 689 - 702

https://doi.org/10.1109/TNET.2003.818183

Published: 01 October 2003 Publication History

Abstract

We present a framework for designing end-to-end congestion control schemes in a network where each user may have a different utility function and may experience noncongestion-related losses. We first show that there exists an additive-increase-multiplicative-decrease scheme using only end-to-end measurable losses such that a socially optimal solution can be reached. We incorporate round-trip delay in this model, and show that one can generalize observations regarding TCP-type congestion avoidance to more general window flow control schemes. We then consider explicit congestion notification (ECN) as an alternate mechanism (instead of losses) for signaling congestion and show that ECN marking levels can be designed to nearly eliminate losses in the network by choosing the marking level independently for each node in the network. While the ECN marking level at each node may depend on the number of flows through the node, the appropriate marking level can be estimated using only aggregate flow measurements, i.e., per-flow measurements are not required.

References

[1]

{1} D. Bertsekas and R. Gallager, Data Networks. Englewood Cliffs, NJ: Prentice-Hall, 1987.

[2]

{2} L. Breslau and S. Shenker, "Best-effort versus reservations: A simple comparative analysis," Comput. Commun. Rev., vol. 28, pp. 3-16, Sept. 1998.

[3]

{3} S. Floyd, "TCP and explicit congestion notification," Comput. Commun. Rev., vol. 24, pp. 10-23, Oct. 1994.

[4]

{4} S. Floyd and K. Fall, "Promoting the use of end-to-end congestion control in the Internet," IEEE/ACM Trans. Networking, vol. 4, pp. 458-472, Aug. 1999.

[5]

{5} S. Floyd and V. Jacobson, "Random early detection gateways for congestion avoidance," IEEE/ACM Trans. Networking, vol. 1, pp. 397-413, Aug. 1993.

[6]

{6} R. J. Gibbens and F. P. Kelly, "Distributed connection acceptance control for a connectionless network," presented at the 16th Int. Teletraffic Congr., Edinburgh, U.K., June 1999.

[7]

{7} R. J. Gibbens, "Resource pricing and the evolution of congestion control," Automatica, vol. 35, pp. 1969-1985, 1999.

[8]

{8} S. J. Golestani and S. Bhattacharyya, "A class of end-to-end congestion control algorithms for the Internet," presented at the Int. Conf. Network Protocols, Oct. 1998.

[9]

{9} P. Hurley, J.-Y. Le Boudec, and P. Thiran, "A note on the fairness of additive increase and multiplicative decrease," presented at the 16th Int. Teletraffic Congr., Edinburgh, U.K., June 1999.

[10]

{10} V. Jacobson, "Congestion avoidance and control," Comput. Commun. Rev., vol. 18, pp. 314-329, Aug. 1988.

[11]

{11} F. P. Kelly, A. Maulloo, and D. Tan, "Rate control in communication networks: shadow prices, proportional fairness and stability," J. Oper. Res. Soc., vol. 49, pp. 237-252, 1998.

[12]

{12} F. P. Kelly, "Charging and rate control for elastic traffic," Eur. Trans. Telecommun., vol. 8, pp. 33-37, 1997.

[13]

{13} F. P. Kelly, "Mathematical modeling of the Internet," in Mathematics Unlimited--2001 and Beyond, B. Engquist and W. Schmid, Eds. Berlin, Germany: Springer-Verlag, 2001, pp. 685-702.

[14]

{14} A. Kumar, "Comparative performance analysis of versions of TCP in a local network with a lossy link," IEEE/ACM Trans. Networking, vol. 6, pp. 485-498, Aug. 1998.

[15]

{15} S. Kunniyur and R. Srikant, "Fairness of congestion avoidance schemes in heterogeneous networks," presented at the 16th Int. Teletraffic Congr., Edinburgh, U.K., June 1999.

[16]

{16} S. Kunniyur, "Analysis and design of an adaptive virtual queue algorithm for active queue management," in Proc. ACM SIGCOMM, San Diego, CA, Aug. 2001, pp. 123-134.

[17]

{17} S. Kunniyur, "A time-scale decomposition approach to adaptive explicit congestion notification (ECN) marking," IEEE Trans. Automat. Contr., vol. 47, pp. 882-894, June 2002.

[18]

{18} H. J. Kushner and D. S. Clark, Stochastic Approximations for Constrained and Unconstrained Systems. New York and Berlin, Germany: Springer-Verlag, 1978.

[19]

{19} T. V. Lakshman and U. Madhow, "The performance of TCP/IP for networks with high bandwidth-delay products and random loss," IEEE/ACM Trans. Networking, vol. 5, pp. 336-350, June 1997.

[20]

{20} J. R. Li, D. Dwyer, and V. Bharghavan, "A transport protocol for heterogeneous packet flows," presented at the IEEE INFOCOM, New York, Mar. 1999.

[21]

{21} S. H. Low and D. E. Lapsley, "Optimization flow control, I: Basic algorithm and convergence," IEEE/ACM Trans. Networking, vol. 7, pp. 861-875, Dec. 1999.

[22]

{22} J. K. MacKie-Mason and H. R. Varian, "Pricing congestible network resources," IEEE J. Select. Areas Commun., vol. 13, pp. 1141-1148, Sept. 1995.

[23]

{23} L. Massoulie and J. Roberts, "Bandwidth sharing: objectives and algorithms," in Proc. IEEE INFOCOM, New York, Mar. 1999, pp. 1395-1403.

[24]

{24} M. Mathis, J. Semke, J. Mahdavi, and T. Ott, "The macroscopic behavior of the TCP congestion avoidance algorithm," Comput. Commun. Rev., vol. 27, 1997.

[25]

{25} V. Misra, W. Gong, and D. Towsley, "A fluid-based analysis of a network of AQM routers supporting TCP flows with an application to RED," in Proc. ACM SIGCOMM, Stockholm, Sweden, Sept. 2000.

[26]

{26} J. Mo and J. Walrand, "Fair end-to-end window-based congestion control," IEEE/ACM Trans. Networking, vol. 8, pp. 556-567, Oct. 1998.

[27]

{27} J. Padhye, V. Firoiu, D. Towsley, and J. Kurose, "Modeling TCP throughput: a simple model and its empirical validation," in Proc. ACM SIGCOMM, 1998.

[28]

{28} J. Waldby, U. Madhow, and T. V. Lakshman, "Total acknowledgment: a robust feedback mechanism for end-to-end congestion control," Proc. ACM Sigmetrics, 1998.

Cited By

Brand CGanian RKalyanasundaram SMc Inerney FWooldridge MDy JNatarajan S(2024)The complexity of optimizing atomic congestionProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i18.29982(20044-20052)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i18.29982
Albahri OZaidan ASalih MZaidan BKhatari MAhmed MAlbahri AAlazab M(2021)Multidimensional benchmarking of the active queue management methods of network congestion control based on extension of fuzzy decision by opinion score methodInternational Journal of Intelligent Systems10.1002/int.2232236:2(796-831)Online publication date: 11-Jan-2021
https://dl.acm.org/doi/10.1002/int.22322
Wirth FStüdli SYu JCorless MShorten R(2019)Nonhomogeneous Place-dependent Markov Chains, Unsynchronised AIMD, and OptimisationJournal of the ACM10.1145/331274166:4(1-37)Online publication date: 7-Jun-2019
https://dl.acm.org/doi/10.1145/3312741
Show More Cited By

Index Terms

End-to-end congestion control schemes: utility functions, random losses and ECN marks
1. Networks
  1. Network protocols
  2. Network services
    1. Network management

Recommendations

Comparison of end-to-end and network-supported fast startup congestion control schemes

A fundamental challenge for congestion control is the flow startup phase after the connection setup or after long idle periods. The Transmission Control Protocol (TCP) uses the time-consuming Slow-Start mechanism in that case. The objective of fast ...
End-to-end multicast congestion control and avoidance
Configurable active multicast congestion control

A multicast congestion control and avoidance scheme is indispensable for group-based applications to fairly share and efficiently use network resources with unicast applications and maintain the stability of the Internet. It is difficult for the ...

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 11, Issue 5

October 2003

179 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 October 2003

Published in TON Volume 11, Issue 5

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

79
Total Citations
View Citations
1,605
Total Downloads

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

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Brand CGanian RKalyanasundaram SMc Inerney FWooldridge MDy JNatarajan S(2024)The complexity of optimizing atomic congestionProceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v38i18.29982(20044-20052)Online publication date: 20-Feb-2024
https://dl.acm.org/doi/10.1609/aaai.v38i18.29982
Albahri OZaidan ASalih MZaidan BKhatari MAhmed MAlbahri AAlazab M(2021)Multidimensional benchmarking of the active queue management methods of network congestion control based on extension of fuzzy decision by opinion score methodInternational Journal of Intelligent Systems10.1002/int.2232236:2(796-831)Online publication date: 11-Jan-2021
https://dl.acm.org/doi/10.1002/int.22322
Wirth FStüdli SYu JCorless MShorten R(2019)Nonhomogeneous Place-dependent Markov Chains, Unsynchronised AIMD, and OptimisationJournal of the ACM10.1145/331274166:4(1-37)Online publication date: 7-Jun-2019
https://dl.acm.org/doi/10.1145/3312741
Poojary SSharma V(2019)An asymptotic approximation for TCP CUBICQueueing Systems: Theory and Applications10.1007/s11134-018-9594-x91:1-2(171-203)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s11134-018-9594-x
Bonaventura MCastro RJohansson BJain S(2018)Fluid-flow and packet-level models of data networks unified under a modular/hierarchical frameworkProceedings of the 2018 Winter Simulation Conference10.5555/3320516.3320973(3825-3836)Online publication date: 9-Dec-2018
https://dl.acm.org/doi/10.5555/3320516.3320973
Xiao KMao STugnait J(2017)MAQIEEE Transactions on Wireless Communications10.1109/TWC.2017.266932216:4(2614-2626)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TWC.2017.2669322
Li YJia YTan HWang RHan ZLau F(2017)Congestion Game With Agent and Resource FailuresIEEE Journal on Selected Areas in Communications10.1109/JSAC.2017.267235835:3(764-778)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1109/JSAC.2017.2672358
Nagaraj KBharadia DMao HChinchali SAlizadeh MKatti SBarcellos MCrowcroft JVahdat AKatti S(2016)NUMFabricProceedings of the 2016 ACM SIGCOMM Conference10.1145/2934872.2934890(188-201)Online publication date: 22-Aug-2016
https://dl.acm.org/doi/10.1145/2934872.2934890
Poojary SSharma V(2016)Analysis of multiple flows using different high speed TCP protocols on a general networkPerformance Evaluation10.1016/j.peva.2016.08.002104:C(42-62)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1016/j.peva.2016.08.002
Bonald TComte C(2016)The multi-source model for dimensioning data networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2016.03.019109:P2(225-233)Online publication date: 9-Nov-2016
https://dl.acm.org/doi/10.1016/j.comnet.2016.03.019
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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents