On the Resiliency of Static Forwarding Tables

Marco Chiesa, Ilya Nikolaevskiy, Slobodan Mitrović, Andrei Gurtov, Aleksander Madry, Michael Shapira, Scott Shenker

Tutkimustuotos: LehtiartikkeliArticleScientificvertaisarvioitu

16 Sitaatiot (Scopus)

Abstrakti

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.
AlkuperäiskieliEnglanti
Sivut1133-1146
Sivumäärä14
JulkaisuIEEE-ACM TRANSACTIONS ON NETWORKING
Vuosikerta25
Numero2
DOI - pysyväislinkit
TilaJulkaistu - 17 huhtikuuta 2017
OKM-julkaisutyyppiA1 Julkaistu artikkeli, soviteltu

Siteeraa tätä

Chiesa, M., Nikolaevskiy, I., Mitrović, S., Gurtov, A., Madry, A., Shapira, M., & Shenker, S. (2017). On the Resiliency of Static Forwarding Tables. IEEE-ACM TRANSACTIONS ON NETWORKING, 25(2), 1133-1146. https://doi.org/10.1109/TNET.2016.2619398