Selfish behavior and stability of the internet:: a game-theoretic analysis of TCP

ABSTRACT

For years, the conventional wisdom [7, 22] has been that the continued stability of the Internet depends on the widespread deployment of "socially responsible" congestion control. In this paper, we seek to answer the following fundamental question: If network end-points behaved in a selfish manner, would the stability of the Internet be endangered?.We evaluate the impact of greedy end-point behavior through a game-theoretic analysis of TCP. In this "TCP Game" each flowattempts to maximize the throughput it achieves by modifying its congestion control behavior. We use a combination of analysis and simulation to determine the Nash Equilibrium of this game. Our question then reduces to whether the network operates efficiently at these Nash equilibria.Our findings are twofold. First, in more traditional environments -- where end-points use TCP Reno-style loss recovery and routers use drop-tail queues -- the Nash Equilibria are reasonably efficient. However, when endpoints use more recent variations of TCP (e.g., SACK) and routers employ either RED or drop-tail queues, the Nash equilibria are very inefficient. This suggests that the Internet of the past could remain stable in the face of greedy end-user behavior, but the Internet of today is vulnerable to such behavior. Second, we find that restoring the efficiency of the Nash equilibria in these settings does not require heavy-weight packet scheduling techniques (e.g., Fair Queuing) but instead can be done with a very simple stateless mechanism based on CHOKe [21].

REFERENCES

• 1: The network simulator - ns-2. http://isi.edu/nsnam/ns/.
• 2: A. Akella, S. Seshan, S. Shenker, and I. Stoica. Exploring congestion control. Technical Report CMU-CS-02-139, CMU, Pittsburgh, Pennsylvania, May 2002.
• 3: M. Allman, V. Paxson, and W. Stevens. TCP congestion control. Internet Draft, Internet Engineering Task Force, Feb. 1999. Work in progress.
• 4: Z. Bar-Yossef. Private Communication, May 2002.
• 5: Ziv Bar-Yossef , Christos H. Papadimitriou, The complexity of massive data set computations, University of California at Berkeley, Berkeley, CA, 2002
• 6: 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]
• 7: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, Symposium proceedings on Communications architectures & protocols, p.1-12, September 25-27, 1989, Austin, Texas, United States
• 8: C. Douligeris and R. mazumdar. On pareto optimal flow control in a multicalss environment. In The 25th Allerton Conference of Communication, Control and Computing, University of Illinois at Urbana-Champaign, Oct. 1987.
• 9: C. Douligeris and R. Mazumdar. A game-theoretic approach to flow conrtol in an integrated environment. Journal of the Franklin Institute, 329(3):383--402, Mar. 1992.
• 10: Kevin Fall , Sally Floyd, Simulation-based comparisons of Tahoe, Reno and SACK TCP, ACM SIGCOMM Computer Communication Review, v.26 n.3, p.5-21, July 1996 [doi>10.1145/235160.235162]
• 11: D. Ferguson, C. Nikolaou, and Y. Yemini. An economy for flow control in computer networks. In Proceedings of the Conference on Computer Communications (IEEE Infocom), 1989.
• 12: S. Floyd. Questions about sack deployment. http://www.icir.org/floyd/sack-questions.html.
• 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: Man-tung T. Hsiao , Aurel A. Lazar, A Game Theoretic Approach to Decentralized Flow Control of Markovian Queueing Networks, Proceedings of the 12th IFIP WG 7.3 International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.55-73, December 07-09, 1987
• 15: V. Jacobson, Congestion avoidance and control, ACM SIGCOMM Computer Communication Review, v.18 n.4, p.314-329, August 1988
• 16: 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
• 17: Dong Lin , Robert Morris, Dynamics of random early detection, ACM SIGCOMM Computer Communication Review, v.27 n.4, p.127-137, Oct. 1997
• 18: R. Mahajan and S. Floyd. Controlling high-bandwidth flows at the congested router. In Proc. of ICNP'01, Riverside, California, USA, Nov. 2001.
• 19: Jitendra Padhye , Victor Firoiu , Donald F. Towsley , James F. Kurose, Modeling TCP Reno performance: a simple model and its empirical validation, IEEE/ACM Transactions on Networking (TON), v.8 n.2, p.133-145, April 2000 [doi>10.1109/90.842137]
• 20: Rong Pan , Lee Breslau , Balaji Prabhakar , Scott Shenker, Approximate fairness through differential dropping: (summary), ACM SIGCOMM Computer Communication Review, v.32 n.1, January 2002 [doi>10.1145/510726.510746]
• 21: R. Pan, B. Prabhakar, and K. Psounis. CHOKE, a stateless active queue management scheme for approximating fair bandwidth allocation. In Proceedings of the Conference on Computer Communications (IEEE Infocom), Mar. 2000.
• 22: Scott J. Shenker, Making greed work in networks: a game-theoretic analysis of switch service disciplines, IEEE/ACM Transactions on Networking (TON), v.3 n.6, p.819-831, Dec. 1995 [doi>10.1109/90.477727]
• 23: Y. R Yang , Simon S. Lam, General AIMD Congestion Control, University of Texas at Austin, Austin, TX, 2000

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

General Terms:
Design, Performance