2026-08-13T05:57:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10073 2024-03-06T10:45:33Z ddc:004 open_access

Local Fast Segment Rerouting on Hypercubes Foerster, Klaus-Tycho Parham, Mahmoud Schmid, Stefan Wen, Tao segment routing local fast failover link failures 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Klaus-Tycho Foerster and Mahmoud Parham and Stefan Schmid and Tao Wen 2019 Is Part Of LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2018.13 urn:nbn:de:0030-drops-100739 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.13 eng https://creativecommons.org/licenses/by/3.0/legalcode