License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.05011.15
URN: urn:nbn:de:0030-drops-1991
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2005/199/
Go to the corresponding Portal

Feldmann, Rainer

Selfish Routing of Splittable Flow with Respect to Maximum Congestion

pdf-format:
05011.FeldmannRainer.ExtAbstract.pdf (0.3 MB)

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 KP-model \cite{KP99} and the
Wardrop-model \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 single-commodity 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
single-commodity networks with linear latency functions.
On our way to our main result we analyze the coordination ratio of
single-hop 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 multi-hop networks,
which is then used to derive the main result for arbitrary
single-commodity linear networks.

BibTeX - Entry

@InProceedings{feldmann:DagSemProc.05011.15,
  author =	{Feldmann, Rainer},
  title =	{{Selfish Routing of Splittable Flow with Respect to Maximum Congestion}},
  booktitle =	{Computing and Markets},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5011},
  editor =	{Daniel Lehmann and Rudolf M\"{u}ller and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2005/199},
  URN =		{urn:nbn:de:0030-drops-1991},
  doi =		{10.4230/DagSemProc.05011.15},
  annote =	{Keywords: selfish routing , coordination ratio}
}

Keywords: selfish routing , coordination ratio
Collection: 05011 - Computing and Markets
Issue Date: 2005
Date of publication: 19.07.2005

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI