1 Search Results for "Kosic, Petar"

Document
DOI: 10.4230/LIPIcs.OPODIS.2020.26
Maximally Resilient Replacement Paths for a Family of Product Graphs

Authors: Mahmoud Parham, Klaus-Tycho Foerster, Petar Kosic, and Stefan Schmid

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract
Modern communication networks support fast path restoration mechanisms which allow to reroute traffic in case of (possibly multiple) link failures, in a completely decentralized manner and without requiring global route reconvergence. However, devising resilient path restoration algorithms is challenging as these algorithms need to be inherently local. Furthermore, the resulting failover paths often have to fulfill additional requirements related to the policy and function implemented by the network, such as the traversal of certain waypoints (e.g., a firewall). This paper presents local algorithms which ensure a maximally resilient path restoration for a large family of product graphs, including the widely used tori and generalized hypercube topologies. Our algorithms provably ensure that even under multiple link failures, traffic is rerouted to the other endpoint of every failed link whenever possible (i.e. detouring failed links), enforcing waypoints and hence accounting for the network policy. The algorithms are particularly well-suited for emerging segment routing networks based on label stacks.
Cite as

Mahmoud Parham, Klaus-Tycho Foerster, Petar Kosic, and Stefan Schmid. Maximally Resilient Replacement Paths for a Family of Product Graphs. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 26:1-26:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{parham_et_al:LIPIcs.OPODIS.2020.26,
  author =	{Parham, Mahmoud and Foerster, Klaus-Tycho and Kosic, Petar and Schmid, Stefan},
  title =	{{Maximally Resilient Replacement Paths for a Family of Product Graphs}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{26:1--26:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.26},
  URN =		{urn:nbn:de:0030-drops-135111},
  doi =		{10.4230/LIPIcs.OPODIS.2020.26},
  annote =	{Keywords: Product Graphs, Resilience, Failures, Routing}
}
  • Refine by Author
  • 1 Foerster, Klaus-Tycho
  • 1 Kosic, Petar
  • 1 Parham, Mahmoud
  • 1 Schmid, Stefan

  • Refine by Classification
  • 1 Computer systems organization → Dependable and fault-tolerant systems and networks
  • 1 Mathematics of computing → Graph algorithms
  • 1 Networks → Routing protocols

  • Refine by Keyword
  • 1 Failures
  • 1 Product Graphs
  • 1 Resilience
  • 1 Routing

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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