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 tradeoff 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.

Flooding and random walk (RW) are the two typical search algorithms in unstructured peer-to-peer networks. The flooding algorithm searches the network aggressively. It covers the most nodes but generates a large number of query messages. Hence it is considered to be not scalable. This cost issue is especially serious when the queried resource locates far from the query source. On the contrary, RW searches the network conservatively. It only generates a fixed amount of query messages at each hop, but it may take particularly longer search time to find the queries resource. We propose the dynamic search algorithm (DS) which is a generalization of flooding, modified breadth first search (MBFS), and RW. This search algorithm takes advantage of different contexts under which each previous search algorithm performs well. The operation of DS resembles flooding or MBFS for the short-term search, and RW for the long-term search. We analyze the performance of DS based on the power-law random graph model and adopt some performance metrics including the guaranteed search time, query hits, query messages, success rate, and a unified metric, search efficiency. The main objective is to obtain the effects of the parameters of DS. Numerical results show that proper setting of the parameters of DS can obtain the short guaranteed search time and provide a good tradeoff between the search performance and the cost.

This paper deliberates on various critical aspects in evaluating searching networks. Existing metrics either draw biased conclusions regarding search performance or provide wrong guidelines for algorithm design. We, therefore, define a unified criterion, search efficiency (SE), to objectively address search performance in a comprehensive manner. The goal of SE is to better characterize performance of searching networks than existing metrics do as well as to guide the design of future ones. We first validate the correctness of SE in performance evaluation in an ideal graph, strictly binary tree, by analyzing SE for two typical search methods, breadth first search and random walk. We further show its strength in performance characterization in the real-world topology, power-law random graph, under various network conditions. We finally design an algorithm, dynamic search, based on SE analysis. Its proved outstanding performance demonstrates the strength of SE to provide guidance for the future design of searching networks.

Recently peer-to-peer networks (P2P) have gained great attention and popularity. One key challenging aspect in a P2P resource sharing environment is an efficient searching algorithm. This is especially important for Gnutella-like decentralized and unstructured networks due to the power-law degree distributions. We propose a hybrid search algorithm that decides the number of running walkers dynamically with respect to peers' topological information and search time state. It is able to control the extent of messages generating temporally by the simulated annealing mechanism, thus being a scalable search. Furthermore, we present a unified quantitative search performance metric, search efficiency, to objectively capture dynamic behavior of various search algorithms in terms of scalability, reliability and responsiveness. We quantitatively characterize, through simulations, the performance of various existing search algorithms. The proposed algorithm outperforms others in terms of search efficiency in both the local and global search spaces.

Recently peer-to-peer networks (P2P) have gained great attention and popularity. One key challenging aspect in P2P resource sharing environments is efficient searching algorithm. This is especially important for Gnutella-like decentralized and unstructured networks since they have power-law degree distributions. A robust search algorithm should respond to the query message promptly without generating redundant query messages. We present unified quantitative search performance measurements: query efficiency, search responsiveness, and search efficiency to objectively capture dynamic behaviors of various search algorithms from different perspectives. To gain insight of these search algorithms, we quantitatively characterize, through simulations, their search performance on different network topologies with different query/replication distributions.