A Tight Characterization of Fast Failover Routing: Resiliency to Two Link Failures is Possible
Wenkai Dai, Klaus-Tycho Foerster, Stefan Schmid · 2023
To achieve fast recovery from link failures, most modern communication networks feature local fast failover mechanisms in the data plane. These failover mechanisms typically rely on pre-installed static rerouting rules which can depend only on local failure information. The locally limited failure information renders the problem of providing a high resilience algorithmically challenging. In this paper, we are interested in algorithms which tolerate a maximal number of k simultaneous link failures to guarantee packet delivery, as long as source and destination remain connected afterwards. Prior work showed that k=1 link failure can always be tolerated in general networks, but already the question of k=2 remained an unresolved problem.