《计算机网络》课程教学资源（参考文献）Making Gnutella-like P2P Systems Scalable

Making gnutella-like P2P Systems Scalable Yatin Chawathe Ratnasamy Lee breslau at&t labs-Research tel research At&t labs-Research yatin@research.att.com sylvia@intel-research net breslau@research.att.com Nick Lanham Scott Shenker UC Berkeley nickl@cs. berkeley. edu shenker@icsi. berkeley. edu ABSTRACT over, such P2P file-sharing systems are self-scaling in that as more peers join the system to look for files, they add to the aggregate Napster pioneered the idea of peer-to-peer file sharing, and sup- download capability as well. 2 ported it with a centralized file search facility. Subsequent P2P sys ms like gnutella adopted decentralized search algorithms. How- However, to make use of this self-scaling behavior, a node looking ever, Gnutella's notoriously poor scaling led some to propose d for files must find the peers that have the desired content. Napster tributed hash table solutions to the wide-area file search problem. used a centralized search facility based on file lists Contrary to that trend, we advocate retaining gnutella's simplicity peer. By centralizing search(which does not re while proposing new mechanisms that greatly improve its scalabil-. width) while distributing download (which does), ity. Building upon prior research [1, 12, 22], we propose several a highly functional hybrid design modifications to Gnutella's design that dynamically adapt the over. The resulting system was widely acknowledged as"the fastest lay topology and the search algorithms in order to accommodate the growing Internet application ever"[4]. But RIAA,s lawsuit forced natural heterogeneity present in most peer-to-peer systems. We test Napster to shut down, and its various centralized-search successors our design through simulations and the results show three to five or- have faced similar legal challenges. These centralized systems have ders of magnitude improvement in total system capacity. We also re- been replaced by new decentralized systems such as gnutella [81 port on a prototype implementation and its deployment on a testbed. that distribute both the download and search capabilities. These sys- tems establish an overlay network of peers. Queries are not sent to Categories and Subject Descriptors central site, but are instead distributed among the peers. gnut the first of such systems, uses an unstructured overlay network C2[Computer Communication Networks]: Distributed Systems that the topology of the overlay network and placement of files within General terms it is largely unconstrained. It floods each query across this overlay with a limited scope. Upon receiving a query, each peer sends a Algorithms, Design, Performance, Experimentation list of all content matching the query to the originating node, Be cause the load on each node grows linearly with the total number Keywords of queries, which in turn grows with system size, this approach is Peer-to-peer, distributed hash tables, Gnutella learly not scalabl Following Gnutella's lead, several other decentralized file-sharing 1. INTRODUCTION systems such as Kazaa [24]have become popular. Kazaa is base The peer-to-peer file-sharing revolution started with the intro on the proprietary Fasttrack technology which uses specially desig nated supernodes that have higher bandwidth connectivity. Pointe tion of Napster in 1999. Napster was the first system to recognize to each peers data are stored on an associated supernode, and all but instead could be handled by the many hosts, or peers, that al- queries are routed to supernodes. While this approach appears to ready possess the content. Such serverless peer-to-peer systems can offer better scaling than Gnutella, its design has been neither docu- chieve astounding aggregate download capacities without requir mented nor analyzed. Recently, there have been any additional expenditure for bandwidth or server farms.! More- porate this approach into the Gnutella network [7). Although some Gnutella clients now implement the supernode proposal, its scalabil- NSF grants ITR-0205519, ANI-0207399, ity has neither been measured nor been analyzed ITR-0121555,r 1698.ITR0225660 and ANI-0196514. That said, we believe that the supernode approach popularized more aggregate download capacity than a single server farm con- sharing systems. In this paper, we leverage this idea of exploit but make the selection of construction of the topology around them more dynamic and adap- ive. We present a new P2P file-sharing system, called Gia. Like is granted ot made or distribut e downbeat tee all or part of this work for Gnutella and KazaA, Gia is decentralized and unstructured. How ever, its unique design achieves an aggregate system capacity that is citation on the first 2This self-sc republish, to post on servers or to redistribute to lists, requires prior specific 时 ms(21 one extent by the free IGCOMM03. August 25-29. 2003 gianduia, which is the generic name for the hazelnut spread Copyright 2003 ACM 1-58113-735-4

Making Gnutella-like P2P Systems Scalable Yatin Chawathe AT&T Labs–Research yatin@research.att.com Sylvia Ratnasamy Intel Research sylvia@intel-research.net Lee Breslau AT&T Labs–Research breslau@research.att.com Nick Lanham UC Berkeley nickl@cs.berkeley.edu Scott Shenker∗ ICSI shenker@icsi.berkeley.edu ABSTRACT Napster pioneered the idea of peer-to-peer file sharing, and sup￾ported it with a centralized file search facility. Subsequent P2P sys￾tems like Gnutella adopted decentralized search algorithms. How￾ever, Gnutella’s notoriously poor scaling led some to propose dis￾tributed hash table solutions to the wide-area file search problem. Contrary to that trend, we advocate retaining Gnutella’s simplicity while proposing new mechanisms that greatly improve its scalabil￾ity. Building upon prior research [1, 12, 22], we propose several modifications to Gnutella’s design that dynamically adapt the over￾lay topology and the search algorithms in order to accommodate the natural heterogeneity present in most peer-to-peer systems. We test our design through simulations and the results show three to five or￾ders of magnitude improvement in total system capacity. We also re￾port on a prototype implementation and its deployment on a testbed. Categories and Subject Descriptors C.2 [Computer Communication Networks]: Distributed Systems General Terms Algorithms, Design, Performance, Experimentation Keywords Peer-to-peer, distributed hash tables, Gnutella 1. INTRODUCTION The peer-to-peer file-sharing revolution started with the introduc￾tion of Napster in 1999. Napster was the first system to recognize that requests for popular content need not be sent to a central server but instead could be handled by the many hosts, or peers, that al￾ready possess the content. Such serverless peer-to-peer systems can achieve astounding aggregate download capacities without requiring any additional expenditure for bandwidth or server farms.1 More- ∗Supported in part by NSF grants ITR-0205519, ANI-0207399, ITR-0121555, ITR-0081698, ITR-0225660 and ANI-0196514. 1For instance, 100,000 peers all connected at 56kbps can provide more aggregate download capacity than a single server farm con￾nected by two OC-48 links. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. SIGCOMM’03, August 25–29, 2003, Karlsruhe, Germany. Copyright 2003 ACM 1-58113-735-4/03/0008 ...$5.00. over, such P2P file-sharing systems are self-scaling in that as more peers join the system to look for files, they add to the aggregate download capability as well.2 However, to make use of this self-scaling behavior, a node looking for files must find the peers that have the desired content. Napster used a centralized search facility based on file lists provided by each peer. By centralizing search (which does not require much band￾width) while distributing download (which does), Napster achieved a highly functional hybrid design. The resulting system was widely acknowledged as “the fastest growing Internet application ever”[4]. But RIAA’s lawsuit forced Napster to shut down, and its various centralized-search successors have faced similar legal challenges. These centralized systems have been replaced by new decentralized systems such as Gnutella [8] that distribute both the download and search capabilities. These sys￾tems establish an overlay network of peers. Queries are not sent to a central site, but are instead distributed among the peers. Gnutella, the first of such systems, uses an unstructured overlay network in that the topology of the overlay network and placement of files within it is largely unconstrained. It floods each query across this overlay with a limited scope. Upon receiving a query, each peer sends a list of all content matching the query to the originating node. Be￾cause the load on each node grows linearly with the total number of queries, which in turn grows with system size, this approach is clearly not scalable. Following Gnutella’s lead, several other decentralized file-sharing systems such as KaZaA [24] have become popular. KaZaA is based on the proprietary Fasttrack technology which uses specially desig￾nated supernodes that have higher bandwidth connectivity. Pointers to each peer’s data are stored on an associated supernode, and all queries are routed to supernodes. While this approach appears to offer better scaling than Gnutella, its design has been neither docu￾mented nor analyzed. Recently, there have been proposals to incor￾porate this approach into the Gnutella network [7]. Although some Gnutella clients now implement the supernode proposal, its scalabil￾ity has neither been measured nor been analyzed. That said, we believe that the supernode approach popularized by KaZaA is a step in the right direction for building scalable file￾sharing systems. In this paper, we leverage this idea of exploit￾ing node heterogeneity, but make the selection of “supernodes” and construction of the topology around them more dynamic and adap￾tive. We present a new P2P file-sharing system, called Gia.3 Like Gnutella and KaZaA, Gia is decentralized and unstructured. How￾ever, its unique design achieves an aggregate system capacity that is 2This self-scaling property is mitigated to some extent by the free rider problem observed in such systems [2]. 3Gia is short for gianduia, which is the generic name for the hazelnut spread, Nutella. 407

three to five orders of magnitude better than that of gnutella as well as that of other attempts to improve gnutella [12, 24]. As such, it retains the simplicity of an unstructured system while offering vastly oved scalability The design of Gia builds on a substantial body of previous work As in the recent work by Lv et al.[12], Gia replaces Gnutella's ing with random walks. Following the work of Adamic et al.[ recognizes the implications of the overlay network's topology while sing random walks and therefore includes a topology adaptation al gorithm. Similarly, the lack of flow control has been recognized as a weakness in the original Gnutella design[16), and Gia introduces token-based fow control algorithm. Finally, like KazaA, Gia rec- ognizes that there is significant heterogeneity in peer bandwidth and Figure 1: Most download requests are for well-replicated files. incorporates heterogeneity into each aspect of our desigr While gia does build on these previous contributions, Gia is, to our knowledge the first open design that(a)combines all these el- and could easily overwhelm nodes with low-bandwidth dial-up con- ements, and(b)recognizes the fact that peers have capacity con- straints and adapts its protocols to account for these constraints nections Our simulations suggest that this results in a tremendous boost tor #2: Keyword searches are more prevalent, and more im- ment comes not just from a single design decision but from the syn- portant, than exact-match queries. DHTs excel at support- ergy among the various design features. ing exact-match lookups: given the exact name of a file, they trans- le discuss Gia's design in Section 3, its performance in Section late the name into a key and perform the corresponding lookup(key) 4, and a prototype implementation and associated practical issues in operation. However, DHTs are les adept at supporting keyword searches: given a sequence of keywords, find files that match them Section 5. However, before embarking on the description of Gia, we The current use of P2P file-sharing systems, which revolves around rst ask why not just use Distributed Hash Tables(dhts) sharing music and video, requires such key word matching. For ex- 2. WHY NOT DHTS ample, to find the song"Ray of Light by Madonna, a user typically submits a search of the form"madonna ray of light "and expects the Distributed Hash Tables are a class of recently-developed file-sharing system to locate files that match all of the keywords in 27]. Much(although not all) of the original rationale for DHTs was biguous naming convention for file names in p2P systems, and thus to provide a scalable replacement for unscalable Gnutella-like file often the same piece of content is stored by different nodes under sharing systems. The past few years has seen a veritable frenzy of several( slightly different)names research activity in this field, with many design proposals and sug Supporting such keyword searching on top of DHTs is a gested applications. All of these proposals use structured overlay trivial task. For example, the typical approach [11, 19, 26]of etworks where both the data placement and overlay topology tightly controlled. The hash-table -like lookup operation provided tain in the face of frequent node(and hence file)churn. This is only arison, Gnutella requires O(n)steps to reliably locate a specific avoid overloading nodes that store the index for popular keywords It is possible that some of these problems maybe addressable in Given this level of performance gain afforded by DHTs, it is natu- DHTS, as indicated by the deployment of the Overnet file sharing ral to ask why bother with Gia when DHTs are available. To answer application [15], which is based on the Kademlia DHT[14].Still this question, we review three relevant aspects of P2P file sharing. DHT-based solutions typically need to go to great lengths to incor porate query models beyond the simple exact-match search. In con- #l: P2P clients are extremely transient. Measured activ- trast, Gnutella and other similar systems effortlessly support key- ity in Gnutella and Napster indicates that the median up-time for a word searches and other complex queries since all such searches are node is 60 minutes [22].- For large systems of, say, 100,000 nodes, executed locally on a node-by-node basis this implies a churn rate of over 1600 nodes coming and going per ninute Churn causes little problem for Gnutella and other systems #3: Most queries are forhay, not needles. DHTs have exact that employ unstructured overlay networks as long as a peer doesn't recall, in that knowing the name of a file allows you to find it, even become disconnected by the loss of all of its neighbors, and even if there is only a single copy of that file in the system. In contrast, in that case the peer can merely repeat the bootstrap procedure Gnutella cannot reliably find single copies of files unless the flooded e-join the network. In contrast, churn does cause significant over- query reaches all nodes we call such files needles.However,we ead for DHTs. In order to preserve the efficiency and correctness expect that most queries in the popular P2P file-sharing systems are ofrouting, most DHTs require O(log n)repair operations after each for relatively well-replicated files, which we call hay. By the very failure. Graceless failures, where a node fails without beforehand nature of P2P file-sharing, if a file is requested frequently, then as informing its neighbors and transferring the relevant state, requ more and more requesters download the file to their machines, there more time and work in DHTs to(a)discover the failure and (b)re- will be many copies of it within the system. We call such systems replicate the lost data or pointers. If the churn rate is too high, the where most queries are for well-replicated content, mass-markerfile overhead caused by these repair operations can become substantial sharing systems Gnutella can easily find well-replicated files. Thus, if most searches are for hay, not needles, then gnutella's lack of exact recall is not a significant disadvantage. To verify our conjecture that most queries

three to five orders of magnitude better than that of Gnutella as well as that of other attempts to improve Gnutella [12, 24]. As such, it retains the simplicity of an unstructured system while offering vastly improved scalability. The design of Gia builds on a substantial body of previous work. As in the recent work by Lv et al. [12], Gia replaces Gnutella’s flood￾ing with random walks. Following the work of Adamic et al. [1], Gia recognizes the implications of the overlay network’s topology while using random walks and therefore includes a topology adaptation al￾gorithm. Similarly, the lack of flow control has been recognized as a weakness in the original Gnutella design [16], and Gia introduces a token-based flow control algorithm. Finally, like KaZaA, Gia rec￾ognizes that there is significant heterogeneity in peer bandwidth and incorporates heterogeneity into each aspect of our design. While Gia does build on these previous contributions, Gia is, to our knowledge, the first open design that (a) combines all these el￾ements, and (b) recognizes the fact that peers have capacity con￾straints and adapts its protocols to account for these constraints. Our simulations suggest that this results in a tremendous boost for Gia’s system performance. Moreover, this performance improve￾ment comes not just from a single design decision but from the syn￾ergy among the various design features. We discuss Gia’s design in Section 3, its performance in Section 4, and a prototype implementation and associated practical issues in Section 5. However, before embarking on the description of Gia, we first ask why not just use Distributed Hash Tables (DHTs). 2. WHY NOT DHTS? Distributed Hash Tables are a class of recently-developed sys￾tems that provide hash-table-like semantics at Internet scale [25, 18, 27]. Much (although not all) of the original rationale for DHTs was to provide a scalable replacement for unscalable Gnutella-like file sharing systems. The past few years has seen a veritable frenzy of research activity in this field, with many design proposals and sug￾gested applications. All of these proposals use structured overlay networks where both the data placement and overlay topology are tightly controlled. The hash-table-like lookup() operation provided by DHTs typically requires only O(log n) steps, whereas in com￾parison, Gnutella requires O(n) steps to reliably locate a specific file. Given this level of performance gain afforded by DHTs, it is natu￾ral to ask why bother with Gia when DHTs are available. To answer this question, we review three relevant aspects of P2P file sharing. #1: P2P clients are extremely transient. Measured activ￾ity in Gnutella and Napster indicates that the median up-time for a node is 60 minutes [22].4 For large systems of, say, 100,000 nodes, this implies a churn rate of over 1600 nodes coming and going per minute. Churn causes little problem for Gnutella and other systems that employ unstructured overlay networks as long as a peer doesn’t become disconnected by the loss of all of its neighbors, and even in that case the peer can merely repeat the bootstrap procedure to re-join the network. In contrast, churn does cause significant over￾head for DHTs. In order to preserve the efficiency and correctness of routing, most DHTs require O(log n) repair operations after each failure. Graceless failures, where a node fails without beforehand informing its neighbors and transferring the relevant state, require more time and work in DHTs to (a) discover the failure and (b) re￾replicate the lost data or pointers. If the churn rate is too high, the overhead caused by these repair operations can become substantial 4We understand that there is some recently published work [3] that questions the exact numbers in this study, but the basic point remains that the peer population is still quite transient. 0 100 200 300 400 500 600 700 800 900 1 2 4 8 16 32 64 128 256 # download requests # available replicas Figure 1: Most download requests are for well-replicated files. and could easily overwhelm nodes with low-bandwidth dial-up con￾nections. #2: Keyword searches are more prevalent, and more im￾portant, than exact-match queries. DHTs excel at support￾ing exact-match lookups: given the exact name of a file, they trans￾late the name into a key and perform the corresponding lookup(key) operation. However, DHTs are les adept at supporting keyword searches: given a sequence of keywords, find files that match them. The current use of P2P file-sharing systems, which revolves around sharing music and video, requires such keyword matching. For ex￾ample, to find the song “Ray of Light” by Madonna, a user typically submits a search of the form “madonna ray of light” and expects the file-sharing system to locate files that match all of the keywords in the search query. This is especially important since there is no unam￾biguous naming convention for file names in P2P systems, and thus often the same piece of content is stored by different nodes under several (slightly different) names. Supporting such keyword searching on top of DHTs is a non￾trivial task. For example, the typical approach [11, 19, 26] of con￾structing an inverted index per keyword can be expensive to main￾tain in the face of frequent node (and hence file) churn. This is only further complicated by the additional caching algorithms needed to avoid overloading nodes that store the index for popular keywords. It is possible that some of these problems maybe addressable in DHTs, as indicated by the deployment of the Overnet file sharing application [15], which is based on the Kademlia DHT [14]. Still, DHT-based solutions typically need to go to great lengths to incor￾porate query models beyond the simple exact-match search. In con￾trast, Gnutella and other similar systems effortlessly support key￾word searches and other complex queries since all such searches are executed locally on a node-by-node basis. #3: Most queries are for hay,not needles. DHTs have exact recall, in that knowing the name of a file allows you to find it, even if there is only a single copy of that file in the system. In contrast, Gnutella cannot reliably find single copies of files unless the flooded query reaches all nodes; we call such files needles. However, we expect that most queries in the popular P2P file-sharing systems are for relatively well-replicated files, which we call hay. By the very nature of P2P file-sharing, if a file is requested frequently, then as more and more requesters download the file to their machines, there will be many copies of it within the system. We call such systems, where most queries are for well-replicated content, mass-market file￾sharing systems. Gnutella can easily find well-replicated files. Thus, if most searches are for hay, not needles, then Gnutella’s lack of exact recall is not a significant disadvantage. To verify our conjecture that most queries 408

re indeed for hay, we gathered traces of queries and download 2. If a random walker query arrives at a node that is already over requests using an instrumented Gnutella client. Our tracing tool loaded with traffic, it may get queued for a long time before it crawled the gnutella network searching for files that match the top 50 query requests seen. After gathering the file names and the num ber of available copies of each of these files, the tool turned around Adamic et al. [1 addressed the first and offered the same files for download to other gnutella clients. We ing that instead of using purely random walks. the search protocol should bias its walks toward high-degree nodes. The intuition be then measured the number of download requests seen by the trac- hind this is that if we arrange for neighbors to be aware of each ing tool for this offered content. Figure I shows the distribution of other's shared files, high-degree nodes will have(pointers to)a large the download requests versus the number of available replicas. We number of files and hence will be more likely to have an answer that notice that most of the requests correspond to files that have a large matches the query. However, this approach ignores the problem of number of available replicas. For example, half of the requests were overloaded nodes. In fact, by always biasing the random walk to- for files with more than 100 replicas, and approximately 80% of the wards high-degree nodes, it can exacerbate the problem if the high- requests were for files with more than 80 replicas In summary, Gnutella-like designs are more robust in the face of ucgree node does not have the capacity to handle a large number of ransients and support general search facilities, both important prop- The design of Gia, on the other hand, explicitly takes into ac- queries. erties to p2P file sharing. They are less adept than DHTs at finding count the capacity constraints associated with each node in the P2P Thus, we conjecture that for mass-market hile-sharing applications, tors including its processing power, disk latencies, and access band turning to DhT-based systems, may be the better approach. width. It is well-documented that nodes in networks like gnutella exhibit significant heterogeneity in terms of their capacity to handle queries[22]. Yet, none of the prior work on scaling Gnutella-like 3. GIA DESIGN systems leverages this heterogeneity. In the design of Gia, we ex gnutella-like systems have one basic problem: when faced with plicitly accommodate(and even exploit) heterogeneity to achieve a high aggregate query rate, nodes quickly become overloaded and etter scaling. The four key components of our design are summa- the system ceases to function satisfactorily. Moreover, this prob- rized below. lem gets worse as the size of the system increases. Our first goal in designing Gia is to create a Gnutella-like P2P system that can a dynamic topology adaptation protocol that puts most node handle much higher aggregate query rates. Our second goal is to within short reach of high capacity nodes aptation ave Gia continue to function well with increasing system sizes. To protocol ensures that the well-connected (i.e this scalability, Gia strives to avoid overloading any of the nodes, which receive a large proportion of th nodes by explicitly accounting for their capacity constraints. In an lly have the capacity to handle those queries. earlier workshop paper [13, we presented a preliminary proposal An active fiow control scheme to avoid overloaded hot-spots or incorporating capacity awareness into Gnutella. In our current The flow control protocol explicitly acknowledges the exis- work, we refine those ideas and present a thorough design, tence of heterogeneity and adapts to it by assigning flow-control algorithms, and a prototype implementation of the new syst tokens to nodes based on available capacity begin with an overview of the reasoning behind our system design and then provide a detailed discussion of the various components One-hop replication of pointers to content. All nodes main- and protocols tain pointers to the content offered by their immediate neigh- bors. Since the topology adaptation algorithm ensures a con- 3.1 Design rationale gruence between high capacity nodes and high degree nodes, The gnutella protocol [6]uses a flooding-based search method to he one-hop replication guarantees that high capacity nodes find files within its P2P network. To locate a file, a node queries each are capable of providing answers to a greater number of querie of its neighbors, which in turn propagate the query to their neigh- A search protocol based on biased random walks that directs rs,and so on until the query reaches all of the clients within a queries towards high-capacity nodes, which are typically best certain radius from the original querier. Although this approach can able to answer the queries. locate files even if they are replicated at an extremely small number of nodes, it has obvious scaling problems. To address this issue, Lv 3.2 Detailed design al. [12] proposed replacing fooding with random walks. Random The framework for the gia client and protocols is modeled after walks are a well-known technique in which a query message is for- the current gnutella protocol [6]. Clients connect to each other using warded to a randomly chosen neighbor at each step until sufficient a three-way handshake protocol. All messages exchanged by clients responses to the query are found. Although they make better uti are tagged at their origin with a globally unique identifier or GUID zation of the P2P network than flooding, they have two associated which is a randomly generated sequence of 16 bytes. The GUID used to track the progress of a message through the Gia network and 1. A random walk is essentially a blind search in that at each to route responses back to the originating client. ery is forwarded to a random node We extend the gnutella protocol to take into account client capac ount any indication of how likely it is that the node ity and network heterogeneity. For this discussion, we assume that will have responses for the query client capacity is a quantity that represents the number of queries that the client can handle per second. In practice, the capacity will Note that since the tracing tool only captures the download requests have to be determined as a function of a clients access bandwidth, that came directly to it, we miss all of the requests that went to the processing power, disk speed, etc. We discuss the four protocol com- other nodes that also had copies of the same file. Thus our numbers lents in detail belo can only be a lower bound on how popular well-replicated content

are indeed for hay, we gathered traces of queries and download requests using an instrumented Gnutella client. Our tracing tool crawled the Gnutella network searching for files that match the top 50 query requests seen. After gathering the file names and the num￾ber of available copies of each of these files, the tool turned around and offered the same files for download to other Gnutella clients. We then measured the number of download requests seen by the trac￾ing tool for this offered content. Figure 1 shows the distribution of the download requests versus the number of available replicas. We notice that most of the requests correspond to files that have a large number of available replicas.5 For example, half of the requests were for files with more than 100 replicas, and approximately 80% of the requests were for files with more than 80 replicas. In summary, Gnutella-like designs are more robust in the face of transients and support general search facilities, both important prop￾erties to P2P file sharing. They are less adept than DHTs at finding needles, but this may not matter since most P2P queries are for hay. Thus, we conjecture that for mass-market file-sharing applications, improving the scalability of unstructured P2P systems, rather than turning to DHT-based systems, may be the better approach. 3. GIA DESIGN Gnutella-like systems have one basic problem: when faced with a high aggregate query rate, nodes quickly become overloaded and the system ceases to function satisfactorily. Moreover, this prob￾lem gets worse as the size of the system increases. Our first goal in designing Gia is to create a Gnutella-like P2P system that can handle much higher aggregate query rates. Our second goal is to have Gia continue to function well with increasing system sizes. To achieve this scalability, Gia strives to avoid overloading any of the nodes by explicitly accounting for their capacity constraints. In an earlier workshop paper [13], we presented a preliminary proposal for incorporating capacity awareness into Gnutella. In our current work, we refine those ideas and present a thorough design, detailed algorithms, and a prototype implementation of the new system. We begin with an overview of the reasoning behind our system design and then provide a detailed discussion of the various components and protocols. 3.1 Design Rationale The Gnutella protocol [6] uses a flooding-based search method to find files within its P2P network. To locate a file, a node queries each of its neighbors, which in turn propagate the query to their neigh￾bors, and so on until the query reaches all of the clients within a certain radius from the original querier. Although this approach can locate files even if they are replicated at an extremely small number of nodes, it has obvious scaling problems. To address this issue, Lv et al. [12] proposed replacing flooding with random walks. Random walks are a well-known technique in which a query message is for￾warded to a randomly chosen neighbor at each step until sufficient responses to the query are found. Although they make better uti￾lization of the P2P network than flooding, they have two associated problems: 1. A random walk is essentially a blind search in that at each step a query is forwarded to a random node without taking into account any indication of how likely it is that the node will have responses for the query. 5Note that since the tracing tool only captures the download requests that came directly to it, we miss all of the requests that went to the other nodes that also had copies of the same file. Thus our numbers can only be a lower bound on how popular well-replicated content is. 2. If a random walker query arrives at a node that is already over￾loaded with traffic, it may get queued for a long time before it is handled. Adamic et al. [1] addressed the first problem by recommend￾ing that instead of using purely random walks, the search protocol should bias its walks toward high-degree nodes. The intuition be￾hind this is that if we arrange for neighbors to be aware of each other’s shared files, high-degree nodes will have (pointers to) a large number of files and hence will be more likely to have an answer that matches the query. However, this approach ignores the problem of overloaded nodes. In fact, by always biasing the random walk to￾wards high-degree nodes, it can exacerbate the problem if the high￾degree node does not have the capacity to handle a large number of queries. The design of Gia, on the other hand, explicitly takes into ac￾count the capacity constraints associated with each node in the P2P network. The capacity of a node depends upon a number of fac￾tors including its processing power, disk latencies, and access band￾width. It is well-documented that nodes in networks like Gnutella exhibit significant heterogeneity in terms of their capacity to handle queries [22]. Yet, none of the prior work on scaling Gnutella-like systems leverages this heterogeneity. In the design of Gia, we ex￾plicitly accommodate (and even exploit) heterogeneity to achieve better scaling. The four key components of our design are summa￾rized below: • A dynamic topology adaptation protocol that puts most nodes within short reach of high capacity nodes. The adaptation protocol ensures that the well-connected (i.e., high-degree) nodes, which receive a large proportion of the queries, actu￾ally have the capacity to handle those queries. • An active flow control scheme to avoid overloaded hot-spots. The flow control protocol explicitly acknowledges the exis￾tence of heterogeneity and adapts to it by assigning flow-control tokens to nodes based on available capacity. • One-hop replication of pointers to content. All nodes main￾tain pointers to the content offered by their immediate neigh￾bors. Since the topology adaptation algorithm ensures a con￾gruence between high capacity nodes and high degree nodes, the one-hop replication guarantees that high capacity nodes are capable of providing answers to a greater number of queries. • A search protocol based on biased random walks that directs queries towards high-capacity nodes, which are typically best able to answer the queries. 3.2 Detailed Design The framework for the Gia client and protocols is modeled after the current Gnutella protocol [6]. Clients connect to each other using a three-way handshake protocol. All messages exchanged by clients are tagged at their origin with a globally unique identifier or GUID, which is a randomly generated sequence of 16 bytes. The GUID is used to track the progress of a message through the Gia network and to route responses back to the originating client. We extend the Gnutella protocol to take into account client capac￾ity and network heterogeneity. For this discussion, we assume that client capacity is a quantity that represents the number of queries that the client can handle per second. In practice, the capacity will have to be determined as a function of a client’s access bandwidth, processing power, disk speed, etc. We discuss the four protocol com￾ponents in detail below. 409

Let Ci represent capacity of node i to accept the new node, we may need to drop an existing neighbor if num-nbrsx +1 smar_brs then ( we have room) lgorithm I shows the steps involved in making this determination ACCEPT Y: return The algorithm works as follows. If, upon accepting the new con- f we need to drop a neighb nection, the total number of neighbors would still be within a pre subset←ii∈ nbrsx such that c:≤C configured bound maz_nbrs. then the connection is automatically if no such neighbors exist then accepted. Otherwise, the node must see if it can find an appropriate REJECT eturn existing neighbor to drop and replace with the new connection. candidate Z + highest-degree neighbor from subset X always favors Y and drops an existing neighbor if Y has higher capacity than all of Xs current neighbors. Otherwise, it decides if( Cy >mar(Ci ViE nbrsx))(Y has higher capa whether to retain y or not as follows From all of Xs neighbors that or(num-nbrsz >num_nbrsy + H)Y has fewe have capacity less than or equal to that of y, we choose the neig then bor z that has the highest degree. This neighbor has the least to DROP Z: ACCEPT Y lose if x drops it in favor of y. The neighbor will be dropped f the new node y has fewer neighbors than z. this ensures REJECT Y we do not drop already poorly-connected neighbors(which Algorithm 1: pick-neighbor-to-drop(x, y get disconnected) in favor of well-connected ones. The topology When node X tries to add Y as a new neighbor, determine whether adaptation algorithm thus tries to ensure that the adaptation proces there is room for Y. If not, pick one of X's existing neighbors makes torward progress toward a stable state. Results from experi- to drop and replace it with r.(In the algorithm, H represents in Section 5.4 3. 2.2 Flow control 3.2.1 Topology Adaptation To avoid creating hot-spots or overloading any one node, Gia uses The topology adaptation algorithm is the core component that an active flow control scheme in which a sender is allowed to direct connects the Gia client to the rest of the network. In this section, thar ties to a neighbor only if that neighbor has notified the sender details of some of the specific mechanisms for discussion later in most proposed Gnutella flow-control mechanisms [16], which are Section 5. When a node starts up, it uses bootstrapping mechanisms eactive in nature: receivers drop packets when they start to become overloaded senders can infer the likelihood that a nei similar to those in Gnutella to locate other Gia nodes. Each Gia packets based on responses that they receive from the neighbor, but client maintains a host cache consisting of a list of other Gia nodes (their IP address, port number, and capacity ) The host cache is pop- there is no explicit feedback mechanism. These technique may be ulated throughout the lifetime of the client using a variety of ren- acceptable when queries are flooded across the network, because dezvous mechanisms including contacting well-known web-based even if a node drops a query, other copies of the query will prop- host caches [5] and exchanging host information with neighbors agate through the network. However, Gia uses random walks(to through PING-PONG messages [6]. Entries in the host cache are address scaling problems with flooding)to forward a single copy of se hosts fail. Dead entries are each query. Hence, arbitrarily dropping queries is not an appropriate periodically aged ou solution The goal of the topology adaptation algorithm is to ensure that To provide better fow control, each Gia client periodically as- capacity nodes are indeed the ones with high degree and that igns flow-control tokens to its neighbors. Each token represents a w capacity nodes are within short reach of higher capacity ones single query that the node is willing to accept. Thus, a node can To achieve this goal, each node independently computes a level of send a query to a neighbor only if it has received a token from that satisfaction(S). This is a quantity between 0 and I that represen neighbor, thus avoiding overloaded neighbors. In the aggregate, a how satisfied a node is with its current set of neighbors. A value node allocates tokens at the rate at which it can process queries. If ofs =0 means that the node is quite dissatisfied, while s=1 It receives queries faster than it can forward them(either because it suggests that the node is fully satisfied. As long as a node is not fully s overloaded or because it has not received enough tokens from its satisfied, the topology adaptation continues to search for appropriate neighbors, then it starts to ce ow of queries by lowering its leue up the excess queries. If this queue neighbors to improve the satisfaction level. Thus, when a node starts gets too long, it tries to reduc token allocation rate up and has fewer than some pre-configured minimum number of eighbors, it is in a dissatisfied state(S= 0). As it gathers more To provide an incentive for high-capacity nodes to advertise their neighbors, its satisfaction level rises, until it decides that its current borg, capacity, Gia clients assign tokens in proportion to the neigh- set of neighbors is sufficient to satisty its capacity, at which point the neighbors. Thus, a node that advertises high capacity to handle the details of the algorithm used to compute the satisfaction level. coming queries is in turn assigned more tokens for its own outgoing To add a new neighbor, a node(say X)randomly selects a small queries. We use a token assignment algorithm based on Start-time number of candidate entries from those in its host cache that are no cuing(SFQ)[9]. Each neighbor is assigned a fair-queuing marked dead and are not already neighbors. From these randomly weight equal to its capacity. Neighbors that are not using any of their hosen entries, x selects the node with maximum capacity greater assigned tokens are marked as inactive and the left-over capacity than its own capacity. If no such candidate entry exists, it selects automatically redistributed proportionally between the remaining one at random Node X then initiates a three-way handshake to the neighbors. As neighbors join and leave, the SFQ algorithm recon- To avoid having X flip back and forth between Y and we drop z and add y only if y has nan implementation, we set the value c here H represents the level 410

Let Ci represent capacity of node i if num nbrsX + 1 ≤ max nbrs then {we have room} ACCEPT Y ; return {we need to drop a neighbor} subset ← i ∀ i ∈ nbrsX such that Ci ≤ CY if no such neighbors exist then REJECT Y ; return candidate Z ←highest-degree neighbor from subset if (CY > max(Ci ∀ i ∈ nbrsX) ) {Y has higher capacity} or (num nbrsZ > num nbrsY + H) {Y has fewer nbrs} then DROP Z; ACCEPT Y else REJECT Y Algorithm 1: pick neighbor to drop(X, Y ): When node X tries to add Y as a new neighbor, determine whether there is room for Y . If not, pick one of X’s existing neighbors to drop and replace it with Y . (In the algorithm, H represents a hysteresis factor.) 3.2.1 Topology Adaptation The topology adaptation algorithm is the core component that connects the Gia client to the rest of the network. In this section, we provide an overview of the adaptation process, while leaving the details of some of the specific mechanisms for discussion later in Section 5. When a node starts up, it uses bootstrapping mechanisms similar to those in Gnutella to locate other Gia nodes. Each Gia client maintains a host cache consisting of a list of other Gia nodes (their IP address, port number, and capacity). The host cache is pop￾ulated throughout the lifetime of the client using a variety of ren￾dezvous mechanisms including contacting well-known web-based host caches [5] and exchanging host information with neighbors through PING-PONG messages [6]. Entries in the host cache are marked as dead if connections to those hosts fail. Dead entries are periodically aged out. The goal of the topology adaptation algorithm is to ensure that high capacity nodes are indeed the ones with high degree and that low capacity nodes are within short reach of higher capacity ones. To achieve this goal, each node independently computes a level of satisfaction (S). This is a quantity between 0 and 1 that represents how satisfied a node is with its current set of neighbors. A value of S = 0 means that the node is quite dissatisfied, while S = 1 suggests that the node is fully satisfied. As long as a node is not fully satisfied, the topology adaptation continues to search for appropriate neighbors to improve the satisfaction level. Thus, when a node starts up and has fewer than some pre-configured minimum number of neighbors, it is in a dissatisfied state (S = 0). As it gathers more neighbors, its satisfaction level rises, until it decides that its current set of neighbors is sufficient to satisfy its capacity, at which point the topology adaptation becomes quiescent. In Section 5.2, we describe the details of the algorithm used to compute the satisfaction level. To add a new neighbor, a node (say X) randomly selects a small number of candidate entries from those in its host cache that are not marked dead and are not already neighbors. From these randomly chosen entries, X selects the node with maximum capacity greater than its own capacity. If no such candidate entry exists, it selects one at random. Node X then initiates a three-way handshake to the selected neighbor, say Y . During the handshake, each node makes a decision whether or not to accept the other node as a new neighbor based upon the capaci￾ties and degrees of its existing neighbors and the new node. In order to accept the new node, we may need to drop an existing neighbor. Algorithm 1 shows the steps involved in making this determination. The algorithm works as follows. If, upon accepting the new con￾nection, the total number of neighbors would still be within a pre￾configured bound max nbrs, then the connection is automatically accepted. Otherwise, the node must see if it can find an appropriate existing neighbor to drop and replace with the new connection. X always favors Y and drops an existing neighbor if Y has higher capacity than all of X’s current neighbors. Otherwise, it decides whether to retain Y or not as follows. From all of X’s neighbors that have capacity less than or equal to that of Y , we choose the neigh￾bor Z that has the highest degree. This neighbor has the least to lose if X drops it in favor of Y . The neighbor will be dropped only if the new node Y has fewer neighbors than Z. This ensures that we do not drop already poorly-connected neighbors (which could get disconnected) in favor of well-connected ones.6 The topology adaptation algorithm thus tries to ensure that the adaptation process makes forward progress toward a stable state. Results from experi￾ments measuring the topology adaptation process are discussed later in Section 5.4. 3.2.2 Flow control To avoid creating hot-spots or overloading any one node, Gia uses an active flow control scheme in which a sender is allowed to direct queries to a neighbor only if that neighbor has notified the sender that it is willing to accept queries from the sender. This is in contrast to most proposed Gnutella flow-control mechanisms [16], which are reactive in nature: receivers drop packets when they start to become overloaded; senders can infer the likelihood that a neighbor will drop packets based on responses that they receive from the neighbor, but there is no explicit feedback mechanism. These technique may be acceptable when queries are flooded across the network, because even if a node drops a query, other copies of the query will prop￾agate through the network. However, Gia uses random walks (to address scaling problems with flooding) to forward a single copy of each query. Hence, arbitrarily dropping queries is not an appropriate solution. To provide better flow control, each Gia client periodically as￾signs flow-control tokens to its neighbors. Each token represents a single query that the node is willing to accept. Thus, a node can send a query to a neighbor only if it has received a token from that neighbor, thus avoiding overloaded neighbors. In the aggregate, a node allocates tokens at the rate at which it can process queries. If it receives queries faster than it can forward them (either because it is overloaded or because it has not received enough tokens from its neighbors), then it starts to queue up the excess queries. If this queue gets too long, it tries to reduce the inflow of queries by lowering its token allocation rate. To provide an incentive for high-capacity nodes to advertise their true capacity, Gia clients assign tokens in proportion to the neigh￾bors’ capacities, rather than distributing them evenly between all neighbors. Thus, a node that advertises high capacity to handle in￾coming queries is in turn assigned more tokens for its own outgoing queries. We use a token assignment algorithm based on Start-time Fair Queuing (SFQ) [9]. Each neighbor is assigned a fair-queuing weight equal to its capacity. Neighbors that are not using any of their assigned tokens are marked as inactive and the left-over capacity is automatically redistributed proportionally between the remaining neighbors. As neighbors join and leave, the SFQ algorithm recon- 6To avoid having X flip back and forth between Y and Z, we add a level of hysteresis: we drop Z and add Y only if Y has at least H fewer neighbors than Z, where H represents the level of hysteresis. In our simulations and implementation, we set the value of H to 5. 410

figures its token allocation accordingly. Token assignment notifica- ons ca be sent to neighbors either as separate control messages or by piggy-backing on other messages 3.2.3 One-hop replication 1000X 4.9% To improve the efficiency of the search process, each Gia node actively maintains an index of the content of each of its neighbors. These indices are exchanged when neighbors establish connections Table 1: Gnutella-like node capacity distributions. to each other, and periodically updated with any incremental changes Thus, when a node receives a query, it can respond not only with FLOOD: Search using TTL-scoped fiooding over random topolo- matches from its own content, but also provide matches from the gies. This represents the Gnutella model content offered by all of its neighbors. When a neighbor is lost, either because it leaves the system, or due to topology adaptation, RWRT: Search using random walks over random the index information for that neighbor gets fiushed. This ensures This represents the recommended search technique that all index information remains mostly up-to-date and consistent by lv et al. [12] for avoiding the scalability probl throughout the lifetime of the node 3. 2. 4 Search protocol SUPER: Sear supermode mechanisms [7, 24]. In this The combination of topology adaptation(whereby high capac- approach, we classify nodes as supernodes and non-supernodes ity nodes have more neighbors) and one-hop replication(whereb Queries are file nly between supernodes nodes keep an index of their neighbors' shared files) ensures that GIA: Search high capacity nodes can typically provide useful responses for a adaptation, e number of queries. Hence, the gia search protocol uses a ased random walks biased random walk: rather than forwarding incoming queries to randomly chosen neighbors, a Gia node selects the highest capacity We first describe our simulation model and the metrics used for evaluating the performance of our algorithms. Then we report the that neighbor. If it has no tokens from any neighbors, it queues the results from a range of simulations. Our experiments focus on the query until new tokens arrive We use TTLs to bound the duration of the biased random walks under a variety of conditions. We show how the individual com- keeping, each query is assigned a unique GUid by its originator e ts of our system(topology adaptation, flow control, one-hop node. A node remembers the neighbors to which it has already for- synergies between them affect the total system capacity. due to warded queries for a given GUID. If a query with the same GUID ace limitations, we do not present detailed results evaluating trade arrives back at the node, it is forwarded to a different neighbor. This offs within each design component reduces the likelihood that a query traverses the same path twice To 4.1 System Model ensure forward progress, if a node has already sent the query to al of its neighbors, it flushes the book-keeping state and starts re-using To capture the effect of query load on the neighbors. tor imposes capacity constraints on each of the nodes within the Each query has a MAX_ RESPONSES parameter, the maximum system. We model each node i as possessing a capacity Ci,which number of matching answers that the query should search for. In ad- represents the number of messages(such as queries and add/drop dition to the TTL, query duration is bounded by MAX RESPONSES. requests for topology adaptation) that it can process per unit time. If a node receives queries from its neighbors at a rate higher than its ments the MAX _RESPONSES in the query. Once MAX-RESPONSES capacity Ci(as can happen in the absence of flow control), then the hits zero, the query is discarded. Query responses are forwarded excess queries are modeled as being queued in connection buffers back to the originator along the reverse-path associated with the until the receiving node can read the queries from those buffers If the reverse-path is lost due to topology adaptation or if For most of our simulations, we assign capacities to nodes based lose or responses are dropped because of node failure, we rely on a distribution that is derived from the measured bandwidth distri- echanisms described later in Section 5.3 to handle the butions for Gnutella as reported by Saroiu et al. [22]. Our distribution has five levels of capacity, each separated by an order Finally, since a node can generate a response either for its own of magnitude as shown in Table I. As described in [221, this dis- files or for the files of one of its neighbors, we append to the for- tribution reflects the reality that a fair fraction of Gnutella clients warded query the addresses of the nodes that own those files. This have dial-up connections to the Internet, the majority are connected ensures that the query does not produce multiple redundant responses via cable-modem or DSL and a small number of participants have for the same instance of a file; a response is generated only if the high speed connections. For the SUPER experiments, nodes with node that owns the matching file is not already listed in the query capacities 1000x and 10000x are designated as supernodes In addition to its capacity, each node i is assigned a query gener ation rate gi, which is the number of queries that node i generates 4. SIMULATIONS per unit time. For our experiments, w In this section, we use simulations to evaluate Gia and erate queries at the same rate(bounded, of course by their capaci ties). When queries need to be buffered, they are held in queues. We its performance to two other unstructured P2P systems. Thus our model all incoming and outgoing queues as having infinite length simulations refer to the following four models: We realize that, in practice, queues are not infinite, but we make this assumption since the effect of dropping a query and adding it to found in 9] arbitrarily long queue is essentially the same

figures its token allocation accordingly.7 Token assignment notifica￾tions can be sent to neighbors either as separate control messages or by piggy-backing on other messages. 3.2.3 One-hop Replication To improve the efficiency of the search process, each Gia node actively maintains an index of the content of each of its neighbors. These indices are exchanged when neighbors establish connections to each other, and periodically updated with any incremental changes. Thus, when a node receives a query, it can respond not only with matches from its own content, but also provide matches from the content offered by all of its neighbors. When a neighbor is lost, either because it leaves the system, or due to topology adaptation, the index information for that neighbor gets flushed. This ensures that all index information remains mostly up-to-date and consistent throughout the lifetime of the node. 3.2.4 Search Protocol The combination of topology adaptation (whereby high capac￾ity nodes have more neighbors) and one-hop replication (whereby nodes keep an index of their neighbors’ shared files) ensures that high capacity nodes can typically provide useful responses for a large number of queries. Hence, the Gia search protocol uses a biased random walk: rather than forwarding incoming queries to randomly chosen neighbors, a Gia node selects the highest capacity neighbor for which it has flow-control tokens and sends the query to that neighbor. If it has no tokens from any neighbors, it queues the query until new tokens arrive. We use TTLs to bound the duration of the biased random walks and book-keeping techniques to avoid redundant paths. With book￾keeping, each query is assigned a unique GUID by its originator node. A node remembers the neighbors to which it has already for￾warded queries for a given GUID. If a query with the same GUID arrives back at the node, it is forwarded to a different neighbor. This reduces the likelihood that a query traverses the same path twice. To ensure forward progress, if a node has already sent the query to all of its neighbors, it flushes the book-keeping state and starts re-using neighbors. Each query has a MAX RESPONSES parameter, the maximum number of matching answers that the query should search for. In ad￾dition to the TTL, query duration is bounded by MAX RESPONSES. Every time a node finds a matching response for a query, it decre￾ments the MAX RESPONSES in the query. Once MAX RESPONSES hits zero, the query is discarded. Query responses are forwarded back to the originator along the reverse-path associated with the query. If the reverse-path is lost due to topology adaptation or if queries or responses are dropped because of node failure, we rely on recovery mechanisms described later in Section 5.3 to handle the loss. Finally, since a node can generate a response either for its own files or for the files of one of its neighbors, we append to the for￾warded query the addresses of the nodes that own those files. This ensures that the query does not produce multiple redundant responses for the same instance of a file; a response is generated only if the node that owns the matching file is not already listed in the query message. 4. SIMULATIONS In this section, we use simulations to evaluate Gia and compare its performance to two other unstructured P2P systems. Thus our simulations refer to the following four models: 7Details of the SFQ algorithm for proportional allocation can be found in [9]. Capacity level Percentage of nodes 1x 20% 10x 45% 100x 30% 1000x 4.9% 10000x 0.1% Table 1: Gnutella-like node capacity distributions. • FLOOD: Search using TTL-scoped flooding over random topolo￾gies. This represents the Gnutella model. • RWRT: Search using random walks over random topologies. This represents the recommended search technique suggested by Lv et al. [12] for avoiding the scalability problems with flooding. • SUPER: Search using supernode mechanisms [7, 24]. In this approach, we classify nodes as supernodes and non-supernodes. Queries are flooded only between supernodes. • GIA: Search using the Gia protocol suite including topology adaptation, active flow control, one-hop replication, and bi￾ased random walks. We first describe our simulation model and the metrics used for evaluating the performance of our algorithms. Then we report the results from a range of simulations. Our experiments focus on the aggregate system behavior in terms of its capacity to handle queries under a variety of conditions. We show how the individual com￾ponents of our system (topology adaptation, flow control, one-hop replication, and searches based on biased random walks) and the synergies between them affect the total system capacity. Due to space limitations, we do not present detailed results evaluating trade￾offs within each design component. 4.1 System Model To capture the effect of query load on the system, the Gia simu￾lator imposes capacity constraints on each of the nodes within the system. We model each node i as possessing a capacity Ci, which represents the number of messages (such as queries and add/drop requests for topology adaptation) that it can process per unit time. If a node receives queries from its neighbors at a rate higher than its capacity Ci (as can happen in the absence of flow control), then the excess queries are modeled as being queued in connection buffers until the receiving node can read the queries from those buffers. For most of our simulations, we assign capacities to nodes based on a distribution that is derived from the measured bandwidth distri￾butions for Gnutella as reported by Saroiu et al. [22]. Our capacity distribution has five levels of capacity, each separated by an order of magnitude as shown in Table 1. As described in [22], this dis￾tribution reflects the reality that a fair fraction of Gnutella clients have dial-up connections to the Internet, the majority are connected via cable-modem or DSL and a small number of participants have high speed connections. For the SUPER experiments, nodes with capacities 1000x and 10000x are designated as supernodes. In addition to its capacity, each node i is assigned a query gener￾ation rate qi, which is the number of queries that node i generates per unit time. For our experiments, we assume that all nodes gen￾erate queries at the same rate (bounded, of course, by their capaci￾ties). When queries need to be buffered, they are held in queues. We model all incoming and outgoing queues as having infinite length. We realize that, in practice, queues are not infinite, but we make this assumption since the effect of dropping a query and adding it to an arbitrarily long queue is essentially the same. 411

a84 86420 0010.11.010010001000 0.010.11.010.0100.01000 Queries per second ries per second Queries per second Figure 2: Success rate, hop-count and delay under increasing query load for a 10,000 node Gia network. Queries are modeled as searching for specific keywords. Each all nodes will be visited with the same probability. On the other nodes. All files associated with a specific keyword are potential an- worsens wlf rmance of FLOOD does depend on degree and in fact wers for a query with that key word. We use the term replication uniformly random graphs with an average degree of eight. This factor to refer to the fraction of nodes at which answers to queries choice is ad hoc, but reflects a decision to avoid unnecessarily bi- reside. Thus, performing a query for a key word that has a replication asing against RWRT and FLOOD. of the nodes in the system. In a deployed system, real search traf- on average, the diameter of our random graphs is 7.Thus, for factor of 1% implies that an answer to this query can be found at 1% fic will include many different queries covering a range of replica- queries do not get artificially limited. For RWRT and gia, the Ttl tion factors simultaneously. However, each search process proceeds is set to a larger value(1024), but in this case setting the right TTL largely independently(aside from delays within queues and the ac- value is not as crucial because the random walks terminate when ons of flow control). Hence, rather than having to pick a specific they find the required number of responses. distribution of queries, each looking for keywords with their own Although the simulator models the behavior of the various pre eplication factors, we focus on a stream of queries all with a partic- tocols discussed in Section 3, it does not capture individual pack ular replication factor and study how our results vary as we change level behavior nor does it account for any of the vagaries in networ the replication factor. behavior caused by background trafic. We do this because our point We begin our simulations with a randomly connected topology. is not to quantify the absolute performance of the algorithm in real The GIA simulations use topology adaptation to reconfigure this ini- world terms, but to evaluate the relative performance of the various tial topology. The algorithms use two pre-configured parameters: design choices. In Section 5.4, we present some preliminary results mbrs=3. We set max _brs to 128. However, there is an additional in the wide-area Internet ces with implementing and deploying Gia min-nbrs and maz-nbrs For all of our experiments, we use min. that report on our experie onstraint on maz nbrs. To avoid mid-or low-capacity nodes from gathering so many neighbors that their capacity is too finely divided, 4.2 Performance Metrics represents the finest level of granularity into which we are willing to To measure the effect of load on the system, we looked at three as- plit a node s capacity. with this additional constraint, we note that pects of the systems performance as a function of the offered load or each node, mar-nbrs min(marnbrs the success rate measured as the fraction of queries issued that suc- some preliminary simulations that tested the performance of the Gi cessfully locate the desired files, the hop-count measured as the topology adaptation for different values of min_alloc, we settled on number of hops required to locate the requested files, and the delay min_alloc 4. All control traffic generated by the topology adap- ure 2 shows the success rate, hop-count and delay under increasing one unit of capacity per message. Thus, the simulator indirectly query loa for a 10,000 node network running the gia system. For captures the impact of control traffic on the overall performance of tion a query load of say 0.1, we mean that every node in the system For rWrt and flooD. there topology adaptation, we use issues 0. 1 queries per unit time(bounded by the node's capacity, a random graph. We know that Gnutella networks, in fact, exhibit of course). As each of the graphs in the figure shows, when the query load increases, we notice a sharp "knee"in the curves beyond properties similar to power-law graphs [20]. However, there is no which the success rate drops sharply and delays increase rapidly ssurance that high-degree nodes in the skewed gnutella distribu- The hop-count holds steady until the knee-point and then decreases plicit congruence of high capacity with high degree, a random walk The reason for this decrease is that hop-count is measured only for successful queries; under increasing load, successful queries tend will cause the high-degree nodes to get overloaded. Comparing a be those where the requested file is located within a few hops from random walk on such a topology to GIA would unfairly bias the re- the originator of the query. These graphs depict the existence of a sults against the random walk. Hence, for RWRT, we choose to use knee in the GIA model; our simulations with RWRT, FLOOD, and a purely random topology with uniform degree distributions, which SUPER over a range of replication factors revealed the same kind of mitigates this problem. The RWRT performance on such a uniformly behavior, although at different query loads random graph is independent of the degree of the individual nodes For the SUPER experiments, we use a where supernodes A query is deemed unsuccessful if at the end of the simulation it set up random connections among thems addition, all non- has generated no responses and is stuck in queues within overloaded su 412

0 0.2 0.4 0.6 0.8 1 0.01 0.1 1.0 10.0 100.0 1000 Success rate Queries per second 0.5% replication 0.1% replication 0 2 4 6 8 10 12 14 16 18 Hop Count (for successful queries) 0.01 0.1 1.0 10.0 100.0 1000 Queries per second 0.5% replication 0.1% replication 0.001 0.01 0.1 1 0.01 1.0 10.0 100.0 1000 Delay Queries per second 0.5% replication 0.1% replication Figure 2: Success rate, hop-count and delay under increasing query load for a 10,000 node Gia network. Queries are modeled as searching for specific keywords. Each keyword maps on to a set of files. Files are randomly replicated on nodes. All files associated with a specific keyword are potential an￾swers for a query with that keyword. We use the term replication factor to refer to the fraction of nodes at which answers to queries reside. Thus, performing a query for a keyword that has a replication factor of 1% implies that an answer to this query can be found at 1% of the nodes in the system. In a deployed system, real search traf- fic will include many different queries covering a range of replica￾tion factors simultaneously. However, each search process proceeds largely independently (aside from delays within queues and the ac￾tions of flow control). Hence, rather than having to pick a specific distribution of queries, each looking for keywords with their own replication factors, we focus on a stream of queries all with a partic￾ular replication factor and study how our results vary as we change the replication factor. We begin our simulations with a randomly connected topology.8 The GIA simulations use topology adaptation to reconfigure this ini￾tial topology. The algorithms use two pre-configured parameters: min nbrs and max nbrs. For all of our experiments, we use min - nbrs = 3. We set max nbrs to 128. However, there is an additional constraint on max nbrs. To avoid mid- or low-capacity nodes from gathering so many neighbors that their capacity is too finely divided, we require that C num nbrs ≥ some min alloc, where min alloc represents the finest level of granularity into which we are willing to split a node’s capacity. With this additional constraint, we note that for each node, max nbrs = min(max nbrs, C min alloc ). After some preliminary simulations that tested the performance of the GIA topology adaptation for different values of min alloc, we settled on min alloc = 4. All control traffic generated by the topology adap￾tation and other components is modeled as consuming resources: one unit of capacity per message. Thus, the simulator indirectly captures the impact of control traffic on the overall performance of the system. For RWRT and FLOOD, there is no topology adaptation; we use a random graph. We know that Gnutella networks, in fact, exhibit properties similar to power-law graphs [20]. However, there is no assurance that high-degree nodes in the skewed Gnutella distribu￾tion are also high-capacity nodes. In fact, in the absence of an ex￾plicit congruence of high capacity with high degree, a random walk will cause the high-degree nodes to get overloaded. Comparing a random walk on such a topology to GIA would unfairly bias the re￾sults against the random walk. Hence, for RWRT, we choose to use a purely random topology with uniform degree distributions, which mitigates this problem. The RWRT performance on such a uniformly random graph is independent of the degree of the individual nodes; 8For the SUPER experiments, we use a topology where supernodes set up random connections among themselves. In addition, all non￾supernodes connect to one supernode at random. all nodes will be visited with the same probability. On the other hand, the performance of FLOOD does depend on degree and in fact worsens with higher degree. For our experiments, we thus chose uniformly random graphs with an average degree of eight. This choice is ad hoc, but reflects a decision to avoid unnecessarily bi￾asing against RWRT and FLOOD. On average, the diameter of our random graphs is 7. Thus, for FLOOD and SUPER, we set the TTL for queries to 10 to ensure that queries do not get artificially limited. For RWRT and GIA, the TTL is set to a larger value (1024), but in this case setting the right TTL value is not as crucial because the random walks terminate when they find the required number of responses. Although the simulator models the behavior of the various pro￾tocols discussed in Section 3, it does not capture individual packet￾level behavior nor does it account for any of the vagaries in network behavior caused by background traffic. We do this because our point is not to quantify the absolute performance of the algorithm in real￾world terms, but to evaluate the relative performance of the various design choices. In Section 5.4, we present some preliminary results that report on our experiences with implementing and deploying Gia in the wide-area Internet. 4.2 Performance Metrics To measure the effect of load on the system, we looked at three as￾pects of the system’s performance as a function of the offered load: the success rate measured as the fraction of queries issued that suc￾cessfully locate the desired files9 , the hop-count measured as the number of hops required to locate the requested files, and the delay measured as the time taken by a query from start to finish. Fig￾ure 2 shows the success rate, hop-count and delay under increasing query load for a 10,000 node network running the Gia system. For these graphs, as in the remainder of our simulations, when we men￾tion a query load of say 0.1, we mean that every node in the system issues 0.1 queries per unit time (bounded by the node’s capacity, of course). As each of the graphs in the figure shows, when the query load increases, we notice a sharp “knee” in the curves beyond which the success rate drops sharply and delays increase rapidly. The hop-count holds steady until the knee-point and then decreases. The reason for this decrease is that hop-count is measured only for successful queries; under increasing load, successful queries tend to be those where the requested file is located within a few hops from the originator of the query. These graphs depict the existence of a knee in the GIA model; our simulations with RWRT, FLOOD, and SUPER over a range of replication factors revealed the same kind of behavior, although at different query loads. 9A query is deemed unsuccessful if at the end of the simulation it has generated no responses and is stuck in queues within overloaded nodes. 412

NRT N10,000 --k 3=, Replication Rate(percentage) Figure 3: Comparison of collapse point for the different algo- Figure 4: Hop-count before collapse rithms fixed replication factor, the CP and CP-HC are largely unaffected Ideally, we want a system that achieves a high success rate while by system size. This is to be expected since the replication factor maintaining a low hop-count and delay. To do so, the system must is the percentage of nodes at which answers are located. Thus, the operate before the knee shown in the graphs above. Consequently, performance figures we show here apply to arbitrarily large system we define the following metrics for use in our evaluation: sIzes Collapse Point(CP): the per node query rate at the knee, which we There are several other performance results of note define as the point beyond which the success rate drops below At higher replication factors, RWRT performs better than FLOOD 90%. This metric reflects total system capacity by approximately two orders of magnitude but is comparable Hop-count before collapse(CP-HC): the average hop-count prior to FLOOD at lower replication rates. This follows from the act that at low replication rates, to find a matching answer RWRT may have to visit all of the nodes in the system just We do not retain delay as a metric since the effect of increasing delay is effectively captured by the collapse poin GIA achieves extremely low hop-counts at higher replication 4.3 Performance Comparison because, in such cases, high capacity nodes are quite likely he behavior of GIA, RWRT, SUPER and FLOOD to hold answers and these are quickly discovered by biased under varying replication factors and different system sizes up to alks. However, at low replication some queries may have to 10,000 nodes. We measured the CP and CP-HC under increasing travel far beyond the high capacity nodes resulting in higher eplication factors. In Figures 3 and 4, we plot the results for systems hop-counts. FLOOD and SUPER achieve consistently low with 5,000 and 10,000 nodes. Experiments with additional system hop-counts(the number of hops to find the first matching an izes yielded results consistent with those presented here; we omit swer), while the hop-count for RWrT is inversely propor them from the graphs for clarity. For a 10,000 node system we sim tional to the replication factor, since RWRT essentially amounts ulate down to 0.01% replication since that corresponds to a singl hatching answer in the entire Sy,o 05 replication. We believe that 000 nodes we simulate down size. This is because, in FLOOD, each query is propagated to eplication factor of0.01% where only one in 10,000 nodes holds every other node in the system. With increasing number of the answer to a query represents a fairly pessimistic test scenario nodes, there are more total number of queries in the system Each query in these experiments runs until it finds one matching an- nd hence a query load arriving at each node. This swer. This represents the case where the query originator sets the causes the collapse point to fall as the system size increases MAX _RESPONSES parameter(see Section 3. 2. 4)in the query to I We observed effects with SUPER as seen from Fig In reality, most users expect a query to return multiple answers; we ure 3 will look at that scenario later. For GIA and RWRT, we measure These experiments clearly demonstrate GIA's scalability the average hop-count of all of the queries. Since for SUPER and to RWRT, SUPER and FLOOD. However, these experiments FLOOD a query gets replicated at each hop, it is hard to define a ited to queries where the search terminates after finding consistent hop-count for the entire query; hence, we measure the matching answer. In reality, most users expect a query to return hop-count as the number of hops taken to find the first answer multiple answers. We now look at(a)how our results generalize be Recall that our first goal in designing Gia was to enable it to han- yond this single case, and(b)how the different design components dle a much higher aggregate query rate than gnutella. The most contribute to this enormous performance boost for GIA obvious, and important, observation from Figures 3 and 4 is that the aggregate system capacity (as defined by the collapse point)is 3 to s 4.4 Multiple Search Responses rders of magnitude higher than either flood or RWRT. Even when ompared to the supernode approach, Gia does better especially at sociated hop-counts) change for our different system models base higher replication rates. This is not surprising since the flooding upon the desired number of responses for a query. Recall from Sec techniques used within supernodes limit their scalability. Thus, our tion 3. 2. 4 that a query includes a MAXRESPONSES eter that goal of improving system capacity with Gia is clearly achieved. Our indicates how many responses should be sent back to the originat second goal was that Gia retain this ability to handle high aggre- of the query before ending the query. The MAXRESPONSES gate query rates for systems of arbitrary sizes. As can be observed rameter is useful only in the context of GIA and RWRT. For FLOOD the graphs, this goal is also satisfied. GIA,s(and RWRT'Ss)scal- and SUPER, queries get flooded through the network, and so MAX- behavior is determined by the replication factor. That is, at a RESPONSES has no effect on their behavior

0.00001 0.0001 0.001 0.01 0.1 1 10 100 1000 0.01 0.05 0.1 0.5 1 Collapse Point (qps) Replication Rate (percentage) GIA; N=10,000 RWRT; N=10,000 FLOOD; N=10,000 SUPER; N=10,000 GIA; N=5,000 RWRT; N=5,000 FLOOD; N=5,000 SUPER; N=5,000 Figure 3: Comparison of collapse point for the different algo￾rithms at varying replication rates and different system sizes. Ideally, we want a system that achieves a high success rate while maintaining a low hop-count and delay. To do so, the system must operate before the knee shown in the graphs above. Consequently, we define the following metrics for use in our evaluation: Collapse Point (CP): the per node query rate at the knee, which we define as the point beyond which the success rate drops below 90%. This metric reflects total system capacity. Hop-count before collapse (CP-HC): the average hop-count prior to collapse. We do not retain delay as a metric since the effect of increasing delay is effectively captured by the collapse point. 4.3 Performance Comparison We compare the behavior of GIA, RWRT, SUPER and FLOOD under varying replication factors and different system sizes up to 10,000 nodes. We measured the CP and CP-HC under increasing replication factors. In Figures 3 and 4, we plot the results for systems with 5,000 and 10,000 nodes. Experiments with additional system sizes yielded results consistent with those presented here; we omit them from the graphs for clarity. For a 10,000 node system we sim￾ulate down to 0.01% replication since that corresponds to a single matching answer in the entire system for any query. Likewise, for 5,000 nodes we simulate down to 0.05% replication. We believe that a replication factor of 0.01% where only one in 10,000 nodes holds the answer to a query represents a fairly pessimistic test scenario. Each query in these experiments runs until it finds one matching an￾swer. This represents the case where the query originator sets the MAX RESPONSES parameter (see Section 3.2.4) in the query to 1. In reality, most users expect a query to return multiple answers; we will look at that scenario later. For GIA and RWRT, we measure the average hop-count of all of the queries. Since for SUPER and FLOOD a query gets replicated at each hop, it is hard to define a consistent hop-count for the entire query; hence, we measure the hop-count as the number of hops taken to find the first answer. Recall that our first goal in designing Gia was to enable it to han￾dle a much higher aggregate query rate than Gnutella. The most obvious, and important, observation from Figures 3 and 4 is that the aggregate system capacity (as defined by the collapse point) is 3 to 5 orders of magnitude higher than either FLOOD or RWRT. Even when compared to the supernode approach, Gia does better especially at higher replication rates. This is not surprising since the flooding techniques used within supernodes limit their scalability. Thus, our goal of improving system capacity with Gia is clearly achieved. Our second goal was that Gia retain this ability to handle high aggre￾gate query rates for systems of arbitrary sizes. As can be observed in the graphs, this goal is also satisfied. GIA’s (and RWRT’s) scal￾ing behavior is determined by the replication factor. That is, at a 1 10 100 1000 10000 0.01 0.05 0.1 0.5 1 Hop Count Before Collapse Replication Rate (percentage) GIA; N=10,000 RWRT; N=10,000 FLOOD; N=10,000 SUPER; N=10,000 GIA; N=5,000 RWRT; N=5,000 FLOOD; N=5,000 SUPER; N=5,000 Figure 4: Hop-count before collapse. fixed replication factor, the CP and CP-HC are largely unaffected by system size. This is to be expected since the replication factor is the percentage of nodes at which answers are located. Thus, the performance figures we show here apply to arbitrarily large system sizes. There are several other performance results of note. • At higher replication factors, RWRT performs better than FLOOD by approximately two orders of magnitude but is comparable to FLOOD at lower replication rates. This follows from the fact that at low replication rates, to find a matching answer RWRT may have to visit all of the nodes in the system just like FLOOD. • GIA achieves extremely low hop-counts at higher replication because, in such cases, high capacity nodes are quite likely to hold answers and these are quickly discovered by biased walks. However, at low replication some queries may have to travel far beyond the high capacity nodes resulting in higher hop-counts. FLOOD and SUPER achieve consistently low hop-counts (the number of hops to find the first matching an￾swer), while the hop-count for RWRT is inversely propor￾tional to the replication factor, since RWRT essentially amounts to random probing. • The performance of FLOOD degrades with increasing system size. This is because, in FLOOD, each query is propagated to every other node in the system. With increasing number of nodes, there are more total number of queries in the system, and hence a greater query load arriving at each node. This causes the collapse point to fall as the system size increases. We observed similar effects with SUPER as seen from Fig￾ure 3. These experiments clearly demonstrate GIA’s scalability relative to RWRT, SUPER and FLOOD. However, these experiments are lim￾ited to queries where the search terminates after finding a single matching answer. In reality, most users expect a query to return multiple answers. We now look at (a) how our results generalize be￾yond this single case, and (b) how the different design components contribute to this enormous performance boost for GIA. 4.4 Multiple Search Responses In this section we look at how the collapse points (and the as￾sociated hop-counts) change for our different system models based upon the desired number of responses for a query. Recall from Sec￾tion 3.2.4 that a query includes a MAX RESPONSES parameter that indicates how many responses should be sent back to the originator of the query before ending the query. The MAX RESPONSES pa￾rameter is useful only in the context of GIA and RWRT. For FLOOD and SUPER, queries get flooded through the network, and so MAX - RESPONSES has no effect on their behavior. 413

Collapse point H Algorithm Collapse Point Hop-count 0.004 RWRT + OHR GIA-TADAPT I RWRT TADAPT 1129 GIA-FLWCTL 15.1 RWRT +FLWCTL 0.0006 957 Table 4: Factor analysis for GIA and RWRT with 10,000 modes and 0.1% replication. We measure GIA with each of the folle components removed, and RWRT with each of those components added: one-hop replication(OHR), biased random walks(BI topology adaptation(TADAPT), and flow-control (FLWCTL RWRT FLOOD SUPER 4.5 Factor Analy factor RESP CP(CP-HC)I CP(CP-HC) Our results in Section 4.3 indicate that GIA outperforms RWRT 0.005 0.000250015 SUPER and FLood by several orders of magnitude in terms of the query load that it can successfully sustain. We now turn our attentio 0.0004 0.00025 0.015 to looking at how the individual c ation, flow control, one-hop replication, and biased random walks) 0.000150.00025005 nfluence this performance gain. Many researchers have proposed (28) (2157) schemes for improving gnutella's scalability that use one o Table 2: CP decreases with increasing numbers of requested of the GIA components. What distinguishes GIA from mos answers(MAX_RESPONSES). The corresponding hop-counts be- schemes is the combination of all of the components int fore collapse for each case are shown in parentheses. Since hop- prehensive system design that, unlike previous work, adap counts are ambiguous for FLOOD and SUPER when there are component to be "capacity-sensitive multiple responses, we ignore CP-HC for those cases. In this section, we show that it is not any single component, but in fact, the combination of them all that provides gla this large perfor- MAX GIA T RWRT T FLOOD T SUPER mance advantage. We show that each of GIAs design components factor I RESPONSES CP is vital to its performance, and yet, the addition of any single Gl 1% 0 80.0004 0.0002510.0151 component to rWRT does not significantly close the performance 000050000250015 gap between GIA and RWRT. We do not consider FLOOD since the 250000150000250015 primary design leap from FLOOD to GIA is in the transition from 200oD0000500 the use of floods to the use of random walks the effect of which is lready captured by the basic RWRT. Similarly, SUPER is just one Table 3: A search for k responses at r% replication is equivalent step toward the gia design that includes some amount of one-hop to one for a single answer at i% replication. replication and an ad-hoc awareness of node heterogeneity. Here, we instead examine the performance of GIA upon removing each of its four design components one at a time and compare it to the be Table 2 shows the CP for all four system models for a 10,000 node havior of RWRT if we were to add those design components to it one system at a replication factor of 1%. For RWRT and GIa, higher at a time values of MAX-RESPONSES imply that the query needs to search Table 4 shows the result of this factor analysis for 10,000 nodes through the network longer before it ends. This results in a higher at a replication of 0. 1%. At first glance, one may conclude that effective hop-count for each query and as a result causes each query GIA gets most of its performance gain from the one-hop replication, to utilize more of the available system capacity. As shown by the since removing one-hop replication from GIA severely impacts its CP values in the table, this effectively reduces the overall system performance. However, adding one-hop replication to RWRT oI capacity. As expected, varying MAX- RESPONSES has no effect on improves the CP by a single order of magnitude while GIA as a whole the suPeR and Flood models offers a Cp that is over four orders of magnitude greater than with As seen earlier in Figure 3, the collapse point also depends on the RWRT. It is the combination of topology adaptation, biased-random plication factor. When files are replicated at fewer nodes, queries walks and flow-control in addition to the one-hop replication that must on average visit more nodes to find them. as a result, the col- gives gla its enormous performance gain over RWRT. lapse point drops with decreasing replication factors. In fact, we find Biasing the random walk appears to be of little consequence that the performance of a query for k MAX RESPONSES at a repli- IA's performance. This is because at high query loads(i. e, close to cation factor of r is equivalent to that of a query for a single response CP), the fiow-control component serves to divert load towards any at a correspondingly lower replication factor of F. This is depicted available capacity(which is typically in the high capacity nodes), Table 3. With all four system models, searching for 10 answers and thus functions akin to the biased walks. However, under lower btained by searching for a single answer at a replication factor of that helps to direct queries rapidly to high capaciy ee ased walk at a replication factor of 1.0% yields a CP almost identical to that query loads, when all nodes are lightly loaded, it is the biased walk 0. 1%. Likewise, searching for 20 answers at 1% replication yields P as searching for a single answer at 0.05% ation 4.6 Effect of Heterogeneity Given this result, we model the rest of our GIA and RWRT sim- Since GIA is explicitly designed to be sensitive to node capaci- ulations for simplicity with searches that terminate after finding the ties, we now examine the impact of heterogeneity on system perfor- first answer for their queries. This does not change the nature of( mance. Table 5 compares the performance of GIA and RWRT with results but makes it simpler to analyze the system and is suficient to node capacities drawn from the gnutella-like capacity distribution bring out the significant differences between the various designs. to the case where all nodes have identical capacities equal to the 414

Algorithm Collapse Point Hop-count GIA 7 15.0 GIA – OHR 0.004 8570 GIA – BIAS 6 24.0 GIA – TADAPT 0.2 133.7 GIA – FLWCTL 2 15.1 Algorithm Collapse Point Hop-count RWRT 0.0005 978 RWRT + OHR 0.005 134 RWRT + BIAS 0.0015 997 RWRT + TADAPT 0.001 1129 RWRT + FLWCTL 0.0006 957 Table 4: Factor analysis for GIA and RWRT with 10,000 modes and 0.1% replication. We measure GIA with each of the following components removed, and RWRT with each of those components added: one-hop replication (OHR), biased random walks (BIAS), topology adaptation (TADAPT), and flow-control (FLWCTL) Repl. MAX GIA RWRT FLOOD SUPER factor RESP. CP (CP-HC) CP (CP-HC) CP CP 1% 1 350 0.005 0.00025 0.015 (1.4) (98.7) 1% 10 8 0.0004 0.00025 0.015 (12.5) (1020) 1% 20 2.5 0.00015 0.00025 0.015 (28) (2157) Table 2: CP decreases with increasing numbers of requested answers (MAX RESPONSES). The corresponding hop-counts be￾fore collapse for each case are shown in parentheses. Since hop￾counts are ambiguous for FLOOD and SUPER when there are multiple responses, we ignore CP-HC for those cases. Repl. MAX GIA RWRT FLOOD SUPER factor RESPONSES CP CP CP CP 1% 10 8 0.0004 0.00025 0.015 0.1% 1 7 0.0005 0.00025 0.015 1% 20 2.5 0.00015 0.00025 0.015 0.05% 1 2.5 0.00015 0.00025 0.015 Table 3: A search for k responses at r% replication is equivalent to one for a single answer at r k% replication. Table 2 shows the CP for all four system models for a 10,000 node system at a replication factor of 1%. For RWRT and GIA, higher values of MAX RESPONSES imply that the query needs to search through the network longer before it ends. This results in a higher effective hop-count for each query and as a result causes each query to utilize more of the available system capacity. As shown by the CP values in the table, this effectively reduces the overall system capacity. As expected, varying MAX RESPONSES has no effect on the SUPER and FLOOD models. As seen earlier in Figure 3, the collapse point also depends on the replication factor. When files are replicated at fewer nodes, queries must on average visit more nodes to find them. As a result, the col￾lapse point drops with decreasing replication factors. In fact, we find that the performance of a query for k MAX RESPONSES at a repli￾cation factor of r is equivalent to that of a query for a single response at a correspondingly lower replication factor of r k . This is depicted in Table 3. With all four system models, searching for 10 answers at a replication factor of 1.0% yields a CP almost identical to that obtained by searching for a single answer at a replication factor of 0.1%. Likewise, searching for 20 answers at 1% replication yields the same CP as searching for a single answer at 0.05% replication. Given this result, we model the rest of our GIA and RWRT sim￾ulations for simplicity with searches that terminate after finding the first answer for their queries. This does not change the nature of our results but makes it simpler to analyze the system and is sufficient to bring out the significant differences between the various designs. 4.5 Factor Analysis Our results in Section 4.3 indicate that GIA outperforms RWRT, SUPER and FLOOD by several orders of magnitude in terms of the query load that it can successfully sustain. We now turn our attention to looking at how the individual components of GIA (topology adap￾tation, flow control, one-hop replication, and biased random walks) influence this performance gain. Many researchers have proposed schemes for improving Gnutella’s scalability that use one or more of the GIA components. What distinguishes GIA from most other schemes is the combination of all of the components into a com￾prehensive system design that, unlike previous work, adapts each component to be “capacity-sensitive”. In this section, we show that it is not any single component, but in fact, the combination of them all that provides GIA this large perfor￾mance advantage. We show that each of GIA’s design components is vital to its performance, and yet, the addition of any single GIA component to RWRT does not significantly close the performance gap between GIA and RWRT. We do not consider FLOOD since the primary design leap from FLOOD to GIA is in the transition from the use of floods to the use of random walks, the effect of which is already captured by the basic RWRT. Similarly, SUPER is just one step toward the GIA design that includes some amount of one-hop replication and an ad-hoc awareness of node heterogeneity. Here, we instead examine the performance of GIA upon removing each of its four design components one at a time and compare it to the be￾havior of RWRT if we were to add those design components to it one at a time. Table 4 shows the result of this factor analysis for 10,000 nodes at a replication of 0.1%. At first glance, one may conclude that GIA gets most of its performance gain from the one-hop replication, since removing one-hop replication from GIA severely impacts its performance. However, adding one-hop replication to RWRT only improves the CP by a single order of magnitude while GIA as a whole offers a CP that is over four orders of magnitude greater than with RWRT. It is the combination of topology adaptation, biased-random walks and flow-control in addition to the one-hop replication that gives GIA its enormous performance gain over RWRT. Biasing the random walk appears to be of little consequence to GIA’s performance. This is because at high query loads (i.e., close to CP), the flow-control component serves to divert load towards any available capacity (which is typically in the high capacity nodes), and thus functions akin to the biased walks. However, under lower query loads, when all nodes are lightly loaded, it is the biased walk that helps to direct queries rapidly to high capacity nodes. 4.6 Effect of Heterogeneity Since GIA is explicitly designed to be sensitive to node capaci￾ties, we now examine the impact of heterogeneity on system perfor￾mance. Table 5 compares the performance of GIA and RWRT with node capacities drawn from the Gnutella-like capacity distribution to the case where all nodes have identical capacities equal to the av- 414

Collapse Point Hop-count A w/ gnutella 46.0 RWRT W/ uniform 0.0525 apacity distribution replication rate =0. 1% Table 5: Impact of heterogeneity: 10,000 nodes, 0.1% replication 0.1 000 0000 no failures rage node capacity from the Gnutella distribution. The CP in GIa Figure 5: Collapse Point under increasing MAXLIFETIME for improves when nodes have heterogeneous capacities. In contrast, we 10,000 node GIA system see that RWRT is not tolerant of heterogeneity and the CP drops by over two orders of magnitude relative to the uniform capacity case While the CP-HC remains the same for RWRT in both cases(as one would expect), the hop-count for GIA drops since the biased random eplication rate=O walks start directing queries towards the high-capacity nodes 4.7 Robustness Our results so far have shown that Gia performs significantly bet- ter than previous unstructured P2P file sharing systems. In this sec- tion, we show that Gia can sustain this performance in the face of 10.0 0000 no failures failure model. We model node failures by an up-time picked uniformly at random from [0, MAXLIFE- Figure 6: Hop Count under increasing MAXLIFETIME for a where MAXLIFETIME is a simulation parameter. When a 10,000 node Gla system node's up-time expires, the node resets. That is, it disconnects from onnecting initially to a random number of neighbors. This is sim- P2P systems need no longer pose insurmountable scaling problems lar to modeling existing nodes shutting down and leaving the system Ifso, we conjecture that the next bottleneck limiting scalability is while other new nodes are simultaneously joining the system. When likely to be the file download process. This will be particularly true a node shuts down, any queries it has queued locally are dropped and if, as recent measurement studies indicate, file sizes continue to in- resumed by the nodes that had originally generated them. Finall crease [21] We believe that Gia's ability to harness capacity in a as nodes join and leave the system, the topology adaptation over- manner that is sensitive to the constraints of individual nodes can head is captured by the fact that each node's adaptation operations have a beneficial impact on downloads as well. Even as is, Gia aids consume capacity within the node node Gia system under increasing MAXLIFETIME. We see that, rel- likely to be significant unless high capacity nodes also store more tive to the static case, the cp drops by approximately an order of magnitude as the MAXLIFETIME is reduced to 10.0 time units, while have to extend the one-hop replication used in Gia to allow the ad the hop-count rises by approximately a factor of five. Note that tive replication of the files themselves(rather than simply pointers a MAXLIFETIME of 10 time units, approximately 20% of the node to files). A simple form of active replication would be for over- reset in every time unit. Even under this extremely stressful test, loaded low capacity nodes to replicate popular files at the higher GIA's performance drops only by less than one order of magnitude. capacity nodes in their one-hop neighborhood. This can be done in This is still an improvement of 2-4 orders of magnitude over RWRT, an on-demand fashion where the high-capacity nodes replicate con- SUPER and FLooD under static conditions ent only when they receive a query and a corresponding download request for that content. 4. 8 File downloads To gauge the extent to which such activ The results presented above indicate that Gia can support signi ful, we did a simple calculation of the total capacity of all the nodes antly higher query loads than previously proposed approaches for at which file is available with and without this active repli- distributed file searching and can maintain this performance advan- cation scheme. The resultant numbers are listed in Table 6.We tage even in the face of high node churn. Gias dramatic perfo that active replication increases the total capacity of nodes serving a mance improvement stems from its unique combination of design given file by a factor of between 38 to 50. This appears promising components and its ability to funnel work to high capacity nodes in although one would need significant more analysis and simulations the system. to validate the usefulness of this approach. Our results thus lead us to conclude that search in decentralized 10 The exact mechanisms for impler 5. IMPLEMENTATION AND PRACTICAL a real sys- m are discussed in Section 5.3 DETAILS pare this to typical gnutella We implemented a prototype Gia client that incorporates all of the utes[22] al gorithms presented in Section 3. The client, which was written in 415

Algorithm Collapse Point Hop-count GIA w/ Gnutella 7 15.0 capacity distribution GIA w/ uniform 2 46.0 capacity distribution RWRT w/ Gnutella 0.0005 978 capacity distribution RWRT w/ uniform 0.0525 987 capacity distribution Table 5: Impact of heterogeneity; 10,000 nodes, 0.1% replication erage node capacity from the Gnutella distribution. The CP in GIA improves when nodes have heterogeneous capacities. In contrast, we see that RWRT is not tolerant of heterogeneity and the CP drops by over two orders of magnitude relative to the uniform capacity case. While the CP-HC remains the same for RWRT in both cases (as one would expect), the hop-count for GIA drops since the biased random walks start directing queries towards the high-capacity nodes. 4.7 Robustness Our results so far have shown that Gia performs significantly bet￾ter than previous unstructured P2P file sharing systems. In this sec￾tion, we show that Gia can sustain this performance in the face of node failures. Node failure model. We model node failures by assigning each node an up-time picked uniformly at random from [0, MAXLIFE￾TIME] where MAXLIFETIME is a simulation parameter. When a node’s up-time expires, the node resets. That is, it disconnects from its neighbors, shuts down, and immediately rejoins the system by connecting initially to a random number of neighbors. This is simi￾lar to modeling existing nodes shutting down and leaving the system while other new nodes are simultaneously joining the system. When a node shuts down, any queries it has queued locally are dropped and resumed by the nodes that had originally generated them.10 Finally, as nodes join and leave the system, the topology adaptation over￾head is captured by the fact that each node’s adaptation operations consume capacity within the node. Figures 5 and 6 plot the CP and CP-HC, respectively, for a 10,000 node Gia system under increasing MAXLIFETIME. We see that, rel￾ative to the static case, the CP drops by approximately an order of magnitude as the MAXLIFETIME is reduced to 10.0 time units, while the hop-count rises by approximately a factor of five. Note that at a MAXLIFETIME of 10 time units, approximately 20% of the nodes reset in every time unit.11 Even under this extremely stressful test, GIA’s performance drops only by less than one order of magnitude. This is still an improvement of 2-4 orders of magnitude over RWRT, SUPER and FLOOD under static conditions. 4.8 File Downloads The results presented above indicate that Gia can support signif￾icantly higher query loads than previously proposed approaches for distributed file searching and can maintain this performance advan￾tage even in the face of high node churn. Gia’s dramatic perfor￾mance improvement stems from its unique combination of design components and its ability to funnel work to high capacity nodes in the system. Our results thus lead us to conclude that search in decentralized 10The exact mechanisms for implementing query restart in a real sys￾tem are discussed in Section 5.3. 11Compare this to typical Gnutella node life-times of 60 min￾utes [22]. 0.1 1 10 100 10.0 100.0 1000.0 no failures Collapse Point (qps) Maxlife (seconds) replication rate=1.0% replication rate=0.5% replication rate=0.1% Figure 5: Collapse Point under increasing MAXLIFETIME for a 10,000 node GIA system 0 10 20 30 40 50 60 10.0 100.0 1000.0 no failures Hop Count at Collapse Point Maxlife (seconds) replication rate=1.0% replication rate=0.5% replication rate=0.1% Figure 6: Hop Count under increasing MAXLIFETIME for a 10,000 node GIA system P2P systems need no longer pose insurmountable scaling problems. If so, we conjecture that the next bottleneck limiting scalability is likely to be the file download process. This will be particularly true if, as recent measurement studies indicate, file sizes continue to in￾crease [21]. We believe that Gia’s ability to harness capacity in a manner that is sensitive to the constraints of individual nodes can have a beneficial impact on downloads as well. Even as is, Gia aids downloads to the extent that users are typically directed to a high￾capacity copy of a file if one exists. However this advantage is un￾likely to be significant unless high capacity nodes also store more files. Thus, for Gia to be able to assist in file downloads, we would have to extend the one-hop replication used in Gia to allow the ac￾tive replication of the files themselves (rather than simply pointers to files). A simple form of active replication would be for over￾loaded low capacity nodes to replicate popular files at the higher capacity nodes in their one-hop neighborhood. This can be done in an on-demand fashion where the high-capacity nodes replicate con￾tent only when they receive a query and a corresponding download request for that content. To gauge the extent to which such active replication might be use￾ful, we did a simple calculation of the total capacity of all the nodes at which a given file is available with and without this active repli￾cation scheme. The resultant numbers are listed in Table 6. We see that active replication increases the total capacity of nodes serving a given file by a factor of between 38 to 50. This appears promising, although one would need significant more analysis and simulations to validate the usefulness of this approach. 5. IMPLEMENTATION AND PRACTICAL DETAILS We implemented a prototype Gia client that incorporates all of the algorithms presented in Section 3. The client, which was written in 415

ia Gia with active replication 4,716 1.0% 9218352,816 Table 6: Total capacity of all the nodes offering a given file with and without active replication for a 10, 000 node GIa network >55 Let Ci represent capacity of node i ifnum-nbrsx min_nbrs then return 0.0 toal←0.0 Satisfaction Level for all N E neighbors(X)do Figure 7: Adaptation Interval: A plot of the function I total← total+ TxK-(I-s), where S= satisfaction-Jevel0, T=maximum interval between adaptation iterations, and K= sensitivity to ifs>1.0 or nurm-nbrsx >mat-nbrs then satisfaction evelo. In this figure, we set T= 10seconds and S←1.0 plot curves for adaptation interval versus satisfaction level for return s different values of k Computes how "satisfied "node x is. Returns value between 0.0 and of a node's neighbors(normalized by their degrees) is to the node's 1.0. 1.0= node X is fully satisfied, while 0.0= it is completely own capacity. Thus a high capacity neighbor with a low degree con- dissatisfied. Values in between represent the extent of satisfaction tributes more to our satisfaction level than another neighbor with the same capacity but a much higher degree. The intuition behind this is that a node with capacity C will forward approximately C queries C++, provides a command-line-based file sharing interface. In this per unit time at full load and needs enough outgoing capacity from section, we discuss some of the systems issues that our prototype all of its neighbors to handle that load. In addition to the factors dis 5.1 Capacity settings he satisfaction level, for example, the load on a node's neighbors network locality, etc. However, for our prototype, we rely only on In our discussion so far, we have assumed that a node's capacity node capacity and degree to compute the satisfaction level is a quantity that represents the number of queries that the node can The satisfaction level is key to deciding how often a no handle per second. For low-bandwidth clients, query pi ng ca- conduct its local topology adaptation. Nodes with low pacity is limited by the clients access bandwidth. On the other hand, levels perform topology adaptation more frequently tha for nodes with high-speed access connections, other issues such nodes. We use an exponential relationship between the satisfaction the speed of the CPU, disk latencies, etc. may affect the capacity level, S, and the adaptation interval, I: I=TX K-d-s),where Our prototype implementation ignores the effects of CPU speed and T is the maximum interval between adaptation iterations, and K disk latency on query capacity. We assume that capacity is a di- represents the aggressiveness of the adaptation. After each interval rect function of the access bandwidth. A node can either have its 1, if a node's satisfaction level is 1.0, it attempts to add a new end-user configure its access bandwidth(via a user interface, as is neighbor. Once a node is fully satisfied, it still continues to iterate done in many gnutella clients), or automatically determine the ac- through the adaptation process, checking its satisfaction level every ess bandwidth by executing a configuration script that downloads T seconds large chunks of data from well-known sites around the Internet and Figure 7 shows how the aggressiveness factor K affects the adap. measures the bandwidth based upon the average time taken for the tation interval. As expected, when a node is fully satisfied(S ownloads. In addition, the advertised capacity of nodes can be 1.0), the adaptation interval is T irrespective of the value of K.As weighted by how long the node has been in the system. This ensures the level of satisfaction decreases, the adaptation interval become that the well-connected high-capacity core of the network shorter. For the same satisfaction level, higher values of K produce posed of mostly stable nodes. In future implementations, we plan shorter intervals and hence cause a more aggressive(i.e, quicker) experiment with auto-configuration scripts that take into response. In Section 5. 4 we look at how the rate of topology ada ther factors in addition to network bandwidth and node life-times tation changes in a real system with different values of K in order to determine client capacity 5.3 Query resilience 5.2 Satisfaction Level: Aggressiveness of Adap- As described earlier, the Gia search protocol uses biased random tation walks to forward queries across the network. One of the drawbacks he notion of satisfaction level of using a random walk instead of fiooding is that it is much more for a client. The satisfaction level determines not only whether susceptible to failures in the network. If a node receives a query and r not to perform topology adaptation, but also how frequently it dies before it can forward the query to a neighbor, that query is lost should be executed. It is a function of pre-configured min_nbrs and forever. This is in contrast to fiooding where a query gets replicated max-mbrs parameters, the node s current set of neighbors, their ca- many times, and so even if a node dies without forwarding a query pacities and their degrees. Neighbors exchange capacity information there is a good chance that other copies of the query still exist in the when they initially connect to each other, and periodically update system each other with information about their current degree. Algorithm 2 To overcome this problem, we rely on query keep-alive messages shows the steps involved in calculating the satis faction-levelo. It Query responses sent back to the originator of the query act as im- is essentially a measure of how close the sum of the capacities of all plicit keep-alives. In addition, if a query is forwarded enough times 416

% Replication Gia Gia with active replication 0.1% 965 48,682 0.5% 4,716 213,922 1.0% 9,218 352,816 Table 6: Total capacity of all the nodes offering a given file with and without active replication for a 10,000 node GIA network Let Ci represent capacity of node i if num nbrsX 1.0 or num nbrsX ≥ max nbrs then S ←1.0 return S Algorithm 2: satisfaction level(X) Computes how “satisfied” node X is. Returns value between 0.0 and 1.0. 1.0 ⇒ node X is fully satisfied, while 0.0 ⇒ it is completely dissatisfied. Values in between represent the extent of satisfaction. C++, provides a command-line-based file sharing interface. In this section, we discuss some of the systems issues that our prototype implementation addresses. 5.1 Capacity settings In our discussion so far, we have assumed that a node’s capacity is a quantity that represents the number of queries that the node can handle per second. For low-bandwidth clients, query processing ca￾pacity is limited by the client’s access bandwidth. On the other hand, for nodes with high-speed access connections, other issues such as the speed of the CPU, disk latencies, etc. may affect the capacity. Our prototype implementation ignores the effects of CPU speed and disk latency on query capacity. We assume that capacity is a di￾rect function of the access bandwidth. A node can either have its end-user configure its access bandwidth (via a user interface, as is done in many Gnutella clients), or automatically determine the ac￾cess bandwidth by executing a configuration script that downloads large chunks of data from well-known sites around the Internet and measures the bandwidth based upon the average time taken for the downloads. In addition, the advertised capacity of nodes can be weighted by how long the node has been in the system. This ensures that the well-connected high-capacity core of the network is com￾posed of mostly stable nodes. In future implementations, we plan to experiment with auto-configuration scripts that take into account other factors in addition to network bandwidth and node life-times in order to determine client capacity. 5.2 Satisfaction Level: Aggressiveness of Adap- tation In Section 3.2.1, we introduced the notion of satisfaction level for a client. The satisfaction level determines not only whether or not to perform topology adaptation, but also how frequently it should be executed. It is a function of pre-configured min nbrs and max nbrs parameters, the node’s current set of neighbors, their ca￾pacities and their degrees. Neighbors exchange capacity information when they initially connect to each other, and periodically update each other with information about their current degree. Algorithm 2 shows the steps involved in calculating the satisfaction level(). It is essentially a measure of how close the sum of the capacities of all 0 2 4 6 8 10 0 0.2 0.4 0.6 0.8 1 Satisfaction Level Adaptation Interval (seconds) K=1024 K=256 K=64 K=16 K=4 Figure 7: Adaptation Interval: A plot of the function I = T × K−(1−S) , where S = satisfaction level(), T = maximum interval between adaptation iterations, and K = sensitivity to satisfaction level(). In this figure, we set T = 10seconds and plot curves for adaptation interval versus satisfaction level for different values of K. of a node’s neighbors (normalized by their degrees) is to the node’s own capacity. Thus a high capacity neighbor with a low degree con￾tributes more to our satisfaction level than another neighbor with the same capacity but a much higher degree. The intuition behind this is that a node with capacity C will forward approximately C queries per unit time at full load and needs enough outgoing capacity from all of its neighbors to handle that load. In addition to the factors dis￾cussed above, a number of other parameters may be used to compute the satisfaction level, for example, the load on a node’s neighbors, network locality, etc. However, for our prototype, we rely only on node capacity and degree to compute the satisfaction level. The satisfaction level is key to deciding how often a node should conduct its local topology adaptation. Nodes with low satisfaction levels perform topology adaptation more frequently than satisfied nodes. We use an exponential relationship between the satisfaction level, S, and the adaptation interval, I: I = T × K−(1−S) , where T is the maximum interval between adaptation iterations, and K represents the aggressiveness of the adaptation. After each interval I, if a node’s satisfaction level is < 1.0, it attempts to add a new neighbor. Once a node is fully satisfied, it still continues to iterate through the adaptation process, checking its satisfaction level every T seconds. Figure 7 shows how the aggressiveness factor K affects the adap￾tation interval. As expected, when a node is fully satisfied (S = 1.0), the adaptation interval is T irrespective of the value of K. As the level of satisfaction decreases, the adaptation interval becomes shorter. For the same satisfaction level, higher values of K produce shorter intervals and hence cause a more aggressive (i.e., quicker) response. In Section 5.4 we look at how the rate of topology adap￾tation changes in a real system with different values of K. 5.3 Query resilience As described earlier, the Gia search protocol uses biased random walks to forward queries across the network. One of the drawbacks of using a random walk instead of flooding is that it is much more susceptible to failures in the network. If a node receives a query and dies before it can forward the query to a neighbor, that query is lost forever. This is in contrast to flooding where a query gets replicated many times, and so even if a node dies without forwarding a query, there is a good chance that other copies of the query still exist in the system. To overcome this problem, we rely on query keep-alive messages. Query responses sent back to the originator of the query act as im￾plicit keep-alives. In addition, if a query is forwarded enough times 416