Oblivious AQM and Nash Equilibria

Oblivious AQM and Nash Equilibria

Dutta, Debojyoti and Goel, Ashish and Heidemann, John
USC/Information Sciences Institute

Debojyoti Dutta, Ashish Goel and John Heidemann 2003. Oblivious AQM and Nash Equilibria. Proceedings of the IEEE Infocom (San Francisco, California, USA, Mar. 2003), 106–113.

Abstract

An oblivious Active Queue Management scheme is one which does not differentiate between packets belonging to different flows. In this paper, we study the existence and the quality of Nash equilibria imposed by oblivious AQM schemes on selfish agents. Oblivious AQM schemes are of obvious importance because of the ease of implementation and deployment, and Nash equilibrium offers valuable clues into network performance under non-cooperative user behavior. Specifically, we ask the following three questions: 1) Do there exist oblivious AQM schemes that impose Nash equilibria on selfish agents? 2) Are the imposed equilibria, if they exist, efficient in terms of the goodput obtained and the drop probability experienced at the equilibrium? 3) How easy is it for selfish users to reach the Nash equilib- rium state? We assume that the traffic sources are Poisson but the users can control the average rate. We show that drop-tail and RED do not impose Nash equilibria. We modify RED slightly to obtain an oblivious scheme, VLRED, that imposes a Nash equilibrium, but is not efficient. We then present another AQM policy, EN- AQM, that can impose an efficient Nash equilibrium. Finally, we show that for any oblivious AQM, the Nash equilibrium imposed on selfish agents is highly sensitive as the number of agents increases, thus making it hard for the users to converge to the Nash equilibrium, and motivating the need for equilibria- aware protocols.

Reference

@inproceedings{Dutta03a,
  author = {Dutta, Debojyoti and Goel, Ashish and Heidemann, John},
  title = {Oblivious {AQM} and {Nash} Equilibria},
  booktitle = {Proceedings of the  IEEE Infocom},
  year = {2003},
  sortdate = {2003-03-01},
  project = {ant, saman},
  jsubject = {networking},
  publisher = {IEEE},
  address = {San Francisco, California, USA},
  month = mar,
  pages = {106--113},
  location = {johnh: pafile},
  keywords = {router buffer strategies, nash equilibria},
  url = {http://www.isi.edu/%7ejohnh/PAPERS/Dutta03a.html},
  pdfurl = {http://www.isi.edu/%7ejohnh/PAPERS/Dutta03a.pdf},
  otherurl = {http://www.isi.edu/%7eddutta/infocom03.pdf},
  myorganization = {USC/Information Sciences Institute},
  copyrightholder = {IEEE},
  copyrightterms = {
  	Personal use of this material is permitted.  However,
  	permission to reprint/republish this material for advertising
  	or promotional purposes or for creating new collective works
          for resale or redistribution to servers or lists,
  	or to reuse any copyrighted component of this work in other works
  	must be obtained from the IEEE.
  }
}

Copyright

Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.