Pruning the computation of distributed shortest paths in power-law networks

We propose a general, simple and practical technique, named Distributed Leafs Pruning (DLP), which can be combined with every distance vector routing algorithm based on shortest paths, allowing to reduce the total number of messages sent by that algorithm. We combine the new technique with three algorithms known in the literature: DUAL, which is loop-free and is part of CISCO’s widely used EIGRP proto- col; DUST, which has been shown to be effective on networks with power law node degree distribution, although it suffers of looping; LFR, which has been very recently introduced, is loop-free and has been shown to be very effective on real networks. We give experimental evidence that these combinations lead to an important gain in terms of the number of messages sent by DUAL, DUST and LFR, on networks having a power-law node degree distribution. We also notice that, in many cases the use of DLP deter- mines a gain in terms of the maximum and the average space occupancy per node.