Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We analyze several distributed, continuous time protocols for a fair allocation of bandwidths to flows in a network (or resources to agents). Our protocols converge to an allocation which is a logarithmic approximation, simultaneously, to all canonical social welfare functions (i.e. functions which are symmetric, concave, and non-decreasing). These protocols can be started in an arbitrary state. While a similar protocol was known before, it only applied to the simple bandwidth allocation problem, and its stability and convergence time was not understood. In contrast, our protocols also apply to the more general case of Leontief utilities, where each user may place a different requirement on each resource. Further, we prove that our protocols converge in polynomial time. The best convergence time we prove is O(n log ^nc_max^a_max/^c_min^a_min), where n is the number of agents in the network, c_max and c_min are the maximum and minimum capacity of the links, and a_max, a_min are the largest and smallest Leontief coefficients, respectively. This time is achieved by a simple MIMD (multiplicative increase, multiplicative decrease) protocol which had not been studied before in this setting. We also identify combinatorial properties of these protocols that may be useful in proving stronger convergence bounds. The final allocations by our protocols are supported by usage-sensitive dual prices which are fair in the sense that they shield light users of a resource from the impact of heavy users. Thus our protocols can also be thought of as efficient distributed schemes for computing fair prices.

REFERENCES

• 1: Yair Bartal , John W. Byers , Danny Raz, Global Optimization Using Local Information with Applications to Flow Control, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.303, October 19-22, 1997
• 2: Rishi Bhargava , Ashish Goel , Adam Meyerson, Using approximate majorization to characterize protocol fairness, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.330-331, June 2001, Cambridge, Massachusetts, United States [doi>10.1145/378420.378826]
• 3: Niv Buchbinder , Joseph (Seffi) Naor, Fair online load balancing, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148159]
• 4: Niv Buchbinder , Joseph (Seffit) Naor, Improved Bounds for Online Routing and Packing Via a Primal-Dual Approach, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.293-304, October 21-24, 2006 [doi>10.1109/FOCS.2006.39]
• 5: Xi Chen , Xiaotie Deng, Settling the Complexity of Two-Player Nash Equilibrium, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.261-272, October 21-24, 2006 [doi>10.1109/FOCS.2006.69]
• 6: S. Cho and A. Goel. Bandwidth allocation in networks: a single dual-update subroutine for multiple objectives. Proceedings of the first Workshop on Combinatorial and Algorithmic Aspects of Networks, 3405:28--41, 2004.
• 7: Sung-woo Cho , Ashish Goel, Pricing for fairness: distributed resource allocation for multiple objectives, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132545]
• 8: B. Codenotti, B. McCune, S. Penumatcha, and k. Varadarajan. Market equilibrium for ces exchange economies: Existence, multiplicity, and computation. FSTTCS, 2005.
• 9: Bruno Codenotti , Amin Saberi , Kasturi Varadarajan , Yinyu Ye, Leontief economies encode nonzero sum two-player games, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.659-667, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109629]
• 10: Constantinos Daskalakis , Paul W. Goldberg , Christos H. Papadimitriou, The complexity of computing a Nash equilibrium, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132527]
• 11: Nikhil R. Devanur , Christos H. Papadimitriou , Amin Saberi , Vijay V. Vazirani, Market Equilibrium via a Primal-Dual-Type Algorithm, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.389-395, November 16-19, 2002
• 12: Naveen Garg , Jochen Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems., Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.300, November 08-11, 1998
• 13: A. Goel and A. Meyerson. Simultaneous optimization via approximate majorization for concave profits or convex costs. Algorithmica, 44(4):301--323, May 2006.
• 14: Ashish Goel , Adam Meyerson , Serge Plotkin, Combining fairness with throughout: online routing with multiple objectives, Journal of Computer and System Sciences, v.63 n.1, p.62-79, August 2001 [doi>10.1006/jcss.2001.1755]
• 15: Ashish Goel , Adam Meyerson , Serge Plotkin, Approximate majorization and fair online load balancing, ACM Transactions on Algorithms (TALG), v.1 n.2, p.338-349, October 2005 [doi>10.1145/1103963.1103970]
• 16: G. H. Hardy, J. E. Littlewood, and G. Polya. Some simple inequalities satisfied by convex functions. Messenger Math., 58:145--152, 1929.
• 17: G. H. Hardy, J. E. Littlewood, and G. Polya. Inequalities. 1st ed., 2nd ed. Cambridge University Press, London and New York., 1934, 1952.
• 18: F. P. Kelly, A. K. Maulloo, and D. K. H. Tan. Rate control in communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society, 49:237--252, 1998.
• 19: Jon Kleinberg , Yuval Rabani , Éva Tardos, Fairness in routing and load balancing, Journal of Computer and System Sciences, v.63 n.1, p.2-20, August 2001 [doi>10.1006/jcss.2001.1752]
• 20: A. Kumar , J. Kleinberg, Fairness measures for resource allocation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.75, November 12-14, 2000
• 21: Steven H. Low , Larry Peterson , Limin Wang, Understanding TCP vegas: a duality model, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.226-235, June 2001, Cambridge, Massachusetts, United States [doi>10.1145/378420.378787]
• 22: A. W. Marshall and I. Olkin. Inequalities: theory of majorization and its applications. Academic Press (Volume 143 of Mathematics in Science and Engineering), 1979.
• 23: Serge A. Plotkin , David B. Shmoys , Éva Tardos, Fast approximation algorithms for fractional packing and covering problems, Mathematics of Operations Research, v.20 n.2, p.257-301, May 1995 [doi>10.1287/moor.20.2.257]
• 24: Y. Ye. A note on exchange market equilibria with leontief's utility: Freedom of pricing leads to rationality. Proceeding of The 1st International Workshop On Internet and Network Economics, 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.3 Applications

General Terms:
Algorithms, Design, Management, Theory