Coping with network failures: routing strategies for optimal demand oblivious restoration
Coping with network failures: routing strategies for optimal demand oblivious restoration
复制标题
应对网络故障：最佳需求不经意恢复的路由策略
DOI：
10.1145/1005686.1005719
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
E. Cohen
中科院分区：
文献类型：
--
作者：
David L. Applegate;L. Breslau;E. Cohen
IP网络中的链路和节点故障对网络控制算法提出了挑战。路由恢复计算新路由以避免链路故障，涉及网络资源的有效利用、恢复策略的复杂性和网络流量中断之间的基本权衡。为了实现这些目标之间的平衡，获得在故障下提供良好性能保证的路由是可取的。在本文中，基于先前在不确定（和可能未知）流量需求下提供性能保证的工作，我们开发了计算最佳恢复路径的算法和评估故障下路由性能保证的方法。然后，我们研究了不同 ISP 网络集合上的路由恢复性能。我们的评估使用竞争性分析类型框架，其中将故障下具有恢复路径的路由性能与故障网络上的最佳性能进行比较。我们得出的结论是，通过仔细选择恢复路径，可以获得在故障网络上保持近乎最佳性能的恢复策略，同时最大限度地减少对未穿越网络故障部分的流量的中断。
Link and node failures in IP networks pose a challenge for network control algorithms. Routing restoration, which computes new routes that avoid failed links, involves fundamental tradeoffs between efficient use of network resources, complexity of the restoration strategy and disruption to network traffic. In order to achieve a balance between these goals, obtaining routings that provide good performance guarantees under failures is desirable.In this paper, building on previous work that provided performance guarantees under uncertain (and potentially unknown) traffic demands, we develop algorithms for computing optimal restoration paths and a methodology for evaluating the performance guarantees of routing under failures. We then study the performance of route restoration on a diverse collection of ISP networks. Our evaluation uses a competitive analysis type framework, where performance of routing with restoration paths under failures is compared to the best possible performance on the failed network. We conclude that with careful selection of restoration paths one can obtain restoration strategies that retain nearly optimal performance on the failed network while minimizing disruptions to traffic flows that did not traverse the failed parts of the network.