Treffer: Principles of Distributed Computing (PODC).

Many modern network designs incorporate ``failover' ' paths into routers ' forwarding tables. While such resilient routing tables are widely used in practice (e.g., ECMP), there has been little theoretical work on their inherent power and limitations. We initiate the theoretical study of the conditions under which such resilient routing tables can guarantee delivery of packets and take the first steps in this research direction. We prove that routing tables can provide guaranteed resilience against single failures, as long as the network remains connected. We show, in contrast, that perfect resilience is not achievable in general.