On the Feasibility of Perfect Resilience with Local Fast Failover

Klaus-Tycho Foerster, Juho Hirvonen, Yvonne-Anne Pignolet, Stefan Schmid, Gilles Trédan

TL;DR

This paper explores the theoretical limits of "perfect resilience" in computer networks—the ability for a packet to reach its destination using only local failover rules as long as the network remains connected. The authors prove that perfect resilience is impossible for any non-planar network and even for some small planar ones, but they provide positive results and simple algorithms for outerplanar graphs and "topologically close" destinations.

What Problem Does This Paper Address?

In modern networking, when a link fails, routers need to react instantly. Waiting for the entire network to "reconverge" (update global routing tables) is too slow for high-availability systems. Instead, routers use Local Fast Failover: pre-configured rules that tell a router where to send a packet based solely on which of its own incident links have failed.

The holy grail of this approach is Perfect Resilience: a guarantee that a packet will always reach its target as long as a physical path exists, despite any number of link failures. While global knowledge makes this easy (just find the shortest path), doing it with only local information is a massive challenge. This paper seeks to answer: For which network topologies is perfect resilience actually possible?

Methods

The authors employ discrete mathematics and graph theory to map the boundaries of feasibility. Their key methodological contributions include:

  • Graph Minor Analysis: They establish a "Minor Stability" theorem, proving that if a graph supports perfect resilience, all of its "minors" (graphs formed by deleting or contracting edges) must also support it.
  • Impossibility Proofs: By showing that the fundamental non-planar building blocks ($K_5$ and $K_{3,3}$) cannot support perfect resilience, they use the minor relationship to prove that no non-planar graph can be perfectly resilient.
  • Constructive Algorithms: For positive results, they utilize "skipping" forwarding functions. These are simple deterministic rules where a node tries its neighbors in a fixed circular order, skipping over any that are currently failed.

Datasets

As a theoretical paper in computer science, this work does not use traditional empirical datasets. Instead, it evaluates performance across classes of graph topologies, including:

  • Planar and Non-planar graphs: Networks that can (or cannot) be drawn on a flat surface without edges crossing.
  • Outerplanar graphs: A subset of planar graphs where all nodes belong to the "outer" face.
  • Specific Gadgets: Small, hand-crafted graph counterexamples (e.g., a 7-node planar graph) used to prove impossibility results.

Key Insights and Ideas

  • The Planarity Barrier: The most striking finding is that planarity is a necessary condition. If your network topology is complex enough to be non-planar, you mathematically cannot guarantee delivery using only local failover rules.
  • Planarity is Necessary but Not Sufficient: Even if a graph is planar, it might still fail. The authors found a planar graph with only 7 nodes where perfect resilience is impossible. This significantly lowers the "complexity floor" for failure compared to previous research that suggested 30+ nodes were needed.
  • The Power of Being "Outerplanar": If a network is outerplanar, a very simple "right-hand rule" (similar to solving a maze by keeping your hand on one wall) is enough to guarantee perfect resilience.
  • Source Matching Matters (But Not Always): The paper distinguishes between models where routers can see where a packet started (source matching) and where they cannot. While source matching helps, it still doesn't overcome the fundamental impossibility on non-planar graphs.

Key Results

  • Negative Result (General): Perfect resilience is impossible on any non-planar graph (Theorem 4.4).
  • Negative Result (Planar): There exists a planar graph with 7 nodes (without source matching) and 8 nodes (with source matching) that cannot achieve perfect resilience.
  • Positive Result (Outerplanar): All outerplanar graphs support perfect resilience using simple "skipping" algorithms (Theorem 6.3).
  • Positive Result (Local): Perfect resilience is always possible if the destination is within two hops of the source after failures (Theorem 6.1).
  • Resilience Scaling: The authors show that for general graphs, you cannot even achieve "superconstant" resilience (tolerating a number of failures that grows with the network size) if you want a 100% guarantee.

Limitations and Future Work

The primary limitation is that the paper focuses strictly on connectivity. It does not account for:

  1. Path Stretch: A perfectly resilient algorithm might send a packet on a very long, circuitous route to reach a destination that is physically nearby.
  2. Congestion: Local rules might inadvertently funnel all rerouted traffic through a single link, causing a bottleneck.

The authors suggest that future research should look into "parametrized resilience"—finding the best possible resilience for non-planar graphs—and incorporating metrics like path length and link capacity into the failover logic.

Summary updated

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. In some scenarios, a local failover algorithm cannot even guarantee that a packet reaches its target, even if the source is still highly connected to the target after the failures. 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.
BibTeX
@inproceedings{foerster2021feasibility,
  author = {Klaus-Tycho Foerster and Juho Hirvonen and Yvonne-Anne Pignolet and Stefan Schmid and Gilles Trédan},
  title = {{On the Feasibility of Perfect Resilience with Local Fast Failover}},
  booktitle = {APOCS},
  year = {2021},
  url = {https://openreview.net/forum?id=n3RlhBz2Nb},
}

Loading related content...

Figure