HybridFlood: minimizing the effects of redundant messages and maximizing search efficiency of unstructured peer-to-peer networks

摘要

Peer-to-peer systems are important Internet applications. A major portion of Internet traffic belongs to such applications. Flooding search is a basic search scheme for unstructured peer-to-peer networks, where a node must send a query message to all its neighbors when seeking a file (in a file sharing situation). Flooding has no knowledge about network topology and files distribution, thus it offers an attractive method for file discovery in dynamic and evolving networks. Although pure flooding can achieve high coverage but it produces exponentially redundant messages in each hop. Consequently, the growth of redundant messages limits system scalability and causes unnecessary traffic in networks. Besides, flooding has no opportunity to get an advantage of node diversity of participating in unstructured P2P networks. To improve this searching scheme and reduce redundant messages, this paper proposes a novel algorithm named HybridFlood. This algorithm is divided into two steps. The first step follows the flooding with a limited number of hops. In the second step, nosey nodes are selected in each searching horizon. The nosey nodes are nodes which have the most links to other nodes. These nodes maintain the data index of all client nodes. We provided analytical studies for flooding and HybridFlood. The analytical results provided the best threshold point of hop for optimum coverage growth rate and redundant messages in flooding. It also proved in HybridFlood broadcasting messages are cut down at least an order of magnitude. Thus, the proposed algorithm extends the search efficiency by reducing redundant messages in each hop. The simulation experiments validated analytical results.