Paper #: 5.1.15
Title: Making Gnutella-like P2P Systems Scalable

(1) Problems
This paper presents the design for a new P2P system called Gia, which adapts the decentralized file-sharing system of Gnutella, with a few minor improvements. These improvements will increase significantly the scalability of the system by reducing the query load per node, as well as making the system more robust. The suggestions also address the added benefits of designing a system to take into account the ¡°natural heterogeneity present in most peer-to-peer systems.¡±

(2) New Idea and Strengths
The four key components of the design are: a dynamic topology adaptation, which includes building nodes close to high capacity nodes, under the assumption that these high capacity nodes can aid queries more than low / regular capacity nodes; an active flow control, using tokens to minimize network bottlenecks by letting nodes know which neighbors are prepared for queries; one-hop replication so that each node maintains an index of shared files contained by its neighbors; and a random walk search protocol instead of the flooding method currently employed by Gnutella.

This design was carefully researched and planned out. Perhaps most interesting is their analysis that no single added concept could account for the significant gains over the Gnutella system- only when taken in combination did they provide higher rates. The idea of designing the network structure around the dynamic capabilities of nodes (rather than the KaZaA notion of a binary super node / regular node) is a good one, as is the one-hop replication index. The replication index is extremely helpful when combined with the random walker, as it produces the same result as a one level flood at each node traversed by the random walker, without the same load.

(3) Weaknesses and Extensions
There were any glaring weaknesses in this proposal, maybe a few jumps in logic, though. Part of the initial assumption of the benefits of the distributed network as opposed to the DHT system relies on the notion of ¡°most queries are for hay, not needles¡±. This declaration that the majority of queries are for popular files and not unpopular specific ones is only assumed, with no proof given. I can personally testify to the difficulty in finding obscure files through a P2P system. 

The one extension I can offer is to suggest skipping nodes in the walker. Because of the one-hop replication, visiting a node¡¯s neighbor, as well as that neighbor¡¯s neighbor will still have duplicate information in the index list (although minor), and the cost for hopping without querying may not outweigh the benefits of hitting every 3 nodes.