Perfect Routing Arborescences for Fast Reroute

Owing to its quick reaction to link failures, fast reroute is among the most popular survivable routing approaches in carrier-grade backbone networks. By using preconfigured routing tables, routers can select a failover path for packets based solely on locally available information. Although arc-disjoint spanning arborescences are frequently used to configure forwarding tables in fast reroute, they only provide survivability up to the global connectivity of the network, thus, they fail to maximize survivability in topologies with dense subgraphs. In this paper, we investigate routing arborescences, a generalization of spanning arborescences for fast reroute in which the arborescences are not required to span the entire network. We prove a surprising graph-theoretical result: for any chosen root node in real-world topologies with bidirectional communication links perfect routing arborescences always exist, i.e., each node with local connectivity k to the root is included in exactly k arc-disjoint arborescences. Our constructive proof gives a fast heuristic algorithm to build perfect routing arborescences, offering four optimization options to minimize path length as its primary objective. Extensive simulations are conducted on real-world topologies, demonstrating that our method significantly improves path stretch in the routing arborescences compared to previous methods.