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

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.