Selfish traffic allocation for server farms

ABSTRACT

We investigate the price of selfish routing in non-cooperative networks in terms of the coordination and bicriteria ratios in the recently introduced game theoretic network model of Koutsoupias and Papadimitriou. We present the first thorough study of this model for general, monotone families of cost functions and for cost functionsm from Queueing Theory. Our main results can be summarized as follows.

• We give a precise characterization of cost functions having a bounded/unbounded coordination ratio. For example, cost functions that describe the expected delay in queueing systems have an unbounded coordination ratio.
• We show that an unbounded coordination ratio implies additionally an extremely high performance degradation under bicriteria measures. We demonstrate that the price of selfish routing can be as high as a bandwidth degradation by a factor that is linear in the network size.
• We separate the game theoretic (integral) allocation model from the (fractional) flow model by demonstrating that even a very small, in fact negligible, amount of integrality can lead to a dramatic performance degradation.
• We unify recent results on selfish routing under different objectives by showing that an unbounded coordination ratio under the min-max objective implies an unbounded coordination ratio under the average-cost (or total-latency) objective and vice versa.

.Our special focus lies on cost functions describing the behavior of Web servers that can open only a limited number of TCP connections. In particular, we compare the performance of queueing systems that serve all incoming requests with servers that reject requests in case of overload.From the result presented in this paper we conclude that queuing systems without rejection cannot give any reasonable guarantee on the expected delay of requests under selfish routing even when the injected load is far away from the capacity of the system. In contrast, Web server farms that are allowed to reject requests can guarantee a high quality of service for every individual request stream even under relatively high injection rates.

REFERENCES

• 1: M. Beckmann, C. B. McGuire, and C. B. Winston. Studies in the Economimices of Transportation. Yale University Press, 1956.
• 2: Mark E. Crovella , Azer Bestavros, Self-similarity in World Wide Web traffic: evidence and possible causes, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.835-846, Dec. 1997 [doi>10.1109/90.650143]
• 3: Artur Czumaj , Berthold Vöcking, Tight bounds for worst-case equilibria, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.413-420, January 06-08, 2002, San Francisco, California
• 4: F. Douglis, A. Feldmann, B. Krishnamurthy, and J. Mogul. Rate of change and other metrics: a live study of the World Wide Web. In Proc USENIX Symposium on Internet Technologies and Systems, pp. 147--158, December 1997.
• 5: Anja Feldmann , Anna C. Gilbert , Polly Huang , Walter Willinger, Dynamics of IP traffic: a study of the role of variability and the impact of control, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.301-313, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 6: M. Frank. The Braess paradox. (MATH)ematical Programming Study, 20:283--302, 1981.
• 7: P. Franken, D. Konig, U. Arndt, and V. Schmidt. Queues and Point Processes. Wiley, Chichester, 1982.
• 8: E. Friedman. A generic analysis of selfish routing. Manuscript, 2001.
• 9: D. Gross and C. M. Harris. Queueing Theory. Third Edition John Wiley & Sons, New York, NY, 1998.
• 10: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 11: Y. A. Korilis, A. A. Lazar, and A. Orda. Capacity allocation under noncooperative routing. In IEEE Transactions on Automatic Control, 42(3):309--325, 1997.
• 12: Y. A. Korilis, A. A. Lazar, and A. Orda. Avoiding the Braess paradox in noncooperative networks. In Journal of Applied Probability, 36(1):211--212, 1999.
• 13: E. Koutsoupias, M. Mavronicolas, and P. Spirakis. Personal communication, 2001.
• 14: E. Koutsoupias and C. H. Papadimitriou. Worst-case equilibria. In Proc. 16th STACS, pp. 404--413, 1999.
• 15: Aurel A. Lazar , Ariel Orda , Dimitrios E. Pendarakis, Virtual path bandwidth allocation in multiuser networks, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.861-871, Dec. 1997 [doi>10.1109/90.650145]
• 16: Marios Mavronicolas , Paul Spirakis, The price of selfish routing, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.510-519, July 2001, Hersonissos, Greece [doi>10.1145/380752.380846]
• 17: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 18: Ariel Orda , Raphael Rom , Nahum Shimkin, Competitive routing in multiuser communication networks, IEEE/ACM Transactions on Networking (TON), v.1 n.5, p.510-521, Oct. 1993 [doi>10.1109/90.251910]
• 19: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 20: C. Papadimitriou, Game Theory and Mathematical Economics: A Theoratical Computer Scientist's Introduction, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.4, October 14-17, 2001
• 21: Christos H. Papadimitriou , Mihalis Yannakakis, On complexity as bounded rationality (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.726-733, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195445]
• 22: Kihong Park , Gitae Kim , Mark Crovella, On the relationship between file sizes, transport protocols, and self-similar network traffic, Proceedings of the 1996 International Conference on Network Protocols (ICNP '96), p.171, October 29-November 01, 1996
• 23: Vern Paxson , Sally Floyd, Wide area traffic: the failure of Poisson modeling, IEEE/ACM Transactions on Networking (TON), v.3 n.3, p.226-244, June 1995 [doi>10.1109/90.392383]
• 24: T. Roughgarden , E. Tardos, How bad is selfish routing?, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.93, November 12-14, 2000
• 25: Tim Roughgarden, Stackelberg scheduling strategies, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.104-113, July 2001, Hersonissos, Greece [doi>10.1145/380752.380783]
• 26: T. Roughgarden, Designing Networks for Selfish Users is Hard, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.472, October 14-17, 2001
• 27: Tim Roughgarden, How unfair is optimal routing?, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.203-204, January 06-08, 2002, San Francisco, California
• 28: R. Steinberg and W. I. Zangwill. The prevalence of Braess' paradox. Transportation Science, 17(3):301--318, 1983.
• 29: J. G. Wardrop. Some theoretical aspects of road traffic research. In Proc Institution of Civil Engineers, Part II, volume 1, pp. 325--362, 1952.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

          Nouns: TCP/IP

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Queueing theory

General Terms:
Algorithms, Experimentation, Performance, Theory