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. doi:10.1137/070693862

PDF WRAP_Cjumaz_Selfish_traffic.pdf - Requires a PDF viewer. Download (393Kb)

Request Changes to record.

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
DOI:	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)

Data sourced from Thomson Reuters' Web of Knowledge

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads