Critical Links Detection to Maintain Small Diameter Against Link Failures

The critical links whose failures significantly deteriorate the performance in a network must be protected not to fail or to be rapidly switched to their backup links. The number of these links should be small to restrict the investment cost of facilities and the operational cost for Internet service providers. Therefore, it is important to find the smallest number of links to be protected such that the diameter of the resulting graph by the failures of non-protected links is less than or equal to a given value. In this paper, we formulate this new 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 the simultaneous link failures is restricted to one. As about 70% of unintentional failures, excluding ones caused by maintenance, are single link failures, our algorithm for the restricted problem is not only theoretically important but also actually useful.