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 http://www.parc.xerox.com/iea/papers/plsearch .