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

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
Conference article in proceedings
This publication is imported from Aalto University research portal.
View publication in the Research portal
View/Open full text file from the Research portal
Date
2020
Major/Subject
Mcode
Degree programme
Language
en
Pages
3
Series
34th International Symposium on Distributed Computing (DISC 2020), Leibniz International Proceedings in Informatics (LIPIcs), Volume 179
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.
Description
Keywords
Other note
Citation
Foerster, K T, Hirvonen, J, Pignolet, Y-A, Schmid, S & Tredan, G 2020, Brief Announcement: What Can(Not) Be Perfectly Rerouted Locally . in H Attiya (ed.), 34th International Symposium on Distributed Computing (DISC 2020) . Leibniz International Proceedings in Informatics (LIPIcs), vol. 179, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, International Symposium on Distributed Computing, Virtual, Online, Germany, 12/10/2020 . https://doi.org/10.4230/LIPIcs.DISC.2020.46