Nash equilibria for combined flow control and routing in networks: Asymptotic behavior for a large number of users

Eitan Altman, Tamer Başar, R. Srikant

Research output: Contribution to journalArticle

Abstract

We consider a noncooperative game framework for combined routing and flow control in a network of parallel links, where the number of users (players) is arbitrarily large. The utility function of each user is related to the power criterion, and is taken as the ratio of some positive power of the total throughput of that user to the average delay seen by the user. The utility function is nonconcave in the flow rates of the user, for which we introduce a scaling to make it well defined as the number of users, N, becomes arbitrarily large. In spite of the lack of concavity, we obtain explicit expressions for the flow rates of the users and their associated routing decisions, which are in O(1/N) Nash equilibrium. This O (1/N) equilibrium solution, which is symmetric across different users and could be multiple in some cases, exhibits a delay-equalizing feature among the links which carry positive flow. The paper also provides the complete optimal solution to the single-user ease, and includes several numerical examples to illustrate different features of the solutions in the single- as well as N-user cases, as N becomes arbitrarily large.

Original languageEnglish (US)
Pages (from-to)917-930
Number of pages14
JournalIEEE Transactions on Automatic Control
Volume47
Issue number6
DOIs
StatePublished - Jun 1 2002

Keywords

  • Asymptotic Nash equilibria
  • Flow control
  • Networks
  • Noncooperative equilibria
  • Nonzero-sum games
  • Routing

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Nash equilibria for combined flow control and routing in networks: Asymptotic behavior for a large number of users'. Together they form a unique fingerprint.

  • Cite this