1 Search Results for "Tredan, Gilles"

Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2020.46
Brief Announcement: What Can(Not) Be Perfectly Rerouted Locally

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

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{foerster_et_al:LIPIcs.DISC.2020.46,
  author =	{Foerster, Klaus-Tycho and Hirvonen, Juho and Pignolet, Yvonne-Anne and Schmid, Stefan and Tredan, Gilles},
  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 =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.46},
  URN =		{urn:nbn:de:0030-drops-131244},
  doi =		{10.4230/LIPIcs.DISC.2020.46},
  annote =	{Keywords: Resilience, Local Failover}
}
  • Refine by Author
  • 1 Foerster, Klaus-Tycho
  • 1 Hirvonen, Juho
  • 1 Pignolet, Yvonne-Anne
  • 1 Schmid, Stefan
  • 1 Tredan, Gilles

  • Refine by Classification
  • 1 Computer systems organization → Dependable and fault-tolerant systems and networks
  • 1 Networks → Routing protocols
  • 1 Theory of computation → Distributed algorithms

  • Refine by Keyword
  • 1 Local Failover
  • 1 Resilience

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact