Network Design Method by Link Protection for Network Load Alleviation against Failures

Network reliability is needed as the Internet becomes an important social infrastructure. However, we face risks of failure and congestion on many links or routers, therefore, a network should be robust enough to avoid failure and congestion. As the route of a path between two nodes is automatically determined by a routing protocol, many paths may be included in a same link and it may cause congestion. Especially, when a link fails, the routes of the paths included in the link are automatically changed, and eventually congestion may occur. If there are critical links whose failures cause congestion, they must be protected by the function that a failed link is rapidly switched to its backup link in the lower layer and the failure is not detected over the IP layer. However, such a link protection increases investment cost for facilities and operational cost. In this paper, we formulate the problem to find links to be protected so that no congestion occurs even if any non-protected links fails. We prove that this problem is NP-hard. In addition, we present a polynomial-time algorithm to solve the problem that the number of simultaneously failed links is restricted to one.