DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2018.13

Local Fast Segment Rerouting on Hypercubes

Authors: Klaus-Tycho Foerster, Mahmoud Parham, Stefan Schmid, and Tao Wen

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

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.

Cite as

Klaus-Tycho Foerster, Mahmoud Parham, Stefan Schmid, and Tao Wen. Local Fast Segment Rerouting on Hypercubes. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{foerster_et_al:LIPIcs.OPODIS.2018.13,
  author =	{Foerster, Klaus-Tycho and Parham, Mahmoud and Schmid, Stefan and Wen, Tao},
  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 =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.13},
  URN =		{urn:nbn:de:0030-drops-100739},
  doi =		{10.4230/LIPIcs.OPODIS.2018.13},
  annote =	{Keywords: segment routing, local fast failover, link failures}
}

Search Results

Documents authored by Wen, Tao

Local Fast Segment Rerouting on Hypercubes

Abstract

Cite as

Thanks for your feedback!

Could not send message