Brief Announcement: What Can(Not) Be Perfectly Rerouted Locally

Klaus Tycho Foerster, Juho Hirvonen, Yvonne-Anne Pignolet, Stefan Schmid, Gilles Tredan

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

3 Downloads (Pure)

Abstract

In order to provide a high resilience and to react quickly to link failures, modern computer networks support fully decentralized flow rerouting, also known as local fast failover. In a nutshell, the task of a local fast failover algorithm is to pre-define fast failover rules for each node using locally available information only. Ideally, such a local fast failover algorithm provides a perfect resilience deterministically: a packet emitted from any source can reach any target, as long as the underlying network remains connected. Feigenbaum et al. showed [Feigenbaum and others, 2012] that it is not always possible to provide perfect resilience; on the positive side, the authors also presented an efficient algorithm which achieves at least 1-resilience, tolerating a single failure in any network. Interestingly, not much more is known currently about the feasibility of perfect resilience. This brief announcement revisits perfect resilience with local fast failover, both in a model where the source can and cannot be used for forwarding decisions. By establishing a connection between graph minors and resilience, we prove that it is impossible to achieve perfect resilience on any non-planar graph; On the positive side, we can derive perfect resilience for outerplanar and some planar graphs.
Original languageEnglish
Title of host publication34th International Symposium on Distributed Computing (DISC 2020)
EditorsHagit Attiya
Chapter46
Number of pages3
ISBN (Electronic)978-3-95977-168-9
DOIs
Publication statusPublished - 2020
MoE publication typeA4 Article in a conference publication
EventInternational Symposium on Distributed Computing - Virtual, Online, Germany
Duration: 12 Oct 202016 Oct 2020
Conference number: 32
http://www.disc-conference.org/wp/disc2020/

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum für Informatik
Volume179
ISSN (Electronic)1868-8969

Conference

ConferenceInternational Symposium on Distributed Computing
Abbreviated titleDISC
Country/TerritoryGermany
CityVirtual, Online
Period12/10/202016/10/2020
Internet address

Fingerprint

Dive into the research topics of 'Brief Announcement: What Can(Not) Be Perfectly Rerouted Locally'. Together they form a unique fingerprint.

Cite this