Exploiting local popularity to prune routing indices in peer-to-peer systems

Abstract

Routing in unstructured peer-to-peer systems relies either on broadcasting (also called flooding) or on routing indices. An approach using routing indices is only scalable if the routing indices are of manageable size. In this paper, we present a strategy to prune routing indices based on popularity of resources. Routing indices maintain routing information for queries to the most popular resources, leaving queries to other resources to be routed randomly. The popularity of resources at each node of a network is learnt by each routing index, by means of a replacement strategy. We compare the performance of the local popularity method against that of the global popularity method in pruning routing indices in both static and dynamic environments. We compare the effectiveness and the efficiency of two standard replacement strategies: Least Frequently Used (LFU) and Least Recently Used (LRU). Our results confirm the efficiency and effectiveness of pruning routing indices based on the local popularity of resources in unstructured peer-to-peer networks. © 2005 IEEE.