×

Fairness and stability of end-to-end congestion control. (English) Zbl 1293.93689

Summary: In recent years, the Internet has attracted the attention of many theoreticians, eager to understand the remarkable success of this diverse and complex artefact. A central element of the design philosophy that shaped the Internet is the end-to-end argument, and a key illustration of the argument is provided by the congestion avoidance algorithm of the Transmission Control Protocol (TCP). Why does this algorithm work so well? How might, or should, it evolve in the future? In this paper, we outline some of the mathematical models that have been developed to help address these questions.
We review the equilibrium and dynamic properties of primal and dual algorithms, concentrating upon fairness, delay instability and stochastic instability. Primal algorithms broadly correspond with congestion control mechanisms where noisy feedback from the network is averaged at endpoints, using increase and decrease rules generalizing those of TCP. Vinnicombe has shown that delay instability is characterized in terms of the increase rule; Ott has shown that stochastic instability is primarily influenced by the decrease rule. The need to control both forms of instability places constraints on possible variants of TCP, and on attempts to remove TCP’s round-trip time bias.
Dual algorithms broadly correspond with congestion control mechanisms where averaging at resources precedes the feedback of more explicit information to endpoints, and may be especially appropriate where round-trip times are short, as in ad hoc networks. Previous work has concentrated on delay-based dual algorithms, which find fairness and stability difficult to reconcile. We describe a family of fair dual algorithms, with attractive stability properties.

MSC:

