Selfish Routing of Splittable Flow with Respect to Maximum Congestion

Author Rainer Feldmann



PDF
Thumbnail PDF

File

DagSemProc.05011.15.pdf
  • Filesize: 262 kB
  • 12 pages

Document Identifiers

Author Details

Rainer Feldmann

Cite AsGet BibTex

Rainer Feldmann. Selfish Routing of Splittable Flow with Respect to Maximum Congestion. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)
https://doi.org/10.4230/DagSemProc.05011.15

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.
Keywords
  • selfish routing
  • coordination ratio

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail