MPI-INF/SWS Research Reports 1991-2021

1. Author,Editor - 3. with BibTeX cite keys


Selfish traffic allocation for server farms

Krysta, Piotr and Czumaj, Artur and Voecking, Berthold

April 2003, 43 pages.

Status: available - back from printing

We study the price of selfish routing in non-cooperative networks like the Internet. In particular, we investigate the price of selfish routing using the coordination ratio and other (e.g., bicriteria) measures in the recently introduced game theoretic network model of Koutsoupias and Papadimitriou. We generalize this model towards 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 those cost functions that have a bounded/unbounded coordination ratio. For example, the coordination ratio for cost functions describing the expected delay in queueing systems is unbounded. (2) In addition, we show that an unbounded coordination ratio implies an extremely high performance degradation under bicriteria measures as well. 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, in fact 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 coordination ratio under the min-max objective implies an unbounded coordination ratio 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 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. We come to the conclusion that 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.

  • Attachement: (405 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Krysta, Piotr and Czumaj, Artur and Voecking, Berthold},
  TITLE = {Selfish traffic allocation for server farms},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2003-1-011},
  MONTH = {April},
  YEAR = {2003},
  ISSN = {0946-011X},