Can Heterogeneity Make Gnutella Scalable?

Qin Lv Sylvia Ratnasamy Scott Shenker

(qlv@[Link]) (sylviar@[Link]) (shenker@[Link])

1 Introduction community, that such random search methods were in-

herently unscalable. As a result, a number of research
Even though recent research has identified many differ- groups have proposed designs for what we call “highly
ent uses for peer-to-peer (P2P) architectures, file shar- structured” P2P systems [9, 13, 10, 15]. In these struc-
ing remains the dominant (by far) P2P application on tured systems the overlay topology is tightly controlled
the Internet. Despite various legal problems, the num- and files (or pointers to files) are placed at precisely
ber of users participating in these file-sharing systems, specified locations.1 These highly structured systems
and number of files transferred, continues to grow at a provide a mapping between the file identifier and loca-
remarkable pace. File-sharing applications are thus be- tion, so that queries can be efficiently routed to the node
coming an increasingly important feature of the Internet with the desired file (or, again, the pointer to the desired
landscape and, as such, the scalability of these P2P sys- file). These systems thus offer a very scalable solution
tems is of paramount concern. While the peer-to-peer for “exact-match” queries.2
nature of data storage and data transfer in these systems However, structured designs are likely to be less re-
is inherently scalable, the scalability of file location and silient in the face of a very transient user population,
query resolution is much more problematic. precisely because it is hard to maintain the structure
(such as neighbor lists, etc.) required for routing to
The earliest P2P file-sharing systems (e.g., Napster,
function efficiently when nodes are joining and leav-
Scour) relied on a centralized directory to locate files.
ing at a high rate. Moreover, it has yet to be demon-
While this was sufficient for the early days of P2P, it is
strated that these structured systems, while well-suited
clearly not a scalable architecture. These centralized-
for exact-match queries, can scalably implement a full
directory systems were followed by a number of fully
range of partial query techniques, such as keyword
decentralized systems such as Gnutella and Kazaa.
searching, which are common on current file-sharing
These systems form an overlay network in which each
systems.3
P2P node “connects” to several other nodes. These P2P
Despite these issues, we firmly believe in the value of
systems are unstructured in that the overlay topology is
these structured P2P systems, and have actively partic-
ad hoc and the placement of data is completely unre-
ipated in their design. However, the (sometimes unspo-
lated to the overlay topology. Searching on such net-
ken) motivating assumption behind much of the work
works essentially amounts to random search, in which
on structured P2P systems is that unstructured P2P sys-
various nodes are probed and asked if they have any
tems such as Gnutella are inherently not scalable, and
files matching the query; one can’t do better on such
therefore should be abandoned. Our goal in this work is
unstructured systems because there is no information
to revisit that motivating assumption and ask if Gnutella
about which nodes are likely to have the relevant files.
(and systems like it) could be made more scalable. We
P2P systems differ in how they construct the overlay
1
topology and how they distribute queries. Gnutella, for The Freenet system is what we would call a “loosely struc-
example, floods all queries and uses a TTL to restrict tured” system; file placement is affected by routing hints that are
based on the object’s identifiers; these locations are not precisely
the scope of the flood. The advantage of such unstruc- specified and so not all searches succeed.
tured systems is that they can easily accommodate a 2
By an exact-match query, we mean that the complete identifier
highly transient node population. The disadvantage is of the requested data object is known.
3
that it is hard to find the desired files without distribut- There are standard ways to use the exact-match facility of hash
tables as a substrate for keyword searches, substring searches, and
ing queries widely.
more fuzzy matches as well [14]. However, it isn’t clear how scal-
It seemed clear, at least in the academic research able these techniques will be in distributed hash tables.
do so because, if scalability concerns were removed, 2 Background
these unstructured P2P systems might be the preferred
choice for file-sharing and other applications with the Our design is based on two ongoing research thrusts:
following characteristics: attempts to improve the search facilities in Gnutella
[8, 3, 1], and a measurement study [11] that revealed
keyword searching is the common operation, significant heterogeneity in P2P systems.

