Discovering Network Neighborhoods Using Peer-to-Peer Lookups

Abstract

In many distributed applications, end hosts need to know the network locations of other nearby participating hosts in order to enhance overall performance. Potential applications that can benefit from the location information include automatic selection of nearby Web servers, proximity routing in a peer-to-peer system, and loss recovery in reliable multicasting. We focus in this paper on the network neighborhood discovery problem in large-scale distributed systems. In these systems, the number of participating nodes can be very large, and the membership can dynamically change. Our goal is for each node to discover other "nearby" participating nodes in a completely decentralized manner, where each node probes only a small subset of other nodes in the system. This approach will lead to improved overall performance by matching client requests for services with participants in the peer-to-peer service system that are, on average, nearby in the network sense. Recent works in distributed peer-to-peer systems, such as Chord, CAN, Tapestry and Pastry, provide efficient distributed lookup structures. In this paper, we investigate a rendezvous-based scheme for a node to discover other nearby participating nodes using a peer-to-peer lookup system such as Chord. Given a key, the Chord protocol maps the key onto a node. Our idea for network neighborhood discovery is for each host to compute a key that characterizes its network location on the Internet. We call such a key the location key, and the nodes that these location keys are mapped to the Rendezvous Points. To lookup other nearby participating nodes, a node seeking some service queries its corresponding rendezvous point using its location key. We focus on the issue of how to generate the location key in a distributed fashion such that nodes that are close to each other in the actual network will have similar location key values, and therefore be mapped to nearby locations on the Chord ring. In this paper, we examine the performance tradeoffs of such a rendezvous scheme using the Global Network Positioning (GNP) approach to generate the location keys. In GNP, each node measures its network distances to a few landmark nodes to derive its coordinates in a D-dimensional geometric space. We generate a host's Chord location key from its 1-dimensional GNP coordinate, and use coordinates from a higher dimensional space to refine the searching process for the closest node. We evaluate our scheme in the context of the nearest neighbor discovery problem. Using data from the Active Measurement Project of the National Laboratory for Applied Network Research (NLANR), we compare its performance with a random mapping scheme, where location keys are randomly generated. Using our coordinate-based rendezvous scheme, 66% of the nodes found their actual closest network neighbor by pinging only a small number of nodes.