The Library

Selfish traffic allocation for server farms

Tools

Czumaj, Artur, Krysta, Piotr and Vöcking, Berthold. (2010) Selfish traffic allocation for server farms. SIAM Journal on Computing, Vol.39 (No.5). pp. 1957-1987. ISSN 0097-5397

PDF
WRAP_Cjumaz_Selfish_traffic.pdf - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (393Kb)

Official URL: http://dx.doi.org/10.1137/070693862

Abstract

We study the price of selfish routing in noncooperative networks like the Internet. In particular, we investigate the price of selfish routing using the price of anarchy (a.k.a. the coordination ratio) and other (e.g., bicriteria) measures in the recently introduced game theoretic parallel links network model of Koutsoupias and Papadimitriou. We generalize this model toward general, monotone families of cost functions and cost functions from queueing theory. A summary of our main results for general, monotone cost functions is as follows: 1. We give an exact characterization of all cost functions having a bounded/unbounded price of anarchy. For example, the price of anarchy for cost functions describing the expected delay in queueing systems is unbounded. 2. We show that an unbounded price of anarchy implies an extremely high performance degradation under bicriteria measures. In fact, the price of selfish routing can be as high as a bandwidth degradation by a factor that is linear in the network size. 3. We separate the game theoretic (integral) allocation model from the (fractional) flow model by demonstrating that even a very small or negligible amount of integrality can lead to a dramatic performance degradation. 4. We unify recent results on selfish routing under different objectives by showing that an unbounded price of anarchy under the min-max objective implies an unbounded price of anarchy under the average cost 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 Transmission Control Protocol (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. Our analysis indicates that all queueing 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.

Item Type:

Journal Article

Subjects:

Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Q Science > QA Mathematics

Divisions:

Faculty of Science > Computer Science

Library of Congress Subject Headings (LCSH):

Web servers, Queuing theory, Computer networks -- Mathematical models, Game theory

Journal or Publication Title:

SIAM Journal on Computing

Publisher:

Society for Industrial and Applied Mathematics

ISSN:

0097-5397

Official Date:

3 February 2010

Dates:

Date	Event
3 February 2010	Published

Volume:

Vol.39

Number:

No.5

Page Range:

pp. 1957-1987

Identification Number:

10.1137/070693862

Status:

Peer Reviewed

Access rights to Published version:

Open Access

Funder:

Engineering and Physical Sciences Research Council (EPSRC), Deutsche Forschungsgemeinschaft (DFG), National Science Foundation (U.S.) (NSF), Sixth Framework Programme (European Commission) (FP6)

Grant number:

CCR-0105701 (NSF), Kr 2332/1-1 (DFG), Vo 889/1-1 (DFG), IST-1999-14186 (FP6), EP/D063191/1 (EPSRC)

References:

[1] B. Awerbuch, Y. Azar, and A. Epstein, The price of routing unsplittable flow, in Proceedings
of the 37th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York,
2005, pp. 57–66.
[2] M. Beckmann, C. B. McGuire, and C. B. Winston, Studies in the Economics of Transportation,
Yale University Press, New Haven, CT, 1956.
[3] G. Christodoulou and E. Koutsoupias, The price of anarchy of finite congestion games,
in Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC),
ACM, New York, 2005, pp. 67–73.
[4] M. E. Crovella and A. Bestavros, Self-similarity in World Wide Web traffic: Evidence and
possible causes, IEEE/ACM Trans. Networking, 5 (1997), pp. 835–846.
[5] A. Czumaj and B. V¨ocking, Tight bounds for the worst-case equilibria, ACM Trans. Algorithms,
3 (1) (2007), article 4.
[6] F. Douglis, A. Feldmann, B. Krishnamurthy, and J. Mogul, Rate of change and other
metrics: A live study of the World Wide Web, in Proceedings of the 1st USENIX Symposium
on Internet Technologies and Systems, Anaheim, CA, 1997, pp. 147–158.
[7] A. Feldmann, A. C. Gilbert, P. Huang, and W. Willinger, Dynamics of IP traffic: A
study of the role of variability and the impact of control, in Proceedings of the ACM
SIGCOMM Conference on Applications, Technologies, Architectures, and Protocols for
Computer Communication, ACM, New York, 1999, pp. 301–313.
[8] M. Frank, The Braess paradox, Math. Programming, 20 (1981), pp. 283–302.
[9] P. Franken, D. Konig, U. Arndt, and V. Schmidt, Queues and Point Processes, Akademie-
Verlag, Berlin; Wiley, Chichester, UK, 1982.
[10] E. Friedman, Genericity and congestion control in selfish routing, in Proceedings of the 43rd
IEEE Conference on Decision and Control, IEEE Control Systems Society, Piscataway, NJ,
2004, pp. 4667–4672.
[11] D. Gross and C. M. Harris, Fundamentals of Queueing Theory, 3rd ed., John Wiley and
Sons, New York, 1998.
[12] L. Kleinrock, Queueing Systems. Volume I: Theory, John Wiley and Sons, New York, 1975.
[13] Y. A. Korilis, A. A. Lazar, and A. Orda, Capacity allocation under noncooperative routing,
IEEE Trans. Automat. Control, 42 (1997), pp. 309–325.
[14] Y. A. Korilis, A. A. Lazar, and A. Orda, Avoiding the Braess paradox in noncooperative
networks, J. Appl. Probab., 36 (1999), pp. 211–212.
[15] E. Koutsoupias, M. Mavronicolas, and P. Spirakis, Approximate equilibria and ball fusion,
Theory Comput. Syst., 36 (2003), pp. 683–693.
[16] E. Koutsoupias and C. H. Papadimitriou, Worst-case equilibria, in Proceedings of the 16th
Annual Symposium on Theoretical Aspects of Computer Science (STACS), Trier, Germany,
1999, pp. 404–413.
[17] A. A. Lazar, A. Orda, and D. E. Penderakis, Virtual path bandwidth allocation in multiuser
networks, IEEE/ACM Trans. Networking, 5 (1997), pp. 861–871.
[18] M. Mavronicolas and P. Spirakis, The price of selfish routing, Algorithmica, 48 (2007),
pp. 91–126.
[19] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, New
York, 1995.
[20] A. Orda, R. Rom, and N. Shimkin, Competitive routing in multi-user communication networks,
IEEE/ACM Trans. Networking, 1 (1993), pp. 510–521.
[21] C. H. Papadimitriou and M. Yannakakis, On complexity as bounded rationality, in Proceedings
of the 26th Annual ACM Symposium on Theory of Computing (STOC), ACM, New
York, 1994, pp. 726–733.
[22] K. Park, G. Kim, and M. E. Crovella, On the relationship between file sizes, transport
protocols, and self-similar network traffic, in Proceedings of the 4th IEEE International
Conference on Network Protocols, IEEE, Washington, DC, 1996, pp. 171–180.
[23] V. Paxson and S. Floyd, Wide area traffic: The failure of Poisson modeling, IEEE/ACM
Trans. Networking, 3 (1995), pp. 226–244.
[24] T. Roughgarden, Stackelberg scheduling strategies, SIAM J. Comput., 33 (2004), pp. 332–350.
[25] T. Roughgarden, On the severity of Braess’s Paradox: Designing networks for selfish users
is hard, J. Comput. System Sci., 72 (2006), pp. 922–953.
[26] T. Roughgarden, How unfair is optimal routing?, in Proceedings of the 13th Annual ACMSIAM
Symposium on Discrete Algorithms (SODA), ACM, New York, SIAM, Philadelphia,
2002, pp. 203–204.
[27] T. Roughgarden, The price of anarchy is independent of the network topology, J. Comput.
System Sci., 67 (2003), pp. 341–364.
[28] T. Roughgarden, Routing games, in Algorithmic Game Theory, N. Nisan, T. Roughgarden,
´E. Tardos, and V. V. Vazirani, eds., Cambridge University Press, Cambridge, UK, 2007,
pp. 461–486.
[29] T. Roughgarden and ´E. Tardos, How bad is selfish routing?, J. ACM, 49 (2002), pp. 236–259.
[30] T. Roughgarden and ´E. Tardos, Bounding the inefficiency of equilibria in nonatomic congestion
games, Games Econom. Behav., 47 (2004), pp. 389–403.
[31] R. Steinberg andW. I. Zangwill, The prevalence of Braess’ paradox, Transportation Science,
17 (1983), pp. 301–318.
[32] B. V¨ocking, Selfish load balancing, in Algorithmic Game Theory, N. Nisan, T. Roughgarden,
´E. Tardos, and V. V. Vazirani, eds., Cambridge University Press, Cambridge, UK, 2007,
pp. 517–542.
[33] J. G. Wardrop, Some theoretic aspects of road traffic research, Proc. Inst. Civil Engineers
Part II, 1 (1952), pp. 325–378.