skip to main content
article

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

Published: 01 October 2008 Publication History

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]
B. Shmoys, D. S. Hochbaum, Ed., "Cut problems and their application to divide-and-conquer," in Approximation Algorithms for NP-Hard Problems. Boston, MA: PWS Pub. Co., 1997, ch. 5.
[2]
D. Bertsekas and R. Gallager, E.-W. Cliffs, Ed., Data Networks, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 1992.
[3]
Y. Afek, Y. Mansour, and Z. Ostfeld, "Phantom: A simple and effective flow control scheme," Comput. Netw., vol. 32, no. 3, pp. 277-305, 2000.
[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]
Y. Bartal, J. Byers, and D. Raz, "Global optimization using local information with applications to flow control," in Proc. 38th Ann. IEEE Symp. Foundations of Computer Science (FOSC), 1997, pp. 303-312.
[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]
J. Mo and J. Warland, "Fair end-to-end window-based congestion control," IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 556-567, Oct. 2000.
[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]
J. M. Kleinberg, Y. Rabani, and E. Tardos, "Fairness in routing and load balancing," in Proc. IEEE Symp. Foundations of Computer Science, 1999, pp. 568-578.
[11]
N. Megiddo, "Optimal flows in networks with sources and sinks," Math. Programming 7, pp. 97-107, 1974.
[12]
A. Goel, A. Meyerson, and S. Plotkin, "Combining fairness with throughput: Online routing with multiple objectives," in Proc. 32nd Ann. ACM Symp. Theory of Computing, 2000, pp. 670-679.
[13]
N. Buchbinder and J. Naor, "Fair online load balancing," in Proc. 18th Ann. ACM Symp. Parallelism in Algorithms and Architectures (SPAA'06), 2006, pp. 291-298.
[14]
Y. T. Hou, Y. Shi, and H. D. Sherali, "Rate allocation in wireless sensor networks with network lifetime requirement," in Proc. 5th ACM Int. Symp. Mobile Ad Hoc Networking and Computing (MobiHoc'04), 2004, pp. 67-77.
[15]
V. V. Vazirani, Approximation Algorithms. Berlin, Germany: Springer-Verlag, 2001.
[16]
F. Shahroki and D. W. Manila, "The maximum concurrent flow problem," J. ACM, vol. 37, pp. 318-334, 1990.
[17]
N. Young, "Randomized rounding without solving the linear program," in Proc. 6th Ann. ACM-SIAM Symp. Discrete Algorithms, 1995, pp. 170-178.
[18]
N. Garg and J. Konemann, "Faster and simpler algorithms for multicommodity flow and other fractional packing problems," in Proc. IEEE Symp. Foundations of Computer Science, 1998, pp. 300-309.
[19]
L. Fleischer, "Approximating fractional multicommodity flow independent of the number of commodities," SIAM J. Discrete Math., vol. 13, no. 4, pp. 505-520, 2000.
[20]
G. Karakostas, "Faster approximation schemes for fractional multicommodity flow problems," in Proc. ACM SODA, 2002, pp. 166-173.
[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.

Cited By

View all
  • (2022)Switching in the Rain: Predictive Wireless x-haul Network ReconfigurationProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/35706166:3(1-26)Online publication date: 8-Dec-2022
  • (2022)Ubiquitous Transmission Service: Hierarchical Wireless Data Rate Provisioning in Space-Air-Ocean Integrated NetworksIEEE Transactions on Wireless Communications10.1109/TWC.2022.316240021:9(7821-7836)Online publication date: 1-Sep-2022
  • (2020)Perfect is the Enemy of Good: Lloyd-Max Quantization for Rate Allocation in Congestion Control PlaneNOMS 2020 - 2020 IEEE/IFIP Network Operations and Management Symposium10.1109/NOMS47738.2020.9110387(1-9)Online publication date: 20-Apr-2020
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 16, Issue 5
October 2008
238 pages

Publisher

IEEE Press

Publication History

Published: 01 October 2008
Revised: 28 September 2006
Received: 10 April 2006
Published in TON Volume 16, Issue 5

Author Tags

  1. bandwidth allocation
  2. distributed algorithm
  3. maximum concurrent multi-commodity flow problem
  4. maxmin fairness criteria

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

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

Other Metrics

Citations

Cited By

View all
  • (2022)Switching in the Rain: Predictive Wireless x-haul Network ReconfigurationProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/35706166:3(1-26)Online publication date: 8-Dec-2022
  • (2022)Ubiquitous Transmission Service: Hierarchical Wireless Data Rate Provisioning in Space-Air-Ocean Integrated NetworksIEEE Transactions on Wireless Communications10.1109/TWC.2022.316240021:9(7821-7836)Online publication date: 1-Sep-2022
  • (2020)Perfect is the Enemy of Good: Lloyd-Max Quantization for Rate Allocation in Congestion Control PlaneNOMS 2020 - 2020 IEEE/IFIP Network Operations and Management Symposium10.1109/NOMS47738.2020.9110387(1-9)Online publication date: 20-Apr-2020
  • (2019)Priority-based bandwidth allocation and load balancing for multipath IP networksInternational Journal of Networking and Virtual Organisations10.5555/3302782.330278720:1(53-72)Online publication date: 1-Jan-2019
  • (2019)A survey on resource scheduling for data transfers in inter-datacenter WANsComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2019.06.011161:C(115-137)Online publication date: 9-Oct-2019
  • (2017)Upward Max-Min FairnessJournal of the ACM10.1145/301128264:1(1-24)Online publication date: 24-Mar-2017
  • (2016)Simplifying software-defined network optimization using SOLProceedings of the 13th Usenix Conference on Networked Systems Design and Implementation10.5555/2930611.2930627(223-237)Online publication date: 16-Mar-2016
  • (2015)BwEACM SIGCOMM Computer Communication Review10.1145/2829988.278747845:4(1-14)Online publication date: 17-Aug-2015
  • (2015)BwEProceedings of the 2015 ACM Conference on Special Interest Group on Data Communication10.1145/2785956.2787478(1-14)Online publication date: 17-Aug-2015
  • (2015)A compact linear programming formulation of the maximum concurrent flow problemNetworks10.1002/net.2158365:1(68-87)Online publication date: 1-Jan-2015
  • 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