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 rout...