DROPS

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.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}
}

Search Results

Documents authored by Kosic, Petar

Maximally Resilient Replacement Paths for a Family of Product Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message