A Replica Relocation Method for Improving Search Efficiency in P2P Networks

In P2P networks, it is effective to allocate replicas of each data item to multiple peers for improving search efficiency and data availability. It has been mathematically proved that the square-root allocation, in which the ratios of numbers of replicas are proportional to the square-root of their access frequencies, is optimal in terms of search efficiency. In this paper, we propose a replica relocation method that not only nearly achieves the square-root allocation but also distributes replicas uniformly in the network as much as possible. Our method creates replicas at each peer on the path along which a query is successfully forwarded. Here, each peer on the path determines whether it creates the replica or not based on the access frequency of the data item. In addition, for creating a new replica when a cache memory space is full, our method preferentially deletes a replica of a data item which has been replicated at a large number of peers.