Paper Info
Title
On the Resiliency of Static Forwarding Tables
Abstract
Fast reroute and other forms of immediate failover have long been used to recover from certain classes of failures without invoking the network control plane. While the set of such techniques is growing, the level of resiliency to failures that this approach can provide is not adequately understood. In this paper, we embarked upon a systematic algorithmic study of the resiliency of forwarding tables in a variety of models (i.e., deterministic/probabilistic routing, with packet-header-rewriting, with packet-duplication). Our results show that the resiliency of a routing scheme depends on the “connectivity” $k$ of a network, i.e., the minimum number of link deletions that partition a network. We complement our theoretical result with extensive simulations. We show that resiliency to four simultaneous link failures, with limited path stretch, can be achieved without any packet modification/duplication or randomization. Furthermore, our routing schemes provide resiliency against $k-1$ failures, with limited path stretch, by storing $\log (k)$ bits in the packet header, with limited packet duplication, or with randomized forwarding technique.
Year
DOI
Venue
2017
10.1109/TNET.2016.2619398
IEEE/ACM Transactions on Networking (TON)
Keywords
Field
DocType
Routing,Robustness,Routing protocols,Probabilistic logic,Network topology,IEEE transactions,Delays
Fast reroute,Failover,Delay-tolerant networking,Computer science,Network packet,Computer network,Network topology,Probabilistic logic,Header,Routing protocol,Distributed computing
Journal
Volume
Issue
ISSN
25
2
1063-6692
Citations 
PageRank 
References 
8
0.48
30
Authors
7
Name
Order
Citations
PageRank
Marco Chiesa11018.20
Ilya Nikolaevskiy2384.38
Slobodan Mitrović3307.68
Andrei Gurtov41326109.52
Aleksander Mądry596145.38
Michael Schapira6112279.89
Scott Shenker7298922677.04