Brief Announcement: What Can(Not) Be Perfectly Rerouted Locally
| Autor: | Foerster, Klaus-Tycho, Hirvonen, Juho, Pignolet, Yvonne-Anne, Schmid, Stefan, Tredan, Gilles |
|---|---|
| Přispěvatelé: | University of Vienna [Vienna], Aalto University, DFINITY Foundation [Zurich], Équipe Tolérance aux fautes et Sûreté de Fonctionnement informatique (LAAS-TSF), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Attiya, Hagit, University of Vienna, Professorship Suomela J., DFINITY, Centre National de la Recherche Scientifique (CNRS), Department of Computer Science, Aalto-yliopisto |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI]
2012 ACM Subject Classification Networks → Routing protocols Resilience Theory of computation → Distributed algorithms phrases Resilience Computer systems organization → Dependable and fault-tolerant systems and networks Theory of computation → Distributed algorithms Networks → Routing protocols Local Failover |
| Zdroj: | 34th International Symposium on Distributed Computing (DISC 2020) 34th International Symposium on Distributed Computing (DISC 2020), Oct 2020, Virtual, France. ⟨10.4230/LIPIcs.DISC.2020.46⟩ |
| DOI: | 10.4230/LIPIcs.DISC.2020.46⟩ |
| Popis: | 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. LIPIcs, Vol. 179, 34th International Symposium on Distributed Computing (DISC 2020), pages 46:1-46:3 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|