FloodTrail: an efficient file search technique in unstructured
peer-to-peer systems

Song Jiang and Xiaodong Zhang

Proceedings of 2003 IEEE Globecom Confernece, (Globecom'03), 
San Fransisco, California, USA, December 1-5, 2003.


Abstract

Searching efficiency is a decisive factor concerning scalability in
large-scale peer-to-peer (P2P) file sharing systems.  While flooding is
the most commonly used and user-performance oriented method to broadcast
query across unstructured P2P networks, it generates a large number of
redundant messages.  Our study shows that more than 70% of messages are
redundant using flooding in a moderately connected network, which imposes
an increasingly excessive burden on the underlying infrastructure,
hindering the growth and scalability of P2P systems. To reduce the
use of flooding as well as its associated overhead, we utilize access
trails left by a standard flooding, which is a collection of P2P links
used by non-redundant messages. Thus the multiple queries following the
flooding can be broadcasted along the trail to achieve two goals: (1)
The ability of flooding to achieve short response time is maintained;
and (2) the cost of a broadcast is minimized. Though the trail can
be partially damaged in an ad hoc system with frequent arrivals and
departures of peers, we use repeated trail refreshings and additional
trail links to make a trail consistently available for query broadcast.
We call this trail-based technique FloodTrail.

We have evaluated the performance of FloodTrail for P2P systems for Web
Contents sharing. Simulation results show that FloodTrail could reduce
flooding traffic by up to 57%, while maintaining almost the same search
coverage as that of flooding.  

Back to the HPCS Main Page at the Ohio State University.