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

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