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.
- 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. Google Scholar
Digital Library
- D. Bertsekas and R. Gallager, E.-W. Cliffs, Ed., Data Networks, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 1992. Google Scholar
- 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. Google Scholar
- B. Awerbuch and Y. Shavitt, "Converging to approximated max-min flow fairness in logarithmic time," in Proc. IEEE INFOCOM, 1998, pp. 1350-1357.Google Scholar
- 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.Google Scholar
- 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. Google Scholar
- 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.Google Scholar
- 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. Google Scholar
- 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.Google Scholar
- 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. Google Scholar
- N. Megiddo, "Optimal flows in networks with sources and sinks," Math. Programming 7, pp. 97-107, 1974.Google Scholar
- 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. Google Scholar
- 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. Google Scholar
- 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. Google Scholar
- V. V. Vazirani, Approximation Algorithms. Berlin, Germany: Springer-Verlag, 2001. Google Scholar
- F. Shahroki and D. W. Manila, "The maximum concurrent flow problem," J. ACM, vol. 37, pp. 318-334, 1990. Google Scholar
- N. Young, "Randomized rounding without solving the linear program," in Proc. 6th Ann. ACM-SIAM Symp. Discrete Algorithms, 1995, pp. 170-178. Google Scholar
- 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. Google Scholar
- L. Fleischer, "Approximating fractional multicommodity flow independent of the number of commodities," SIAM J. Discrete Math., vol. 13, no. 4, pp. 505-520, 2000. Google Scholar
- G. Karakostas, "Faster approximation schemes for fractional multicommodity flow problems," in Proc. ACM SODA, 2002, pp. 166-173. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
Index Terms
- Centralized and distributed algorithms for routing and weighted max-min fair bandwidth allocation
Recommendations
Bandwidth allocation in fair distributed queue (FDQ) networks
Fair distributed queue (FDQ) is a high speed metropolitan area network^3^,^5. It has been shown^3^,^5 that FDQ has fair throughput and delay characteristics and is a highly scalable protocol, in that its performance is little affected by growing network ...
Interference-aware routing and bandwidth allocation for QoS provisioning in multihop wireless networks: Research Articles
RRM for Next-Generation Wireless and Mobile Communication SystemsIn this paper, we study the bandwidth guaranteed routing and timeslot allocation (BANDRA) in TDMA-based multihop wireless networks with dynamic traffic. We formally model BANDRA as an optimization problem and present an integer linear programming (ILP) ...
Bandwidth Allocation with Half-Duplex Stations in IEEE 802.16 Wireless Networks
IEEE 802.16 is a recent IEEE standard for broadband wireless access networks. In IEEE 802.16 networks, the medium access control (MAC) protocol is centralized and explicitly supports quality of service (QoS). That is to say, access to the medium by a ...
Comments