Back to Search
Start Over
Brief Announcement: What Can(Not) Be Perfectly Rerouted Locally
- Source :
- 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⟩
- Publication Year :
- 2020
- Publisher :
- HAL CCSD, 2020.
-
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.<br />LIPIcs, Vol. 179, 34th International Symposium on Distributed Computing (DISC 2020), pages 46:1-46:3
- Subjects :
- [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
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- 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⟩
- Accession number :
- edsair.doi.dedup.....fdbf266d9f45b0a1dd2aabf62791b93e