Abstract Exploiting network proximity in peer-to-peer overlay networks

Generic peer-to-peer (p2p) overlay networks like CAN, Chord, Pastry and Tapestry offer a novel platform for a variety of scalable and decentralized distributed applications. These systems provide efficient and fault-tolerant routing, object location and load balancing within a self-organizing overlay network. One important aspect of these systems is how they exploit network proximity in the underlying Internet. In this paper, we present a comprehensive study of the network locality properties of a p2p overlay network. Results obtained via analysis and via simulation of two large-scale topology models indicate that it is possible to efficiently exploit network proximity in self-organizing p2p substrates. A simple heuristic measures a scalar proximity metric among a small number of nodes, incurring only a modest additional overhead for organizing and maintaining the overlay network. The resulting locality properties improve application performance and reduce network usage in the Internet substantially. Finally, we study the impact of proximity-based routing on the load balancing in the p2p overlay.