Pop-Routing: Centrality-based Tuning of Control Messages for Faster Route Convergence

Fast and efficient recovery from node failure, with minimal disruption of routes and the consequent traffic loss is of the utmost importance for any routing protocol. Link-state protocols, albeit preferred to distance vector ones because of faster convergence, still suffer from a trade-off between control message overhead and performance. This work formalizes the routes' disruption following a node failure as an optimization problem depending on the nodes' centrality in the topology, constrained to a constant signaling overhead. Next, it shows that the solution can be found using Lagrange Multipliers. The solution complexity is low enough to be computed on-line on the network routers, thus obtaining the optimal setting of control message timers that minimize the traffic loss following a node failure. The gain obtained is quantified in power-law synthetic topologies, and it is also tested on real network topologies extending the OLSR protocol to use the modified timers, showing that the inevitable approximations introduced in the analysis do not hamper the very good results achievable through this novel approach. The technique can be applied to any link state protocol, including OSPF, and improves route convergence not only upon failures but on every topology modification.