Competitive routing in networks with polynomial cost

Eitan Altman, Tania Jimenez, Tamer Basar, Nahum Shimkin

Research output: Contribution to journalConference articlepeer-review


We study a class of noncooperative general topology networks shared by N users. Each user has a given flow while 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.

Original languageEnglish (US)
Pages (from-to)1586-1593
Number of pages8
JournalProceedings - IEEE INFOCOM
StatePublished - 2000
Externally publishedYes
Event19th Annual Joint Conference of the IEEE Computer and Communications Societies - IEEE INFOCOM2000: 'Reaching the Promised Land of Communications' - Tel Aviv, Isr
Duration: Mar 26 2000Mar 30 2000

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'Competitive routing in networks with polynomial cost'. Together they form a unique fingerprint.

Cite this