Abstract
In order to provide a high resilience and to react quickly to link failures, modern computer networks support fully decentralized flow rerouting, also known as local fast failover. In a nutshell, the task of a local fast failover algorithm is to pre-define fast failover rules for each node using locally available information only. These rules determine for each incoming link from which a packet may arrive and the set of local link failures (i.e., the failed links incident to a node), on which outgoing link a packet should be forwarded. Ideally, such a local fast failover algorithm provides a perfect resilience deterministically: a packet emitted from any source can reach any target, as long as the underlying network remains connected. Feigenbaum et al. (ACM PODC 2012) and also Chiesa et al. (IEEE/ACM Trans. Netw. 2017) showed that it is not always possible to provide perfect resilience. Interestingly, not much more is known currently about the feasibility of perfect resilience. This paper revisits perfect resilience with local fast failover, both in a model where the source can and cannot be used for forwarding decisions. We first derive several fairly general impossibility results: By establishing a connection between graph minors and resilience, we prove that it is impossible to achieve perfect resilience on any non-planar graph; furthermore, while planarity is necessary, it is also not sufficient for perfect resilience. On the positive side, we show that graph families closed under link subdivision allow for simple and efficient failover algorithms which simply skip failed links. We demonstrate this technique by deriving perfect resilience for outerplanar graphs and related scenarios, as well as for scenarios where the source and target are topologically close after failures.
Introduction
In modern computer networking, high availability is paramount. When a link fails, routers must react instantly to reroute traffic. Waiting for global network reconvergence—where all routers update their global routing tables—is often too slow for real-time systems. Local Fast Failover (LFF) addresses this by using pre-configured rules that allow a router to make forwarding decisions based solely on locally available information: the incoming port and the status of its own incident links.
The gold standard for this approach is Perfect Resilience: a guarantee that a packet will always reach its destination as long as the physical network remains connected, regardless of the number or location of link failures. While this is trivial with global knowledge, achieving it with purely local rules is a significant theoretical challenge. This paper explores the topological boundaries of where perfect resilience is mathematically possible.
The Planarity Barrier and Impossibility Results
A key contribution of this research is the establishment of a link between graph theory and network resilience. The authors prove a "Minor Stability" theorem, which states that if a graph supports perfect resilience, all of its minors (graphs formed by deleting or contracting edges) must also support it.
This leads to a major impossibility result: because the fundamental non-planar building blocks (the $K_5$ and $K_{3,3}$ graphs) cannot support perfect resilience, no non-planar graph can be perfectly resilient. Planarity is thus a necessary condition for local fast failover to guarantee delivery.
However, planarity alone is not sufficient. The authors identified a planar graph with only 7 nodes where perfect resilience is impossible without source matching (and 8 nodes with source matching). This finding significantly lowers the known "complexity floor" for failure, as previous research suggested much larger graphs were required to break local failover logic.
Positive Results: Outerplanar Graphs and Proximity
On the positive side, the paper identifies specific topologies where perfect resilience is achievable using simple deterministic algorithms. For outerplanar graphs—a subset of planar graphs where all nodes are on the outer face—a "skipping" algorithm is sufficient. In this model, nodes attempt to forward packets to neighbors in a fixed circular order, simply skipping over any links that have failed. This is analogous to a "right-hand rule" for solving mazes.
Additionally, the authors show that perfect resilience is always possible in general graphs if the destination remains "topologically close" (within two hops) to the source after failures occur.
Summary of Resilience Characteristics
The following table summarizes the feasibility of perfect resilience across different graph classes and forwarding models, highlighting the impact of source matching.
Conclusion and Future Work
This work maps the theoretical limits of local fast failover, proving that while planarity is a requirement for perfect resilience, it does not guarantee it. The results suggest that for complex, non-planar industrial networks, a 100% delivery guarantee using only local rules is mathematically impossible. Future research should focus on "parametrized resilience"—optimizing delivery rates for non-planar graphs—and incorporating practical metrics like path stretch and link capacity into failover logic.
Summary updated