Detecting protected links to keep reachability to server against failures
Detecting protected links to keep reachability to server against failures
复制标题
检测受保护的链接以保持服务器的可达性以防止出现故障
DOI：
10.1109/icoin.2013.6496347
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
H. Miwa
中科院分区：
文献类型：
--
作者：
K. Imagawa;H. Miwa
如何设计一个可靠的网络来抵御网络故障对于互联网服务提供商（ISP）来说是非常重要的。ISP必须为用户提供连接，即使发生链路故障。设计一个可靠的网络最好的方法是通过足够的备份资源和快速恢复系统来保护所有的链路，使链路的故障概率足够小。然而，足够的备份资源需要ISP付出很大的代价。因此，有必要找到要保护的最小数量的链路，使得即使任何不受保护的链路发生故障，所产生的网络也能为用户提供连接。在本文中，作为连接性的度量，我们关注的是连接组件的大小，包括服务器或网关。关键链路的故障会大大减少包括服务器在内的连接组件的大小，因此必须保护这些关键链路不发生故障，因为这种故障会阻止大量用户访问服务器。同样，当服务器是另一个ISP网络的网关时，许多用户无法与外部用户和服务器通信。我们的目的是找到要保护的链接，即使任何不受保护的链接失败，在所产生的网络中与服务器连接的节点的数量不小于阈值。在本文中，我们制定了这个问题，并证明了该问题是NP-困难的。此外，我们提出了一个多项式时间的算法来解决的问题，同时链路故障的数量限制为一个。此外，我们提出了一个多项式时间算法来解决的问题，同时链路故障的数量限制为两个和网络是一棵树。
Methods to design a reliable network against network failures are important for Internet service providers (ISPs). ISPs must offer connectivity to users, even if link failures occur. The best way to design a reliable network is to protect all links so that the failure probability of a link is sufficiently small by sufficient backup resource and rapid recovery system. However, sufficient backup resource needs much cost for ISP. Therefore, it is necessary to find the smallest number of links to be protected such that, even if any non-protected links fail, the resulting network offers users connectivity. In this paper, as a measure of connectivity, we focus on the size of the connected component including a server or a gateway. Critical links whose failures drastically decrease the size of the connected component including a server must be protected not to fail, because such a failure prevent a large number of users from access to the server. Similarly, when a server is a gateway to another ISP's network, many users cannot communicate with exterior users and servers. Our purpose is to find the links to be protected such that, even if any non-protected links fail, the number of the nodes connected with a server in the resulting network is not less than a threshold. In this paper, we formulate this 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. Furthermore, we present a polynomial-time algorithm to solve the problem that the number of the simultaneous link failures is restricted to two and a network is a tree.