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

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 R^N. 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 R^N, 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: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 8: Dan Rubenstein , Jim Kurose , Don Towsley, The impact of multicast layering on network fairness, IEEE/ACM Transactions on Networking (TON), v.10 n.2, April 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: John W. Byers , Michael Luby , Michael Mitzenmacher , Ashutosh Rege, A digital fountain approach to reliable distribution of bulk data, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.56-67, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 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: Bozidar Radunovic , Jean-Yves Le Boudec, Power Control is not Required for Wireless Networks in the Linear Regime, Proceedings of the Sixth IEEE International Symposium on World of Wireless Mobile and Multimedia Networks, p.417-427, June 13-16, 2005 [doi>10.1109/WOWMOM.2005.79]
• 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: Xiao Long Huang , Brahim Bensaou, On max-min fairness and scheduling in wireless ad-hoc networks: analytical framework and implementation, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501445.501447]
• 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.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Minimax approximation and algorithms
      G.1.6 Optimization
          Subjects: Linear programming

General Terms:
Algorithms, Design

Keywords:
best-effort traffic, elastic traffic, mathematical programming/optimization, max-min fairness, system design