Low State Fairness: Lower Bounds and Practical Enforcement

Low State Fairness: Lower Bounds and Practical Enforcement

Dutta, Debojyoti and Das, Abhimanyu and Goel, Ashish and Helmy, Ahmed and Heidemann, John
USC/Information Sciences Institute

Debojyoti Dutta, Abhimanyu Das, Ashish Goel, Ahmed Helmy and John Heidemann 2005. Low State Fairness: Lower Bounds and Practical Enforcement. Proceedings of the IEEE Infocom (Miami, Florida, USA, Mar. 2005), to appear.

Abstract

Providing approximate max-min fair bandwidth allocation among flows within a network or at a single router has been an important research problem. In this paper, we study the space complexity of fairness algorithms, and the communication complexity of distributed global fairness algorithms. We show that in order to enforce max-min fairness with bounded errors, a router must maintain per-flow state. Then we present a practical edge-marking based architecture to demonstrate the enforcement of approximate global max-min fairness for representative scenarios with multiple bottlenecks and non-responsive traffic. We validate our architecture using packet level simulations.

Reference

@inproceedings{Dutta05a,
  author = {Dutta, Debojyoti and Das, Abhimanyu and Goel, Ashish and Helmy, Ahmed and Heidemann, John},
  title = {Low State Fairness: Lower Bounds and Practical Enforcement},
  booktitle = {Proceedings of the  IEEE Infocom},
  year = {2005},
  sortdate = {2005-03-01},
  project = {ant, saman},
  jsubject = {networking},
  publisher = {IEEE},
  address = {Miami, Florida, USA},
  month = mar,
  pages = {to appear},
  location = {johnh: pafile xxx},
  url = {http://www.isi.edu/%7ejohnh/PAPERS/Dutta05a.html},
  pdfurl = {http://www.isi.edu/%7ejohnh/PAPERS/Dutta05a.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.