Abstract
Distributed hash tables (DHTs), used in a number of structured peer-to-peer systems, provide efficient mechanisms for resource location. A key distinguishing feature of current DHT systems such as Chord, Pastry, and Tapestry is the way they handle locality in the underlying network. Topology-based node identifier assignment, proximity routing, and proximity neighbor selection are examples of heuristics used to minimize message delays in the underlying network. While these heuristics are sometimes effective, they rely on a single global overlay that may install the key of a popular object at a node far from most of the nodes accessing it. Furthermore, a response to a lookup does not contain any locality information about the nodes holding a copy of the object. We address these issues by proposing a novel two-level overlay peer-to-peer architecture. In our architecture, local overlays act as locality-aware caches for the global overlay, grouping nodes close together in the underlying network. Local overlays are constructed by exploiting the structure of the Internet as autonomous systems. We present detailed experimental results demonstrating the practicality of the system, and showing performance gains in response time of up to 60% compared to a single global overlay with state-of-the-art localization schemes. We also present efficient distributed algorithms for maintaining local overlays in the presence of node arrivals and departures.
