Leopard: A Location-Aware Peer-To-Peer System With No Hot Spot

Date of Submission: 
July 27, 2004
Report Number: 
04-031
Report PDF: 
Abstract: 
We propose an alternative approach for building structured peer-to-peer systems. The major design objectives are i) to explicitly incorporate locality information into the system to minimize routing stretch in object look-up service, and ii) to inherently better cope with the ``flash crowd'' problem. Unlike the standard DHT-based approach, where both objects and nodes are assigned a randomly hashed id in the same id space, we separate the object id space from the node space. More specifically, each object is assigned an id in an object id space, whereas each node is assigned a coordinate in a coordinate system (referred to as the node geo space) reflects the ``geographical proximity'' of nodes. The object id space and the node geo space are ``weaved'' together via a novel hashing technique called {\em geographically-scoped hashing}. Using this approach, we develop a structured P2P look-up system called Leopard. Through analysis and simulations, we demonstrate that i) in Leopard object look-up latency is proportional to the distance between a requesting node and the target object; ii) in case multiple copies of an object exist, Leopard always locates a near-by copy; and iii) Leopard can effectively handle ``flash crowd'' traffic with near optimal load balancing.