License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2020.26
URN: urn:nbn:de:0030-drops-135111
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13511/
Go to the corresponding LIPIcs Volume Portal

Parham, Mahmoud ; Foerster, Klaus-Tycho ; Kosic, Petar ; Schmid, Stefan

Maximally Resilient Replacement Paths for a Family of Product Graphs

pdf-format:
LIPIcs-OPODIS-2020-26.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{parham_et_al:LIPIcs:2021:13511,
  author =	{Mahmoud Parham and Klaus-Tycho Foerster and Petar Kosic and Stefan Schmid},
  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 =	{Quentin Bramas and Rotem Oshman and Paolo Romano},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13511},
  URN =		{urn:nbn:de:0030-drops-135111},
  doi =		{10.4230/LIPIcs.OPODIS.2020.26},
  annote =	{Keywords: Product Graphs, Resilience, Failures, Routing}
}

Keywords: Product Graphs, Resilience, Failures, Routing
Collection: 24th International Conference on Principles of Distributed Systems (OPODIS 2020)
Issue Date: 2021
Date of publication: 25.01.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI