Low State Fairness: Lower Bounds and Practical Enforcement
Debojyoti Dutta, Abhimanyu Das, Ashish Goel, Ahmed Helmy, and John HeidemannUSC/Information Sciences Institute
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.Availability
This paper is available in several formats: abstract web page with pointers and cites, PDF, paper copies can be obtained by mail to the authors. Copyright terms for this paper appear below.
Reference
- Dutta05a
- Debojyoti Dutta, Abhimanyu Das, Ashish Goel, Ahmed Helmy, and John Heidemann. Low State Fairness: Lower Bounds and Practical Enforcement. In Proceedings of the IEEE Infocom, p. to appear. Miami, Florida, USA, IEEE. March, 2005. <http://www.isi.edu/~johnh/PAPERS/Dutta05a.html>.
@inproceedings{Dutta05a,
author = "Debojyoti Dutta and Abhimanyu Das and Ashish Goel and Ahmed Helmy and John Heidemann",
title = "Low State Fairness: Lower Bounds and Practical Enforcement",
booktitle = "Proceedings of the {IEEE} Infocom",
year = "2005",
publisher = "{IEEE}",
address = "Miami, Florida, USA",
month = "March",
pages = "to appear",
url = "http://www.isi.edu/~johnh/PAPERS/Dutta05a.html",
pdfurl = "http://www.isi.edu/~johnh/PAPERS/Dutta05a.pdf",
myorganization = "USC/Information Sciences Institute",
copyrightholder = "{IEEE}",
}