LighFlight: An Efficient Flooding Scheme for File Search in Unstructured 
Peer-to-Peer Systems  

Song Jiang, Lei Guo, and Xiaodong Zhang 
 
Proceedings of 2003 International Conference on Parallel Processing (ICPP'03), 
Kaohsung, Taiwan, China, October 6-9, 2003. 

Abstract

``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.