On the Resiliency of Static Forwarding Tables

Chiesa, Marco, 1987- (author): Université catholique du Louvain, Belgium,Catholic University of Louvain, Belgium

Gurtov, Andrei (author): Linköpings universitet,Databas och informationsteknik,Tekniska fakulteten,ITMO University, Russia

Shenker, S. (author): University of Calif Berkeley, CA 94720 USA; Int Comp Science Institute, CA 94704 USA

(creator_code:org_t)

Institute of Electrical and Electronics Engineers (IEEE), 2017
2017
English.
In: IEEE/ACM Transactions on Networking. - : Institute of Electrical and Electronics Engineers (IEEE). - 1063-6692 .- 1558-2566. ; 25:2, s. 1133-1146

Related links:: https://urn.kb.se/re...; show more...; https://doi.org/10.1...; https://urn.kb.se/re...; show less...

Abstract Subject headings

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-headerrewriting, 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.

TEKNIK OCH TEKNOLOGIER -- Elektroteknik och elektronik -- Kommunikationssystem (hsv//swe)
ENGINEERING AND TECHNOLOGY -- Electrical Engineering, Electronic Engineering, Information Engineering -- Communication Systems (hsv//eng)
NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

By the author/editor: Chiesa, Marco, 1 ...; Nikolaevskiy, I.; Mitrovic, S.; Gurtov, Andrei; Madry, A.; Schapira, M.; show more...; Shenker, S.; show less...

About the subject

ENGINEERING AND TECHNOLOGY: ENGINEERING AND ...; and Electrical Engin ...; and Communication Sy ...

NATURAL SCIENCES: NATURAL SCIENCES; and Computer and Inf ...; and Computer Science ...

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.