Competitive routing in networks with polynomial cost

Eitan Altman, Tania Jiménez, Tamer Başar, Nahum Shimkin

Abstract

We study a class of noncooperative general topology networks shared by N users. Each user has a given flow which it has to ship from a source to a destination. We consider a class of polynomial link cost functions, adopted originally in the context of road traffic modeling, and show that these costs have appealing properties that lead to predictable and efficient network flows. In particular, we show that the Nash equilibrium is unique, and is moreover efficient, i.e., it coincides with the solution of a corresponding global optimization problem with a single user. These properties make the cost structure attractive for traffic regulation and link pricing in telecommunication networks. We finally discuss the computation of the equilibrium in the special case of the affine cost structure for a topology of parallel links.
BibTeX
@inproceedings{altman2000competitive,
  author = {Eitan Altman and Tania Jiménez and Tamer Başar and Nahum Shimkin},
  title = {{Competitive routing in networks with polynomial cost}},
  booktitle = {INFOCOM},
  year = {2000},
  doi = {10.1109/infcom.2000.832557},
}

Loading related content...

Figure