Back to Search
Start Over
Grafting Arborescences for Extra Resilience of Fast Rerouting Schemes
- Source :
- INFOCOM, Infocom 2021, Infocom 2021, May 2021, Virtual, France
- Publication Year :
- 2021
- Publisher :
- HAL CCSD, 2021.
-
Abstract
- International audience; To provide a high availability and to be able to quickly react to link failures, most communication networks feature fast rerouting (FRR) mechanisms in the data plane. However, configuring these mechanisms to provide a high resilience against multiple failures is algorithmically challenging, as rerouting rules can only depend on local failure information and need to be predefined. This paper is motivated by the observation that the common approach to design fast rerouting algorithms, based on spanning trees and covering arborescences, comes at a cost of reduced resilience as it does not fully exploit the available links in heterogeneous topologies. We present several novel fast rerouting algorithms which are not limited by spanning trees, but rather extend and combine ("graft") multiple spanning arborescences to improve resilience. We compare our algorithms analytically and empirically, and show that they can significantly improve not only the resilience, but also accelerate the preprocessing to generate the local fast failover rules.
- Subjects :
- Spanning tree
[INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI]
Computer science
Distributed computing
Grafting (decision trees)
[INFO] Computer Science [cs]
Network topology
Telecommunications network
Failover
[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI]
Forwarding plane
[INFO]Computer Science [cs]
Resilience (network)
Heterogeneous network
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- INFOCOM, Infocom 2021, Infocom 2021, May 2021, Virtual, France
- Accession number :
- edsair.doi.dedup.....a48ca7eeebc00f8bc8e11d9e37ae6fb0