Network Design Problem by Link Protection to Keep Small Increase of Path Length during Link Failures

Many actual networks face the risk that the quality of service drastically degrades when the length of paths increases by link failure. To get rid of this risk, it is necessary to design a network so that the maximum increase ratio of path length by link failure is small for all paths. Therefore, the critical links whose failures significantly degrade the performance must be protected by rapid recovery so that the failures cannot be detected over the IP layer. The number of protected links must be small to restrict the investment cost for facilities and operational cost for Internet service providers. In this paper, we formulate this link protection problem and prove that the problem is NP-hard. In addition, we propose a polynomial-time algorithm to solve the problem that the number of simultaneous link failures is restricted to one.