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.2018.13
URN: urn:nbn:de:0030-drops-100739
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10073/
Go to the corresponding LIPIcs Volume Portal

Foerster, Klaus-Tycho ; Parham, Mahmoud ; Schmid, Stefan ; Wen, Tao

Local Fast Segment Rerouting on Hypercubes

pdf-format:
LIPIcs-OPODIS-2018-13.pdf (1 MB)

Abstract

Fast rerouting is an essential mechanism in any dependable communication network, allowing to quickly, i.e., locally, recover from network failures, without invoking the control plane. However, while locality ensures a fast reaction, the absence of global information also renders the design of highly resilient fast rerouting algorithms more challenging. In this paper, we study algorithms for fast rerouting in emerging Segment Routing (SR) networks, where intermediate destinations can be added to packets by nodes along the path. Our main contribution is a maximally resilient polynomial-time fast rerouting algorithm for SR networks based on a hypercube topology. Our algorithm is attractive as it preserves the original paths (and hence waypoints traversed along the way), and does not require packets to carry failure information. We complement our results with an integer linear program formulation for general graphs and exploratory simulation results.

BibTeX - Entry

@InProceedings{foerster_et_al:LIPIcs:2018:10073,
  author =	{Klaus-Tycho Foerster and Mahmoud Parham and Stefan Schmid and Tao Wen},
  title =	{{Local Fast Segment Rerouting on Hypercubes}},
  booktitle =	{22nd International Conference on Principles of Distributed  Systems (OPODIS 2018)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{125},
  editor =	{Jiannong Cao and Faith Ellen and Luis Rodrigues and Bernardo Ferreira},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10073},
  URN =		{urn:nbn:de:0030-drops-100739},
  doi =		{10.4230/LIPIcs.OPODIS.2018.13},
  annote =	{Keywords: segment routing, local fast failover, link failures}
}

Keywords: segment routing, local fast failover, link failures
Collection: 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)
Issue Date: 2018
Date of publication: 15.01.2019

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