论文标题
当地的快速重新布置与拥塞低：一种随机方法
Local Fast Rerouting with Low Congestion: A Randomized Approach
论文作者
论文摘要
大多数现代通信网络都包括完全在数据平面中实现的快速重新布置机制，以在链接失败后快速恢复连接性。通过仅依赖局部故障信息，这些数据平面机制提供了非常快的反应时间，但同时在多个链接故障的情况下引入了算法挑战：故障转路途径需要鲁棒性，以使其他额外的途径在下游，但本地未知的故障。本文介绍了当地的快速重新布置算法，这些算法不仅可以针对多个链接失败提供高度的弹性，而且还可以确保在所得的故障转移路径上的拥堵较低。我们考虑一种随机方法，并专注于在发生故障之前高度连接的网络。我们的主要贡献是三种简单的算法，这些算法具有可证明的保证，并提供了有趣的弹性负载折衷，这大大优于任何确定性的快速重新布置算法，概率很高。
Most modern communication networks include fast rerouting mechanisms, implemented entirely in the data plane, to quickly recover connectivity after link failures. By relying on local failure information only, these data plane mechanisms provide very fast reaction times, but at the same time introduce an algorithmic challenge in case of multiple link failures: failover routes need to be robust to additional but locally unknown failures downstream. This paper presents local fast rerouting algorithms which not only provide a high degree of resilience against multiple link failures, but also ensure a low congestion on the resulting failover paths. We consider a randomized approach and focus on networks which are highly connected before the failures occur. Our main contribution are three simple algorithms which come with provable guarantees and provide interesting resilience-load tradeoffs, significantly outperforming any deterministic fast rerouting algorithm with high probability.
