article

A globally stable adaptive congestion control scheme for internet-style networks with delay

Authors:

Tamer BasarAuthors Info & Claims

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

Pages 1261 - 1274

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

Published: 01 December 2005 Publication History

Abstract

In this paper, we develop, analyze and implement a congestion control scheme in a noncooperative game framework, where each user's cost function is composed of a pricing function proportional to the queueing delay experienced by the user, and a fairly general utility function which captures the user demand for bandwidth. Using a network model based on fluid approximations and through a realistic modeling of queues, we establish the existence of a unique equilibrium as well as its global asymptotic stability for a general network topology, where boundary effects are also taken into account. We also provide sufficient conditions for system stability when there is a bottleneck link shared by multiple users experiencing nonnegligible communication delays. In addition, we study an adaptive pricing scheme using hybrid systems concepts. Based on these theoretical foundations, we implement a window-based, end-to-end congestion control scheme, and simulate it in ns-2 network simulator on various network topologies with sizable propagation delays.

References

[1]

{1} V. Jacobson, "Congestion avoidance and control," in Proc. Symp. Communications Architectures and Protocols (SIGCOMM), Stanford, CA, Aug. 1988, pp. 314-329.

[2]

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

[3]

{3} F. 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.

[4]

{4} R. Srikant, The Mathematics of Internet Congestion Control, ser. Systems & Control: Foundations & Applications. Boston, MA: Birkhä& Applications. Boston, MA: Birkhääuser, 2004.

[5]

{5} J. Mo and J. Walrand, "Fair end-to-end window-based congestion control," IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 556-567, Oct. 2000.

[6]

{6} R. J. La and V. Anantharam, "Charge-sensitive TCP and rate control in the Internet," in Proc. IEEE INFOCOM, 2000, pp. 1166-1175.

[7]

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

[8]

{8} S. Deb and R. Srikant, "Global stability of congestion controllers for the Internet," IEEE Trans. Automat. Contr., vol. 48, no. 6, pp. 1055-1060, Jun. 2003.

[9]

{9} S. Kunniyur and R. Srikant, "A time-scale decomposition approach to adaptive explicit congestion notification (ECN) marking," IEEE Trans. Automat. Contr., vol. 47, no. 6, pp. 882-894, Jun. 2002.

[10]

{10} G. Vinnicombe, "On the stability of networks operating TCP-like congestion control," in Proc. 15th IFAC World Congr. Automatic Control, Barcelona, Spain, Jul. 2002.

[11]

{11} L. Massoulie, "Stability of distributed congestion control with heterogeneous feedback delays," IEEE Trans. Automat. Contr., vol. 47, no. 6, pp. 895-902, Jun. 2002.

[12]

{12} R. Johari and D. Tan, "End-to-end congestion control for the Internet: Delays and stability," IEEE/ACM Trans. Netw., vol. 9, no. 6, pp. 818-832, Dec. 2001.

[13]

{13} A. Elwalid, "Analysis of adaptive rate-based congestion control for high-speed wide-area networks," in Proc. IEEE Int. Conf. Communications (ICC), vol. 3, Seattle, WA, Jun. 1995, pp. 1948-1953.

[14]

{14} S. Liu, T. Basar, and R. Srikant, "Controlling the Internet: A survey and some new results," in Proc. 42nd IEEE Conf. Decision and Control, Maui, HI, Dec. 2003, pp. 3048-3057.

[15]

{15} J. Wen and M. Arcak, "A unifying passivity framework for network flow control," in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 2003, pp. 1156-1166.

[16]

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

[17]

{17} T. Basar and G. J. Olsder, Dynamic Noncooperative Game Theory, 2nd ed. Philadelphia, PA: SIAM, 1999.

[18]

{18} H. Yaiche, R. R. Mazumdar, and C. Rosenberg, "A game theoretic framework for bandwidth allocation and pricing in broadband networks," IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 667-678, Oct. 2000.

[19]

{19} E. Altman, T. Basar, T. Jimenez, and N. Shimkin, "Competitive routing in networks with polynomial costs," IEEE Trans. Automat. Contr., vol. 47, no. 1, pp. 92-96, Jan. 2002.

[20]

{20} E. Altman and T. Basar, "Multi-user rate-based flow control," IEEE Trans. Commun., vol. 46, no. 7, pp. 940-949, Jul. 1998.

[21]

