Network design for tolerating multiple link failures using Fast Re-route (FRR)
Network design for tolerating multiple link failures using Fast Re-route (FRR)
复制标题
使用快速重新路由 (FRR) 来容忍多个链路故障的网络设计
DOI：
10.1109/drcn.2014.6816140
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
K. Ramakrishnan
中科院分区：
文献类型：
--
作者：
R. Sinha;Funda Ergun;K. Oikonomou;K. Ramakrishnan
在本文中，我们提出的技术和协议，保护网络免受多个链路故障。现有的基于链路的MPLS快速重路由（FRR）的恢复是快速的，但可以通过过载的边缘，这是不希望的，因为许多应用程序是敏感的，与拥塞相关的数据包丢失创建拥塞。多个链路故障会加剧这个问题，频繁到足以引起生产网络的关注。在本文中，我们调查的增强FRR恢复存在多个故障，通过网络和协议设计。我们描述了几个网络设计，增加了少量的边缘到现有的拓扑结构，旨在用于备份路径。对于每一个设计，我们描述了一个协议（捎带OSPF）的分布状态信息和分布式算法重新配置备份路径，每次故障后，根据状态信息。我们证明，对于任何k，我们的设计，相关的协议，和分布式备份路径重新配置方案可以处理k任意链路故障，而不会导致断开连接或拥塞。通过一系列的建设，我们最终的网络设计是接近最佳的拓扑结构中的额外的边缘的数量。我们相信，这些网络设计是第一个有这样的可证明的保证任意多重故障。
In this paper we present techniques and protocols for protecting a network against multiple link failures. The existing link-based restoration with MPLS Fast Re-route (FRR) is fast, but can create congestion by overloading edges, which is undesirable since many applications are sensitive to congestion-related packet loss. The problem is exacerbated with multiple link failures, frequent enough to be of concern in production networks. In this paper we investigate enhancements to FRR restoration in the presence of multiple failures through network and protocol design. We describe several network designs that add a small number of edges to an existing topology, intended for use by backup paths. For each design, we describe a protocol (that piggybacks on OSPF) for distributing state information and a distributed algorithm for reconfiguring backup paths, after each failure, based on the state information. We prove that for any k, our design, associated protocol, and distributed backup path reconfiguration scheme can handle k arbitrary link failures without causing disconnection or congestion. Through a series of constructions, our final network design is nearly optimal with respect to the number of additional edges in the topology. We believe that these network designs are the first to have such provable guarantees for failures of arbitrary multiplicity.