Improving routing convergence with centrality: Theory and implementation of pop-routing

One of the key features of a routing protocol is its ability to recover from link or node failures, recomputing routes efficiently without creating temporary loops. Indeed, in real conditions, there is always a trade-off between the overhead due to the periodic generation of control messages and route convergence time. This paper formalizes the problem of the choice of timers for control message generation as an optimization problem that minimizes the route convergence time, constrained to a constant signaling overhead. The solution requires the knowledge of nodes' centrality in the topology and can be obtained with a computational complexity low enough to allow on-line computation of the timers. Results on both synthetic and real topologies show a significant decrease of the transient duration with the consequent performance gain in terms of reduced number of unreachable destinations and routing loops. Our proposal is general and it can be applied to enhance any link-state routing protocol, albeit it is more suited for wireless networks. As a concrete example, we present the extension of OLSRv2 with our proposal, named Pop-Routing, and discuss its performance and the stability of centrality metrics in three large-scale real wireless mesh networks. This exhaustive analysis on traces of the topology evolution of real networks for one entire week shows that pop-routing outperforms the non-enhanced protocol in every situation, even when it runs with sub-optimal timers due to centrality computation on stale information. This situation must be taken into account, as, albeit computationally light weight, the optimization cannot run in real-time on wireless routers.