most content is typically replicated at a fair frac- Improvements to Gnutella: Gnutella uses TTL-
tion of participating sites, and limited flooding to distribute its queries. Lv et al.
[8] investigate several alternative query distribution
the node population is highly transient methods on a range of overlay topologies: random
graphs, power-law random graphs,5 grids and a mea-
The first condition is that one often doesn’t know the sured Gnutella topology. Based on their results, they
exact file identifier, or is looking for a set of files all propose the use of multiple parallel random walks in-
matching a given attribute (e.g., all by the same artist). stead of flooding. To search for an object using a ran-
The second is that one isn’t typically searching for ex- dom walk, a node chooses a neighbor at random and
tremely rare files that are only stored at a few nodes. send the query to it. Each neighbor in turn repeats this
This would apply to the music-sharing that dominates process until the object is found. Random walks avoid
today’s file-sharing systems. The third condition seems the problem of the exponentially increasing number of
to apply to currently popular P2P systems, although it query messages that arise in flooding.
may not apply to smaller community-based systems. Cohen et al. [3] study proactive replication algo-
File-sharing is one (widely deployed) example that rithms.6 They find that the optimal replication scheme
fits these criteria, distributed search engines [4] might for random search is to replicate objects proportional
well be another. Unstructured P2P systems may be a to the square-root of their query rate; this replication
suitable choice for these applications because of their scheme can be implemented in a distributed fashion by
overall simplicity and their ability to tolerate tran- replicating objects a number of times proportional to
sient user populations and comfortably support key- the length of the search.
word searches.4 This all depends, of course, on whether These combined approaches, proactive replication
or not such systems can be made scalable, and that is plus parallel random walking, was tested via simula-
the question we address in this short paper. tion in [8] and was found to significantly improve –
Our approach to improving the scalability of these by two orders of magnitude in some cases – the per-
systems is based on recent work which shows the preva- formance of flooding and passive replication, as mea-
lence of heterogeneity in deployed P2P systems and on sured by the query resolution time (in terms of number
work improving the efficiency of search in unstructured of overlay hops), the per-node query load and the mes-
networks. After reviewing this relevant background in sage traffic generated by individual queries. In the case
Section 2, we describe, in Section 3, a simple flow con- of power-law random graphs it was observed that high
trol algorithm that takes advantage of heterogeneity and degree nodes experienced correspondingly high query
evaluate its performance in Section 4. We offer this loads. For this reason, the authors conclude that P2P
algorithm not as a polished design but as a proof-of- network construction algorithms should avoid generat-
concept that heterogeneity can be used to improve the ing very high degree nodes.
scalability of unstructured P2P systems. Similarly, one Adamic et al.[1] approach the problem from a very
should take this position paper not as a “proof” that different viewpoint. They take power-law random
Gnutella can be made scalable, but as a conjecture in 5
Power-law random graphs are graphs where the degree distri-
search of more evidence.
bution is a power-law and the nodes are connected randomly con-
sistent with the degree distribution. A node’s “degree” is its number
4
We should add that unstructured P2P systems, whether scalable of neighbors.
6
or not, will never be able match the exact-matching performance of With proactive replication, an object may be replicated at a
highly structured P2P systems. We expect that these highly struc- node even though that node has not requested the object. Passive
tured P2P systems will eventually find many uses; we just aren’t replication, where nodes hold copies only if they’ve requested the
convinced that popular-music file-sharing will be one of them. object, is the standard approach in Gnutella-like P2P systems.
graphs as a given and instead ask how to best search nodes, and thus are more likely to find the desired files.
on them. They, too, suggest the use of random walks, Our design results in a quasi-hierarchical organization
but that these random walks should be biased to seek of nodes with high-capacity nodes at the higher levels
out high-degree nodes. They show how this leads to in the hierarchy. This “hierarchy” is not, however, ex-
superior scaling behavior in the limit of large systems. plicit; instead it is achieved through a distributed, adap-
However, their work does not take into account the tive and lightweight self-organization algorithm.
query load on individual nodes; as shown by [8] the
high-degree nodes carry an extremely large share of the Flow control and Topology Adaption: In what fol-
query traffic and are likely to be overloaded. lows, we represent the capacity of node by
 . For
