License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-1991
URL: http://drops.dagstuhl.de/opus/volltexte/2005/199/

Feldmann, Rainer

Selfish Routing of Splittable Flow with Respect to Maximum Congestion

pdf-format:
Dokument 1.pdf (263 KB)


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: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 =	{1862-4405},
  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}
}

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


DROPS-Home | Fulltext Search | Imprint Published by LZI