Feldmann, Rainer
Selfish Routing of Splittable Flow with Respect to Maximum Congestion
Abstract
We study the problem of selfishly routing
splittable traffic with respect to maximum congestion through a shared
network.
Our model naturally combines features of the two best studied
models in the context of selfish routing: The KPmodel \cite{KP99} and the
Wardropmodel \cite{War52}.
We are given a network with source nodes $s_i$, sink
nodes $t_i$, $1 \leq i \leq k$, $m$ edges,
and a latency function for each edge. Traffics of rate
$r_i$ are destined from $s_i$ to $t_i$.
Traffics are splittable and each piece of traffic tries to route in
such a way that it minimizes its private latency.
In the absence of a central regulation, Nash Equilibria represent
stable states of such a system. In a Nash Equilibrium, no
piece of traffic can decrease its private latency by
unilaterally changing its route. The increased social cost due to
the lack of central regulation is defined in terms of the
coordination ratio, i.e. the worst
possible ratio of the social cost of a traffic flow at Nash
Equilibrium and the social cost of a global optimal traffic flow.
In this paper,
we show that in the above model pure Nash Equilibria always exist.
Then, we analyze the coordination ratio of singlecommodity networks with
linear latency functions.
Our main result is a tight upper bound of $\frac{4}{3} m$, where $m$
is the number of edges of the network, for the coordination ratio of
singlecommodity networks with linear latency functions.
On our way to our main result we analyze the coordination ratio of
singlehop networks and show a tight upper bound of
$m+\Theta(\sqrt{m})$. A more sophisticated analysis yields an upper
bound of $\frac{4}{3}m$ for the coordination ratio of multihop networks,
which is then used to derive the main result for arbitrary
singlecommodity linear networks.
BibTeX  Entry
@InProceedings{feldmann:DSP:2005:199,
author = {Rainer Feldmann},
title = {Selfish Routing of Splittable Flow with Respect to Maximum Congestion},
booktitle = {Computing and Markets},
year = {2005},
editor = {Daniel Lehmann and Rudolf M{\"u}ller and Tuomas Sandholm},
number = {05011},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Internationales Begegnungs und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2005/199},
annote = {Keywords: selfish routing , coordination ratio}
}
19.07.2005
Keywords: 

selfish routing , coordination ratio 
Seminar: 

05011  Computing and Markets

Issue date: 

2005 
Date of publication: 

19.07.2005 