Survey of Various Search Mechanisms in Unstructured Peer-to-Peer Networks
---
paper_title: Learning to route queries in unstructured P2P networks: Achieving throughput optimality subject to query resolution constraints

paper_content:

Finding a document or resource in an unstructured peer-to-peer network can be an exceedingly difficult problem. In this paper we propose a dynamic query routing approach that accounts for arbitrary overlay topologies, nodes with heterogeneous processing capacity and heterogenous class-based likelihoods of query resolution at nodes, reflecting the query loads and manner in which files/resources are distributed across the network. Finite processing capacity at nodes, e.g., reflecting their degree of altruism, can indeed limit the stabilizable load into the system. Our approach is shown to be throughput optimal subject to a grade of service constraint, i.e., it stabilizes the query load subject to a guarantee that queries' routes meet pre-specified class-based bounds on their associated a priori probability of query resolution. Numerical and simulation results show significant improvement in capacity region and performance benefits, in terms of mean delay, over random walk based searches. Additional aspects associated with reducing complexity, learning, and adaptation to class-based query resolution probabilities and traffic loads are studied.
---
paper_title: Exploiting dynamic querying like flooding techniques in unstructured peer-to-peer networks

paper_content:

In unstructured peer-to-peer networks, controlled flooding aims at locating an item at the minimum message cost. Dynamic querying is a new controlled flooding technique. While it is implemented in some peer-to-peer networks, little is known about its undesirable behavior and little is known about its general usefulness in unstructured peer-to-peer networks. This paper describes the first evaluation and analysis of such techniques, and proposes novel techniques to improve them. We make three contributions. First, we find the current dynamic querying design is flawed. Although it is advantageous over the expanding ring algorithm in terms of search cost, it is much less attractive in terms of peer perceived latency, and its strict constraints on network connectivity prevent it from being widely adopted. Second, we propose an enhanced flooding technique which requires the search cost close to the minimum, reduces the search latency by more than four times, and loosens the constraints on the network connectivity. Thus, we make such techniques useful for the general unstructured peer-to-peer networks. Third, we show that our proposal requires only minor modifications to the existing search mechanisms and can be incrementally deployed in peer-to-peer networks.
---
paper_title: Hybrid search schemes for unstructured peer-to-peer networks

paper_content:

We study hybrid search schemes for unstructured peer-to-peer networks. We quantify performance in terms of number of hits, network overhead, and response time. Our schemes combine flooding and random walks, look ahead and replication. We consider both regular topologies and topologies with supernodes. We introduce a general search scheme, of which flooding and random walks are special instances, and show how to use locally maintained network information to improve the performance of searching. Our main findings are: (a) a small number of supernodes in an otherwise regular topology can offer sharp savings in the performance of search, both in the case of search by flooding and search by random walk, particularly when it is combined with 1-step replication. We quantify, analytically and experimentally, that the reason of these savings is that the search is biased towards nodes that yield more information. (b) There is a generalization of search, of which flooding and random walk are special instances, which may take further advantage of locally maintained network information, and yield better performance than both flooding and random walk in clustered topologies. The method determines edge critically and is reminiscent of fundamental heuristics from the area of approximation algorithms.
---
paper_title: Survey of Search and Replication Schemes in Unstructured P2P Networks

paper_content:

P2P computing lifts taxing issues in various areas of computer science. The largely used decentralized unstructured P2P systems are ad hoc in nature and present a number of research challenges. In this paper, we provide a comprehensive theoretical survey of various state-of-the-art search and replication schemes in unstructured P2P networks for file-sharing applications. The classifications of search and replication techniques and their advantages and disadvantages are briefly explained. Finally, the various issues on searching and replication for unstructured P2P networks are discussed.
---
paper_title: Search performance analysis in peer-to-peer networks

paper_content:

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.
---
paper_title: Enhancing Routing Robustness of Unstructured Peer-to-Peer Networks Using Mobile Agents

paper_content:

