Designing Networks with Existing Traffic to Support Fast Restoration

In this paper we are interested in the problem of dedicating the least amount of the currently available network capacity for protection, while guaranteeing fast restoration to the existing traffic along with any traffic that may be admitted in the future. We show that the problem is NP-hard, and give a 2-approximation algorithm for the problem. We also show that the integrality gap of a natural relaxation of our problem is 3, thus establishing that any LP based approach using this relaxation cannot yield a better than a 3-approximation algorithm for our problem. Our simulation, on some standard core networks, show that our algorithm works well in practice as well.