EFFICIENT ROUTING MECHANISM IN UNSTRUCTURED P2P NETWORKS

International Journal of Computer Science (IJCS) Published by SK Research Group of Companies (SKRGC)

Abstract

Designing efficient search algorithms is a key challenge in unstructured peer-to-peer networks. Flooding and random walk (RW) are two typical search algorithms. Flooding searches aggressively and covers the most nodes. However, it generates a large amount of query messages and, thus, does not scale. On the contrary, RW searches conservatively. It only generates a fixed amount of query messages at each hop but would take longer search time. We propose the dynamic search (DS) algorithm, which is a generalization of flooding and RW. DS takes advantage of various contexts under which each previous search algorithm performs well. It resembles flooding for short-term search and RW for long-term search. Moreover, DS could be further combined with knowledge-based search mechanisms to improve the search performance. We analyze the performance of DS based on some performance metrics including the success rate, search time, query hits, query messages, query efficiency, and search efficiency. Numerical results show that DS provides a good trade off between search performance and cost. On average, DS performs about 25 times better than flooding and 58 times better than RW in power-law graphs, and about 186 times better than flooding and 120 times better than RW in bimodal topologies.

References

[1]D. Stutzbach, R. Rejaie, N. Duffield, S. Sen, and W. Willinger, “Sampling Techniques for Large, Dynamic Graphs,” Proc. Ninth IEEE Global Internet Symp. (Global Internet ’06), Apr. 2006.

[2] A.H. Rasti, D. Stutzbach, and R. Rejaie, “On the Long-Term Evolution of the Two-Tier Gnutella Overlay,” Proc. Ninth IEEE Global Internet Symp. (Global Internet ’06), Apr. 2006.

[3] D. Milojicic, V. Kalogeraki, R. Lukose, K. Nagaraja, J. Pruyne,B. Richard, S. Rollins, and Z. Xu, “Peer-to-Peer Computing,” Technical Report HPL-2002-57, HP, 2002.

[4] K. Sripanidkulchai, The Popularity of Gnutella Queries and ItsImplications on Scalability, white paper, Carnegie Mellon Univ.,Feb. 2001.

[5] M. Jovanovic, F. Annexstein, and K. Berman, “Scalability Issues in Large Peer-to-Peer Networks: A Case Study of Gnutella,”technical report, Laboratory for Networks and Applied Graph Theory, Univ. of Cincinnati, 2001.

[6] B. Yang and H. Garcia-Molina, “Improving Search in Peer-to-Peer Networks,” Proc. 22nd Int’l Conf. Distributed Computing Systems (ICDCS ’02), pp. 5-14, July 2002.

[7] G. Kan, “Gnutella,” Peer-to-Peer Harnessing the Power of Disruptive Technologies, O’Reilly, pp. 94-122, 2001.

[8] RFC-Gnutella 0.6, https://rfc-gnutella.sourceforge.net /developer/ testing/index.html, 2008.

[9] C. Gkantsidis, M. Mihail, and A. Saberi, “Random Walks in Peer-to-Peer Networks,” Proc. IEEE INFOCOM ’04, pp. 120-130,2004.

[10] L.A. Adamic, R.M. Lukose, A.R. Puniyani, and B.A. Huberman, “Search in Power-Law Networks,” Physical Rev., E, vol. 64, 046135,2001.

Keywords

Peer-to-Peer, Search, Stability, Backpressure, Random Walk