Publication: Search Algorithms for Unstructured PeertoPeer Networks
All
 By Area
 By Year
Title 
Search Algorithms for Unstructured PeertoPeer Networks

Authors/Editors* 
Reza Dorrigiv, Alejandro LopezOrtiz, Pawel Pralat

Where published* 
Proceedings of 32nd IEEE Conference on Local Computer Networks (LCN) 
How published* 
Proceedings 
Year* 
2007 
Volume 
1 
Number 
1 
Pages 
343352 
Publisher 
LCN 
Keywords 

Link 
http://www.math.ryerson.ca/~pralat/research.html 
Abstract

We study the performance of several search algorithms on unstructured peertopeer networks, both using classic search algorithms such as flooding and random walk, as well as a new hybrid algorithm proposed in this paper. This hybrid algorithm first uses flooding to find sufficient number of nodes and then starts random walks from these nodes. We compare the performance of the search algorithms on several graphs corresponding to common topologies proposed for peertopeer networks. In particular, we consider binomial random graphs, regular random graphs, powerlaw graphs, and clustered topologies. Our experiments show that for binomial random graphs and regular random graphs all algorithms have similar performance. For powerlaw graphs, flooding is effective for small number of messages, but for large number of messages our hybrid algorithm outperforms it. Flooding is ineffective for clustered topologies in which random walk is the best algorithm. For these topologies, our hybrid algorithm provides a compromise between flooding and random walk. We also compare the proposed hybrid algorithm with the kwalker algorithm on powerlaw and clustered topologies. Our experiments show that while they have close performance on clustered topologies, the hybrid algorithm has much better performance on powerlaw graphs. We theoretically prove that flooding is effective for regular random graphs which is consistent with our experimental results. 
Go to Random Graph Theory
Back to page 69 of list
