Low State Fairness: Lower Bounds and Practical Enforcement. Dutta, D., Das, A., Goel, A., Helmy, A., & Heidemann, J. In Proceedings of the IEEE Infocom, pages to appear, Miami, Florida, USA, March, 2005. IEEE. Paper abstract bibtex 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.
@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,
sortdate = "2005-03-01",
project = "ant, saman",
jsubject = "networking",
publisher = "IEEE",
address = "Miami, Florida, USA",
month = mar,
pages = "to appear",
jlocation = "johnh: pafile xxx",
url = "https://ant.isi.edu/%7ejohnh/PAPERS/Dutta05a.html",
pdfurl = "https://ant.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. ",
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.
",
}
Downloads: 0
{"_id":"zSpT6gFHZ7Niox3rT","bibbaseid":"dutta-das-goel-helmy-heidemann-lowstatefairnesslowerboundsandpracticalenforcement-2005","author_short":["Dutta, D.","Das, A.","Goel, A.","Helmy, A.","Heidemann, J."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Debojyoti"],"propositions":[],"lastnames":["Dutta"],"suffixes":[]},{"firstnames":["Abhimanyu"],"propositions":[],"lastnames":["Das"],"suffixes":[]},{"firstnames":["Ashish"],"propositions":[],"lastnames":["Goel"],"suffixes":[]},{"firstnames":["Ahmed"],"propositions":[],"lastnames":["Helmy"],"suffixes":[]},{"firstnames":["John"],"propositions":[],"lastnames":["Heidemann"],"suffixes":[]}],"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":"March","pages":"to appear","jlocation":"johnh: pafile xxx","url":"https://ant.isi.edu/%7ejohnh/PAPERS/Dutta05a.html","pdfurl":"https://ant.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. ","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. ","bibtex":"@InProceedings{Dutta05a,\n\tauthor = \"Debojyoti Dutta and Abhimanyu Das and Ashish Goel and Ahmed Helmy and John Heidemann\",\n\ttitle = \t\"Low State Fairness: Lower Bounds and Practical Enforcement\",\n\tbooktitle = \t\"Proceedings of the \" # \" IEEE Infocom\",\n\tyear = \t\t2005,\n\tsortdate = \"2005-03-01\",\n\tproject = \"ant, saman\",\n\tjsubject = \"networking\",\n\tpublisher =\t\"IEEE\",\n\taddress =\t\"Miami, Florida, USA\",\n\tmonth =\t\tmar,\n\tpages =\t\t\"to appear\",\n\tjlocation =\t\"johnh: pafile xxx\",\n\turl =\t\t\"https://ant.isi.edu/%7ejohnh/PAPERS/Dutta05a.html\",\n\tpdfurl =\t\"https://ant.isi.edu/%7ejohnh/PAPERS/Dutta05a.pdf\",\n\tmyorganization =\t\"USC/Information Sciences Institute\",\n\tcopyrightholder = \"IEEE\",\n\tcopyrightterms = \"\tPersonal use of this material is permitted. However, \tpermission to reprint/republish this material for advertising \tor promotional purposes or for creating new collective works for resale or redistribution to servers or lists, \tor to reuse any copyrighted component of this work in other works \tmust be obtained from the IEEE. \",\n\tabstract = \"\nProviding approximate max-min fair bandwidth allocation among flows\nwithin a network or at a single router has been an important research\nproblem. In this paper, we study the space complexity of fairness\nalgorithms, and the communication complexity of distributed global\nfairness algorithms. We show that in order to enforce max-min fairness\nwith bounded errors, a router must maintain per-flow state. Then we\npresent a practical edge-marking based architecture to demonstrate the\nenforcement of approximate global max-min fairness for representative\nscenarios with multiple bottlenecks and non-responsive traffic. We\nvalidate our architecture using packet level simulations.\n\",\n}\n\n","author_short":["Dutta, D.","Das, A.","Goel, A.","Helmy, A.","Heidemann, J."],"bibbaseid":"dutta-das-goel-helmy-heidemann-lowstatefairnesslowerboundsandpracticalenforcement-2005","role":"author","urls":{"Paper":"https://ant.isi.edu/%7ejohnh/PAPERS/Dutta05a.html"},"metadata":{"authorlinks":{}}},"bibtype":"inproceedings","biburl":"https://bibbase.org/f/dHevizJoWEhWowz8q/johnh-2023-2.bib","dataSources":["YLyu3mj3xsBeoqiHK","fLZcDgNSoSuatv6aX","fxEParwu2ZfurScPY","7nuQvtHTqKrLmgu99"],"keywords":[],"search_terms":["low","state","fairness","lower","bounds","practical","enforcement","dutta","das","goel","helmy","heidemann"],"title":"Low State Fairness: Lower Bounds and Practical Enforcement","year":2005}