Decentralized Peer-to-Peer (P2P) overlay networks are distributed systems in nature, without any hierarchical organization or centralized control. They are typically divided in two main classes: structured and unstructured .
Structured P2P overlay network have tightly controlled topologies and content is placed at specified locations to efficiently solve queries. Some well-known examples are Content Addressable Network (CAN) , Chord  and Pastry . Such overlays use a Distributed Hash Table (DHT) as substrate, where data objects (or values) are placed deterministically at the peers whose identifiers correspond to the data object’s unique key. In DHT-based systems, node ...view middle of the document...
When a node asks for an object, the query passes through the circle until it gets to its proper successor. In Pastry , each node in the network has a unique, uniform random identifier in a circular 128-bit identifier space. In order to route a query, each node checks its routing table and forwards it to a node that is numerically closest to the key. Since the focus of this paper is not on structured P2P networks, for the reasons highlighted in the next Subsection 2.2, we refer to [39, 40] for more information about them.
An unstructured P2P system is composed of peers joining the network with some loose rules and without any prior knowledge of a specific topology to preserve . The resulting topology may have certain properties, though the placement of objects at the peers is not based on any specific topology-related property . Thus, unstructured overlays provide complete flexibility on where resources can be published by the peers; search methods are not based on hash functions and can naturally support non-exact matches.
Search techniques for unstructured P2P overlays are typically categorized in blind and informed [41, 43].
Blind search schemes employ flooding or random-based techniques to relay queries to peers in the network. Peers keep no information about the P2P network or the probable locations of objects for routing queries . Flooding is the typical mechanism used to send queries across the overlay with a limited scope (e.g. Gnutella ). It consists in a Breadth First Search (BFS) of the overlay network: when a peer receives a query, it returns the results if present, otherwise it retransmits the query to all of its neighbors, except for the sender, until the TTL associated with the query expires. Flooding-based techniques are effective for locating highly replicated items and resilient to peers joining and leaving the system, but they are not scalable as the load on each peer grows linearly with the total number of queries and the system size . Thus, low bandwidth nodes easily become bottlenecks when handling a high rate of queries and large systems quickly become overwhelmed by the query-induced load . Several approaches have been proposed to address this problem. These include variations on random BFS [46-48], which perform random neighbors selection based on local degree information; iterative deepening [49-51] consisting in successive multiple breadth-first searches with increasing depth limits; random walks and its variations like random k-walk  or probabilistic gossip strategies and a two-level random k-walk . However, blind methods either does not scale well because of the high message overhead or exhibit high resolution time as the query routing is not guided towards the target peers during random walks and the same paths can be repeatedly explored.
Therefore, informed search algorithms have been introduced to improve search performance by using network information during query routing....