Capacity Allocation and Routing of Locally Restorable Bandwidth Guaranteed Connections

The contribution of this paper is a fast combinatorial approximation algorithm for network capacity determination when the routed traffic is required to be locally restorable. To the best of our knowledge, this is the first Fully Polynomial Time Approximation Scheme (FPTAS) for this problem, i.e., for any given e > 0, our algorithm guarantees (1 + e)-factor closeness to the optimal solution, and runs in time polynomial in the network size and 1/e. We investigate the extra capacity for protecting against node failures (vs. link failures) and also compare the capacity overhead of local restoration with 1+1-dedicated path protection.