the purpose of this paper, we assume that
 denotes the
Heterogeneity: Saroiu et al., in [11], report on the re-
maximum number of messages node is willing/able
sults of a measurement study of Napster and Gnutella.
to process over a given time interval  . A node is
Their study reveals (amongst other things) a significant
connected, at the application-level, to a set of neighbor
amount of heterogeneity in bandwidth across peers.  
nodes, denoted 
 . For each of 
 a node
The authors of [11] argue that architectures for P2P
systems should take into account the characteristics of maintains the following information:
participating hosts, including their heterogeneity. How- 
  : the number of incoming messages from
ever, since the measurement study was the main focus node  to in the last time interval  . Every
of [11], they did not propose any design strategies. 
node reports its total incoming rate ( 
 "!$#$%&
' *
These two lines of work, the observed heterogene- )(   ) to all its neighbors.
ity and the improvements to Gnutella-like P2P systems, ,+.-0/  1  : the number of outgoing messages from
lead us to the following observation. Using random- node to  in the last time interval 
walk searches on power-law random graphs is an effi- ,+.-0/325476  1  : the maximum number of messages
cient search technique, but results in a very skewed us-
node can send to node  per time interval  .
:9; +.-8/<25476  1  and
At all times, +.-8/  1
age pattern with some nodes carrying too large a share
of the load. Measurement studies reveal, however, that +.-0/325476  1 =
 ;
9  +.-8/  1 
 > @? A

1 . 8
node capabilities (particularly in terms of bandwidth,
but presumably in terms of other resources such as When a new node, say , joins the network, it is con-
CPU, memory and disk) are also skewed. If we could nected to a random set of neighbor nodes. For each
align these two skews – that is, have the highest capac- neighbor node  , initializes:
ity nodes carry the heaviest burdens – we might end up ,+.-0/325476  1 

*B$C7
with a scalable P2P design. ED
  and
This is what we attempt to do in the next section. ,+.-0/  1 FED

3 Design Every node counts the number of messages it re-

ceives from and transmits to each neighbor node 
* 
Our design for an unstructured P2P system uses a dis- (   and +.-0/  1 respectively). Periodically, node
tributed flow control and topology construction algo- checks whether it is overloaded; i.e. whether its total
rithm that (1) restricts the flow of queries into each node incoming query rate exceeds its capacity. If overloaded,
so they don’t become overloaded and (2) dynamically node attempts to adapt the topology so as to reduce its
evolves the overlay topology so that queries flow to- incoming query load – node selects a neighbor (say G )

wards the nodes that have sufficient capacity to han- with a high incoming query rate (i.e. high  GH ) and
dle them.7 Over this capacity-driven topology we use redirects it to another neighbor (say I ) with high spare
a biased random walk quite similar to that employed capacity. Intuitively, the above topology adaptation rule
in [1]. The combination of these algorithms results in sets up a direct “link” between a node with high query
a system where queries are directed to high capacity rate (node G ) and one with high capacity (node I ) and
7
We still consider this an unstructured design, even though the 8JKLNM)O8P Q"RASUT represents node S ’s current spare capacity. With
topology has become more structured, because the topology adjust- the above bounds on VUW$X P M*RYSUT and VZW.*X [\] P M*RYSUT , a node M can at
ment, while it improves scalability, is not required for correctness most increase its current outgoing rate to S by an amount equal to
of operation. node S ’s current spare capacity.
 checkLoad(node ) example, a useful measure to factor into the topology
