Replication methods for enhancing search performance in peer-to-peer services on power-law logical networks
Shingo Ata, Masayuki Murata, Yoshihiro Gotoh · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 2003
Many services have recently been offered based on a peer-to-peer (P2P) communication model. Peers connect to each other and build an overlaid logical network and available services are communicated over this network. The robustness of the P2P network against frequent peer failure must be considered. This includes when the peers leave the network and this directly affects the stability of the entire logical network. Replication of the content is one of the most useful techniques to increase robustness. However, the overall effectiveness of replication is heavily dependent on the topology of the logical network. As topology of networks, including the Internet and P2P, follows a Power-Law distribution pattern, we first investigate the effect of the logical network topology (especially of the Power-Law characteristics) on replication methods. We use a search method called "n-walkers random walk" in which multiple queries move randomly across the P2P logical network. We use a "path replication method," to create replicas at all the intermediate nodes on the path between the requesting and responding nodes. Through simulations experiments, we observed that peers with a large number of degrees (e.g., degree > 10) make four times as many replicas as peers with a small number of degrees. In addition, replicas on large degree's peers are used ten times as frequently as those on peers with small degrees. Based on these observations, we propose a query forwarding method that considers the Power-Law property of the network topology in order to improve the performance of the P2P service. In our method the queries are transmitted with different probabilities, dependending on the degree of each adjacent node. Our simulation results show that our proposed method can greatly improve the query performance by considering the characteristics of Power-Law. Our method reduces the average hop count in finding replicas by up to 60% compared with the random forwarding method.