skip to main content
article

A unified framework for max-min and min-max fairness with applications

Published: 01 October 2007 Publication History

Abstract

Max-min fairness is widely used in various areas of networking. In every case where it is used, there is a proof of existence and one or several algorithms for computing it; in most, but not all cases, they are based on the notion of bottlenecks. In spite of this wide applicability, there are still examples, arising in the context of wireless or peer-to-peer networks, where the existing theories do not seem to apply directly. In this paper, we give a unifying treatment of max-min fairness, which encompasses all existing results in a simplifying framework, and extend its applicability to new examples. First, we observe that the existence of max-min fairness is actually a geometric property of the set of feasible allocations. There exist sets on which max-min fairness does not exist, and we describe a large class of sets on which a max-min fair allo cation does exist. This class contains, but is not limited to the compact, convex sets of RN. Second, we give a general purpose centralized algorithm, called Max-min Programming, for computing the max-min fair allocation in all cases where it exists (whether the set of feasible allocations is in our class or not). Its complexity is of the order of N linear programming steps in RN, in the case where the feasible set is defined by linear constraints. We show that, if the set of feasible allocations has the free disposal property, then Max-min Programming reduces to a simpler algorithm, called Water Filling, whose complexity is much lower. Free disposal corresponds to the cases where a bottleneck argument can be made, andWater Filling is the general form of all previously known centralized algorithms for such cases. All our results apply mutatis mutandis to min-max fairness. Our results apply to weighted, unweighted and util-max-min and min-max fairness. Distributed algorithms for the computation of max-min fair allocations are outside the scope of this paper.

References

[1]
{1} A. Charny, "An algorithm for rate allocation in a packet-switched network with feedback," M.S. thesis, MIT, Cambridge, MA, May 1994.
[2]
{2} A. Mas-Colell, M. Whinston, and J. Green, Microeconomic Theory. Oxford, U.K.: Oxford Univ. Press, 1995.
[3]
{3} Traffic Management Specification-Version 4.0, Feb. 1996, ATM Forum/95-0013R13, ATM Forum Technical Committee.
[4]
{4} W. Bossert and J. A. Weymark, "Utility in social choice," in Handbook of Utility Theory, S. Barbera, P. J. Hammond, and C. Seidl, Eds. Boston, MA: Kluwer Academic, 2004.
[5]
{5} M. A. Chen, "Individual monotonicity and the leximin solution," Economic Theory, vol. 15, pp. 353-365, 2000.
[6]
{6} R. Cruz and A. V. Santhanam, "Optimal routing, link scheduling and power control in multi-hop wireless networks," in Proc. IEEE INFOCOM, 2003, pp. 702-711.
[7]
{7} D. Bertsekas and R. Gallager, Data Networks. Englewood Cliffs, NJ: Prentice-Hall, 1987.
[8]
{8} D. Rubenstein, J. Kurose, and D. Towsley, "The impact of multicast layering on network fairness," IEEE/ACM Trans. Networking, vol. 10, no. 2, pp. 169-182, Apr. 2002.
[9]
{9} E. Hahne, "Round-robin scheduling for max-min fairness in data networks," IEEE J. Sel. Areas Commun., vol. 9, no. 7, pp. 1024-1039, Sep. 1991.
[10]
{10} H. Tzeng and K. Siu, "On max-min fair congestion control for multicast ABR service in ATM," IEEE J. Sel. Areas Commun., vol. 15, no. 3, pp. 545-556, Apr. 1997.
[11]
{11} J. Byers, "A digital fountain approach to reliable distribution of bulk data," in Proc. ACM SIGCOMM'98, Vancouver, Canada, Sep. 1998.
[12]
{12} J. Ros and W. Tsai, "A theory of convergence order of maxmin rate allocation and an optimal protocol," in Proc. IEEE INFOCOM, 2001, pp. 717-726.
[13]
{13} J. H. Chang and L. Tassiulas, "Energy conserving routing in wireless ad-hoc networks," in Proc. IEEE INFOCOM, 2000, pp. 22-31.
[14]
{14} L. Georgadis, "Lexicographically optimal balanced networks," in Proc. IEEE INFOCOM, 2001, pp. 689-698.
[15]
{15} L. Tassiulas and S. Sarkar, "Maxmin fair scheduling in wireless networks," in Proc. IEEE INFOCOM, 2002, pp. 763-772.
[16]
{16} A. L. McKellips and S. Verdu, "Maximin performance of binary-input channels with uncertain noise distributions," IEEE Trans. Inf. Theory, vol. 44, no. 3, pp. 947-972, May 1998.
[17]
{17} P. Marbach, "Priority service and max-min fairness," in Proc. IEEE INFOCOM, 2002, pp. 266-275.
[18]
{18} B. Radunovic and J.-Y. Le Boudec, "Optimal power control, scheduling and routing in UWB networks," IEEE J. Sel. Areas Commun., vol. 22, no. 7, pp. 1252-1270, Sep. 2004.
[19]
{19} B. Radunovic and J.-Y. Le Boudec, "Power control is not required for wireless networks in the linear regime," in Proc. 6th IEEE Int. Symp. World ofWireless Mobile and Multimedia Networks (WoWMoM 2005), Jun. 2005, pp. 417-427.
[20]
{20} B. Radunovic and J.-Y. Le Boudec, "Aunified framework for Max-Min and Min-Max Fairness with applications," EPFL, Tech. Rep. LCA-REPORT-2006-001, Jan. 2006.
[21]
{21} J. Rawls, A Theory of Justice. Cambridge, MA: Harvard Univ. Press, 1971.
[22]
{22} V. Rodoplu and T. H. Meng, "Minimum energy mobile wireless networks," IEEE J. Sel. Areas Commun., vol. 17, no. 8, pp. 1333-1344, Aug. 1999.
[23]
{23} S. Sarkar and L. Tassiulas, "Fair allocation of discrete bandwidth layers in multicast networks," in Proc. IEEE INFOCOM, 2000, pp. 1491-1500.
[24]
{24} J. Van Leeuwen, "Graph algorithms," in Algorithms and Complexity, J. Van Leeuwen, Ed. New York: Elsevier, 1992.
[25]
{25} M. Win and R. Scholtz, "Ultra-wide bandwidth time-hopping spread-spectrum impulse radio for wireless multiple-access communications," IEEE Trans. Commun., vol. 48, no. 4, pp. 679-691, Apr. 2000.
[26]
{26} X. L. Huang and B. Bensaou, "On max-min fairness and scheduling in wireless ad-hoc networks: Analytical framework and implementation," in Proc. MobiHoc'01, Long Beach, CA, Oct. 2001.
[27]
{27} Y. Hou, H. Tzeng, and S. Panwar, "A generalized max-min rate allocation policy and its distributed implementation using the ABR flow control mechanism," in Proc. IEEE INFOCOM, 1998, pp. 1366-1375.
[28]
{28} Z. Cao and E. Zegura, "Utility max-min: An application-oriented bandwidth allocation scheme," in Proc. IEEE INFOCOM, 1999, pp. 793-801.