If (
 
 
    
// periodic flow control and topology adaptation at
) // overloaded?
adjustment process would be the amount of time a node
!#"$&% .  '( ) *!#"$&% is expected to remain in the system. We also plan to add
+#"-, /%0!#"$&%
pick with max over all
a proactive component to the above algorithm whereby
132/46587'9: !;+<>=?132/4- ;;+<@A ( C DB -E"(+% )
search for node such that:
( ) && ( a node whose capacity is not being utilized can explic-
itly discover and connect to nodes that are experiencing
+ high query loads.
 + 
If ( exists) // adapt topology

+
redirect to ; // i.e. disconnects from

132F46587G9:!+< . . 31 2/46587'9: !;+<>=H ( ;

// and connects to
Search: We use a random-walk based search that
132F46587G9: I+< .  I&  ; combines features from the algorithms in [8, 1]. As in
132F46587G9: +E(J 13F2 46587G9: !K> ; [8] we use TTLs to terminate walks and “state-keeping”
to accelerate walks.10 Similar to [1], a node forwards
else // no satisfactory + exists a query to its neighbor with the maximum value of
node send  a slowdown message +.-8/<2 4 6 . This causes searches to quickly gravitate to-
forall L*!#"$&% :  '&  .NM , 132F4- !  .OM
forall L*!#"$&% : 132/46587G9I !  . 132/46587G9I ! GPRQ
wards high capacity nodes. As in Adamic’s work, the
high degree nodes in our topology do face higher query
recvSlowDown(node  , node )
load. However, unlike Adamic’s work, high degree
// node  receives a slowdown message from nodes in our system are also high capacity nodes and
132F46587G9I '&  . 132F46587G9I '& KB3S hence better equipped to handle this load.
In summary, a node that receives a query, for-
Figure 1: Pseudo-code for flow control and topology wards it to its neighbor  with the highest value
 
adaptation. Although not explicitly shown in the pseu- of +.-8/<25476  1 over all   
 provided (1)
+.-8/  1  9 
+.-8/<25476  1 and (2) has not previously
docode, the upper bound on outMax is enforced in per-
forming the increase operations on outMax. forwarded the same query to  .
While we do not explore proactive replication strate-
gies in this paper, any of the solutions described in [8]
gets the overloaded node (node ) out of the way. If the could be used to further improve the performance of our
overloaded node cannot find an appropriate neighbor search algorithm. In its stead, we assume that the num-
I (as would be the case when all of ’s neighbors are ber of copies of each object is proportional to the rate
running close to capacity), it requests node G to throt- at which it is being queried (which would occur under
tle the number of queries it is forwarding to node (i.e. passive replication). Moreover, we assume that these
reduce outMax[p,i]). The detailed pseudocode for the copies are randomly placed proportional to the capac-
above high-level description is shown in Figure 1. ity of nodes.
Note that all flow control/topology adjustment deci-
sions made by a node are based on local information
(i.e. about the node itself and its neighbors). Further, 4 Evaluation
if a node’s capacity was to undergo a sudden change or
if the node leaves the system, the topology would auto-
In this section, we present initial simulation results on
matically re-adapt to accommodate the change.
the performance of our design outlined in Section 3.

T VU W XUEY[Z#\
Our simulations in Section 4 use the algorithm from
 "D  We stress that these results are not intended to provide a

and 
]U J^
Figure 1 with parameter values of
 "DD 9
,
. We defer an exploration of the pa-
, comprehensive picture of the behavior of our algorithm
but merely to serve as a first-order proof of concept.
rameter space to later work. While our initial simula- 10
With state-keeping, a search is given a unique identifier. A
tion results appear promising, we expect to incorporate
node then remembers the neighbors to which it has already for-
extensions and modifications to the above rules as we warded queries for a given identifier, and if a query with the same
continue to study the behavior of our algorithm. For identifier arrives back at the node, it is forwarded to a different

_ `
neighbor. Using state-keeping thus reduces the likelihood that a
9
In practice, and need not be fixed values. A node can quite random walk will traverse the same path twice. State can be dis-
easily communicate more precise increase and decrease parameters carded after a short time by a node, so it does not become burden-
to its neighboring nodes. some.
 Chang of avg #hops: alpha = 2.0, avg replic ratio = 1% Cumulative Hop Distribution: alpha = 2.0, avg replic ratio = 1% Degree Distribution: alpha = 2.0, avg replic ratio = 1%
70 1000
10000-node graph 10000-node random graph

percentage of queries finished (%)

100
60

50 80
100

node degree
avg #hops

40 60
30
40
10
20
20
10
last 12000 queries
0 0 1
0 5 10 15 20 25 30 35 40 45 50 1 2 4 8 16 32 64 128 256 512 1 10 100 1000 10000
#queries performed (x 12000) #hops node rank

Figure 2: Degree distribution, average query resolution time and the distribution of query resolution times for a
10,000 node simulation using a Zipf-like capacity distribution

Simulation methodology: We use, as our main eval- Capacity level Percentage of nodes
uation metric, the average query resolution time (as x 20%
10x 45%
measured in terms of the number of application-level 100x 30%
hops required to find a particular object). We measure 1000x 4.9%
this in simulations in which the object popularity, the 10000x 0.1%
rate at which queries are issued for it, follows a Zipf-
like distribution where the popularity of the ’th most Table 1: Gnutella-like node capacity distributions


popular object is proportional to
lations we used 
 XUEY[Z
. In these simu-
(based on the Gnutella mea- in a uniform random graph topology; for the Zipf-like
surements in [12]). Individual nodes generate queries capacity distribution we use a 10,000 node graph with
using a Poisson process with an average query rate of average degree 9.9, for the Gnutella-like distribution
1.2 queries/minute. Recall, as described above, that we capacity distribution we use a a 5,000 node graph with
use a proportional replication strategy so that objects average degree 7.5. We then assign the capacities and
are replicated proportional to their query rate. The av- objects to the nodes as described above.
erage degree of replication is 1%11 – that is, on average
Results: Figures 2 and 3 plot the results of simu-
objects are replicated on 1% of the nodes, but the more
lations using, respectively, the Zipf and Gnutella-like
popular objects are replicated more than the less popu-
capacity distribution. The first plots show how, as
lar ones. Recall also that objects are assigned randomly
to nodes, proportional to their capacity
 .
the topology adjusts, the average query response time
D
rapidly decreases from  to in the Zipf case and
Z
To investigate the effect of heterogeneous node ca-

in the Gnutella case. The middle plots show the dis-

pabilities, we use two different capacity distributions.
tribution of the number of hops for individual queries
First, we use a Zipf-like distribution where
 is propor-
tional to

where 

. Second, we used a distri-
Z towards the end of the simulation run. In both cases all
queries were successfully resolved. The last plots show
bution based (loosely) on the measured bandwidth dis-
the degree distributions of the resulting topology at the
tributions of [11]. Here, we assume 5 capacity levels
end of the simulation run. As one can see, the degree
separated by an order of magnitude. The node pop-
distributions evolve to match the capacity distributions
ulation is then divided amongst these levels as shown
– higher capacity nodes have significantly higher de-
in Table 1. The distribution reflects the observation
grees – causing the improved performance.
that a fair fraction of Gnutella clients have dial-up con-
nections to the Internet, the majority are connected via
cable-modem or DSL and a small number of partici- 5 Other Related Work
pants, via high speed lines. The Kazaa [5] network appears similar to our work
in many respects. Kazaa is a self-organizing, multi-
layered network where powerful hosts act as search
For each simulation, we start with nodes connected hubs (called SuperNodes). Details of the Kazaa proto-
11
We also experimented with a replication degree of 0.1% and cols and code are not publicly available making it hard
obtained similar results to draw comparisons to our work.
 Chang of avg #hops: Gnutella, avg replic ratio = 1% Cumulative Hop Distribution: Gnutella, avg replic ratio = 1% Degree Distribution: Gnutella, avg replic ratio = 1%
70 100
5000-node graph 5000-node graph

percentage of queries finished (%)

100
60

50 80

node degree
avg #hops

40 60
10
30
40
20
20
10
last 10000 queries
0 0 1
0 5 10 15 20 25 30 35 40 45 50 1 2 4 8 16 32 64 128 256 512 1 2 level 3 level 4 level 5
#queries performed (x 12000) #hops node resource level

Figure 3: Degree distribution, average query resolution time and the distribution of query resolution times for a
5,000 node simulation using a Gnutella-like capacity distribution

In [7] the authors propose a cluster-based architec- References

ture for P2P systems (CAP). CAP organizes nodes [1] A DAMIC , L., H UBERMAN , B., L UKOSE , R., AND P UNIYANI , A. Search in power law net-
works. Physical Review. E 64 (2001), 46135–46143.
into a two-level hierarchy using a centralized cluster-
[2] C LARKE , I., S ANDBERG , O., W ILEY, B., AND H ONG , T. Freenet: A Distributed Anonymous
ing server [6]. Each cluster has a delegate node that Information Storage and Retrieval System. ICSI Workshop on Design Issues in Anonymity and
Unobservability, July 2000.
acts as directory server for objects stored by nodes
within the cluster. Delegate nodes perform intra-cluster [3] C OHEN , E.,
2001.
AND S HENKER , S. Optimal replication in random search networks. preprint,

node membership registration while a central server

[4] I NFRASEARCH. [Link]
tracks existing clusters and their delegates. To some
[5] K A Z A A. [Link]
extent, our algorithms achieve the same effect as CAP,
with high capacity nodes behaving like delegate nodes. [6] K RISHNAMURTHY, B., AND WANG , J. On network-aware clustering of web clients. In
Proceedings of SIGCOMM ’00 (Stockholm, Sweden, Aug. 2000).
There are however significant differences: unlike CAP
[7] K RISHNAMURTHY, B., WANG , J., AND X IE , Y. Early measurements of a cluster-based archi-
our algorithms are completely decentralized and we do tecture for p2p systems. In ACM SIGCOMM Internet Measurement Workshop (San Francisco,
Nov. 2001).
not build an explicit hierarchy.
[8] LV, C., C AO , P., C OHEN , E., L I , K., AND S HENKER , S. Search and replication in unstruc-
File sharing in FreeNet [2] uses hints about the place- tured peer-to-peer networks. preprint, 2001.
ment of files to improve search scalability. FreeNet [9] R ATNASAMY, S., F RANCIS , P., H ANDLEY, M., K ARP, R., AND S HENKER , S. A Scalable
does not address node heterogeneity. Content-Addressable Network. In Proceedings of SIGCOMM 2001 (Aug. 2001).

[10] ROWSTRON , A., AND D RUSCHEL , P. Storage management and caching in PAST, a large-
scale, persistent peer-to-peer storage utility. In Proceedings of the Eighteenth SOSP (2001),
6 Discussion ACM.

We started this paper with the basic question of whether [11] S AROIU , S., G UMMADI , K., AND G RIBBLE , S. A measurement study of peer-to-peer file
sharing systems. In Proceedings of Multimedia Conferencing and Networking (San Jose, Jan.
one could make unstructured P2P systems scalable. 2002).

Building on the work in [8, 3, 1, 11] we proposed a de- [12] S RIPANIDKULCHAI , K. The popularity of gnutella queries and its implications on scalability.
In O’Reilly’s [Link] (Feb. 2001).
sign that appears to achieve significant scalability. This
[13] S TOICA , I., M ORRIS , R., K ARGER , D., K AASHOEK , M. F., AND BALAKRISHNAN , H.
design is extremely preliminary, and and our evaluation Chord: A scalable peer-to-peer lookup service for internet applications. In Proceedings of
SIGCOMM 2001 (Aug. 2001).
leaves many questions unanswered. We offer it how-
ever, merely as support for the conjecture that unstruc- [14] W ITTEN , I. H., M OFFAT, A., AND B ELL , T. C. Managing Gigabytes: Compressing and
Indexing Documents and Images, second ed. Morgan Kaufmann, 1999.
tured P2P systems can be significantly improved, per-
[15] Z HAO , B., K UBIATOWICZ , J., AND J OSEPH , A. Tapestry: An infrastructure for fault-tolerant
haps to the point where their scalability is no longer a wide-area location and routing. UCB Technical Report, 2001.

barrier.
Our design also raised the more philosophical ques-
tion of how to deal with heterogeneity. Most of the
highly structured P2P designs start with the assumption
of a homogeneous node population and then alter their
designs to accommodate heterogeneity. The design we
present here actively exploits heterogeneity. One can
ask whether the highly structured designs could also be
modified to exploit heterogeneity.