Scalable P2P Search

Despite the negative press on P2P business models, there is some very interesting research now on better performing search in P2P networks.

The basic premise of these networks is that voluntary, ad-hoc, dynamic peers can exchange information (mostly large files) and attain a critical mass that allows most parties to find something they want. The core technology that supports this social dynamic is a decentralized search service that delivers quality results.

There are piles of these file sharing applications , listed in many many many directories. There is no declared winner yet, so take a look at some client reviews and a recent file sharing smackdown favoring AudioGalaxy and Gnotella. I used to use Napster and then moved on to LimeWire (Gnutella), but am now on Morpheus (same as KaZaA minus spyware) and judging from download popularity, these FastTrack based servents are out in front today (9/9/01) as THE most popular downloads of all; even unseating ICQ, the top downloaded application for years.

The P2P space is interesting because these file sharing networks are the largest user created overlay networks to date; sharing disk, bandwidth and compute time. The world's largest supercomputer has fewer than 10,000 processors, and carries a hefty $100 million price tag. But SETI@Home grew to 1.5 million users and Napster to 50M users! It's harder to count the number of active users on a Gnutella network, but clearly interest in file sharing is an order of magnitude larger than for distributed computing. Harnessing this dark matter while serving a diverse constituency is "very powerful".

P2P nets are also interesting because they can form the basic infrastructure to a host of applications, including:

• building a truly distributed DNS [CAN]
• content distribution networks like Akamai's [Karger99]
• better discovery of routing paths than BGP [RON1]
• scalable event notification infrastructures
• instantaneous distributed search facility (better than Google)

Gnutella's scalability problem

The imminent collapse of Gnutella networks due to freeloaders didn't materialize. This call is reminiscent of Metcalfe's call for the imminent collapse of the internet. Are the Xerox people going to eat their paper this time? Turns out these networks have very strong reliability properties [Albert00].

However, while Gnutella won't collapse, and it won't collapse the internet, it doesn't scale. Gnutella's file search query propagation radius (the time to live of the search) theoretically tops out at around 10K nodes but in practice looks smaller than that. Search traffic was taking a quarter of the net bandwidth and users had limited visibility of what they could find. Better solutions in this space could win the P2P race.

There have been a couple of suggested approaches to reduce the Gnutella network traffic. The first set focuses on improving the Gnutella flooding protocol by changing the organizational structure of the network and by routing queries. Another set favors routing protocols [Route]. I was expecting some review on this split of approaches at the O'Reilly P2p Conference in November 2001 in DC. I might have missed it, but I expect much more technical details out of the IPTPS'02 held at MIT in March'02.

Self Organizing Networks

How the P2P topology maps to the underlying network topology becomes important when nodes differ in:

• 3 orders of magnitude of bandwidth (50Kbps-100Mbps)
• 6 orders of magnitude of latency (10us-10s)
• 4 orders of magnitude in availability (1%-99.99%)

It is clear that not all nodes are created equal. Designers of these nets really need to decide very carefully which nodes are trusted and what functions are delegated to them [Saroiu01].

Modem users were becoming dead-end nodes on the Gnutella network, creating a modem bandwidth barrier. The first strategy was to move the hosts on slower connections to the edge of the network introducing a hierarchy. Some Gnutella servents (LimeWire) tiered the network by using gateways and connection preferencing: pinging peers who stop sending information, and dropping those who don't respond.

The FastTrack network also takes this strategy by designating some high bandwidth nodes as supernodes and matching new client arrivals to a supernode, looking more like a federated Napster than Gnutella. They claim to be able to scale to 1M nodes, and so far I see Morpheus with 0.5M visible nodes. The FastTrack network is closed but giFT in trying to start an open development interface to the FastTrack stack.

Query Routing and Cacheing

Given that Gnutella has a power-law structure [Javonavic01], with a few nodes having very high degree and many with low, [Adamic01] propose that a host pass queries only to the neighbor with the most connections. An obvious intuition if you are aware of the dynamics of social networks.

Another approach is to route the query to nodes that are likely to have the item for the query term. [Prinkey00] suggests nodes pass a hash summary of their index up the hierarchy and that subsequent nodes combine the summary hashes of their peers and itself and pass that up the hierarchy. With this information a query can be routed to the nodes that are likely to return positive results. A similar approach was used for dramatically improving web proxies [Fan98] and Prinkey00 may want to consider the use of Bloom filters [Bloom70].

Another strategy is to cache the queries of gnutella searches. But even small caches can be a drain on the memory of clients on the network.

Routing Networks

Hypercube, butterfly, and Plaxton tree [Plaxton99] architectures for highly parallel computers have re-emerged in the P2P space in CAN, Chord, Pastry, Tapestry, Past, etc.. These P2P architectures don't flood queries but devise mapping methods between object id spaces and sets of nodes.

These networks have great lookup algorithms (essentially with infinite horizon) with efficient use of memory. Most just need log(N) time and space. But log(N) for 1000 nodes is still 10 hops away, which is isn't insignificant given the dynamic nature of these networks.

But no current network in use today is based on routing architectures. One view is that these networks will have a hard time stabilizing given the heterogeneity (wrt bandwidth, etc.) and availability of peers, requiring lots of maintenance traffic to update the mapping.

But if one of these architectures can be adapted to the needs of file sharing networks available today, we may see a dramatic improvement in query performance and results.

Conclusion

In the same way Google was not first to market but provided a simple interface with better search results, so will go the file sharing network fight, with the added wrinkle that this battle is being fought on the three fronts of user adoption, protocol, and legal level.

P2P Systems

• Gnutella
• Freenet
• Freehaven
• OpenNap
• Mojo Nation
• Publius, ATT Research and NYU
• Chord, MIT LCS.
• Ohaha, open sourced similar to Chord.
• Tapestry. U.C. Berkeley
• OceanStore , U.C Berkeley
• PAST, Microsoft Research
• Pastry, Microsoft Research, and Rice
• Farsite, Microsoft Research.
• Piazza, Gribble at UWash.
• OpenCola's Swarmcast
• BitTorrent
• ALPINE: Adaptive Large-scale Peer2peer Information NEtworking (at SourceForge)

P2P Companies

• Red Swoosh
• Kontiki
• Blue Falcon
• Yaga
• OpenCola
• PeerGenius
• eMikolo
• others

Acknowledgements