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

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 nondeterminism, 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. (C) 2006 Elsevier B.V. All rights reserved.