Method for Keeping Small Distance from Users to Servers during Failures by Link Protection

摘要

Large-volume contents distributed by a content delivery network (CDN) on the Internet increase load of content delivery servers and networks, which may degrade the quality of service. As a method to keep high quality service for CDN, some mirror servers providing the same content are located on a network and a request is navigated to one of the mirror servers. The network must offer connectivity between a user and servers with small distance even during link failures. In this paper, we address a network design method by protection of critical links whose failures significantly degrade the performance. The objective is to find the smallest number of the links to be protected so that a user can access servers with small increase of distance even if non-protected links fail. First, we formulate this problem and prove that it is NP-hard. Second, we present a polynomial-time algorithm to solve this problem when the number of simultaneously failed links is restricted to one. Furthermore, we evaluate the number of protected links of actual ISP network topologies by the algorithm and show the relationship between the number of protected links and the values of the parameters.