Echo: A peer-to-peer clustering framework for improving communication in DHTs

One of the main challenges of peer-to-peer (P2P) systems is how to efficiently store and locate the ever-increasing amount of data being shared by participants. Indexing methods have been adapted on top of P2P networks and querying methods have been developed to handle data distribution across different nodes. Among these technologies, Distributed hash tables (DHTs) provide the highest scalable substrates. Although DHTs have many virtues, yet, it is hard to develop certain types of applications. For instance, distributing multimedia content among users who form communities based on their interests or their location is difficult to achieve in plain DHTs. To support a broader range of applications, we present Echo, a framework that benefits from the recursive structure of DHTs to embed clusters into their structures at almost no cost. While retaining the uniformity, scalability and load balancing of the original designs, Echo improves their scalability by taking advantage of the locality in communication exhibited by communities of users. Since our framework is based on the Cayley graph-theoretic model, it is applicable to a large subset of the most representative DHTs. As an illustrative example, we show how Chord can be transformed into a clustered DHT using our methodology. Furthermore, we give some indicative hints of how six different DHTs - Randomized Chord, Symphony, Kademlia, P-Grid, Tapestry and Pastry - can be transformed into their Echoing versions. Simulations results verify the effectiveness of Echo. (C) 2009 Elsevier Inc. All rights reserved.