An E?cient Algorithm for Resource Sharing in Peer-to-Peer Networks
Wei-Cherng Liao, Fragkiskos Papadopoulos, and Konstantinos Psounis
University of Southern California, Los Angeles,
CA 90089 weicherl,fpapadop,email@example.com
Abstract. The performance of peer-to-peer systems depends on the level of cooperation of the system’s participants. While most existing peer-to-peer architectures have assumed that users are generally cooperative, there is great evidence from widely deployed systems suggesting the opposite. To date, many schemes have been proposed to alleviate this problem. However, the majority of these schemes are either too complex to use in practice, or do not provide strong enough incentives for cooperation. In this work we propose a scheme based on the general idea that o?ering uploads brings revenue to a node, and performing downloads has a cost. We also introduce a theoretical model that predicts the performance of the system and computes the values of the scheme’s parameters that achieve a desired performance. Our scheme is quite simple and very easy to implement. At the same time, it provides very strong incentives for cooperation and improves the performance of P2P networks signi?cantly. In particular, theory and realistic simulations show that it reduces the query response times and ?le download delays by one order of magnitude, and doubles the system’s throughput. Keywords: P2P networks, user cooperation, theoretical analysis, realistic simulations.
Peer-to-peer (P2P) systems provide a powerful infrastructure for large-scale distributed applications, such as ?le sharing. While cooperation among the system’s participants is a key element to achieve good performance, there has been growing evidence from widely deployed systems that peers are usually not cooperative. For example, a well known study of the Gnutella ?le sharing system in 2000 reveals that almost 70% of all peers only consume resources (download ?les), without providing any ?les to the system at all . This phenomenon is called “free-riding”. Despite the fact that this phenomenon was identi?ed several years ago, recent studies of P2P systems show that the percentage of free-riders has signi?cantly increased . This is not because industry and academia have ignored the problem. There is a large body of work on incentive mechanisms for P2P networks, varying from centralized and decentralized credit-based mechanisms, e.g. [3–6], to game-theoretic approaches and utility-based schemes, e.g. [7, 8], to schemes that attempt to identify and/or penalize free-riders, e.g. [9–11], the last two being proposed by the popular KaZaA and eMule systems. The problem of free-riders is hard to tackle because the solution has to satisfy con?icting requirements: minimal overhead, ease of use, and at the same time good amount of fairness and resilience to hacking.
In this paper we propose and study the performance of an e?cient algorithm that is very easy to use, it enforces users to be fair, and it can be implemented in a number of ways that tradeo? overhead and resilience to malicious users. According to the algorithm, users use tokens as a means to trade bytes within the system. A user earns Kup tokens for each byte he/she uploads to the system and spends Kdown tokens for each byte he/she downloads from the system. The user also gains Kon tokens for each second his/her machine is on the system (i.e. it is online). A user can initiate a download only if the number of tokens that he/she has is large enough to download the complete ?le. The proposed algorithm relies on the general idea that users should be awarded for o?ering uploads and staying online, and pay for performing downloads. While others have proposed solutions that use the same general idea in the past, e.g. [6, 8], there are a number of questions that either have not been addressed at all or have been studied via simulations only: (i) How should one tune the parameters that dictate the gain from uploads and the cost of downloads? Speci?cally to our scheme, what is the right value for the parameters Kon , Kup , Kdown ? (ii) What is the exact e?ect of such an algorithm on overall system performance over a wide range of conditions? (iii) Would a small number of malicious users, that manage to subvert the scheme, degrade overall performance noticeably? (iv) Is it possible to trade o? one performance metric for another by varying the parameters of the algorithm, e.g. trade o? download delay for total system capacity? Our theoretical analysis of the performance of the resulting system, coupled with extensive realistic simulations, gives concrete answers to all these questions. Interestingly enough, it shows that the query response times and ?le download delays can be reduced by one order of magnitude while being able to sustain higher user download demands. An important aspect of any solution to the free-riding problem is if the information about the users’ behavior is determined and maintained locally and without any interaction with the other peers of the system (localized solutions), or it is determined and maintained by either a centralized authority (non-localized centralized solutions), or by the continuous exchange of information among the system’s participants (non-localized distributed solutions). Localized solutions are simple and impose very little overhead but they are easy to subvert. Non-localized solutions are hard to subvert but are complex to use in practice. (KaZaA, eMule, and BitTorrent all use localized approaches.) In any case, our proposed scheme can be easily implemented in any way, and we describe later in the paper how to implement it e?ciently with each one of the approaches. The rest of the paper is organized as follows: In Section 2 we brie?y discuss prior work on providing incentives for P2P systems. In Section 3 we provide a detailed description of the proposed scheme. In Section 4 we provide a mathematical model that predicts the performance of the system and gives guidelines on how to set the scheme’s parameters. In Section 5 we present realistic experiments of P2P systems on top of TCP networks. In Section 6 we brie?y discuss some implementation thoughts and ?nally conclude in Section 7.
There has been a large body of work on incentive mechanisms for P2P networks. Three of the most popular localized schemes are the ones implemented by the eMule , the KaZaA , and the BitTorrent  systems. eMule rewards users that provide ?les to the system by reducing their waiting time when they upload ?les using a scoring function (called QueueRank ). Similarly, in KaZaA, each peer computes locally its Participation
Level as a function of download and upload volumes, and peers with high participation levels have higher priority . A disadvantage of both of these schemes is that they provide relatively weak incentives for cooperation since peers that have not contributed to the system at all can still bene?t from it, if they are patient enough to wait in the upload queues. Other problems include that they favor users with high access bandwidth, which may result in frustration or a feeling of unfairness , and that they are vulnerable to the creation and distribution of hacked daemons that do not conform to the desired behavior . BitTorrent uses a di?erent scheme that is speci?c to its architecture. Each peer periodically stops o?ering uploads to its neighbors that haven’t been o?ering uploads to him/her recently. This scheme is hard to subvert. However, it su?ers from some unfairness issues and it only works with “BitTorrent-style” systems, that is, in systems where ?les are broken into pieces, and downloading a ?le involves being connected to almost all of ones neighbors in order to collect and reassemble all the pieces of the ?le. Non-localized proposals are primarily concerned with creating systems that cannot be subverted. Some of them make use of credit/cash-based systems. They achieve protection from hackers by either using central trusted servers to issue payments (centralized approach), e.g. [3, 4], or by distributing the responsibility of transactions to a large number of peers (distributed approach), e.g. . Other distributed approaches use lighterweight exchanged-based mechanisms, e.g. , or reputation management schemes, e.g. . These mechanisms are indeed hard to subvert but they are also quite complex to use in practice . In this paper we decouple the issue of how to design an algorithm to prevent free-riding from the issue of how to implement this algorithm in a P2P system. We ?rst propose an e?cient scheme that provides very strong incentives for cooperation. We show this via both theory and simulations. Then, we show that the scheme is generally applicable to any P2P system and comment on how to implement it using either a localized, or a non-localized approach. Another important contribution is the theoretical analysis of the performance of a P2P system with and without the proposed scheme. The analysis yields a set of equations that are used to predict the system’s performance under a wide range of conditions, and to tune the parameters of the scheme.
A Simple and E?ective Algorithm
As mentioned earlier, the algorithm uses tokens as a means to trade bytes within the system. Each user is given an initial number of tokens M when he/she ?rst joins the network. This allows new users to start downloading a small number of ?les as soon as they join the system. When a user rejoins the system he/she uses the amount of tokens he/she previously had. Users spend Kdown tokens for each byte they download from the system and earn Kup tokens for each byte they upload to the system. This forces users to o?er ?les for upload proportionally to the number of ?les they want to download. Further, users gain Kon tokens/sec while being online. This mechanism of accumulating tokens serves two purposes. First, it allows users who are not contacted frequently for uploads to gain tokens by just being online, which is more fair towards users with low access bandwidth . Second, it provides an incentive for users to keep their machines on the system even when they are not downloading a ?le, which helps to prevent the so-called problem of “low availability” . Note that the value of Kon should be relatively small, in order to prevent users from gaining many tokens by just keeping their machines on without
providing any uploads. Finally, a user can initiate a download only if the number of tokens he/she currently possesses is greater or equal to the number of tokens required to download the requested ?le. This scheme provides strong incentives for cooperation. Free-riders are “forced” to provide some uploads to the system in order to gain tokens fast enough to sustain their desirable download demands. Some free-riders may decide to share their ?les as soon as they are out of tokens. Others may adopt a more dynamic behavior and decide to adjust the number of uploads they provide to the system as a function of the number of tokens they currently have. In any case, the change in the free-rider’s behavior increases the amount of available system resources tremendously, which, in turn, signi?cantly improves the system’s performance, as we shall see in Section 5.
A Mathematical Model For The Proposed Scheme
In this section we derive a mathematical model that predicts the system’s performance and can be used to tune the parameters of the scheme. Predicting the performance of the system from the model is bene?cial because the alternative is P2P simulations/experiments, and those either involve a signi?cantly smaller number of peers than in reality, or are prohibitively expensive. Tuning the parameters of the scheme is important because an arbitrary setting of their parameters may lead to several undesired situations. For example, giving a large value to Kon may provide tokens to the free-riders fast enough, so that there won’t be any reason for them to start sharing their ?les with the system. As another example, giving relatively small values to both Kon and Kup may reduce the token accumulation rate of cooperative users so much such that they can’t sustain their download demands. 4.1 System Dynamics
We assume a system that implements the proposed scheme which we call “system with the tokens”. Recall that Kdown and Kup are expressed in tokens/byte and Kon in tokens/sec. Now, let Cdown and Cup denote the ?le download and upload speeds of a user (access line bandwidth), both expressed in bytes/sec. The user spends KdownCdown dt tokens if he/she is downloading ?les from other peers during time (t, t + dt). Also, he/she earns Kon dt tokens if he/she is online during time (t, t + dt) and Kup Cup dt tokens if other users are uploading ?les from the user under study during time (t, t + dt). Let T (t) denote the number of the user’s tokens at time t, with T (0) ≥ 0. We can then write the following di?erential equation: dT (t) = Kon Ion (t) + Kup Cup Iup (t) ? KdownCdown Idown (t), dt where Ion (t) = Iup (t) = Idown (t) = 1 0 1 0 if the user is online in (t, t+dt) , otherwise (1)
1 if the user provides uploads in (t, t+dt) , 0 otherwise if the user performs downloads in (t, t+dt) . otherwise
Taking expectations on both sides of Equation (1), and interchanging the expectation with the derivative on the left hand side1 , we get: dE[T (t)] = Kon Pon (t) + Kup Cup Pup (t) ? Kdown Cdown Pdown (t), dt (2)
where Pon (t) is the probability the user is online at time t, Pup (t) is the probability that the user provides uploads to the system at time t, and Pdown (t) is the probability that the user performs downloads from the system at time t. Note that Equation (2) can be regarded as a ?uid model describing the token dynamics. Pon (t), Pup (t), and Pdown (t) depend on how the user behaves given the number of tokens that he/she has at some point in time, and on his/her download demands. Along these lines, one can de?ne user pro?les and solve the di?erential equation. Due to limitations of space we will not proceed with this task here. (The interested reader is referred to ). Instead, we will only study the steady state by setting dE[T (t)] = 0, and dropping dt the time dependence from the probabilities in Equation (2). Note that the existence of a steady state can be easily justi?ed for a free-rider, by taking into consideration that in the long-run he/she will spend as many tokens as he/she gains. 2 Without loss of generality assume Pon = 1. 3 Let Rup be the long-run average rate of ?le upload requests per second that the user handles, which we refer to as the upload rate. Also, let Rdown be the long-run average rate of ?le download requests per second that the user initiates, which we refer to as the download rate. Last, let S denote the Rup S average ?le size in the system in bytes. Then, it is easy to see that Pup = Cup and Pdown =
Rdown S 4 Cdown .
Equation (2) in steady state yields: Kon + Kup Rup S ? Kdown Rdown S = 0.
Taking the average over all free-riders yields: Kup = Kdown E[Rdown |FR] E[Rup |FR] ? Kon . E[Rup |FR]S (3)
Equation (3) relates the parameters of the scheme, Kon , Kup , and Kdown , with the average download and upload activity of free-riders. We will later use it to select the parameter values that yield a target performance. But ?rst, we need to compute the average download and upload rates, which is the next topic. 4.2 User Download Rate (Rdown )
Let N be the number of peers in the system and let a proportion α of them be free-riders. Assume that free-riders are uniformly distributed over the system. Also, assume that both cooperative users and free-riders have the same download demands. In particular, they
Taking into account that T (t) is bounded in practice, we can use the bounded convergence theorem  to justify the interchange. Considering the existence of a steady state for a non-freerider is a bit more involved. As we will shortly see he/she may or may not have a steady state. Nevertheless, this will not be important for the system dynamics. A similar analysis holds for Pon < 1. Assuming a stable system, the exact values of Cup and Cdown are not important for our analysis.
have the same query request rate, denoted by Rq queries/sec, and the same preference over ?les, that is, each query is for ?le i with some probability Qf (i) irrespectively of the query issuer. Finally, assume that free-riders respond to a query only if the amount of tokens they currently have is less than the amount required to download the ?le they currently desire. (Recall that cooperative users always respond to query requests.) Let Pans (i) be the probability that a query request for ?le i is successfully answered. Now, recall that in the system with the tokens a user can initiate a download only if the amount of tokens he/she has is larger than the amount required to download the ?le. Let FR NF Ptkn and Ptkn denote respectively the probability that a free-rider and a non-freerider have enough tokens to initiate a download. Then, we can express the average download rate of free-riders and non-freeriders as follows: E[Rdown |FR] =
i FR Rq · Qf (i) · Pans (i) · Ptkn ,
E[Rdown |NF] =
NF Rq · Qf (i) · Pans (i) · Ptkn ,
where the summation is taken over all ?les i. Clearly, the average download rate over all users in the system is: E[Rdown ] = E[Rdown |FR] · α + E[Rdown |NF] · (1 ? α). (6)
To complete the calculation of the download rates, note that Rq , Qf (i), and α are given quantities. (There exist a large body of work in measurement studies of P2P systems, e.g. [20, 21], from which one can deduce typical values for these quantities.) Hence, NF FR what remains is to compute Pans , Ptkn , and Ptkn . We start by deriving a relation beNF FR tween Ptkn and Ptkn . First, note that in steady state the token earning rate equals the token spending rate for each free-rider. A free-rider responds to a query request only FR when he/she doesn’t have enough tokens, i.e. with probability 1 ? Ptkn . Since a nonfreerider always responds to a query request, it is easy to see that the token earning FR rate of free-riders over that of non-freeriders equals 1 ? Ptkn . Now, the token spending rate is proportional to the download rate, and Equations (4) and (5) imply that the token spending rate of free-riders over that of non-freeriders equals P tkn . Assuming that NF tkn non-freeriders are also in steady state (in which case Equation (3) also holds if the average is taken with respect to non-freeriders only), we can equate the two ratios and
NF write Ptkn = FR Ptkn = initiate token earning rate of non-freeriders will be larger than their token spending rate, which implies that their amount of tokens will continuously increase. However, this still suggests NF that Ptkn = 1. We can now write: NF Ptkn = min 1, FR Ptkn FR 1 ? Ptkn
FR Ptkn FR F R . Clearly, this equality is valid for Ptkn ≤ 0.5. In particular when 1?Ptkn NF 0.5, Ptkn = 1, which implies that non-freeriders always have enough tokens to FR downloads. For Ptkn > 0.5, the last equality no longer holds. In this case the
Now, lets ?nd a relation for Pans (i). First, assume that due to congestion at the overlay layer , each message (either a query request or a query response) has a probability p of being dropped at some peer. 5 Then, if L is the average number of overlay hops until a
This assumption is introduced to make the model more general. A well designed system usually has p ≈ 0, which is accomplished by setting the bu?er size of the TCP socket su?ciently large.
query is answered, Pdrop = 1 ? (1 ? p)L is the probability that the query response is lost. Next, observe that if K ≤ N is the average number of peers that a query request can FR reach, then the request can be answered by an average of K · ((1 ? Ptkn ) · α + 1 · (1 ? α)) peers. Finally, let Pf (i) be the probability that a peer has ?le i. We can then write: Pans (i) = 1 ? (1 ? Pf (i) · (1 ? Pdrop ))K·((1?Ptkn )·α+1?α) . 4.3 User Upload Rate (Rup )
The total number of downloads equals the total number of uploads, and thus the expected download and upload rates over all nodes are also equal. This does not mean that all peers provide uploads. For example, in a system that does not implement the proposed scheme E[Rdown ] = E[Rup ] but we know that only non-freeriders provide uploads, i.e. E[Rup |FR] = 0, and hence E[Rup |NF] = E[Rdown ] . On the other hand, in the system (1?α) FR with the tokens each free-rider answers to a query request with probability 1 ? Ptkn . As FR a result, this system behaves as if there are N · ((1 ? α) + α · (1 ? Ptkn )) non-freeriders. It is easy to see that the expected upload rate of each non-freerider is now given by: E[Rup |NF] = E[Rdown ] . FR (1 ? α) + α · (1 ? Ptkn ) (9)
And, since E[Rup ] = E[Rdown ], the expected upload rate of each free-rider equals: E[Rup |FR] =
FR (1 ? Ptkn ) · E[Rdown ] . FR (1 ? α) + α · (1 ? Ptkn )
Choosing the right values for Kon , Kup , and Kdown
FR We use Ptkn as the design parameter of our system since it dictates how often free-riders o?er uploads, which, in turn, speci?es the average amount of available resources in the system. We are given the query- and ?le-popularity probability functions Qf (i), Pf (i), the query request rate Rq , and information about the overlay network. (For example, information about the overlay network includes the percentile of free-riders α, the socket bu?er sizes that dictate the drop probability p, and the structure of the overlay graph as well as the search algorithm that dictate the number of peers that a query reaches K and the average path length between a query issuer and a query responder L.) We want FR to ?nd a set of values for Kon , Kup and Kdown that will satisfy a target Ptkn , and, in turn, a target performance. First, observe from Equation (3) that it is the relative values of Kon , Kup , and Kdown that are important for the proper operation of the system. Recall also that Kon should be su?ciently smaller than the token spending rate of free-riders. This is to prevent them from accumulating enough tokens by just staying online without o?ering any uploads. Thus, we should have Kon ? KdownE[Rdown |FR]S. With the above observations in mind we proceed as follows in order to satisfy the FR target Ptkn :
(i) Fix Kdown to some arbitrary value, NF (ii) use Equation (7) to compute Ptkn , (To guarantee that cooperative users will not be NF penalized, Ptkn should be close to 1.)
(iii) use Equations (4) and (8) to compute the value of E[Rdown |FR], and Equations (10), (6) and (5) to compute E[Rup |FR], (iv) assign a value to Kon which is one order of magnitude smaller than KdownE[Rdown |FR]S, (The speci?c value turns out not to a?ect the performance sizeably.) and (v) use Equation (3) to ?nd the right value for Kup . Conversely, if we are given the values of Kon , Kup , and Kdown we can use our equations to predict quantities like E[Rdown |FR], E[Rdown |NF], E[Rup |FR] and so on. 6 In the next Section we verify the accuracy of our analysis via experiments on top of TCP networks, and show the impact of the proposed scheme on system’s performance.
For our experiments we use GnutellaSim , a packet-level peer-to-peer simulator build on top of ns-2 , which runs as a Gnutella system. We implement the ?le downloading operation using the HTTP utilities of ns-2. We use a 100-node transit-stub network topology as the backbone, generated with GT-ITM . We attach a leaf node to each stub node. Each leaf node represents a peer. The propagation delays assigned to the links of the topology are proportional to their length and are in the order of ms. We assign capacities to the network such that the congestion levels are moderate. The capacity assigned to a peer’s access link is 1.5Mbps. In order to test the algorithm on a general gnutella-like unstructured P2P network we use Gnutella v0.4, which uses pure ?ooding as the search algorithm and does not distinguish between peers. The T T L for a query request message is set to 7 (the default value used in Gnutella). All peers join the system initially and never go o?ine. For simulation purposes we implement the following user behavior: each user initiates query requests at the constant rate of 1 query every 20sec. Once a timeout for a query request occurs, the corresponding query is retransmitted. The maximum number of retransmissions is set to 5, and the timeout to 60sec. There are 1000 distinct ?les in the system, i = 1...1000. A query request is for ?le i with probability proportional to 1 (Zipf distribution). The number of replicas of a certain i ?le is also described by a Zipf distribution with a scaling parameter equal to 1, and the replicas of a certain ?le are uniformly distributed among all peers. These settings are in accordance with measurement studies from real P2P networks [20, 21]. We distinguish two systems: (i) the original system which does not implement the proposed algorithm, and (ii) the system with the tokens. In both systems, 85% of peers are free-riders in accordance to the percentage reported in . Finally, the ?le size is set to 1MB. 5.2 Simulation Results
FR Download and Upload Rates For various values of the design parameter Ptkn we compute the corresponding values of Kon , Kup and Kdown according to the procedure described in the previous Section. We then assign these values to all users of the system
Note that we can also use Equations (4)...(10) to compute upload/download rates in a system FR that does not implement the scheme, by setting Ptkn = 1.
and compare the theoretical download and upload rates with the experimental results. Figures 1(i) and 1(ii) show respectively the expected download and upload rate over all non-freeriders, over all free-riders, and over all users of the system, as a function FR of Ptkn . The horizontal line in Figure 1(i) represents the expected download rate of a
FR =0.32 tkn
45 Download Rate (Downloads / 1000 sec) 40 35 30 25 20 15 10 5 0 0
FR =0.55 tkn
E[R |NF] (Theoretical)
Upload Rate (Uploads / 1000 sec)
E[R |NF] (Simulation) E[Rup|FR (Theoretical) E[Rup|FR] (Simulation) E[R ] (System with tokens-Theoretical)
up up up
FR =0.45 tkn
E[R ] (System with Tokens-Simulation) E[R ] (Original System) PFR=0.32
E[Rdown|NF] (Theoretical) E[Rdown|NF] (Simulation) E[R
E[Rdown|FR] (Simulation) E[Rdown] (System with Tokens-Theoretical) E[R E[R
] (System with Tokens-Simulation) ] (Original System)
40 Ptkn (%)
Fig. 1. (i) User’s expected download rate, and (ii) user’s expected upload rate.
user in the original system. (Clearly, in the original system E[Rdown ] = E[Rdown |F R] = E[Rdown |N F ].) The horizontal line in Figure 1(ii) represents the expected upload rate of a non-freerider in the original system. (Recall that in this system E[Rup |F R] = 0.) It is clear from the plots that analytical and simulation results match. Further, we can FR make several interesting observations. First, notice that as Ptkn increases, the download rate for both classes of users ?rst increases and then starts decreasing until it reaches the value of the original system. Second, observe that while the upload rate of free-riders behaves in a similar manner, the upload rate of non-freeriders continuously increases until it reaches its original value. Based on these observations we divide the plots into FR three regions. The ?rst region corresponds to Ptkn < 0.32. In this region, both classes of peers are constrained to a lower download rate compared to the original system, since the probability of having tokens to initiate a new download after a successful query is FR NF pretty low. Notice that for Ptkn = 0.32, and hence for Ptkn = 0.47 < 1, cooperative users can at least sustain the same download rate they had in the original system. The second FR region corresponds to 0.32 ≤ Ptkn ≤ 0.55. In this region, users accumulate tokens at a higher rate than before. Since there are more responses than in the original network, users can use the extra tokens to initiate more downloads. Notice that cooperative users earn FR tokens faster than free-riders since they always respond to query requests. At Ptkn = 0.55, non-freeriders achieve their maximum download rate, which is approximately twice the one they had in the original system. Finally, the third region corresponds to 0.55 < FR Ptkn ≤ 1. In this region free-riders accumulate tokens faster than before and reduce their query response rate since they do not need to provide as many uploads as before. This causes cooperative users to handle more uploads. Futher, since the query response rate FR regulates the download rate, the latter also decreases. At Ptkn = 1, the two systems have approximately the same performance, as expected.
Impact On Delays Figures 2(i) and 2(ii) show respectively the average query response time (that includes retransmissions) and the average download delay as a function of FR FR Ptkn . The plots can be divided in the same three regions as before. For Ptkn < 0.32, the low user download rate imposes a low load into the network. This yields the low delays. FR For 0.32 ≤ Ptkn ≤ 0.55, as the user download rate increases, the load in the network and hence the delays also increase. Note that the query and download delays are still signi?cantly smaller than in the original system, despite that the download rate, and hence the load, is higher. This is because a signi?cant portion of the load is now handled FR by the free-riders. For 0.55 < Ptkn ≤ 1 the delays continue to increase even though the download rate decreases. This is because free-riders provide fewer and fewer uploads. As FR Ptkn approaches 1, the performance of the two systems is approximately the same. To
Average Query Response Time (Seconds)
Averaged File Download Delay (Seconds)
System with Tokens Original System Ptkn=0.32 Ptkn=0.55
System with Tokens Original System
40 60 FR Ptkn (%)
40 60 FR Ptkn (%)
Fig. 2. (i) Average query response time, and (ii) average ?le download delay.
fairly compare the delays between the two systems, we should consider the case where the load is the same, i.e. where E[Rdown ] = 22 downloads/1000sec. This value corresponds FR to Ptkn = 0.45, and as we can see from the plots this corresponds to approximately one order of magnitude lower query and ?le download delays. This is a gigantic amount of improvement on the system’s performance. FR As a ?nal note, the best operating region is the second, where 0.32 ≤ Ptkn ≤ 0.55. In FR this region, we can either choose to operate the system at Ptkn = 0.32, where cooperative users can sustain the same download demands as in the original system, or sacri?ce a bit from the performance improvement with respect to reduced delays to support higher user demands.
Implementing the scheme
As mentioned before, this scheme can be implemented either locally or non-locally. Implementing this scheme locally is quite simple. The local P2P client takes care of bookkeeping by increasing the user’s tokens for each acknowledged byte he/she uploads and for being online, and by decreasing the tokens for each byte the user downloads. However as we have already mentioned, this approach is quite vulnerable to hacked clients.
There are several directions for making the hacking of localized solutions hard. One can utilize encryption techniques e.g.  that make unauthorized modi?cations to data (such as the scheme’s parameters) hard. In addition, one can also use technologies like DRM (Digital Rights Management) in order to protect the entire client’s code from being altered e.g. , and re-distribute new clients frequently in order to minimize the number of hacked clients that can be connected to the network. Further, one could also employ techniques such as tamper-proo?ng and self-checking in order to verify the client’s code integrity during the join process and/or on every download request e.g. [28–31]. Of course, the only way to guarantee that all P2P clients are original is to have a trusted platform where both the hardware and the operating system can be trusted . This is clearly not an option in practice. However, interestingly enough, both theory and simulations dictate that our scheme is quite resilient to a small number of hacked clients. In particular, the system performance is virtually unchanged when the hackers comprise less than 10% . Hence, all one needs to do is to make it hard for users to use hacked clients. The scheme can be also implemented in a secure non-localized centralized manner, where peers exchange messages with a centralized trusted authority that updates and maintains their amount of tokens. Peers would communicate with the centralized authority once they ?nish downloading to report the source node and the ?le size, periodically while being online, and to get permission to initiate a new download. This is similar to the main idea that many centralized “cash-based” systems, e.g [3, 4], follow. Finally, the scheme can be also implemented in a secure non-localized decentralized manner, e.g. by utilizing the framework suggested in .
In this paper we studied a simple algorithm that provides strong incentives for cooperation in ?le sharing P2P networks. We derived a mathematical model that describes the system’s dynamics and which can be used for parameter tuning and performance prediction. We demonstrated the e?ectiveness of the algorithm via experiments with TCP networks. Future work consists of performing larger scale experiments, implementing the scheme in an operational P2P network, and extending our analytical methodology to compute other important performance metrics, e.g. the improvement on the expected download delays and response times.
1. E. Adar and B. Huberman, “Free riding on gnutella,” http://www.firstmonday.dk/ issues/issue5 10/adar, October 2000 (accessed Aug. 2005). 2. D. Hughes, G. Coulson, and J. Walkerdine, “Free riding on gnutella revisited: the Bell Tolls?,” IEEE Distributed Systems Online Journal, vol. 6, no. 6, June 2005. 3. “Mojonnation,” http://www.mojonation.net/Mojonation.html (accessed Aug. 2005). 4. J. Ioannidis, S. Ioannidis, A. Keromytis, and V. Prevelakis, “Fileteller. paying and getting paid for ?le storage,” in Proc. of 6th International Conference on Financial Cryptography, March 2002. 5. S. D. Kamvar, M. T. Schlosser, and H. Garcia-Molina, “EigenRep: Reputation management in P2P networks,” in Proc. of 12th International World Wide Web Conference (WWW 2003), May 2003. 6. V. Vishnumurthy, S. Chandrakumar, and E. G. Sirer, “KARMA: A secure economic framework for P2P resource sharing,” in 1st Workshop on Economics of Peer-to-Peer Systems, June 2003.
7. C. Buragohain, D. Agrawal, and S. Suri, “A game-theoretic framework for incentives in P2P systems,” in Proc. of International Conference on Peer-to-Peer Computing, Sep 2003. 8. L. Ramaswanmy and L. Liu, “Free-riding: A new challenge to peer-to-peer ?le sharing systems,” in Proc. of the 36th Hawaii international conference on system sciences, 2003. 9. M. Feldman, C. Papadimitriou, I. Stoica, and J. Chuang., “Free-riding and whitewashing in Peer-toPeer systems,” in SIGCOMM Workshop, 2004. 10. “KaZaA participation level,” http://www.kazaa.com/us/help/glossary/participation ratio.htm (accessed Aug. 2005). 11. “The emule project,” http://www.emule-project.net/ (accessed Aug. 2005). 12. “KaZaA media desktop,” http://www.kazaa.com/ (accessed Aug. 2005). 13. “Bittorrent,” http://www.bittorrent.com/protocol.html (accessed Aug. 2005). 14. H. Bretzke and J. Vassileva, “Motivating cooperation in peer to peer networks,” in Proc. of User Modeling UM03, June 2003. 15. “Hack KaZaA participation level,” http://www.davesplanet.net/kazaa/ (accessed Aug. 2005). 16. K. Anagnostakis and M. Greenwald, “Exchanged-based incentive mechanisms for peerto-peer ?le sharing,” in Proc. of 24th International Conference on Distributed Computing Systems, 2004. 17. R. Bhagwan, S. Savage, and G. M. Voelker, “Understanding availability,” in Proc. of 2nd IPTPS, 2003. 18. R. Durrett, Probability: Theory and Examples, Duxbury Press, 2nd edition, 1996. 19. W.-C. Liao, F. Papadopoulos, and K. Psounis, “An e?cient algorithm for resource sharing in peer-to-peer networks,” Tech. Rep. CENG-2005-15, University of Southern California, 2005. 20. S. Saroiu, K. P. Gummadi, R. J. Dunn, S.D. Gribble, and H. M. Levy, “An analysis of internet content delivery systems,” in Proc. of the Fifth Symposium on Operating System Design and Implementation (OSDI), December 2002. 21. J. Chu, K. Labonte, and B. N. Levine, “Availability and locality measurements of peer-topeer ?le sharing systems,” in Proc. of SPIEITCom: Scalability and Tra?c Control in IP Networks, July 2002. 22. Mostafa Amar Qi He, “Congestion control and massage loss in gnutella networks,” in Proc. of Multimedia Computing and Networking, 2004. 23. “Packet-level Peer-to-Peer Simulation Framework and GnutellaSim,” http://www.cc. gatech.edu/computing/compass/gnutella/ (accessed Oct. 2005). 24. “Network simulator,” http://www.isi.edu/nsnam/ns (accessed Sep. 2005). 25. K. Calvert, M. Doar, and E. W. Zegura, “Modeling internet topology,” IEEE Communications Magazine, 1997. 26. “Data encryption standard,” http://www.itl.nist.gov/fipspubs/fip46-2.htm (accessed Oct. 2005). 27. T. Sander, Security and Privacy in Digital Rights Management, Springer, 1st Edition, 2002. 28. D. Aucsmith, “Tamper resistant software: An implementation,” in Proc. 1st International Information Hiding Workshop, May 1996. 29. H. Chang and M. Atallah, “Protecting software code by guards,” in Proc. of 1st ACM Workshop on Digital Rights Management, May 2002. 30. Y. Chen, R. Venkatesan, M. Cary, R. Pang, S. Sinha, and M. Jakubowski, “Oblivious hashing: A stealthy software integrity veri?cation primitive,” in Proc. of 5th International Information Hiding Workshop, October 2002. 31. C.S. Collberg and C. Thomborson, “Watermarking, tamper-proo?ng, and obfuscation tools for software protection,” IEEE Transactions on Software Engineering, vol. 28, no. 6, June 2002. 32. S. W. Smith, Trusted Computing Platforms: Design and Applications, Springer, 1st Edition, 2004.