Network Design Method by Finding Server Placement and Protected Links to Keep Connectivity to Servers Against Link Failures
Network Design Method by Finding Server Placement and Protected Links to Keep Connectivity to Servers Against Link Failures
复制标题
通过寻找服务器放置和受保护的链路来保持与服务器的连接以防止链路故障的网络设计方法
DOI：
10.1109/incos.2016.73
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Hiroyoshi Miwa
中科院分区：
文献类型：
--
作者：
Daishi Irie;Hiroyoshi Miwa
对于网络服务提供商来说，设计和运营可靠的网络是非常重要的，该网络对网络故障具有鲁棒性。特别是，即使发生链路故障，网络也必须充分连接。有很多方法可以设计一个健壮的网络。一种是基于服务器选址问题的方法。由于镜像服务器的位置会影响内容交付服务的性能，因此有必要找到更好的服务器位置。另一种方法是基于链路保护。希望通过足够的备份资源和快速恢复系统来保护所有链路，使得链路的故障概率足够小。然而，链路保护成本很高;因此，重要的是找到要保护的最小数量的链路，以便由任何不受保护的链路的故障产生的网络为用户提供连接。本文提出了一种结合服务器布局法和链路保护法的网络设计方法。即使不能简单地通过服务器布置方法或简单地通过链路保护方法使网络可靠，它们的组合也可以使网络可靠。因此，我们的目的是找到一个服务器的位置和一组要保护的链接，这样，即使任何不受保护的链接失败，所有连接的组件包括指定的服务器在最终的网络。首先，我们制定了这种可靠的网络设计方法相结合的服务器布局方法和链路保护方法，并表明这个问题是NP-难的。此外，我们还提出了一个多项式时间算法来解决受保护链路数限制为零的问题，以及一个多项式时间算法来解决同时链路失效数限制为一的问题。此外，我们评估的算法，将其应用到实际网络的拓扑结构，并表明所提出的算法工作良好。
It is important for network 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. There are many methods to design a robust network. One is a method based on a server location problem. As the location of mirror servers affects the performance of a content delivery service, it is necessary to find a better server placement. Another method is based on link protection. 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 costs are high; 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 address a network design method by combining server placement method and link protection method. Even if a network cannot be made reliable simply by server placement method or simply by link protection method, the combination of them may make the network reliable. Thus, our purpose is to find a server placement and a set of links to be protected such that, even if any non-protected links fail, all connected components include specified servers in the resulting network. First, we formulate this reliable network design method by combining server placement method and link protection method and show that this problem is NP-hard. In addition, we propose a polynomial-time algorithm to solve the problem that the number of the protected links is restricted to zero, and a polynomial-time algorithm to solve the problem that the number of the simultaneous link failures is restricted to one. Furthermore, we evaluate the algorithm by applying it to the topology of actual networks and show that the proposed algorithms work well.