The growing popularity of Peer-to-Peer (P2P) technology in real applications in recent years has sparked increasing interest from both academia and industry in designing resilient P2P networks for these applications. Routing is a crucial technique to support successful P2P applications, and designing robust routing mechanisms is still a technical challenge for P2P systems and applications due to their inherent dynamics. This paper addresses the issue of resilient routing in unstructured P2P networks. To this end, we first propose a novel query routing approach to improving query performance in unstructured P2P networks, and then develop a mobile agent based network reconfiguration mechanism that provides a combined node and link failure diagnosis and restoration to maintain routing performance even in dynamic network environments. Simulated results show that the proposed query routing approach can achieve a good tradeoff between query hit rates and space costs in scale-free networks and that the mobile agent based network reconfiguration mechanism outperforms the existing methods in different types of network topologies.
---
paper_title: Survey of Search and Replication Schemes in Unstructured P2P Networks

paper_content:

P2P computing lifts taxing issues in various areas of computer science. The largely used decentralized unstructured P2P systems are ad hoc in nature and present a number of research challenges. In this paper, we provide a comprehensive theoretical survey of various state-of-the-art search and replication schemes in unstructured P2P networks for file-sharing applications. The classifications of search and replication techniques and their advantages and disadvantages are briefly explained. Finally, the various issues on searching and replication for unstructured P2P networks are discussed.
---
paper_title: Maintenance strategies for routing indexes

paper_content:

Query processing in large-scale unstructured P2P networks is a crucial part of operating such systems. In order to avoid expensive flooding of the network during query processing so-called routing indexes are used. Each peer maintains such an index for its neighbors. It provides a compact representation (data summary) of data accessible via each neighboring peer. An important problem in this context is to keep these data summaries up-to-date without paying high maintenance costs. In this paper, we investigate the problem of maintaining distributed data summaries in P2P-based environments without global knowledge and central instances. Based on a classification of update propagation strategies, we discuss several approaches to reduce maintenance costs and present results from an experimental evaluation.
---

<format>
Title: Survey of Various Search Mechanisms in Unstructured Peer-to-Peer Networks

Section 1: INTRODUCTION
Description 1: Provide an overview of peer-to-peer (P2P) computing, focus on unstructured P2P networks, explain the challenges of search algorithms, and underline the importance of efficient search mechanisms.

Section 2: SEARCH TECHNIQUES
Description 2: Discuss the categorization of search algorithms into blind and informed search techniques. Describe their characteristics and how they influence the search process in unstructured P2P networks.

Section 3: Gnutella (Flooding)
Description 3: Describe the original Gnutella algorithm using flooding for object discovery, its simplicity, and the significant overhead it causes in large networks.

Section 4: Modified-BFS
Description 4: Explain the variation of flooding that uses a random ratio of neighbors to forward the query. Highlight its message reduction capabilities and contact spread.

Section 5: Iterative Deepening
Description 5: Discuss the iterative deepening method where BFS searches have increasing depth limits. Include its termination conditions, advantages, and drawbacks in dynamic situations.

Section 6: Random Walk
Description 6: Describe the Random Walk method, its conservative nature, termination methods, and limitations related to search time and success rate.

Section 7: Intelligent-BFS
Description 7: Explain Intelligent-BFS, which uses query results to forward queries more intelligently. Discuss its advantages like high accuracy and limitations like non-adaptation to network changes.

Section 8: Adaptive Probabilistic Search (APS)
Description 8: Describe APS, which uses past search experiences to build knowledge. Highlight its bandwidth efficiency and its strengths in handling large workloads.

Section 9: Local Indices
Description 9: Explain the Local Indices mechanism where nodes index objects within a specific radius. Discuss its high accuracy and how the indices are updated with node changes.

Section 10: Routing Indices (RI)
Description 10: Discuss the use of thematic categories in Routing Indices and the forwarding process. Highlight its advantages and major problems like index maintenance overheads.

Section 11: Distributed Resource Location Protocol (DRLP)
Description 11: Describe DRLP, which relies on probabilistic parameters for node forwarding and query backtracking for efficient resource location. Discuss its message production and its performance in dynamic networks.

Section 12: CONCLUSION
Description 12: Summarize the various algorithms and mechanisms discussed, outline their advantages and disadvantages, and suggest guidelines for choosing the appropriate mechanism based on specific network requirements.

Section 13: REFERENCES
Description 13: List all references used in the survey paper.
</format>
