Fast Rerouting Against Multi-Link Failures Without Topology Constraint
Fast Rerouting Against Multi-Link Failures Without Topology Constraint
复制标题
DOI：
10.1109/tnet.2017.2780852
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
Yuan Yang;Mingwei Xu;Qi Li
中科院分区：
文献类型：
--
作者：
Yuan Yang;Mingwei Xu;Qi Li
多链路故障会导致严重的数据包丢失，降低网络性能。快速重路由已经被提出来通过启用路由保护来解决这个问题。然而，快速重路由的有效性和效率问题没有得到很好的解决。特别是，现有的方法的保护性能是不令人满意的，即使开销是高的，并且需要满足拓扑约束的方法，以实现完整的保护。为了优化效率，我们首先回答无标签路由是否可以对任何网络中的任意多链路故障提供完整保护的问题。我们提出了一个模型，接口特定的路由，它可以被看作是一个通用的无标签路由。我们分析的条件下，多链路故障将导致路由环路。然后，我们提出，存在一些网络中，没有接口特定的路由（ISR）可以构建任何k$ -链路故障（$k \geq 2$），以保护路由。然后，我们提出了一个隧道按需（TOD）的方法，它涵盖了大多数故障与ISR，并激活隧道只有当故障不能绕过ISR。我们开发的算法来计算ISR正确，以尽量减少激活的隧道的数量，并计算保护隧道，如果必要的。我们证明了TOD可以保护路由对任何单链路故障和双链路故障。我们评估TOD模拟与现实世界的拓扑结构。结果表明，TOD可以实现近100%的保护率与小的隧道开销的多链路故障，使一个更好的权衡比最先进的标签为基础的方法。
Multi-link failures may incur heavy packet loss and degrade the network performance. Fast rerouting has been proposed to address this issue by enabling routing protections. However, the effectiveness and efficiency issues of fast rerouting are not well addressed. In particular, the protection performance of existing approaches is not satisfactory even if the overhead is high, and topology constraints need to be met for the approaches to achieve a complete protection. To optimize the efficiency, we first answer the question that whether label-free routing can provide a complete protection against arbitrary multi-link failures in any networks. We propose a model for interface-specific-routing which can be seen as a general label-free routing. We analyze the conditions under which a multi-link failure will induce routing loops. And then, we present that there exist some networks in which no interface-specific-routing (ISR) can be constructed to protect the routing against any $k$ -link failures ( $k \geq 2$ ). Then, we propose a tunneling on demand (TOD) approach, which covers most failures with ISR, and activate tunneling only when failures cannot be detoured around by ISR. We develop algorithms to compute ISR properly so as to minimize the number of activated tunnels, and compute the protection tunnels if necessary. We prove that TOD can protect routing against any single-link failures and dual-link failures. We evaluate TOD by simulations with real-world topologies. The results show that TOD can achieve a near 100% protection ratio with small tunneling overhead for multi-link failures, making a better tradeoff than the state-of-the-art label-based approaches.