{21} A. Orda, R. Rom, and N. Shimkin, "Competitive routing in multiuser communication networks," IEEE/ACM Trans. Netw., vol. 1, no. 5, pp. 510-521, Oct. 1993.

[22]

{22} T. Alpcan and T. Basar, "A variable rate model with QoS guarantees for real-time Internet traffic," in Proc. SPIE Int. Symp. Information Technologies, Internet Performance and Control of Networked Systems, vol. 2411, Boston, MA, Nov. 2000.

[23]

{23} T. Alpcan and T. Basar, "A game-theoretic framework for congestion control in general topology networks," in Proc. 41st IEEE Conf. Decision and Control, Las Vegas, NV, Dec. 2002, pp. 1218-1224.

[24]

{24} T. Alpcan and T. Basar, "Global stability analysis of an end-to-end congestion control scheme for general topology networks with delay," in Proc. 42nd IEEE Conf. Decision and Control, Maui, HI, Dec. 2003, pp. 1092-1097.

[25]

{25} T. Alpcan and T. Basar, "A utility-based congestion control scheme for Internet-style networks with delay," in Proc. IEEE INFOCOM, San Francisco, CA, Apr. 2003, pp. 2039-2048.

[26]

{26} L. S. Brakmo and L. L. Peterson, "TCP Vegas: End to end congestion avoidance on a global Internet," IEEE J. Sel. Areas Communications, vol. 13, no. 8, pp. 1465-1480, Oct. 1995.

[27]

{27} J. Mo, R. J. La, V. Anantharam, and J. C. Walrand, "Analysis and comparison of TCP Reno and Vegas," in Proc. IEEE INFOCOM, 1999, pp. 1556-1563.

[28]

{28} J. Widmer, R. Denda, and M. Mauve, "A survey on TCP-friendly congestion control," IEEE Network, vol. 15, no. 3, pp. 28-37, May-Jun. 2001.

[29]

{29} R. J. La and V. Anantharam, "Utility-based rate control in the Internet for elastic traffic," IEEE/ACM Trans. Netw., vol. 10, no. 2, pp. 272-286, Apr. 2002.

[30]

{30} T. Basar and R. Srikant, "Revenue-maximizing pricing and capacity expansion in a many-users regime," in Proc. IEEE INFOCOM, New York, Jun. 2002, pp. 294-301.

[31]

{31} H. K. Khalil, Nonlinear Systems, 2nd ed. Upper Saddle River, NJ: Prentice Hall, 1996.

[32]

{32} J. K. Hale and S. M. V. Lunel, Introduction to Functional Differential Equations, ser. Applied Mathematical Sciences. New York: Springer Verlag, 1993, vol. 99.

[33]

{33} T. A. Burton, Stability and Periodic Solutions of Ordinary and Functional Differential Equations, ser. Mathematics in Science and Engineering. Orlando, FL: Academic Press, 1985, vol. 178.

[34]

{34} D. Liberzon, Switching in Systems and Control. Boston, MA: Birkhauser, 2003.

[35]

{35} Network Simulator ns (Version 2). UCB, LBNL, and VINT. {Online}. Available: http://www.isi.edu/nsnam/ns/

[36]

{36} A. S. Tanenbaum, Computer Networks, 3rd ed. Upper Saddle River, NJ: Prentice Hall, 1996.

[37]

{37} S. Floyd, M. Handley, J. Padhye, and J. Widmer, "Equation-based congestion control for unicast applications," in Proc. ACM SIGCOMM, Aug. 2000, pp. 45-58.

Cited By

Revathi TMuneeswaran KRamar K(2011)Fuzzy enabled congestion control for Differentiated Services NetworksApplied Soft Computing10.1016/j.asoc.2011.05.01311:8(5457-5462)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1016/j.asoc.2011.05.013
Singh JAlpcan TAgrawal PSharma V(2010)A Markov Decision Process based flow assignment framework for heterogeneous network accessWireless Networks10.1007/s11276-008-0148-816:2(481-495)Online publication date: 1-Feb-2010
https://dl.acm.org/doi/10.1007/s11276-008-0148-8
Houmkozlis CRovithakis G(2009)Fairness guarantees in a neural network adaptive congestion control frameworkIEEE Transactions on Neural Networks10.1109/TNN.2009.201346320:3(527-533)Online publication date: 1-Mar-2009
https://dl.acm.org/doi/10.1109/TNN.2009.2013463
Show More Cited By

Index Terms

