The O'Reilly Peer-to-Peer and Web Services Conference
oreilly.comO'Reilly Network
ConferencesInternationalSafari: Books Online

Arrow Home
Arrow Registration
Arrow Hotel/Travel
Arrow See & Do
Arrow Tutorials
Arrow Keynotes
Arrow Sessions
Arrow BOFs
Arrow Community
Arrow Speakers
Arrow Press
Arrow Mail List
Arrow Exhibitors
Arrow Sponsors
Inventing the Post-Web World
The O'Reilly Peer-to-Peer and
Web Services Conference

Washington, D.C. -- November 5-8, 2001


P2P Search That Scales

Lada A. Adamic, Researcher, Information Dynamics group, Hewlett-Packard

Track: Metadata/Search
Date: Wednesday, November 07
Time: 9:15am - 10:00am
Location: Thomas Boardroom

Decentralized peer-to-peer networks tend to have a power-law structure, with a few nodes having very high degree and many with low degree. This feature can be exploited to keep search costs down as the size of the peer-to-peer network increases. Minimizing search costs is important in networks such as Gnutella, which reached a bandwidth barrier last year when low-bandwidth nodes were unable to support query traffic from a growing network. As a result, the network became fragmented, with large portions unreachable. The query traffic was so high because the current search algorithm broadcasts each query to all nodes within a fixed range. However, the structure of the Gnutella network lends itself to a search strategy which requires much less bandwidth, but is still fairly efficient.

Lada Adamic and associates propose that instead of passing a query to all of the hosts it is connected to, a host passes it only to its neighbor with the most connections. This is equivalent to choosing a person with the most connections in the real world to get something transmitted for you. This intuitive strategy performs remarkably well and requires a slight modification of the hosts. Just as in the real world you might know what our friend's friends have, Gnutella hosts would need to store the names of the files that their neighbors' neighbors have. In effect, every node becomes a local directory able to direct a query to a nearby node with a matching file. Adamic shows that as the size of the network increases from 1,000 to 10,000 nodes, the number of steps required to search 50% of the network increases from 8 to 12 steps, compared to an increase from 100 to 1,000 steps in a non-power-law network. Had the broadcast method of search been used, the number of hosts handling the query would have risen from 500 to 5,000, consuming many times the bandwidth.

The proposed search strategy scales well as the size of the network grows, takes advantage of the existing network structure, and incurs a relatively small additional storage and computational cost for nodes.

The talk will present results relevant to peer-to-peer networks from "Search in Power-Law Networks" by Lada A. Adamic, Rajan M. Lukose, Amit R. Puniyani, and Bernardo A. Huberman. It can be viewed at . Home | Conferences Home | P2P & Web Services Home
Registration | Hotels/Travel | Tutorials | Sessions | Speakers
Press | Mail List | Exhibitors | Sponsors

© 2001, O'Reilly Media, Inc.