Understanding TCP Vegas: a duality model

ABSTRACT

We view congestion control as a distributed primal--dual algorithm carried out by sources and links over a network to solve a global optimization problem. We describe a multilink multisource model of the TCP Vegas congestion control mechanism. The model provides a fundamental understanding of delay, fairness and loss properties of TCP Vegas. It implies that Vegas stabilizes around a weighted proportionally fair allocation of network capacity when there is sufficient buffering in the network. It clarifies the mechanism through which persistent congestion may arise and its consequences, and suggests how we might use REM active queue management to prevent it. We present simulation results that validate our conclusions.

REFERENCES

• 1: Jong Suk Ahn , Peter B. Danzig , Zhen Liu , Limin Yan, Evaluation of TCP Vegas: emulation and experiment, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.185-195, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 2: Athuraliya, S., Li, V. H., Low, S. H., and Yin, Q. 2001. REM: Active queue management. IEEE Netw. May/June. Extended version in Proceedings of ITC17 (Salvador, Brazil, Sept.). 2001. http://netlab.caltech.edu.
• 3: Athuraliya, S., and Low, S. H. 2000a. Optimization flow control. II: Implementation. Submitted for publication, http://netlab.caltech.edu, May 2000.
• 4: Athuraliya, S., and Low, S. H. 2000b. Optimization flow control with Newton--like algorithm. J. Telecommun. Syst. 15, 3/4, 345--358.
• 5: Bertsekas, D. 1995. Nonlinear Programming. Athena Scientific.
• 6: Dimitri P. Bertsekas , John N. Tsitsiklis, Parallel and distributed computation: numerical methods, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 7: Bonald, T. 1998. Comparison of TCP Reno and TCP Vegas via fluid approximation. In Workshop on the Modeling of TCP. Dec. http://www.dmi.ens.fr/%7Emistral/tcpworkshop.html.
• 8: Boutremans, C., and Le Boudec, J. Y. 2000. A note on the fairness of tcp vegas. In Proceedings of International Zurich Seminar on Broadband Communications (Feb.), pp. 163--170.
• 9: Brakmo, L. S., and Peterson, L. L. 1995. TCP Vegas: End to end congestion avoidance on a global Internet. IEEE J. Select. Areas Commun. 13, 8 (Oct.), 1465--1480. http://cs.princeton.edu/nsg/papers/jsac-vegas.ps.
• 10: Gustavo de Veciana , Takis Konstantopoulos , Tae-Jin Lee, Stability and performance analysis of networks supporting elastic services, IEEE/ACM Transactions on Networking (TON), v.9 n.1, p.2-14, Feb., 2001 [doi>10.1109/90.909020]
• 11: Sally Floyd, Connections with multiple congested gateways in packet-switched networks part 1: one-way traffic, ACM SIGCOMM Computer Communication Review, v.21 n.5, p.30-47, Oct. 1991 [doi>10.1145/122431.122434]
• 12: Sally Floyd, TCP and explicit congestion notification, ACM SIGCOMM Computer Communication Review, v.24 n.5, p.8-23, Oct. 1994 [doi>10.1145/205511.205512]
• 13: Sally Floyd , Van Jacobson, Random early detection gateways for congestion avoidance, IEEE/ACM Transactions on Networking (TON), v.1 n.4, p.397-413, Aug. 1993 [doi>10.1109/90.251892]
• 14: Hengartner, U., Bolliger, J., and Gross, T. 2000. TCP Vegas revisited. In Proceedings of IEEE Infocom. (Mar.). IEEE Computer Society Press, Los Alamitos, Calif.
• 15: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 16: Kar, K., Sarkar, S., and Tassiulas, L. 2001. Optimization based rate control for multirate multicast sessions. In Proceedings of IEEE Infocom (Apr.). IEEE Computer Society Press, Los Alamitos, Calif.
• 17: Kelly, F. P. 1997. Charging and rate control for elastic traffic. Europ. Trans. Telecom. 8, 33--37. http://www.statslab.cam.ac.uk/~frank/elastic.html.
• 18: Kelly, F. P. 1999. Mathematical modelling of the Internet. In Proceedings of the 4th International Congress on Industrial and Applied Mathematics (July). http://www.statslab.cam.ac.uk/~frank/mmi.html.
• 19: Kelly, F. P., Maulloo, A., and Tan, D. 1998. Rate control for communication networks: Shadow prices, proportional fairness and stability. J. Oper. Res. Soci. 49, 3 (Mar.), 237--252.
• 20: Kunniyur, S., and Srikant, R. 2000. End--to--end congestion control schemes: Utility functions, random losses and ECN marks. In Proceedings of IEEE Infocom (Mar.). IEEE Computer Society Press, Los Alamitos, Calif. http://www.ieee-infocom.org/2000/papers/401.ps.
• 21: La, R., and Anantharam, V. 2000. Charge-sensitive TCP and rate control in the Internet. In Proceedings of IEEE Infocom (Mar.). IEEE Computer Society Press, Los Alamitos, Calif. http://www.ieee-infocom.org/2000/papers/401.ps.
• 22: T. V. Lakshman , Upamanyu Madhow, The performance of TCP/IP for networks with high bandwidth-delay products and random loss, IEEE/ACM Transactions on Networking (TON), v.5 n.3, p.336-350, June 1997 [doi>10.1109/90.611099]
• 23: Low, S. H. 2000. A duality model of TCP flow controls. In Proceedings of ITC Specialist Seminar on IP Traffic Measurement, Modeling and Management (Sept. 18--20). http://netlab.caltech.edu.
• 24: Steven H. Low , David E. Lapsley, Optimization flow control—I: basic algorithm and convergence, IEEE/ACM Transactions on Networking (TON), v.7 n.6, p.861-874, Dec. 1999 [doi>10.1109/90.811451]
• 25: Low, S. H., Paganini, F., and Doyle, J. C. 2002. Internet congestion control. IEEE Cont. Syst. Mag.(Feb.).
• 26: Steven H. Low , Larry Peterson , Limin Wang, Understanding TCP vegas: a duality model, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.226-235, June 2001, Cambridge, Massachusetts, United States
• 27: Matthew Mathis , Jeffrey Semke , Jamshid Mahdavi, The macroscopic behavior of the TCP congestion avoidance algorithm, ACM SIGCOMM Computer Communication Review, v.27 n.3, p.67-82, July 1997 [doi>10.1145/263932.264023]
• 28: Mo, J., La, R., Anantharam, V., and Walrand, J. 1999. Analysis and comparison of TCP Reno and Vegas. In Proceedings of IEEE Infocom (Mar.).
• 29: Jeonghoon Mo , Jean Walrand, Fair end-to-end window-based congestion control, IEEE/ACM Transactions on Networking (TON), v.8 n.5, p.556-567, Oct. 2000 [doi>10.1109/90.879343]
• 30: NS Network Simulator. http://www.isi.edu/nsnam/ns/.
• 31: Paganini, F., Doyle, J. C., and Low, S. H. 2001. Scalable laws for stable network congestion control. In Proceedings of Conference on Decision and Control (Dec.). http://www.ee.ucla.edu/~paganini.
• 32: Vern Paxson, End-to-end routing behavior in the Internet, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.25-38, August 28-30, 1996, Palo Alto, California, United States
• 33: Larry L. Peterson , Bruce S. Davie, Computer networks: a systems approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 34: K. K. Ramakrishnan , R. Jain, A binary feedback scheme for congestion avoidance in computer networks, ACM Transactions on Computer Systems (TOCS), v.8 n.2, p.158-181, May 1990 [doi>10.1145/78952.78955]
• 35: W. Richard Stevens, TCP/IP illustrated (vol. 1): the protocols, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1993

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Algorithms, Performance, Theory

Keywords:
Persistent congestion, REM, TCP Vegas, TCP congestion control