On the Distributed Computation of Load Centrality and its Application to DV Routing

Centrality metrics are a key instrument for graph analysis and play a central role in many problems related to networking such as service placement, robustness analysis and network optimization. Betweenness centrality is one of the most popular and well-studied metric. While distributed algorithms to compute this metric exist, they are either approximated or limited to certain topologies (directed acyclic graphs or trees). Exact distributed algorithms for betweenness centrality are computationally complex, because its calculation requires the knowledge of all possible shortest paths within the graph. In this paper we consider load centrality, a metric that usually converges to betweenness, and we present the first distributed and exact algorithm to compute it. We prove its convergence, we estimate its complexity and we show it is directly applicable-with minimal modifications-to any distance-vector routing protocol based on Bellman-Ford. We finally implement it on top of the Babel routing protocol and we show that, exploiting centrality, we can significantly reduce Babel's convergence time upon node failure without increasing signalling overhead. Our contribution is relevant in the realm of wireless distributed networks, but the algorithm can be adopted in any distributed system where it is not possible, or computationally impractical, to reconstruct the whole network graph at each node and compute betweenness centrality with the classical approach based on Dijkstra's algorithm.