Dynamic Search Algorithm used in Unstructured Peer-to-Peer Networks
 |
International Journal of Engineering Trends and Technology (IJETT) |  |
| © 2011 by IJETT Journal | ||
| Volume-2 Issue-3 |
||
| Year of Publication : 2011 | ||
| Authors : B.Srikanth,K.Venkateswara Rao |
||
Citation
B.Srikanth,K.Venkateswara Rao."Dynamic Search Algorithm used in Unstructured Peer-to-Peer Networks". International Journal of Engineering Trends and Technology (IJETT),V2(3):15-19 Nov to Dec 2011. ISSN:2231-5381. www.ijettjournal.org. Published by Seventh Sense Research Group.
Abstract
Designing efficient search algorithms is a key challenge in unstructured peer - to - peer networks. Flooding and rand om 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 fix ed 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 p erform s 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 met rics including the success rate, search time, query hits, query messages, query efficiency, and search efficiency. Numerical results show that DSprovides a good tradeoff between search performance and cost. On average, DS performs about 25 times better tha n 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. Rejai e, 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 Gnu tella 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 Its Implications 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 Stud y 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.
Keywords
Peer - to - peer, performance analysis, search algorithm.