Accelerating Lookups in P2P Systems using Peer Caching

Many structured peer-to-peer (P2P) systems have been proposed as distributed hash tables (DHTs) for fast and efficient lookup of queries. In this paper, we propose a novel technique for improving average lookup times in P2P systems by caching additional neighbor pointers based on peer access frequencies. In particular, we address the problem of each peer choosing the k best pointers to store (in addition to its index pointers) to minimize the average query lookup times. We focus on two popular P2P systems, namely Pastry and Chord: we exploit the inherent structure of these systems to develop efficient, scalable algorithms for optimally choosing the k additional pointers. Simulations with Chord and Pastry demonstrate that our algorithms are very effective in reducing the lookup times significantly. Our approach can be used in tandem with other techniques such as item caching and replication, and is particularly useful for applications such as name services in mobile environments or location services, where we can expect a low churn rate for peers and a relatively higher churn rate for items.