Detecting critical protected links to keep connectivity to servers against link failures

It is important for service providers to design and operate reliable network which is robust against network failures. Especially, a network must be sufficiently connected, even if link failures occur. It is desirable to protect all links so that the failure probability of a link is sufficiently small by sufficient backup resource and rapid recovery system. However, link protection needs much cost; therefore, it is important to find the smallest number of links to be protected so that a network resulting from failures of any non-protected links provides users connectivity. In this paper, we focus on the criteria that all connected components include specified servers in a resulting network after links fail. Our purpose is to find the links to be protected such that, even if any non-protected links fail, all connected components in the resulting network include the servers. First, we formulate this link protection problem and prove that this problem is NP-hard. Next, we present a polynomial-time algorithm to solve the problem that the number of the simultaneous link failures is restricted to one. Furthermore, we present a polynomial-time approximation algorithm with the approximation ratio of a constant, the number of the simultaneous link failures. In addition, we apply the approximation algorithms to the topology of actual networks and evaluate the approximation ratio. The results indicate that the approximation ratio in the actual networks is much smaller than the theoretical upper bound. It follows that our algorithms are efficient when we determine protected links in an actual network.