Centralized and distributed algorithms for routing and weighted max-min fair bandwidth allocation

ABSTRACT

Given a set of demands between pairs of nodes, we examine the traffic engineering problem of flow routing and fair bandwidth allocation where flows can be split to multiple paths (e.g., MPLS tunnels). This paper presents an algorithm for finding an optimal and global per-commodity max-min fair rate vector in a polynomial number of steps. In addition, we present a fast and novel distributed algorithm where each source router can find the routing and the fair rate allocation for its commodities while keeping the locally optimal max-min fair allocation criteria. The distributed algorithm is a fully polynomial epsilon-approximation (FPTAS) algorithm and is based on a primal-dual alternation technique. We implemented these algorithms to demonstrate its correctness, efficiency, and accuracy.

REFERENCES

• 1: David B. Shmoys, Cut problems and their application to divide-and-conquer, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 2: Dimitri Bertsekas , Robert Gallager, Data networks (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 3: Yehuda Afek , Yishay Mansour , Zvi Ostfeld, Phantom: a simple and effective flow control scheme, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.32 n.3, p.277-305, March 2000 [doi>10.1016/S1389-1286(99)00138-3]
• 4: B. Awerbuch and Y. Shavitt, "Converging to approximated max-min flow fairness in logarithmic time," in Proc. IEEE INFOCOM, 1998, pp. 1350-1357.
• 5: Y. Bartal, M. Farach-Colton, S. Yooseph, and L. Zhang, "Fast, fair, and frugal bandwidth allocation in ATM networks," Algorithmica, vol. 33, Special Issue on Internet Algorithms, no. 3, pp. 272-286, 2002.
• 6: 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
• 7: F. P. Kelly, A. K. Maulloo, and D. K. H. Tan, "Rate control for communication networks: Shadow prices, proportional fairness and stability," Oper. Res. Soc., vol. 49, pp. 237-252, 1998.
• 8: Jeonghoon Mo , Jean Walrand, Fair end-to-end window-based congestion control, IEEE/ACM Transactions on Networking (TON), v.8 n.5, p.556-567, Oct. 2000 [doi>10.1109/90.879343]
• 9: S. Chen and K. Nahrstedt, "Maxmin fair routing in connection-oriented networks," in Proc. Euro-Parallel and Distributed Systems Conf. (Euro-PDS'98), 1998, pp. 163-168.
• 10: Jon Kleinberg , Eva Tardos , Yuval Rabani, Fairness in Routing and Load Balancing, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.568, October 17-18, 1999
• 11: N. Megiddo, "Optimal flows in networks with sources and sinks," Math. Programming 7, pp. 97-107, 1974.
• 12: Ashish Goel , Adam Meyerson , Serge Plotkin, Combining fairness with throughput: online routing with multiple objectives, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.670-679, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335400]
• 13: 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]
• 14: Y. Thomas Hou , Yi Shi , Hanif D. Sherali, Rate allocation in wireless sensor networks with network lifetime requirement, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989469]
• 15: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 16: Farhad Shahrokhi , D. W. Matula, The maximum concurrent flow problem, Journal of the ACM (JACM), v.37 n.2, p.318-334, April 1990 [doi>10.1145/77600.77620]
• 17: Neal E. Young, Randomized rounding without solving the linear program, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.170-178, January 22-24, 1995, San Francisco, California, United States
• 18: 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
• 19: Lisa K. Fleischer, Approximating Fractional Multicommodity Flow Independent of the Number of Commodities, SIAM Journal on Discrete Mathematics, v.13 n.4, p.505-520, Oct. 2000 to Nov. 2000 [doi>10.1137/S0895480199355754]
• 20: George Karakostas, Faster approximation schemes for fractional multicommodity flow problems, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.166-173, January 06-08, 2002, San Francisco, California
• 21: M. Allalouf and Y. Shavitt, "Maximum flow routing with weighted max-min fairness," in Proc. 1st Int. Workshop QoS Routing (WQoSR 2004), Barcelona, Spain, Oct. 2004, pp. 279-285.
• 22: M. Allalouf and Y. Shavitt, "Centralized and distributed approximation algorithms for routing and weighted max-min fair bandwidth allocation," in Proc. IEEE Workshop on High Performance Switching and Routing (HPSR'05), Hong Kong, May 2005, pp. 306-311.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Spline and piecewise polynomial approximation
      G.1.6 Optimization

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
bandwidth allocation, distributed algorithm, maximum concurrent multi-commodity flow problem, maxmin fairness criteria