AbstractsComputer Science

Finding all shortest paths in a distributed dynamic network has many practical applications, but it is perhaps most important in network routing. To this end a number of algorithms and techniques have been developed. This paper investigates one such technique called Distributed Computation Pruning (DCP), that utilizes a property found in many real-world networks, including the Internet, called Power Law degree distribution. DCP has previously been shown to improve All Pairs Shortest Paths algorithms on networks generated by the Barabási-Albert model. In this paper we extend the experimental evidence by evaluating the performance of algorithms combined with DCP on networks generated by the Generalized Linear Preference model (GLP). This model has previously been shown to generate networks that are more representative of the Internet than those generated by previous models. We found that algorithms that are combined with DCP see a distinct decrease in the amount of messages sent across the network, suggesting that DCP is a viable technique for improving existing routing algorithms.