Search Strategies in Unstructured Overlays

• Author(s): Fonseca, Pedro
• Date: 2008
• Persistent ID: http://hdl.handle.net/10451/13892
• Origin: Repositório da Universidade de Lisboa
• Subject(s): Peer-to-peer; unstructured overlays; churn; efficient search
• Document Type: Master thesis
• Language: Portuguese
• Advisor(s): Miranda, Hugo
• Contributor(s): Repositório da Universidade de Lisboa

Description

Unstructured peer-to-peer networks have a low maintenance cost, high resilience and tolerance to the continuous arrival and departure of nodes. In these networks search is usually performed by flooding, which generates a high number of duplicate messages. To improve scalability, unstructured overlays evolved to a two-tiered architecture where regular nodes rely on special nodes to locate resources, called supernodes or superpeers, thus reducing the scope of flooding based searches. While this approach takes advantage of node heterogeneity, it makes the overlay less resilient to accidental and malicious faults, and less attractive to users concerned with the consumption of their resources and who may not desire to commit additional resources that are required by nodes selected as superpeers. Another point of concern is churn, defined as the constant entry and departure of nodes. Churn affects both structured and unstructured overlay networks and, in order to build resilient search protocols, it must be taken into account. This dissertation proposes a novel search algorithm, called FASE, which combines a replication policy and a search space division technique to achieve low hop counts using a small number of messages, on unstructured overlays with non-hierarquical topologies. The problem of churn is mitigated by a distributed monitoring algorithm designed with FASE in mind. Simulation results validate FASE efficiency when compared to other search algorithms for peer-to-peer networks. The evaluation of the distributed monitoring algorithm shows that it maintains FASE performance when subjected to churn