93E03 Stochastic systems in control theory (general)
93E12 Identification in stochastic control theory
68M11 Internet topics
90B18 Communication networks in operations research
93E25 Computational methods in stochastic control (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Arrow, K. J.; Hurwicz, L., Gradient method for concave programming III: further global results and applica tions to resource allocation, (Arrow, K. J.; Hurwicz, L.; Uzawa, H., Studies in linear and non-linear programming (1958), Stanford University Press), 133-145
[2] Bansal, D.; Balakrishnan, H., Binomial congestion con trol algorithms, Proc IEEE INFOCOM (2001)
[3] Barham, P., Explicit congestion avoidance: cooperative mechanisms for reducing latency and proportionally sharing bandwidth, Microsoft Research (2001), Technical Report MSR-TR-2001-100
[4] Carpenter, B., Architectural principles of the Internet, Network Working Group RFC-1958 (1996)
[5] Clark DD, Blumenthal MS. Rethinking the design of the Internet: the end to end arguments vs the brave new world, 2000.; Clark DD, Blumenthal MS. Rethinking the design of the Internet: the end to end arguments vs the brave new world, 2000.
[6] Crowcroft, J.; Gibbens, R.; Kelly, F.; Östring, S., Modelling incentives for collaboration in mobile ad hoc networks, (Proc WiOpt’03. Proc WiOpt’03, Sophia Antipolis, France (2003))
[7] Crowcroft, J.; Oechslin, P., Differentiated end-to-end Internet services using a weighted proportionally fair sharing TCP, ACM Comput Commun Rev, 28, 53-67 (1998)
[8] Clark, D. D., The design philosophy of the DARPA Internet protocols, ACM Comput Commun Rev, 18, 106-114 (1998)
[9] Floyd, S., TCP and Explicit Congestion Notification, ACM Comput Commun Rev, 24, 10-23 (1994)
[10] Floyd, S., Highspeed TCP for large congestion windows, Internet Draft <draft-floyd-tcp-highspeed-02.txt> (February 2003), Work in progress
[11] Floyd, S.; Jacobson, V., On traffic phase effects in packet- switched gateways, Internetworking: Res Experience, 3, 115-156 (1992)
[12] Gibbens, R. J.; Kelly, F. P., Resource pricing and the evolution of congestion control, Automatica, 35, 1969-1985 (1999) · Zbl 0946.93028
[13] Henderson, T. R.; Katz, R. H., TCP performance over satellite channels, UCB Computer Science Technical Report 99-1083 (December 1999)
[14] Hollot, C. V.; Misra, V.; Towsley, D.; Gong, W. B., Analysis and design of controllers for AQM routers supporting TCP flows, IEEE Trans Autom Control, 47, 945-959 (2002) · Zbl 1364.93279
[15] Jacobson, V., Congestion avoidance and control, Proc ACM Sigcomm, 314-329 (1988)
[16] Johari, R.; Tan, D. K.H., End-to-end congestion control for the Internet: delays and stability, IEEE/ACM Trans Networking, 9, 818-832 (2001)
[17] Katabi, D.; Handley, M.; Rohrs, C., Internet congestion control for future high bandwidth-delay product environments, Proc ACM Sigcomm (2002)
[18] Kelly, F. P., Mathematical modelling of the Internet, (Engquist, B.; Schmid, W., Mathematics Unlimited - 2001 and Beyond (2001), Springer-Verlag: Springer-Verlag Berlin), 685-702 · Zbl 1044.00526
[19] Kelly, F. P.; Maulloo, A. K.; Tan, D. K.H., Rate control in communication networks: shadow prices, proportional fairness and stability, J Oper Res Soc, 49, 237-252 (1998) · Zbl 1111.90313
[20] Kelly T. On engineering a stable and scalable TCP variant. Cambridge University Engineering Department Technical Report CUED/F-INFENG/TR.435, June 2002.; Kelly T. On engineering a stable and scalable TCP variant. Cambridge University Engineering Department Technical Report CUED/F-INFENG/TR.435, June 2002.
[21] Kelly, T., Scalable TCP. improving performance in highspeed wide area networks, (First International Workshop on Protocols for Fast Long-Distance Net works (2003))
[22] Kleinrock, L., Communication nets: stochastic message flow and delay (1964), McGraw-Hill: McGraw-Hill New York · Zbl 0137.11906
[23] Kunniyur, S.; Srikant, R., A time-scale decomposition approach to adaptive ECN marking, IEEE Trans Autom Control, 47, 882-894 (2002) · Zbl 1364.90125
[24] Kunniyur S, Srikant R. Stable, scalable, fair congestion control and AQM schemes that achieve high utilization in the Internet, 2002.; Kunniyur S, Srikant R. Stable, scalable, fair congestion control and AQM schemes that achieve high utilization in the Internet, 2002. · Zbl 1364.90124
[25] Low, S. H.; Lapsley, D. E., Optimization flow control I: basic algorithm and convergence, IEEE/ACM Trans Networking, 7, 861-875 (1999)
[26] Low, S. H.; Paganini, F.; Doyle, J. C., Internet conges tion control, IEEE Control Systems Mag, 22, 28-43 (2002)
[27] Low, S. H.; Peterson, L. L.; Wang, L., Understanding Vegas: a duality model, J ACM, 49, 207-235 (2002) · Zbl 1323.68056
[28] Low, S. H.; Srikant, R., A mathematical framework for designing a low-loss, low-delay Internet, Networks Spatial Econom (2003) · Zbl 1079.90026
[29] Massoulie, L., Stability of distributed congestion control with heterogeneous feedback delays, IEEE Trans on Autom Control, 47, 895-902 (2002) · Zbl 1364.93868
[30] Mathis, M.; Semke, J.; Mahdavi, J.; Ott, T., The macro scopic behaviour of the TCP congestion avoidance algorithm, Comput Commun Rev, 27, 67-82 (1997)
[31] Mazumdar, R.; Mason, L. G.; Douligeris, C., Fairness in network optimal flow control: optimality of product forms, IEEE Trans Commun, 39, 775-782 (1991)
[32] Misra, A.; Baras, J.; Ott, T., Generalized TCP congestion avoidance and its effect on bandwidth sharing and variability, Proc GLOBECOM (2000)
[33] Mo, J.; Walrand, J., Fair End-to-End Window-based Congestion Control, IEEE/ACM Trans Networking, 8, 556-567 (2000)
[34] Nash, J. F., The bargaining problem, Econometrica, 28, 155-162 (1950) · Zbl 1202.91122
[35] Ott, T. J., ECN protocols and the TCP paradigm (1999)
[36] Paganini, F., A global stability result in network flow control, Systems Control Lett, 46, 165-172 (2002) · Zbl 1031.93137
[37] Paganini, F.; Doyle, J. C.; Low, S. H., Scalable laws for stable network congestion control, (IEEE CDC. IEEE CDC, Orlando, FL (December 2001))
[38] Paganini, F.; Wang, Z.; Low, S. H.; Doyle, J. C., A new TCP/AQM for stable operation in Fast networks (2002)
[39] Ramakrishnan, K. K.; Floyd, S.; Black, D., The addition of Explicit Congestion Notification (ECN) to IP, Internet Engineering Task Force (June 2001)
[40] Saltzer, J. H.; Reed, D. P.; Clark, D. D., End-to-end argu ments in system design, ACM Trans Comput Systems, 2, 277-288 (1984)
[41] Varian HR.Microeconomic analysis. 3rd edn. Norton, New York.; Varian HR.Microeconomic analysis. 3rd edn. Norton, New York.
[42] Vinnicombe G. On the stability of end-to-end conges tion control for the Internet. Cambridge University Engineering Department Technical Report CUED/F-INFENG/TR.398, 2000.; Vinnicombe G. On the stability of end-to-end conges tion control for the Internet. Cambridge University Engineering Department Technical Report CUED/F-INFENG/TR.398, 2000.
[43] Vinnicombe, G., On the stability of networks operating TCP-like congestion control, IFAC (2002)
[44] Vinnicombe, G., Robust congestion control for the Internet (2002)
[45] Wen, T.; Arcak, M., A unifying passivity framework for network flow control (2003)
[46] Willinger, W.; Doyle, J., Robustness and the Internet: design and evolution, (Jen, E., Robust design: a repertoire from biology, ecology and engineering (2003), Oxford University Press)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.