文章基本信息

标题：Maximally Resilient Replacement Paths for a Family of Product Graphs
本地全文：下载
作者：Mahmoud Parham ; Klaus-Tycho Foerster ; Petar Kosic 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：184
页码：26:1-26:16
DOI：10.4230/LIPIcs.OPODIS.2020.26
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Product Graphs; Resilience; Failures; Routing