A globally stable adaptive congestion control scheme for internet-style networks with delay
1. Networks
  1. Network services
    1. Network management
2. Social and professional topics
  1. Professional topics
    1. Management of computing and information systems
      1. Implementation management
        Pricing and resource allocation
      2. Information system economics

Recommendations

Delay-based early congestion detection and adaptation in TCP: impact on web performance

Concerns over the scalability of TCP's end-to-end approach to congestion control and its AIMD congestion adaptation have led to proposals for router-based congestion control, specifically, active queue management (AQM). In this paper we present an end-...
Stability of the Internet congestion control with diverse delays

Based on the clockwise property of parameterized curves and the general Nyquist criterion of stability, a conjecture on the stability of the Internet congestion control algorithm with diverse propagation delays is proved. A more general stability ...
Stability analysis and design of the second-order congestion control for networks with heterogeneous delays

This paper addresses the problem of the stability of congestion control for networks with heterogeneous round-trip communication delays. We present a frequency-domain approach to this problem. The approach is based on the analysis of the clockwise ...

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 13, Issue 6

December 2005

207 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 December 2005

Published in TON Volume 13, Issue 6

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
521
Total Downloads

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

Reflects downloads up to 24 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Revathi TMuneeswaran KRamar K(2011)Fuzzy enabled congestion control for Differentiated Services NetworksApplied Soft Computing10.1016/j.asoc.2011.05.01311:8(5457-5462)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1016/j.asoc.2011.05.013
Singh JAlpcan TAgrawal PSharma V(2010)A Markov Decision Process based flow assignment framework for heterogeneous network accessWireless Networks10.1007/s11276-008-0148-816:2(481-495)Online publication date: 1-Feb-2010
https://dl.acm.org/doi/10.1007/s11276-008-0148-8
Houmkozlis CRovithakis G(2009)Fairness guarantees in a neural network adaptive congestion control frameworkIEEE Transactions on Neural Networks10.1109/TNN.2009.201346320:3(527-533)Online publication date: 1-Mar-2009
https://dl.acm.org/doi/10.1109/TNN.2009.2013463
Zhu XAgrawal PSingh JAlpcan TGirod B(2009)Distributed rate allocation policies for multihomed video streaming over heterogeneous access networksIEEE Transactions on Multimedia10.1109/TMM.2009.201764111:4(752-764)Online publication date: 1-Jun-2009
https://dl.acm.org/doi/10.1109/TMM.2009.2017641
Guo SFeng GLiao XLiu Q(2009)Novel delay-range-dependent stability analysis of the second-order congestion control algorithm with heterogonous communication delaysJournal of Network and Computer Applications10.1016/j.jnca.2008.08.00132:3(568-577)Online publication date: 1-May-2009
https://dl.acm.org/doi/10.1016/j.jnca.2008.08.001
Rosberg ZSabrina F(2009)Rate control of multi class priority flows with end-to-end delay and rate constraints for QoS networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2009.07.00453:16(2810-2824)Online publication date: 1-Nov-2009
https://dl.acm.org/doi/10.1016/j.comnet.2009.07.004
Jin NJordan S(2008)On the feasibility of dynamic congestion-based pricing in differentiated services networksIEEE/ACM Transactions on Networking10.1109/TNET.2007.90816316:5(1001-1014)Online publication date: 1-Oct-2008
https://dl.acm.org/doi/10.1109/TNET.2007.908163
Singh JAlpcan TZhu XAgrawal P(2007)Towards heterogeneous network convergenceProceedings of the 2007 Workshop on Middleware for next-generation converged networks and applications10.1145/1376878.1376879(1-6)Online publication date: 26-Nov-2007
https://dl.acm.org/doi/10.1145/1376878.1376879
Zhu XAgrawal PPal Singh JAlpcan TGirod BLienhart RPrasad AHanjalic AChoi SBailey BSebe N(2007)Rate allocation for multi-user video streaming over heterogenous access networksProceedings of the 15th ACM international conference on Multimedia10.1145/1291233.1291247(37-46)Online publication date: 29-Sep-2007
https://dl.acm.org/doi/10.1145/1291233.1291247
Wang XEun D(2007)Local and global stability of TCP-newReno/RED with many flowsComputer Communications10.1016/j.comcom.2006.11.00730:5(1091-1105)Online publication date: 1-Mar-2007
https://dl.acm.org/doi/10.1016/j.comcom.2006.11.007
Show More Cited By

View Options

Get Access

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