License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2020.46
URN: urn:nbn:de:0030-drops-131244
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13124/
Foerster, Klaus-Tycho ;
Hirvonen, Juho ;
Pignolet, Yvonne-Anne ;
Schmid, Stefan ;
Tredan, Gilles
Brief Announcement: What Can(Not) Be Perfectly Rerouted Locally
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.
BibTeX - Entry
@InProceedings{foerster_et_al:LIPIcs:2020:13124,
author = {Klaus-Tycho Foerster and Juho Hirvonen and Yvonne-Anne Pignolet and Stefan Schmid and Gilles Tredan},
title = {{Brief Announcement: What Can(Not) Be Perfectly Rerouted Locally}},
booktitle = {34th International Symposium on Distributed Computing (DISC 2020)},
pages = {46:1--46:3},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-168-9},
ISSN = {1868-8969},
year = {2020},
volume = {179},
editor = {Hagit Attiya},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13124},
URN = {urn:nbn:de:0030-drops-131244},
doi = {10.4230/LIPIcs.DISC.2020.46},
annote = {Keywords: Resilience, Local Failover}
}
Keywords: |
|
Resilience, Local Failover |
Collection: |
|
34th International Symposium on Distributed Computing (DISC 2020) |
Issue Date: |
|
2020 |
Date of publication: |
|
07.10.2020 |