Cited By

View all
  • (2025)Cooperative Graceful Degradation in Containerized CloudsProceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 110.1145/3669940.3707244(214-232)Online publication date: 3-Feb-2025
  • (2025)Channel Cycle Time: A New Measure of Short-Term FairnessIEEE Transactions on Mobile Computing10.1109/TMC.2024.348417724:3(1386-1401)Online publication date: 1-Mar-2025
  • (2024)Fair resource allocation in multi-task learningProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692179(2715-2731)Online publication date: 21-Jul-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 15, Issue 5
October 2007
235 pages

Publisher

IEEE Press

Publication History

Published: 01 October 2007
Published in TON Volume 15, Issue 5

Author Tags

  1. best-effort traffic
  2. elastic traffic
  3. mathematical programming/optimization
  4. max-min fairness
  5. system design

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)0
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2025)Cooperative Graceful Degradation in Containerized CloudsProceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 110.1145/3669940.3707244(214-232)Online publication date: 3-Feb-2025
  • (2025)Channel Cycle Time: A New Measure of Short-Term FairnessIEEE Transactions on Mobile Computing10.1109/TMC.2024.348417724:3(1386-1401)Online publication date: 1-Mar-2025
  • (2024)Fair resource allocation in multi-task learningProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692179(2715-2731)Online publication date: 21-Jul-2024
  • (2024)Fairness in serving large language modelsProceedings of the 18th USENIX Conference on Operating Systems Design and Implementation10.5555/3691938.3691990(965-988)Online publication date: 10-Jul-2024
  • (2024)Solving max-min fair resource allocations quickly on large graphsProceedings of the 21st USENIX Symposium on Networked Systems Design and Implementation10.5555/3691825.3691931(1937-1958)Online publication date: 16-Apr-2024
  • (2024)Probabilistic Bounds on the k-Traveling Salesman Problem and the Traveling Repairman ProblemMathematics of Operations Research10.1287/moor.2021.028649:2(1169-1191)Online publication date: 1-May-2024
  • (2024)DNS Congestion Control in Adversarial SettingsProceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles10.1145/3694715.3695982(726-747)Online publication date: 4-Nov-2024
  • (2024)Impossibility Results for Data-Center Routing with Congestion Control and Unsplittable FlowsProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662777(358-368)Online publication date: 17-Jun-2024
  • (2024)Fair Resource Allocation in Virtualized O-RAN PlatformsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/36390438:1(1-34)Online publication date: 21-Feb-2024
  • (2024)IF-City: Intelligible Fair City Planning to Measure, Explain and Mitigate InequalityIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.323990930:7(3749-3766)Online publication date: 1-Jul-2024
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media