MPI-I-2003-1-011. April 2003, 43 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry
Abstract in LaTeX format:
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.
References to related material:
|To download this research report, please select the type of document that fits best your needs.||Attachement Size(s):|
|Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView|