Perfect Network Resilience in Polynomial Time

Modern communication networks support local fast rerouting mechanisms to quickly react to link failures: nodes store a set of conditional rerouting rules which define how to forward an incoming packet in case of incident link failures. Ideally, such rerouting mechanisms provide perfect resilience: any packet is routed from its source s to its target t as long as s and t are still connected in the underlying graph after the link failures. However, ensuring perfect resilience is algorithmically challenging as the rerouting decisions at any node v must rely solely on the local information available at v: the link from which a packet arrived at v (known as the in-port), the target of the packet, and the incident link failures at v. Already in their seminal paper at ACM PODC '12, Feigenbaum, Godfrey, Panda, Schapira, Shenker, and Singla showed that there are instances in which perfect resilience cannot be achieved. While the design of local rerouting algorithms has received much attention since then, we still lack a detailed understanding of when perfect resilience is achievable.

This paper closes this gap and presents a complete characterization of when perfect resilience can be achieved. This characterization also allows us to design an O(n)-time algorithm to decide whether a given instance is perfectly resilient and an O(nm)-time algorithm to compute perfectly resilient rerouting rules whenever it is. Our algorithm is also attractive for the simple structure of the rerouting rules it uses, known as skipping in the literature: alternative links are chosen according to an ordered priority list (per in-port), where failed links are simply skipped. This is also naturally supported in hardware. The size of such an encoding is in Θ(nm) and therefore the running time of our algorithm is optimal when considering skipping rerouting rules. Intriguingly, our result also implies that in the context of perfect resilience, skipping rerouting rules are as powerful as more general rerouting rules that define the out-port for each set of incident failed links explicitly. This partially answers a long-standing open question by Chiesa, Nikolaevskiy, Mitrovic, Gurtov, Madry, Schapira, and Shenker [IEEE/ACM Transactions on Networking, 2017] in the affirmative.

While our algorithm is simple, its analysis is intricate. A key concept in the analysis are links whose two endpoints also form a node separator. We prove that removing those links does not change whether a given instance is perfectly resilient or not. We also show that once all such links are removed, any instance either contains one of four specific rooted minors or belongs to one of three classes. If one of the four rooted minors is contained, then we are dealing with a no-instance (this was previously known for only two of them). Lastly, we show that any instance in any of the three remaining classes is a yes-instance, completing the characterization of perfectly resilient graphs. We do this by showing that simply following a particular face of a planar embedding of the reduced instance using the right-hand rule until a link directly to the target is found is sufficient.