Title :
Centralized and distributed approximation algorithms for routing and weighted max-min fair bandwidth allocation
Author :
Allalouf, Miriam ; Shavitt, Yuval
Author_Institution :
Sch. of Electr. Eng., Tel Aviv Univ., Israel
Abstract :
Given a set of demands between pairs of nodes, we examine the traffic engineering problem of maximal flow routing and fair bandwidth allocation where flows can be split to multiple paths (e.g., MPLS tunnels). In the past we presented a polynomial solution for this problem but its complexity makes it hard to implement for large problem sizes. Thus, this paper presents a fully polynomial epsilon-approximation (FPTAS) algorithm for the max-min fair allocation problem which is based on a primal-dual alternation technique. 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. We implemented the centralized algorithm to demonstrate its correctness, efficiency, and accuracy.
Keywords :
bandwidth allocation; distributed algorithms; minimax techniques; polynomial approximation; telecommunication network routing; centralized algorithms; distributed approximation algorithms; max-min fair bandwidth allocation; maximal flow routing; polynomial epsilon-approximation; polynomial solution; primal-dual alternation technique; traffic engineering problem; Approximation algorithms; Bandwidth; Channel allocation; Communication system traffic control; Distributed algorithms; Iterative algorithms; Multiprotocol label switching; Polynomials; Routing; Telecommunication traffic;
Conference_Titel :
High Performance Switching and Routing, 2005. HPSR. 2005 Workshop on
Print_ISBN :
0-7803-8924-7
DOI :
10.1109/HPSR.2005.1503244