TR-08-2.pdf

``LightFlood: minimizing redundant messages and maximizing scope of  
peer-to-peer search"

Song Jiang, Lei Guo, Xiaodong Zhang, and Haodong Wang 

IEEE Transactions on Parallel and Distributed Systems, Vol. 19, No. 5, 
pp. 601-614, 2008.  

Abstract

Flooding is a fundamental file search operation in unstructured peer-to-peer 
(P2P) file sharing systems, in which a peer starts the file search procedure 
by broadcasting a query to its neighbors, who continue to propagate it to 
their neighbors. This procedure repeats until a time-to-live (TTL) counter 
is decremented to 0. Flooding can seriously limit system scalability because 
the number of redundant query messages grows exponentially during the message 
propagation. Our study shows that more than 70% of the generated messages 
are redundant in a flooding with a TTL of 7 in a moderately connected 
Gnutella network. Existing efforts to address this issue have been focused 
on limiting the use of the flooding operation. We propose a new flooding 
scheme, called LightFlood, with the objective of minimizing the number 
of redundant messages and retaining a similar message propagating scope 
as that of the standard flooding. In the scheme, each peer keeps track of 
the connectivities of every immediate and next indirect neighbor peers, 
which can be acquired locally. LightFlood identifies the neighbor with the 
highest connectivity, and uses the link to that neighbor to form a 
sub-overlay within the existing P2P overlay. In LightFlood, flooding is 
divided into two stages. The first stage is a standard flooding with a 
limited number of TTL hops, where a message can spread to a sufficiently 
large scope with a small number of redundant messages. In the second stage, 
message propagating is only conducted along the sub-overlay, significantly 
reducing the number of redundant messages. Our analysis and simulation 
experiments show that the LightFlood scheme provides a low-overhead 
broadcast facility that can be effectively used in P2P search. For example, 
compared with standard flooding with 7 TTL hops, we show that LightFlood 
with an additional 2 to 3 hops can reduce up to 69% of the flooding 
messages, and retain the same flooding scope. We believe that LightFlood 
can be widely used as a core mechanism for efficient message broadcasting 
in P2P systems due to its near-optimal performance.