On the Resiliency of Randomized Routing Against Multiple Edge Failures
On the Resiliency of Randomized Routing Against Multiple Edge Failures
复制标题
DOI：
10.4230/lipics.icalp.2016.134
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Marco Chiesa;A. Gurtov;A. Madry;Slobodan Mitrovic;Ilya Nikolaevskiy;Michael Schapira;S. Shenker
中科院分区：
文献类型：
--
作者：
Marco Chiesa;A. Gurtov;A. Madry;Slobodan Mitrovic;Ilya Nikolaevskiy;Michael Schapira;S. Shenker
我们研究静态路由弹性问题，其动机是互联网上的路由：给定图 G = (V,E)、唯一的目标顶点 d 和整数常量 c > 0，是否存在基于静态和基于目标的路由方案，只要 (1) 不超过 c 个边失败且 (2) 存在从 s 到 d 的物理路径，就可以保证将数据包从任何源 s 正确传送到目标 d？我们通过将图的边连通性（即删除分区 G 的边的最小数量）与其弹性联系起来，开始研究这个问题。继随机路由算法在处理各种问题（例如，网络设计问题中的 Valiant 负载平衡）取得成功之后，我们开始研究静态路由弹性问题的随机路由算法。对于任何 k 连接图，我们展示了一个令人惊讶的简单随机算法，如果最多 k-1 个边失败，则预期跳数为 O(|V|k)，如果只有一小部分 t 的链接失败（其中 t < 1 是常数），则跳数会减少到 O(|V|)。此外，如果路由没有遇到任何失败的链路，我们的算法是确定性的。
We study the Static-Routing-Resiliency problem, motivated by routing on the Internet: Given a graph G = (V,E), a unique destination vertex d, and an integer constant c > 0, does there exist a static and destination-based routing scheme such that the correct delivery of packets from any source s to the destination d is guaranteed so long as (1) no more than c edges fail and (2) there exists a physical path from s to d? We embark upon a study of this problem by relating the edge-connectivity of a graph, i.e., the minimum number of edges whose deletion partitions G, to its resiliency. Following the success of randomized routing algorithms in dealing with a variety of problems (e.g., Valiant load balancing in the network design problem), we embark upon a study of randomized routing algorithms for the Static-Routing-Resiliency problem. For any k-connected graph, we show a surprisingly simple randomized algorithm that has expected number of hops O(|V|k) if at most k-1 edges fail, which reduces to O(|V|) if only a fraction t of the links fail (where t < 1 is a constant). Furthermore, our algorithm is deterministic if the routing does not encounter any failed link.