TCP is competitive against a limited adversary

ABSTRACT

While the well-known Transport Control Protocol (TCP) is a de facto standard for reliable communication on the Internet, and performs well in practice, the question "how good is the TCP/IP congestion control algorithm?" is not completely resolved. In this paper, we provide some answers to this question using the competitive analysis framework. First, we prove that for networks with a single bottleneck (or point of congestion), TCP is competitive to the optimal global algorithm in minimizing the user-perceived latency or flow time of the sessions. Specifically, we show that with O(1) times as much bandwidth and O(1) extra time per job, TCP is O(1)-competitive against an optimal global algorithm. We motivate the need for allowing TCP to have extra resources by observing that existing lower bounds for non-clairvoyant scheduling algorithms imply that no online, distributed, non-clairvoyant algorithm can be competitive with an optimal offline algorithm if both algorithms were given the same resources. Second, we show that TCP is fair by proving that it converges quickly to allocations where every session gets its fair share of network bandwidth.

REFERENCES

• 1: Sanjeev Arora , Bo Brinkman, A randomized online algorithm for bandwidth utilization, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.535-539, January 06-08, 2002, San Francisco, California
• 2: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 3: D.-M. Chiu , R. Jain, Analysis of the increase and decrease algorithms for congestion avoidance in computer networks, Computer Networks and ISDN Systems, v.17 n.1, p.1-14, June 10, 1989 [doi>10.1016/0169-7552(89)90019-6]
• 4: Daniel R. Dooly , Sally A. Goldman , Stephen D. Scott, TCP dynamic acknowledgment delay (extended abstract): theory and practice, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.389-398, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276792]
• 5: Jeff Edmonds, Scheduling in the dark, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.179-188, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301299]
• 6: J. Edmonds. On the competitiveness of TCP within a general network. Draft available at http://www.cs.yorku.ca/ jeff/research/tcp, 2001.
• 7: J. Edmonds. Scheduling in the dark -- improved results: manuscript. available at http://www.cs.yorku.ca/ jeff/research, 2001.
• 8: Jeff Edmonds , Kirk Pruhs, Broadcast scheduling: when fairness is fine, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.421-430, January 06-08, 2002, San Francisco, California
• 9: 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]
• 10: 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]
• 11: T. R. Henderson, E. Sahouria, S. McCanne, and R. H. Katz. On improving the fairness of TCP congestion avoidance. In Proceedings of IEEE Globecom `98, volume 1, pages 539--544, 1998.
• 12: Ramesh Johari , David Kim Hong Tan, End-to-end congestion control for the internet: delays and stability, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.818-832, December 2001 [doi>10.1109/90.974534]
• 13: Bala Kalyanasundaram , Kirk Pruhs, Speed is as powerful as clairvoyance, Journal of the ACM (JACM), v.47 n.4, p.617-643, July 2000 [doi>10.1145/347476.347479]
• 14: R. Karp , E. Koutsoupias , C. Papadimitriou , S. Shenker, Optimization problems in congestion control, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.66, November 12-14, 2000
• 15: F. Kelly. Mathematical modelling of the internet. In Bjorn Engquist and Wilfried Schmid (Eds.), Mathematics Unlimited -- 2001 and Beyond. Springer, 2001.
• 16: F. Kelly, A. Maulloo, and D. Tan. Rate control in communication networks: shadow prices, proportional fairness and stability. In Journal of the Operational Research Society, volume 49, 1998.
• 17: James F. Kurose , Keith W. Ross, Computer Networking: A Top-Down Approach Featuring the Internet Package, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 18: 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]
• 19: L. Massoulie. Stability of distributed congestion control with heterogeneous feedback delays. IEEE Transactions on Automatic Control, 47:895--902, 2002.
• 20: 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]
• 21: A. Misra and T. Ott. The window distribution of idealized TCP congestion avoidance with variable packet loss. In Proceedings of INFOCOM, pages 1564--1572, March 1999.
• 22: Rajeev Motwani , Steven Phillips , Eric Torng, Nonclairvoyant scheduling, Theoretical Computer Science, v.130 n.1, p.17-47, Aug. 1, 1994 [doi>10.1016/0304-3975(94)90151-1]
• 23: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 24: T. Ott, J. Kemperman, and M. Mathis. The stationary behavior of ideal TCP congestion avoidance, August 1996. ftp://ftp.bellcore.com/pub/tjo/TCPwindow.ps.
• 25: Jitendra Padhye , Victor Firoiu , Don Towsley , Jim Kurose, Modeling TCP throughput: a simple model and its empirical validation, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.303-314, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 26: W. R. Stevens. TCP illustrated : volume I. Addison-Wesley publishing co., 1994.
• 27: K. Thompson, G. J. Miller, and R. Wilder. Wide-area internet traffic patterns and characteristics. IEEE Network, 11(6):10--23, November 1997.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)

General Terms:
Algorithms, Performance, Theory

Keywords:
TCP/IP, competitive analysis, congestion control, performance evaluation, scheduling