Novel approaches to efficient flooding search in peer-to-peer networks

• Published in: Computer networks (Amsterdam, Netherlands : 1999) Netherlands : 1999), 2007-07, Vol.51 (10), p.2818-2832
• Main Authors: Jin, Shudong, Jiang, Hongbo
• Format: Article
• Language: English
• Subjects: Algorithms; Applied sciences; Business and industry local networks; Controlled flooding; Determinism; Exact sciences and technology; Miscellaneous; Network topologies; Networks and services in france and abroad; Organization and planning of networks (techniques and equipments); Peer to peer computing; Peer-to-peer networks; Power-law; Random graphs; Studies; Systems, networks and services of telecommunications; Telecommunications; Telecommunications and information theory; Teleprocessing networks. Isdn; Teletraffic
• ISSN: 1389-1286; 1872-7069
• DOI: 10.1016/j.comnet.2006.12.002

Efficient search algorithms are crucial to the success of unstructured and hybrid peer-to-peer networks. Performance requirements on search algorithms include low search traffic, low search latency, and determinism in returning the searched items. However, existing search algorithms fail to meet these goals. We propose, analyze, and evaluate two novel flooding search algorithms. The first algorithm conducts on-the-fly estimation of the popularity of the searched item, and uses such knowledge to guide a peer’s search process. It requires the minimum search cost and very low latency, and albeit its non-determinism, often returns the desired number of results. The second algorithm, Hurricane flooding, exponentially expands the search horizon of the source of a search in a spiral pattern. Hurricane flooding is deterministic, requires search cost arbitrarily close to a lower bound, and returns the results in logarithmic time. We analyze and optimize our proposed algorithms, and evaluate them using various network models, including a real Gnutella network topology.