Local Fast Failover Routing on Directed Networks
Jonas Grobe, Stephanie Althoff, Klaus-Tycho Foerster · 2024
The fast and resilient routing of packets in networks presents a complex problem with high practical relevance due to its application in local/wide area networks and the Internet in general: nearly all modern communication networks implement some form of re-routing to retain connectivity after failures. Therefore a lot of research regarding this problem has been conducted, but it is almost exclusively focused on the prevalent case of undirected networks. In this paper we hence provide an overview of the current research concerning fast rerouting algorithms and the unique challenges of re-routing on directed graphs, in particular the transferability of existing algorithms to this special case. Subsequently, one of these algorithms, called Keep Forwarding, originally designed for undirected graphs, is adapted for directed graphs and then evaluated against other algorithms in a simulation on synthetic (random and disk graphs) and real-world (from the Heathland sensor network experiment) topologies. We show that our adaptation is superior to the other algorithms on most topologies, with the average packet loss and stretch being up to$61 \%$and$65 \%$lower than the second-best respectively on the real-world topology.