ALCOMFT-TR-02-25

Artur Czumaj, Piotr Krysta and Berthold Voecking
Selfish Traffic Allocation for Server Farms
MPI. Work packages 2 and 4. May 2002.

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 functions 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.

Postscript file: ALCOMFT-TR-02-25.ps.gz (138 kb).