{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T11:33:36Z","timestamp":1774352016325,"version":"3.50.1"},"reference-count":13,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,2,28]],"date-time":"2017-02-28T00:00:00Z","timestamp":1488240000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["822-10 and 1841-14"],"award-info":[{"award-number":["822-10 and 1841-14"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100005386","name":"Israeli Centers of Research Excellence (I-CORE) program","doi-asserted-by":"crossref","award":["4\/11"],"award-info":[{"award-number":["4\/11"]}],"id":[{"id":"10.13039\/501100005386","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Israel Ministry of Science and Technology"},{"DOI":"10.13039\/501100001736","name":"German-Israeli Foundation for Scientific Research and Development","doi-asserted-by":"crossref","award":["1161\/2011"],"award-info":[{"award-number":["1161\/2011"]}],"id":[{"id":"10.13039\/501100001736","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2017,2,28]]},"abstract":"<jats:p>Often one would like to allocate shared resources in a fair way. A common and well-studied notion of fairness is<jats:italic>Max-Min Fairness<\/jats:italic>, where we first maximize the smallest allocation, and subject to that the second smallest, and so on. We consider a networking application where multiple commodities compete over the capacity of a network. In our setting, each commodity has multiple possible paths to route its demand (for example, a network using Multiprotocol Label Switching (MPLS) tunneling). In this setting, the only known way of finding a max-min fair allocation requires an iterative solution of multiple linear programs. Such an approach, although polynomial time, scales badly with the size of the network, the number of demands, and the number of paths, and is hard to implement in a distributed environment. More importantly, a network operator has limited control and understanding of the inner working of the algorithm.<\/jats:p><jats:p>In this article we introduce Upward Max-Min Fairness, a novel relaxation of Max-Min Fairness, and present a family of simple dynamics that converge to it. These dynamics can be implemented in a distributed manner. Moreover, we present an efficient combinatorial algorithm for finding an upward max-min fair allocation. This algorithm is a natural extension of the well-known Water Filling Algorithm for a multiple path setting.<\/jats:p><jats:p>We test the expected behavior of this new algorithm and show that on realistic networks upward max-min fair allocations are comparable to the max-min fair allocations both in fairness and in network utilization.<\/jats:p>","DOI":"10.1145\/3011282","type":"journal-article","created":{"date-parts":[[2017,3,24]],"date-time":"2017-03-24T14:54:11Z","timestamp":1490367251000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Upward Max-Min Fairness"],"prefix":"10.1145","volume":"64","author":[{"given":"Emilie","family":"Danna","sequence":"first","affiliation":[{"name":"Google"}]},{"given":"Avinatan","family":"Hassidim","sequence":"additional","affiliation":[{"name":"Google"}]},{"given":"Haim","family":"Kaplan","sequence":"additional","affiliation":[{"name":"Tel Aviv University"}]},{"given":"Alok","family":"Kumar","sequence":"additional","affiliation":[{"name":"Google"}]},{"given":"Yishay","family":"Mansour","sequence":"additional","affiliation":[{"name":"Tel Aviv University and Microsoft Research"}]},{"given":"Danny","family":"Raz","sequence":"additional","affiliation":[{"name":"Technion"}]},{"given":"Michal","family":"Segalov","sequence":"additional","affiliation":[{"name":"Google"}]}],"member":"320","published-online":{"date-parts":[[2017,3,24]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Y. Afek Y. Mansour and Z. Ostfeld. 1996. On the convergence of rate based flow control. In STOC. 106--143. Y. Afek Y. Mansour and Z. Ostfeld. 1996. On the convergence of rate based flow control. In STOC. 106--143."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2007.905605"},{"key":"e_1_2_1_3_1","unstructured":"D. Bertsekas and R. Gallager. 2001. Data Networks. Prentice-Hall Englewood Cliffs NJ. D. Bertsekas and R. Gallager. 2001. Data Networks. Prentice-Hall Englewood Cliffs NJ."},{"key":"e_1_2_1_4_1","volume-title":"Dinitz","author":"Dinitz Y.","unstructured":"Y. Dinitz . 2006. Dinitz \u2019 algorithm: The original version and Even\u2019s version. In Essays in Memory of Shimon Even . 218--240. Y. Dinitz. 2006. Dinitz\u2019 algorithm: The original version and Even\u2019s version. In Essays in Memory of Shimon Even. 218--240."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199355754"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446232"},{"key":"e_1_2_1_7_1","unstructured":"R. Jain D. Chiu and W. Hawe. 1998. A quantitative measure of fairness and discrimination for resource allocation in shared computer systems. Computing Research Repository cs.NI\/9809 (1998). R. Jain D. Chiu and W. Hawe. 1998. A quantitative measure of fairness and discrimination for resource allocation in shared computer systems. Computing Research Repository cs.NI\/9809 (1998)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2534169.2486019"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SURV.2008.080403"},{"key":"e_1_2_1_10_1","volume-title":"40th Annual Allerton Conference on Communication, Control, and Computing.","author":"Radunovic B.","unstructured":"B. Radunovic and J. Le Boudec . 2002. A unified framework for max-min and min-max fairness with applications . In 40th Annual Allerton Conference on Communication, Control, and Computing. B. Radunovic and J. Le Boudec. 2002. A unified framework for max-min and min-max fairness with applications. In 40th Annual Allerton Conference on Communication, Control, and Computing."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/COMST.2008.4483669"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/49.12889"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"E. Zegura K. Calvert and S. Bhattacharjee. 1996. How to model an internetwork. In INFOCOM. 594--602. E. Zegura K. Calvert and S. Bhattacharjee. 1996. How to model an internetwork. In INFOCOM. 594--602.","DOI":"10.1109\/INFCOM.1996.493353"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3011282","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3011282","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:05:28Z","timestamp":1750273528000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3011282"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,28]]},"references-count":13,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,2,28]]}},"alternative-id":["10.1145\/3011282"],"URL":"https:\/\/doi.org\/10.1145\/3011282","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,2,28]]},"assertion":[{"value":"2015-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}