LightFlood: an efficient flooding scheme for file search in unstructured Peer-to-Peer systems

Flooding is a fundamental operation in unstructured Peer-to-Peer (P2P) file sharing systems, such as Gnutella. Although it is effective in content search, flooding is very inefficient because it results in a great amount of redundant messages. Our study shows that more than 70% of the generated messages are redundant for a flooding with a TTL of 7 in a moderately connected network. Existing efforts to address this problem have been focused on limiting the use of flooding operations. In this paper, we propose LightFlood, an efficient flooding scheme, with the objective of minimizing the number of redundant messages and retaining the same message propagating scope as that of standard flooding. By constructing a tree-like sub-overlay within the existing P2P overlay called FloodNet, the flooding operation in LightFlood is divided into two stages. In the first stage, a message is propogated by using the standard flooding scheme with three or four TTL hops, through which the message can be spread to a sufficiently large scope with a small number of redundant messages. In the second stage, the message propagating is only conducted across the FloodNet, significantly reducing the number of redundant messages. Our analysis and simulation results show that the LightFlood scheme provides a low overhead broadcasting facility that can be effectively used in P2P searching. Compared with standard flooding used in Gnutella, we show that the LightFlood scheme with an additional 2 to 3 hops can reduce up to more than 69% of flooding messages, and retain the same flooding scope.