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

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



PDF
Thumbnail PDF

File

LIPIcs.DISC.2020.46.pdf
  • Filesize: 0.56 MB
  • 3 pages

Document Identifiers

Author Details

Klaus-Tycho Foerster
  • Faculty of Computer Science, University of Vienna, Austria
Juho Hirvonen
  • Aalto University, Finland
Yvonne-Anne Pignolet
  • DFINITY, Zürich, Switzerland
Stefan Schmid
  • Faculty of Computer Science, University of Vienna, Austria
Gilles Tredan
  • LAAS-CNRS, Toulouse, France

Acknowledgements

We would like to thank Jukka Suomela for several fruitful discussions.

Cite AsGet BibTex

Klaus-Tycho Foerster, Juho Hirvonen, Yvonne-Anne Pignolet, Stefan Schmid, and Gilles Tredan. Brief Announcement: What Can(Not) Be Perfectly Rerouted Locally. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 46:1-46:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.DISC.2020.46

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.

Subject Classification

ACM Subject Classification
  • Networks → Routing protocols
  • Computer systems organization → Dependable and fault-tolerant systems and networks
  • Theory of computation → Distributed algorithms
Keywords
  • Resilience
  • Local Failover

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. J. A. Bondy and U. S. R. Murty. Graph Theory with Applications. Elsevier, New York, 1976. Google Scholar
  2. M. Chiesa et al. On the resiliency of static forwarding tables. Trans. Netw., 25(2), 2017. Google Scholar
  3. J. Feigenbaum et al. BA: On the resilience of routing tables. In Proc. PODC, 2012. Google Scholar
  4. K.-T. Foerster, J. Hirvonen, Y.-A. Pignolet, S. Schmid, and G. Trédan. On the feasibility of perfect resilience with local fast failover. CoRR, 2020. URL: http://arxiv.org/abs/2006.06513.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail