Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Stpc : a robust incentive mechanism for improving DHT-based peer-to-peer systems Huang, Gary 2007

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-ubc_2007-0120a.pdf [ 1.85MB ]
Metadata
JSON: 831-1.0051991.json
JSON-LD: 831-1.0051991-ld.json
RDF/XML (Pretty): 831-1.0051991-rdf.xml
RDF/JSON: 831-1.0051991-rdf.json
Turtle: 831-1.0051991-turtle.txt
N-Triples: 831-1.0051991-rdf-ntriples.txt
Original Record: 831-1.0051991-source.json
Full Text
831-1.0051991-fulltext.txt
Citation
831-1.0051991.ris

Full Text

STPC: A Robust Incentive Mechanism for Improving DHT-based Peer-to-Peer Systems Gary Huang B.Math, The University of Waterloo, 2003 A THESIS S U B M I T T E D IN P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E OF Master of Science in T H E F A C U L T Y OF G R A D U A T E STUDIES (Computer Science) The University of British Columbia February 2007 @ Gary Huang, 2007 Abstract The Distributed Hash Table-based (DHT-based) Peer-to-Peer (P2P) system is a large-scale, distributed structured system with a very promising routing algorithm to efficiently retrieve information. The academic community has paid great attention to DHT-based P2P systems. However, since peers are self-behaved in these systems, they can frequently join or leave the systems as they want. Therefore, these dynamic systems have high overhead to maintain the D H T topology. Also, any P2P systems encounter free-riding - peers try to maximize their own utility and provide as little service to other peers as possible. Free-riding decreases the usability of system utilities and restricts the development of P2P systems. We investigate the following two factors that may be able to improve these systems: (1) the longer session time peers provide in the system, the more stable the system tends to be with lower maintenance overhead; (2) the more the peers contribute, the more resources they can share in the system. We propose an incentive mechanism that applies the two factors in an incentive value, which determines peer payoff such as service priority and resource distribution. Applying this incentive mechanism, peers are encouraged to provide more session time and make a larger peer contribution. Our experiment results show that our incentive mechanism effectively reduces system maintenance overhead and dramatically controls free-riding in DHT-based P2P systems. i i Contents Abstract 1 1 Contents m List of Tables vi List of Figures •• v n Acknowledgements vii i Chapter 1 Introduction 1 1.1 Motivation 1 1.2 Thesis Contributions • 3 1.3 Thesis Organization 5 Chapter 2 Background and Related Work 6 2.1 Background 6 2.1.1 P2P Systems 7 2.1.2 Chord Systems 8 2.1.3 Incentive Mechanisms 10 2.2 Related Work 11 2.2.1 Payment-based Mechanisms 11 2.2.2 Reputation-based Mechanisms 13 2.2.3 Contribution-based Mechanisms 13 2.2.4 Other Mechanisms 14 i i i Chapter 3 Incentive Mechanism Design • 15 3.1 Incentive Factors 15 3.1.1 Session Time • 16 3.1.2 Peer Contribution • • • • 17 3.2 Incentive Value 18 3.2.1 Definitions of Incentive Variables 19 3.2.2 Expressions of Incentive Variables 19 3.3 Peer Payoff 20 3.3.1 Service Priority 21 3.3.2 Resource Distribution 22 3.4 Mechanism Expectations 23 Chapter 4 Incentive System Architecture 25 4.1 Incentive Service Component 25 4.1.1 STPC Model 26 4.1.2 SPRD Model 27 4.2 System Architecture 28 Chapter 5 ISC Implementation 30 5.1 STPC Model Implementation 30 5.1.1 Analysis of STPC Model Implementation 31 5.1.2 STPC Model Algorithms 32 5.2 SPRD Model Implementation : 34 5.2.1 Analysis of SPRD Model Implementation 34 iv 5.2.2 SPRD Model Algorithms 35 Chapter 6 Simulation and Evaluation 38 6.1 Simulation Setup 38 6.2 Maintenance Overhead Level 40 6.3 Resource Usability Ratio 42 6.4 a and (3 Analysis • • • • • 44 Chapter 7 Conclusions 47 7.1 Summary 47 7.2 Future Work 49 Bibliography 51 v List of Tables Table 3-1 Incentive Variables 19 Table 3-2 Incentive Expressions 20 vi List of Figures Figure 2-1 Classifications of P2P Systems 7 Figure 2-2 Chord Ring and Finger Table , 9 Figure 3-1 The PDF Curve of Session Distribution 16 Figure 3-2 Resource Distribution by Incentive Values 22 Figure 4-1 STPC Model 26 Figure 4-2 SPRD Model 27 Figure 4-3 Incentive System Architecture 28 Figure 5-1 The Function of STPC Courier 32 Figure 5-2 The Function of STPC Verifier 33 Figure 5-3 The Function of SP Service 36 Figure 5-4 The Function of R D Service 37 Figure 6-1 Maintenance Overhead Level (MOL) 41 Figure 6-2 Resource Usability Ratio (RUR) 43 Figure 6-3 M O L s with Different a and P 44 Figure 6-4 RURs with Different a and P 45 vi i Acknowledgements I would like to thank my supervisor, Dr. Son Vuong, for his wonderful guidance and great encouragement. M y current achievement would have been impossible without his inspiration and support. I thank Dr. Charles Krasic for his helpful guidance and useful feedback that helped me improve my thesis. I also thank all NIC lab members, especially Juan L i , Jun Wang, X i n L iu , Peiqun Y u , and Mohammed Alam for their useful discussions and comments. Also, I thank Craig Wilson for proofreading my thesis. I gratefully acknowledge the financial support in the form of a teaching assistance ship from the Department of Computer Science in the University of British Columbia during my study. Finally, I would like to thank my family members for their consistent support, especially my wife, Ting Cheng for her love and understanding. Gary Huang The University of British Columbia February 2007 vi i i Chapter 1 Introduction In this chapter, we provide the motivation that DHT-based P2P systems can be improved with an incentive mechanism. Also, we briefly introduce the contributions of this thesis and its organization. 1.1 Motivation The DHT-based P2P system is based on a very promising topology model. The academic community has paid great attention to D H T systems such as Chord [11], Pastry [1], Tapestry [4], and C A N [25] for their efficient, scalable, and robust P2P infrastructures. The system is also the foundation of the new generation architecture of large-scale distributed applications in the IRIS project [12]. However, few systems based on the DHT-based P2P system have been successfully deployed in the Internet to this point, while systems such as Morpheus [19] and Limewire [16] etc., which are based on the Gnutella [9] protocol, have millions of Internet users. The reason D H T -based P2P systems have been less successful is that they have two main 1 shortcomings: (1) from the point of view of system topology, DHT-based P2P systems have a high maintenance overhead; (2) from the point of view of system utilization, DHT-based P2P systems, like other P2P systems, experience a high degree of free-riding. System Maintenance Overhead D H T systems implement global routing and location by means of each node keeping a partial routing table; therefore, these systems are very sensitive to the node's joining and leaving. Generally speaking, for a node to join or leave, it needs messages to maintain the right P2P network topology (Balakrishana et al. [3]). If the D H T systems are deployed in a dynamic environment where nodes continuously join or leave, the maintenance overhead becomes huge, seriously affecting the performance of the system (Ledlie, et al. [15]). D H T systems have to face such a dynamic environment, where each node is free to leave and join. The experimental results of Saroiu et al. [23] showed that almost 50% of nodes had a session time of less than 60 minutes, indicating that, in a real situation, the maintenance overhead is excessive and the performance of DHT-based P2P systems is greatly affected. If applying an incentive mechanism and using session time as an incentive factor to encourage peers to provide longer session time (for example, finish downloading resource once, that is, never try many times), then the system wil l have more stable nodes (i.e., the system eventually tends to be stable), and the overhead of maintaining it wil l be reduced. 2 Free-riding Free-riding means that nodes do not share their own resources and only wait for other nodes. In the report of Adar et al. [8], nearly 70% of users do not share any resources (e.g., files) in P2P systems. Roughly 50% of all resource-searching responses come from the top 1% of information-sharing nodes. As a result, some nodes will get overloaded and become the bottleneck for the whole system, decreasing the usability of the system utilities (e.g., resources). However, the usability of the system utilities will increase if applying an incentive mechanism and using peer contribution as an incentive value to encourage nodes to provide more contribution to other nodes. This thesis proposes an incentive mechanism combining two incentive factors, session time and peer contribution, in an incentive value. The mechanism encourages every node to increase its incentive value in order to get more bandwidth distribution from a resource-provider node. The goal of this thesis is to reduce the overhead of system maintenance is reduced and increase the usability of the system utilities, by applying an incentive mechanism by which nodes get payoff while providing longer session time and more peer contribution. 1.2 Thesis Contributions In this thesis, we make the following contributions: 3 • We propose a new incentive mechanism using an incentive value to determine the bandwidth distribution of resource-provider nodes. The incentive mechanism can reduce the overhead of maintaining DHT-based P2P systems and also effectively solve the free-riding problem. • Most existing incentive mechanisms use peer contribution as an incentive factor. Our incentive mechanism employs a new incentive factor, session time, and combines session time and peer contribution together in the mechanism. • We propose an Incentive Service Component (ISC) as the key component of an incentive DHT-based P2P system in achieving our goal. • We create a new incentive system architecture using ISC. The new system consists of four components: GUI and Logic of Resource Sharing Applications, ISC, DHT Service, and Network Communication Layer. • We introduce two models (the STPC Model and SPRD Model) that achieve the functionalities of ISC. The STPC Model consists of two sub-components, STPC Courier and STPC Verifier. The SPRD Model consists of two sub-components, SP Service and RD Service. . • We implement ISC and propose four algorithms, DeliverSTPC, VerifySTPC, SP_Service, and RD_Service for four sub-components respectively. 4 • We simulate and evaluate DHT-based P2P systems with the proposed incentive mechanism. We compare incentive P2P systems with non-incentive P2P systems with respect to Maintenance Overhead Level (MOL) and Resource Usability Ratio (RUR). • Also, we run experiments to determine optimal values for a and f3 in the formula of an incentive value. 1.3 Thesis Organization This thesis consists of seven chapters. The rest of the thesis is organized as follows. Chapter 2 provides a basic background to DHT-based P2P systems and incentive mechanisms. Chapter 3 introduces the design of our incentive mechanism and discusses why we chose session time and peer contribution as incentive factors, as well as how they improve the system. Chapter 4 introduces Incentive Service Component (ISC) in a new incentive system architecture, as well as the STPC Model and SPRD Model in ISC. Chapter 5 describes the implementation of ISC. Chapter 6 describes the simulation and evaluation of our incentive mechanism for improving DHT-based P2P systems. Chapter 7 concludes the thesis and discusses future research works. 5 r Chapter 2 Background and Related Work This chapter briefly introduces the background related to the P2P network system, D H T systems, and related work about incentive mechanisms. 2 . 1 B a c k g r o u n d In this section, we review P2P systems (especially DHT-based P2P systems) and P2P classifications from the point of view of system topology structures, since these are the systems we are trying to improve with our proposed incentive mechanism. It is a characteristic of the DHT-based P2P system structure that a new incentive mechanism is needed to make all peers cooperate to reduce the maintenance overhead for DHT-based system topology and control free-riding. Finally, we review incentive mechanisms previously introduced by researchers and show the reason why incentive mechanisms are needed. 6 2 . 1 . 1 P 2 P Systems The P2P network has been one of the most popular Internet research areas in recent years receiving extensive scrutiny from academic communities and commercial organizations. P2P technologies have transformed a traditional client/server (C/S) model into a distributed management model. A l l nodes in P2P systems can request and provide services simultaneously. There have been three generations of P2P networks classified into three models (see Figure 2-1). Each P2P model has its own merits and shortcomings. These models coexist today, and lessons can be drawn from each. (1) Centralized P2P System (2) Pure P2P System (3) Structured P2P System (Chord) Figure 2-1 Classifications of P2P Systems T h e first model (see (1) of Figure 2-1), the centralized P2P system (e.g., Napster [20], BitTorrent [5], etc.) is the earliest P2P model with the centralized feature, so it is also called an impure P2P model. The user's registration and file indices are stored in a 7 server. After retrieving file indices (i.e. file location), nodes directly communicate with each other with no server involvement. The model is very simple, but it needs a centralized-index server. The second model (see (2) of Figure 2-1), the pure P2P system (e.g., Gnutella [9], KaZaA [14], Freenet [10], J X T A [13], etc.) is also a broadcast P2P system, but it omits a central server. Content searching and file sharing are achieved by flooding broadcast among neighborhoods. The model consumes a large amount of bandwidth and easily causes network congestion. The third model (see (3) of Figure 2-1), the structured P2P system (e.g., Chord [11], C A N [25], Pastry [1], Tapestry [4], etc.) applies a pure distributed message passing mechanism, and finds content locations by searching keys. Most systems employing these models use D H T technology, which is one of the best P2P routing algorithms. 2 . 1 . 2 Chord Systems Since we used Chord P2P as the basic P2P model in our system simulation, we will provide a brief overview for Chord systems with its advantages. Chord is a decentralized and structured P2P network, which can perform efficient lookup of data items or the name of the service based on a distributed hash table (DHT). Each peer in Chord has been assigned m-bit identifier via hashing its IP address using S H A . Then, peers are ordered and organized in sequence on a ring of identifiers modulo 2™ , referred to as the Chord ring (see Figure 2-2). 8 Each peer in the Chord ring provides space to store data items, which are assigned identifiers called keys, in the same m-bit key space. Every peer is responsible for the data items with key value smaller than the value of the peer's identifier but bigger than the identifier of its predecessor peer in the Chord ring. N49, N33 N26 Finger table N 2 + 1 N8 N 2 + 2 N8 N 2 + 4 N8 N 2 + 8 N15 N 2 + 16 N26 N 2 + 3 2 N33 Figure 2-2 Chord Ring and Finger Table In order to find a data item, peers will lookup the key by passing this key around the Chord ring in a clockwise direction (that is, the direction of increasing identifier). The query for this key wil l transit from peer to peer until it reaches the peer responsible for storing that key. To facilitate this routing, peers on the Chord ring maintain a routing table called the finger table (see Figure 2-2), which is a lookup table with up to m entries. Each entry wil l point to the peer on the Chord ring that 9 has a key value at least 2' - 1 units away in the identifier space, where 1 < I <m. When routing a lookup message, a peer forwards it to the closest peer identifier key in the finger entries, but no greater than the key hashed in the message. This lookup message mechanism is proven to. be 0( log JV) hops per lookup, where N is the total number of peers in the Chord ring. 2.1.3 Incentive Mechanisms In a P2P network, especially file-sharing applications, peers are assumed to cooperate since they have the common objective of downloading content. However, the report on free-riders in the Gnutella [9] network indicates that about 70% of users did not share files, much less than in KaZaA [14], which introduced multi-level participation for peers as an incentive mechanism. KaZaA defined that the more peers there are dedicated to storage and sharing content, the more content that can be downloaded. Collaboration among peers is difficult. However, i f we consider P2P networks from the other perspective of peers in the network offering the service, peers wil l earn their payoff by competing with one another. Thus, incentive mechanisms are needed as a basis for motivating peers to join together and provide services. In order to encourage the cooperation between nodes, researchers have proposed many incentive mechanisms, most of which focus on resolving free-riding. However, our incentive mechanism not only solves free-riding problem, but also reduce the maintenance overhead for DHT-base P2P system topology. 10 2 . 2 R e l a t e d Work Several studies have investigated incentive mechanisms for Internet applications and P2P systems. Researchers have suggested building explicit incentive mechanisms into various types of P2P applications. The most widely studied mechanisms fall into four categories: (1) payment-based mechanisms that require tokens, scores, credit, or money to be exchanged in return for service; (2) reputation-based mechanisms that punish or reward peers based on their observed behavior; (3) contribution-based mechanisms that require peers to provide a contribution to get service from others; and (4) other mechanisms that use different approaches. 2 .2 .1 Payment-based Mechanisms The payment-based mechanism has been implemented and proven (Zhong et al. [24]). In a payment-based mechanism, when a peer sends a query message, the peer wil l lose credit to the decentralized virtual marketplace network, since other peers wil l incur a cost to forward the message. On the other hand, peers that forward other peers' messages wil l earn credit, which can be used for their own query messages. Peers can obtain credit in three ways. In the first, peers can directly buy more credit by using real money or other equivalent-money format. In the second, peers earn credit by forwarding other peers' messages. Lastly, peers can obtain credit by providing and/or selling services. 11 Golle et al. [21] proposed a micro-payment mechanism, where each peer can earn rewards if they upload to other peers. The rewards can be used for future download. Using a game theoretic model, the authors analyze the equilibrium of peer strategies under several payment mechanisms and conclude that equilibrium exists for the micro-payment based system. The objective of this system is to achieve maximum cooperation from the peers. K A R M A [27] and the lightweight currency paradigm [7] are examples of payment-based mechanisms. K A R M A uses a single currency as a way of secure trading, and the lightweight currency paradigm allows the users to trade any resource with their own currencies. Any entity can introduce its own currency, as long as it is acceptable to other users in the system. A score-based system (Nowak et al. [18]) allows a peer to download multiple times from other peers having lower scores than its own. KaZaA [14], a score-based P2P system as well, provides downloading priority to peers with high scores over peers with low scores. In our incentive mechanism, we use an incentive value to evaluate peer payoff, such as service priority and resource distribution, instead of using other means such as credit, etc. However, an incentive value is a combination of two incentive factors, session time and peer contribution (see Chapter 3). 12 2.2.2 Reputation-based Mechanisms Reputation-based mechanisms require the capability to evaluate a peer's cooperativeness on the basis of observable behavior and to provide a punishment or reward with the desired incentive. Each peer would like to obtain or maintain reputation (Hu et al. [26]). The reputation incentive mechanism has been shown to be successful in eBay, where buyers and sellers use feedback ratings to gain their reputation values. In a reputation-based system (Gupta et al. [17]), the peers earn their reputation by sharing, and the reputation determines peer quality. Downloading from a peer with a high reputation has a higher probability of leading better service. 2.2.3 Contribution-based Mechanisms Buragohain et al. [6] proposed a game theoretic framework to provide incentives in P2P systems. In this model, peer contribution is expressed in terms of disk space shared per unit time. This contribution allows a peer to obtain differential service, i.e., greater contribution to the system wil l earn a higher probability with which others wil l serve its request. If the contribution is small, its request is more likely to be rejected. The incentive mechanism eliminates the free-riders and increases the overall availability of the system. 13 In our incentive mechanism, we express peer contribution in terms of the difference between uploading amount and downloading amount, and an incentive value is a combination of session time and peer contribution. Since incentive values of peers determines peer payoff, the more peer contribution, the more payoff peers earn. 2 . 2 . 4 O t h e r M e c h a n i s m s BitTorrent [2] provides incentives to users to download files i f they allow simultaneous upload by other users. In this way, the server redistributes the uploading cost to the downloaders, and a file can be served concurrently to a large number of users. BitTorrent does not need any score, token, or reputation computation, and therefore has the advantage of simplicity. 14 Chapter 3 Incentive Mechanism Design In this chapter, we introduce the design of our incentive mechanism through explaining how we explore two incentive factors, peer session time and peer contribution, employed in our incentive mechanism. Also, we introduce an incentive value that is a combination of the two factors for each peer. The system uses the incentive values of peers to define peer payoff such as service priority and resource (e.g., bandwidth) distribution. Finally, we show what can be expected from the incentive mechanism. Thus, this chapter will show a unique approach in our incentive mechanism for DHT-based P2P systems. 3 . 1 I n c e n t i v e F a c t o r s A n incentive factor is a factor that peers can provide before getting some payoff in return. In the previous section, we introduced some related works that used 15 reputation, credit, etc., as incentive factors. In this thesis, we propose some new incentive factors, described in the following sections. 3.1.1 Session Time Session time of a peer is the amount of time between the peer joining a system and leaving the system. First, let us look at some peer session time experiments. • Saroiu et al. [23] studied the session distribution of Napster [20] and Gnutella [9] in 2002. Their results showed that 50% of the nodes had session times of less than 60 minutes. Figure 3-1 shows the corresponding session PDF (Probability Density Function) curve, indicating an uneven distribution of session time among nodes. While many nodes' session time is very short, only a few have a long session time. 0 i — . — i . i . i r i , ~ i . H 0 120 240 360 480 600 720 Session Time (mins) Figure 3-1 The PDF Curve of Session Distribution 16 This observation explains why structured P2P systems have a huge maintenance overhead. Many nodes whose session time is short would join and then leave the P2P network so frequently as to disturb the construction of network topology, rapidly increasing its maintenance overhead. Considering this fact, the intuitive idea is to encourage peers to extend their session time. We can call nodes with longer session time stable nodes. If there are more stable nodes in the system, the system wil l tend to be more stable. 3.1.2 Peer Contribution The definition of peer contribution is the difference between the amount of uploading resource and the amount of downloading resource. When a peer provides service to others, such as sharing its resources (files, image, video, etc.), its peer contribution increases. On the other hand, after a peer downloads a resource from others, then its peer contribution will decrease. We chose peer contribution as an incentive factor for the following two reasons. (1) Session-Time Threshold In order to avoid cheating by malicious peers (consuming unlimited time to increase session time, while not providing any contribution), we set a session-time threshold. In our experiments, we define the value of the threshold to be the amount of time to download the largest resource using the smallest downloading rate in the system. That is, session time wil l reach a maximal value as long as peers keep staying in the 17 system. If session time is greater than the threshold, then the session time will be set to the threshold and cannot be further increased. However, some non-malicious riodes wil l reach the session-time threshold as well, as long as they stay in the system for a longer period of time (but the majority of peers wil l not reach the session time threshold). For this reason,' we chose peer contribution as a second incentive factor, so that these non-malicious nodes can still increase their incentive value by increasing peer contribution. (2) Free-riding As we mentioned in the Introduction, nearly 70% of peers do not share their own resource, and wait for others. That is, these peers just share resources from others and never provide their own resources, or only a very minor portion of services, to others. If peer contribution is an incentive factor, then peers are encouraged to contribute more in order to increase incentive value. If every peer tries to maximize its contribution, then free-riding wil l be significantly controlled. 3 . 2 I n c e n t i v e V a l u e The goal of our incentive mechanism is to reduce the overhead of system maintenance and control free-riding. We combine the two incentive factors to form an incentive value. Our incentive mechanism then uses the incentive value to determine peer payoff. 18 3.2.1 Definitions of Incentive Variables We define variables for session time, peer contribution, and incentive value. These variables used in deriving our incentive mechanism are defined in Table 3-1. Variables Variable Definitions Ti( t ) The session time of the i'h peer at time t. C ; ( t ) The i'h peer contribution, which is equal to the amount of the i'h peer uploading minus the amount of the i'h peer downloading. Ii(t) The incentive value of the Ith peer. The payoff of peers is determined by its incentive value. Table 3-1 Incentive Variables 3.2.2 Expressions of Incentive Variables Based on the above definitions of these variables, each variable has a corresponding expression. The mathematical equations used in calculating our incentive variables are given in Table 3-2. For the expression of incentive values, we wil l determine optimal values for a and (3 in our experiments (see Chapter 6). 19 Expressions Equation Numbers Related Information - T,(t) = t-t0 Equation (1) t 0 is the initial time when the i'h peer logs into the system. If T; (t) > STT, then set T; (t) = STT, where STT represents Session Time Threshold. Ci(t)=\[Ui(t)-Di(t)]dt Equation (2) Uj is the amount of the i'h peer's uploading, and D ^ s the amount of the i'h peer's downloading. Ii(t) = a-Ti(t) + /3-Ci(t) Equation (3) a and P are incentive coefficients, wherea + = 1 a n d a , / ? £ [0,1]. a and (3 are dependent on the importance degrees of their incentive factors in the mechanism. Table 3-2 Incentive Expressions 3 . 3 P e e r P a y o f f As long as peers can get payoff from the system, then they are willing to provide longer session time and peer contribution. This is how our incentive mechanism 20 works. There are two forms of payoff, service priority and resource distribution. When peers have higher incentive value, they wil l obtain higher service priority and larger resource distribution. 3.3.1 Service Priority To avoid getting a resource-provider node overloaded, the system sets a limited amount of connections for each resource-provider node. We define this limit to be an integer M , which depends on the application setting. If M is set too large, it wil l affect the amount of resource distribution for each resource-consumer node. For instance, each share of the resource distribution wil l be tiny. If M is set too small, many resource-consumer nodes need to wait, since the number of connections that resource-provider nodes offer are set too small. Since incentive values determine service priorities, i f there are more than M nodes connecting to a resource-provider node, then the M nodes with the highest incentive values wil l get the service from the resource-provider node, and the rest of nodes with lower incentive values wil l be put on a waiting list. These nodes on the waiting list wi l l still compete with other new incoming resource-consumer nodes that are requesting the same resource from the resource-provider node. When there is no competition for resource downloads (that is, there are less than M nodes connecting to the resource-provider node), the system only keeps accounts with T i W a n d C j C t ) . 21 3.3.2 Resource Distribution The bandwidth of a resource-provider node wil l be distributed to all applicants according to their incentive values. On the other hand, in order to get more bandwidth distribution from resource-provider nodes, a resource-consumer node needs to increase its incentive value, that is, increase its session time and/or peer contribution. Figure 3-2 Resource Distribution by Incentive Values Suppose that there are n nodes, N , , N 2 , N 3 , N n (see Figure 3-2), requesting a resource from a resource-provider node N . Let I , ( t ) , I 2 ( t ) , I 3 ( t ) , • • • , ! „ ( t ) be the incentive values of these nodes N 1 5 N 2 , N 3 , N n at timet. Let W p denote the 22 bandwidth of n o d e N p and W p k (t) denote the bandwidth distributed to the node N k from the node N p , where k e [1, n]. These symbols are illustrated in Figure 3-2. The expression of W k (t) is: Ik(0 n Equation (4) i=l From Equation (4), we can see that the higher the node's I k (t) , the more bandwidth it gets. That is, nodes with a higher incentive value wil l get more resource distribution. Conversely, nodes with a lower incentive value wil l either be delayed or cannot get the resource. Meanwhile, the Quality of Service wil l be guaranteed. Equation (3) represents our proposed incentive mechanism. Based on this equation, peers need to increase incentive value, that is, increase session time and/or peer contribution, to maximize peer payoff. Two improvements for DHT-based P2P systems are expected if our incentive mechanism is applied as follows: If every peer's session time tends to increase in the system, eventually the system tends to be stable, because peers with longer session time are stable. The overhead of maintaining the system topology wil l therefore be reduced through our incentive mechanism. 3 . 4 M e c h a n i s m E x p e c t a t i o n s 23 \ If every peer tries to increase its peer contribution in the system, that is, every peer increases the amount of uploading, then the free-riding problem can be reduced, and more resources wil l be available to share in the system. Our incentive mechanism wil l therefore tend to increase the usability of the system utilities. In Chapter 6, "Simulation and Evaluation", we demonstrate how our incentive mechanism improves DHT-based P2P systems with respect to Maintenance Overhead Level (MOL) and Resource Usability Ratio (RUR). 24 Chapter 4 Incentive System Architecture In this chapter, we introduce a new incentive system architecture that applies our incentive mechanism. We add an Incentive Service Component (ISC) into a normal DHT-based P2P system to construct the new incentive DHT-based P2P system. ISC is the core component reflecting our incentive mechanism in an incentive DHT-based P2P system. 4 . 1 I n c e n t i v e S e r v i c e C o m p o n e n t The task of ISC is to verify session time and peer contribution, calculate incentive values using session time and peer contribution, and evaluate peer payoff, such as service priority and resource distribution. ISC consists of two models: STPC Model and SPRD Model. We provided the detail of designing STPC Model and SPRD Model. 25 4.1.1 STPC Model The structure of STPC (Session Time and Peer Contribution) Model is shown in Figure 4-1. The figure depicts STPC Model as consisting of two components, STPC Courier and STPC Verifier, which indicate the two functions of STPC Model. Figure 4-1 STPC Model STPC Courier delivers session time and peer contribution, when a node is a resource-consumer node. Note that the node should not send an incorrect session time or peer contribution, since each node has a STPC Verifier, that is, the resource-provider node wil l verify the resource-consumer node's session time and peer contribution. If there are any incorrect data (i.e., cheating behaviors exist), then the offending node will receive serious punishment - it wil l be rejected by resource-provider nodes and put onto the system's blacklist. STPC Verifier has a key role in STPC Model. If a node is a resource-provider node, when other resource-consumer nodes request the resource, the resource-provider node 26 will verify the session time and peer contribution that resource-consumer nodes deliver. We discuss the detail of verifying session time and peer contribution in the sections on implementation analysis in Chapter 5, "ISC Implementation". 4.1.2 SPRD Model The structure of SPRD (Service Priority and Resource Distribution) Model is shown in Figure 4-2. From the figure, SPRD Model can be to consist of two parts, SP Service and R D Service, which indicate the two functions of SPRD Model. Figure 4-2 SPRD Model The function of SP Service is to manage the service priorities of resource-consumer nodes and decide which candidates wil l be served next i f there are more than M (defined in Section 3.3.1) nodes requesting the resource from a resource-provider node. The function of R D Service is to distribute the resource-provider node's bandwidth to those qualified resource-consumer nodes by Equation (4), after STPC 27 Verifier finishes verifying the session time and peer contribution of these resource-consumer nodes. 4 . 2 S y s t e m A r c h i t e c t u r e Based on a normal DHT-based P2P system architecture, adding an ISC wil l create a new incentive DHT-based P2P system architecture. Figure 4-3 shows the new incentive system architecture. Figure 4-3 Incentive System Architecture 28 In the new architecture, there are three types of layers: the top layer, the middle layer, and the bottom layer. The top layer represents the GUI and Logic of resource-sharing applications, which provides the graphical user interface for users choosing service options, and also executes the logic part of applications to handle connecting with ISC and D H T service. The bottom layer represents Network Communication, which ISC and D H T service use to make network connections. There are two middle layers, the ISC middle layer and the D H T Service middle layer. The D H T Service middle layer provides responses to the peer-to-peer lookup service, searches contents, checks peer topology, and maintains the D H T circle. The ISC middle layer consists of two components, STPC Model and SPRD Model. ISC collects incentive values, determines service priority, and distributes resource (discussed in Sections 4.1.1 and 4.1.2). If the system eliminates the ISC middle layer, then the system becomes a normal DHT-based P2P system. There is an indirect relationship between the ISC middle layer and the D H T middle layer, since STPC Verifier needs to contact neighbors of resource-consumer nodes. Searching these neighbors is one of the D H T Service functions. 29 Chapter 5 ISC Implementation Our incentive system adds a key middle layer, Incentive Service Component (ISC) to a normal DHT-based P2P system to achieve our incentive mechanism. Thus, for system implementation, we focus only on ISC implementation in this thesis. The implemented ISC API can be called by the top layer, Resource Sharing Applications in order to execute our incentive mechanism. The ISC implementation includes STPC Model implementation and SPRD Model implementation. 5 . 1 S T P C M o d e l I m p l e m e n t a t i o n In this section, we first analyze the implementation of STPC Model including the two components STPC Courier (delivering session time and peer contribution) and STPC Verifier (verifying the correctness of session time and peer contribution, in order to avoid malicious nodes cheating). We then provide algorithms for the functions of STPC Courier and STPC Verifier respectively. 30 5.1.1 Analysis of STPC Model Implementation As introduced in Section 4.1.1, STPC Model consists of two components, STPC Courier and STPC Verifier. In this section, we analyze implementation of the two components. STPC Courier is applied only i f a node is a resource-consumer node. When the node requests a resource, STPC Courier needs to deliver its session time and peer contribution to a resource-provider node. For session time, STPC just needs to send the node's login time and the current time of the resource request. Before STPC Courier delivers the node's peer contribution, it needs to collect the information of the downloads and uploads. Then, STPC Courier of the resource-consumer node sends one peer list for downloading and one peer list for uploading. The downloading list contains each downloading amount and the corresponding node from which the resource-consumer node downloaded the resource. Similarly, the uploading list contains each uploading amount and the corresponding node to which the resource-consumer node uploaded the resource. Thus, the two lists are very useful and important for STPC Verifier verifying peer contribution. The implementation of STPC Verifier is much more complicated than the implementation of STPC Courier. The function of STPC Verifier requires it to verify the resource-consumer nodes' session time and peer contribution to prevent nodes cheating. To verify the session time of a resource-consuming node, STPC Verifier needs to contact the node's neighbors to confirm the node's login time. To verify 31 peer contribution, STPC Verifier wil l contact the nodes on the two lists. If some nodes on the lists have left from the system, then STPC Verifier wil l contact the nodes' neighbors, because each node backs up service information onto its neighbors. 5.1.2 STPC Model Algorithms Based on our implementation analysis of STPC Courier and STPC Verifier, we provide the algorithms for their functions in Figure 5-1 and Figure 5-2. 1 /* 2 * The function i s to deliver a node's session tine 3 * and peer contribution to resource providers. 4 * @para: tpIP - the IP address of a resource provider 5 * / 6 DeliverSTPC (ResourceProvider rpIP) { 7 // 1. Deliver session time 8 9 // Retrieve login time and current tine 10 loginTime = getLoginTime(); 11 currentTime = System. getCurrentTime(); 12 // Send both tine to Resource Provider 13 sendSessionTime(loginTime, currentTime, rpIP); 14 15 // 2. Deliver peer contribution 16 1? // Store nodes that the node has downloaded from 18 List dn = getDounloadNodesList(); 19 // Store nodes that the node has uploaded to 20 L i s t up = getUploadHodesList(); 21 for i = 1 to dn.size 22 dnStr.append(dn[i].ip, dn[i].amount); 23 for i = 1 to up.size 24 upStr.append(up[i].ip, up[i].amount); 25 // Send two l i s t s to Resource Provider 26 sendPeerContriliution(dnStr, upStr, rpIP); 27 } Figure 5-1 The Function of STPC Courier 32 1 / * 2 * The f u n c t i o n i s to v e r i f y two types o f da ta ( s e s s ion t i n e and peer 3 * c o n t r i b u t i o n ) sent from resource consumers. 4 * @para: cornsumerIP - the IP address of a consumer node 'j * log inTime - l o g i n t i n e o f a consumer node 6 * c u r r e n t T i n e - the t i n e o f a consumer node making request 7 * dnStr - the s t r i n g s t o r i n g a l l download i n f o r m a t i o n 8 * upStr - the s t r i n g s t o r i n g a l l up load i n f o r m a t i o n 9 * Q r e t u r n : f a l s e i f i n c o r r e c t da ta e x i s t . Otherwise , t r u e . And the 10 f u n c t i o n f i g u r e s out s e s s i o n t i n e and peer c o n t r i b u t i o n . 11 * / 12 Ver i fySTPC (consumerIP, l o g i n T i m e , c u r r e n t T i n e , d n S t r , upStr) { 13 14 t i l . V e r i f y s e s s i o n time 15 . 16 / / F i r s t get these v e r i f i e d times of consumer nodes 17 v e r i f i e d L o g i n T i n e = getLoginTime (getHeighbors(consumerIP)); 13 v e r i f i e d C u r r e n t T i m e = System. g e t C u r r e n t T i n e ( ) ; 19 20 / / Check i f consumer nodes cheat or not 21 i f ( loginTime != v e r i f i e d L o g i n T i m e OR c u r r e n t T i n e > v e r i f i e d C u r r e n t T i m e ) { 22 r e t u r n f a l s e 23 } 24 / / C a l c u l a t e s e s s i o n time 25 sess ionTime = currentTime - l og inTime; 26 27 / / 2. V e r i f y peer c o n t r i b u t i o n 28 29 / / F i r s t v e r i f y download amount 30 L i s t dn = c o n v e r t S t r T o L i s t ( d n S t r ) ; 31 f o r i = 1 to (In. s i z e { 32 i f ( v e r i f i e d D o w n l o a d ( d n [ i ] , getHeighbors(consumerIP)) — fa l se ) 33 r e t u r n f a l s e ; 34 e l s e 35 downloadAmount += dn[ i ] .amount; 36 } 37 / / Then v e r i f y upload amount 38 L i s t up = c o n v e r t S t r T o L i s t ( u p S t r ) ; 39 for i = 1 to u p . s i z e { 40 i f ( v e r i f i e d u p l o a d ( u p [ i ] , getHeighbors(consumerIP)) = f a l s e ) 41 r e t u r n f a l s e ; 42 e l s e 43 uploadAmount += up [ i ] .amount; 44 } > 45 46 / / C a l c u l a t e peer c o n t r i b u t i o n 47 p e e r C o n t r i b u t i o n = uploadAmount - downloadAmount; 48 49 r e t u r n t r u e ; 50 } Figure 5-2 The Function of STPC Verifier 33 5 . 2 S P R D M o d e l I m p l e m e n t a t i o n In this section, we analyze the implementation of SPRD Model, including the two components SP Service and R D Service. We then provide algorithms for the function of two components. 5.2.1 Analysis of SPRD Model Implementation As introduced in Section 4.1.2, SPRD Model consists of two components, SP Service and R D Service. SP Service provides the function to determine the service priorities of resource-consumer nodes, and R D service provides the function to distribute the resource of resource-provider nodes to resource-consumer nodes. If the number of nodes is less than M (defined in Section 3.3.1), then every node wil l get service and service priorities are not applied. If the number of nodes is greater than M , then other nodes out of M highest service priorities wil l be put onto a waiting list. If one of M nodes leaves, then SP Service will determine the next candidate to get service by choosing a node with the highest service priority among all candidates. SP Service determines the highest service priority by sorting incentive values of all candidates and then picking the candidate with the highest incentive value. From Equation (3), we know that an incentive value is a combination of session time and peer contribution. Before calculating an incentive value, SP Service must know a node's session time and peer contribution. Since the node's STPC Courier has sent 34 all related information concerning session time and peer contribution (see the function of STPC Courier in Section 5.1), SP Service only needs to call STPC Verifier to verify the node's session time and peer contribution (see the function of STPC Verifier in the section 5.1). Once the verification is done, SP Service can calculate the incentive value and determine the node's service priority. The function of R D Service is called when there are new resource-consumer nodes eligible to receive resource from resource-provider nodes. From Equation (4), R D Service distributes the resource-provider node's bandwidth to all resource-consumer nodes that have been qualified by SP Service. For each new resource-consumer node just qualified to get a service, R D Service will recompute the distribution, first recomputing all nodes' incentive values and then calculating the distribution of bandwidth for each node. 5.2.2 SPRD Model Algorithms Based on our implementation analysis for SP Service, we provide the algorithm for its function in Figure 5-3. 35 1 /* 2 * The f u n c t i o n i s to evaluate s e r v i c e p r i o r i t i e s and. decide 3 * next q u a l i f i e d nodes to get the s e r v i c e 4 * (Spar a: numftctivellodes - the number of resource-consuming nodes 5 * that are g e t t i n g the s e r v i c e from the resource p r o v i d e r . 6 * @return: the next q u a l i f i e d resource-consuming nodes w i t h the 7 * highest s e r v i c e p r i o r i t i e s . 8 */ 9 10 SP_Service ( i n t numftctivellodes) { 11 // SP Se r v i c e i s not a p p l i e d i f there i s l e s s than M nodes 12 i f (numftctivellodes >= M) { // M is predefined. 13 r e t u r n ; 14 } 15 16 // F i n d a l l resource-consuming nodes w a i t i n g f o r the s e r v i c e 17 L i s t w a i t i n g L i s t = getAllWaitingHodes(); // create a node l i s t 18 ' 19 f o r i = 1 to w a i t i n g L i s t . s i z e { 20 // V e r i f y these nodes f i r s t 21 i f ( V e r i f y S T P C ( w a i t i n g L i s t [ i ] . l o g i n T i m e , 22 w a i t i n g L i s t [ i ] . c u r r e n t T i m e 23 w a i t i n g L i s t [ i ] . d n S t r , 24 w a i t i n g L i s t [ i ] . u p S t r ) == t r u e ) ) { 25 26 // Figure out i n c e n t i v e values 27 in c e n t i v e V a l u e = (sessionTime + p e e r C o n t r i b u i t o n ) / 2 ; 28 29 // Store i n c e n t i v e value i n f o r m a t i o n i n the nodes 30 w a i t i n g L i s t [ i ] . i n c e n t i v e V a l u e = i n c e n t i v e V a l u e ; 31 32 } 33 > 34 35 // F i n d put how many nodes can be served next 36 numFreeSlots = ii - numftctivellodes; 3? 38 // Sort the wait l i s t based on i n c e n t i v e values 39 s o r t L i s t O n l n c e n t i v e V a l u e ( w a i t i n g L i s t ) ; 10 '11 // Return only those q u a l i f i e d nodes 42 " r e t u r n w a i t i n g L i s t [ 1 ..numFreeSlots]; 43 } Figure 5-3 The Fmiction of SP Service 36 Based on our implementation analysis for R D Service, we provide the algorithm for its function in Figure 5-4. 1 /* 2 * The f u n c t i o n i s to compute the d i s t r i b u t i o n of 3 * bandwidth f o r q u a l i f i e d resource-consuming nodes. A * <§para: bw - the bandwidth a resource provider has. 5 * numActiveHodes - the number of nodes that i s 6 * g e t t i n g the se r v i c e from the resource provider. 7 * Oreturn: a l i s t of resource-consuming nodes with the 8 * bandwidth d i s t r i b u t i o n information. 9 */ 10 11 RD_Service ( i n t bw, i n t num&ctiveHodes) { 12 13 // Obtain the current consumers l i s t 14 L i s t currConsumers = getCurrentResourceConsumingHodes(); 15 16 // Call. SP Service to get next q u a l i f i e d consumer nodes 17 L i s t nextConsumers = SP_Service(numftctiveNodes); 18 19 // Combine the two l i s t s to make a new consumers l i s t 20 L i s t consumersList = combineLists(currConsumers, nextConsumers); 21 22 // Calculate the summation of a l l . i n c e n t i v e values 23 t o t a l l n c e n t i v e V a l u e s = 0 ; 24 f o r i = 1 to consumersList.size { 25 t o t a l l n c e n t i v e V a l u e s += consumersList[i].incentiveValue; 26 } 27 28 // Calculate the d i s t r i b i t o n of bandwidth f o r each consumer 29 f o r i = 1 to consumersList.size { 30 c o n s u m e r s L i s t . d i s t r i b u t i o n = bw * 31 (consumersList[i].incentiveValue / t o t a l l n c e n t i v e V a l u e s ) ; 32 } 33 34 // Return the l i s t w i t h the bandwidth d i s t r i b u t i o n information 35 r e t u r n consumersList; 36' } Figure 5-4 The-Function of RD Service 37 Chapter 6 Simulation and Evaluation In this chapter, we present the simulation of our incentive mechanism in a D H T -based P2P system. We show the results of the simulated experiments and evaluate our incentive mechanism, which improves DHT-based P2P systems with respect to system maintenance overhead and free-riding. Also from the experiments, we determine optimal values for a and P applied in the formula of an incentive value. 6 . 1 S i m u l a t i o n S e t u p We need to compare two types of DHT-based P2P systems, one without our incentive mechanism and the other with our incentive mechanism. Thus, in this section we briefly introduce the simulation setup for the two systems before discussing experiments. As stated previously, we wil l use the Chord system as the basis of our simulated systems. 38 First, we simulate a Chord system without our incentive mechanism. Based on the idea of p2pSim (Thomer G i l , et al., M I T [22]) for supporting Chord, Accordion, Koorde, Kelips, Tapestry, and Kademlia, we wrote our own version of Chord simulator in Java. There are six major classes, Chord.java, Node.java, GUID.java, NodeAddress.java, Address2D.java, and IDRange.java. In the Chord class, our Chord simulator implements the chord algorithms such as join(Node me, NodeAddress old), leave(), lookup(GUID key), and stabilize(). In the simulation, we apply 2D Euclidean space to arrange the network topology. The network delay is simulated in counting S T A B I L I Z E _ D E L A Y (e.g., we set such delay as 5000 ms), F I X F I N G E R _ D E L A Y , C H E C K P R E D E C E S S O R _ D E L A Y , etc. When simulated nodes are created, they are randomly assigned with data (i.e. resource) with random sizes. When they share data with others, data transferring is simulated in counting D A T A - T R A N S F E R - D E L A Y and the amount of data transferred. Next, we simulate a Chord system with our incentive mechanism. Based on the previous simulation, we add our incentive mechanism by implementing four algorithms, DeliverSTPC, VerifySTPC, SP_Service, and RD_Service, in a mechanism class. In the Node class, there is a member, a mechanism object. During the simulation, each resource-consumer node obtains the resource distribution from resource-providers by evaluating incentive values. We simulate a node session time by accumulating idle time plus all kinds of delays, such as data-transfer delay, lookup delay, etc. To simulate STPC Model and SPRD Model, each node will record two amount types, such as the amount of downloading and the amount of uploading. Also, each node wil l replicate the data onto its neighbors. Finally, we collect statistical data for evaluating M O L and RUR, discussed in the following sections. 39 6 . 2 M a i n t e n a n c e O v e r h e a d L e v e l First, we compare system maintenance overhead in DHT-based P2P systems with and without the incentive mechanism. In our experiments, we simulate two types of Chord P2P systems. In the first simulated system, nodes have to apply our incentive mechanism in order to get service from other nodes, while the second simulated system is non-incentive and nodes can be selfish and/or altruistic. Figure 6-1 shows that Maintenance Overhead Level (MOL) varies with Session Time. M O L is the percentage of nodes that need to update their finger tables at the current time in the system. In Figure 6-1, the lower curve represents the M O L of the incentive P2P system, while the upper curve represents the M O L of the non-incentive P2P system. From Figure 6-1, it can be seen that in the incentive P2P system, the M O L increases for roughly the first 200 minutes, since at the beginning of running the system, those selfish nodes refuse applying the incentive mechanism. They cannot get any resource, or only a very small amount, in its system. Therefore, they continuously leave the system in a short period of time. After those nodes are gone, the curve reaches the maximum and then drops down, since the rest of the nodes are applying the incentive mechanism and leave the system normally. However, in the non-incentive P2P system, the M O L always increases as Session Time increases, since 40 not all nodes have to apply the incentive mechanism, and can leave the system when they want. Session Time (minutes) Figure 6-1 Maintenance Overhead Level (MOL) The curve of the incentive system in Figure 6-1 is always below the curve of the non-incentive system at any corresponding session time. Thus, we can conclude that the incentive P2P system has a much lower M O L than the non-incentive P2P system. That is, the incentive P2P system has lower system maintenance overhead than the non-incentive P2P system. 41 6 . 3 R e s o u r c e U s a b i l i t y R a t i o We now compare free-riding in P2P systems with and without the incentive mechanism. In our experiments, we simulate two types of Chord P2P systems, set up in the same way as in Section 6.1. Figure 6-2 shows that the Resource Usability Ratio (RUR) varies with Session Time. R U R is the ratio of the number of resources being served and the total number of resource requests at the current time in the system. In Figure 6-2, the upper curve represents the R U R of the incentive P2P system, while the lower curve represents the R U R of the non-incentive P2P system. From Figure 6-2, it can be seen that in the incentive P2P system, the R U R decreases for roughly the first 200 minutes, since at the beginning of running the system, those selfish nodes refuse applying the incentive mechanism. They cannot get any resource, or only a very small amount, in this system. Therefore, they leave the system in a short period of time. After all those nodes are gone, the curve reaches the minimum and then rises, since the rest of nodes are applying the incentive mechanism and share their resources with other nodes. However, in the non-incentive P2P system, the R U R always decreases as Session Time increases, since not all nodes have to apply the incentive mechanism and do not need to share resources with other nodes. 42 0 100 200 300 400 500 600 700 800 Session Time (minutes) Figure 6-2 Resource Usability Ratio (RUR) The curve of the incentive system in Figure 6-2 is always above the curve of the non-incentive system at any corresponding session time. Thus, we can conclude that the incentive P2P system has a much higher R U R than the non-incentive P2P system. That is, the incentive P2P system has less free-riding than the non-incentive P2P system. 43 6 . 4 a a n d P A n a l y s i s Finally, we observe optimal values for a and p\ Since a is related to session time and P is related to peer contribution, we ran two types of experiments to observe different combinations of a and (3 values with respect to M O L and R U R . In the experiments, we simulated only one type of Chord P2P system, which applies our incentive mechanism. 300 400 500 Session Time (minutes) 600 700 800 Figure 6-3 M O L s with Different a and P Figure 6-3 shows the different M O L s using different combinations of a and P values. The curves from upper to lower represent the M O L s using a, with increasing values. 44 If a = 0 and P = 1, the incentive mechanism does not consider session time as an incentive value. In this case, the M O L wil l keep increasing, since an incentive value is not related to session time so that there is no encouragement for peers to extend their session time. If a = 1 and P = 0, the incentive mechanism only considers session time in an incentive value. In this case, M O L wil l reach the lowest level, since every peer has to extend its session time to increase its incentive value. When a > 0, P > 0, and after about 200 minutes, the M O L s wil l always decrease. Also, we observe that when a becomes larger, the M O L decreases more. Figure 6-4 shows the different RURs using different combinations of a and P values. The curves from upper to lower represent the RURs using a, with increasing values. If a = 0 and P = 1, the incentive mechanism only considers peer contribution as an incentive value. In this case, the R U R will keep increasing, since an incentive value is only related to the incentive factor, peer contribution. If a = 1 and P = 0, the incentive mechanism does not consider peer contribution as an incentive value, and there is no encouragement for peers to provide peer contribution. In this case, R U R will always decrease, since not every peer needs to make a contribution to the system (that is, free-riding frequently occurs.) When a > 0, P > 0, and after about 200 minutes, the RURs will always increase. Also, we observe that when P becomes larger, the R U R increases more. 45 a = 0.0, P = 1.0 a = 0.3', p = 0.7 - B - a = 0.5,|1 = 0.5 -0- a = 0.7, M 0.3 -*- <x = 1.0, p = 0.0 300 400 500 Session Time (minutes) Figure 6-4 RURs with Different a and P 700 800 From Figure 6-3 and Figure 6-4, we can observe that a larger a wil l benefit M O L , and vice versa. However, a larger P wil l benefit RUR, and vice versa. Thus, a = 0.5 and P = 0.5 will create the best combination of M O L and R U R . 46 Chapter 7 Conclusions In this chapter, we summarize this thesis and provide conclusions. Also, we discuss possible future work related to our incentive mechanism. 7.1 Summary In this thesis, we have investigated two aspects of DHT-based P2P systems with the aim of improving such systems: (1) the longer session time peers provide in the system, the more stable the system tends to be with lower system overhead for maintaining D H T topology; (2) the more the peers contribute, the more resources they can share in the system. Based on these two facts, we have proposed an incentive mechanism that reduces system maintenance overhead and dramatically controls free-riding in DHT-based P2P systems. 47 Our incentive mechanism applies two incentive factors, session time and peer contribution, in an incentive value. Session time is the amount of time a peer stays in a system, and peer contribution is the difference between the amount they upload and the amount they download. The incentive value determines peer payoff: (1) a peer with a larger incentive value will get higher service priority; (2) a peer with a larger incentive value wil l more resource distribution from resource-provider nodes. We proposed a new incentive system architecture that employs our incentive mechanism. The difference between a normal DHT-based P2P system and our new incentive system is that the new architecture adds a new component, Incentive Service Component (ISC), consisting of two models, STPC Model and SPRD Model. STPC Model consists of STPC Courier and STPC Verifier, and SPRD Model consists of SP Service and R D Service. STPC Model delivers and verifies session time and peer contribution. SPRD Model determines service priorities to get resources, as well as the resource (e.g., bandwidth) distribution to resource-consumer nodes. We simulated two types of Chord systems, one with our incentive mechanism and the other one without our incentive mechanism. Our simulation results show that the incentive P2P system has a much lower Maintenance Overhead Level (MOL) than the non-incentive P2P system, and that the incentive P2P system has a much higher Resource Usability Ratio (RUR) than the non-incentive P2P system. Our simulation also demonstrates that both system maintenance overhead and the free-riding problem are efficiently reduced in our proposed incentive system. 48 7 . 2 F u t u r e W o r k There are four major areas that need further investigation in future. First, in STPC Model, STPC Verifier needs to consider the special case where all neighbors of a resource-consumer node are gone. In this case, our current implementation will ignore the resource-consumer node's peer contribution since no peer can approve its contribution. In future system development, it would need a new verification algorithm for this special case. Second, neighbors of resource-consumer nodes can cheat with them together, since these neighbors can send fake information, when resource-provider nodes verify the session time and peer contribution of these resource-provider nodes. The future solution would be to apply reputation of these peers to pre-estimate the degree of peer trustiness. Third, when a resource-consumer node gets its bandwidth distribution that exceeds its own maximal downloading bandwidth, currently we deal with the situation by using its own maximal downloading bandwidth to assign the bandwidth distribution. The future solution for the situation would be to save these extra bandwidth distributions as some credit to redeem at next time. Last, in SPRD Model, if there are more than M nodes requesting a resource, then SP Service selects M nodes with the highest service to share the resource, put the other nodes on a waiting list. From the experiments, we observe that resource distribution 49 has a close relationship with M . If M is set too large, it will affect the amount of resource distribution for each resource-consumer node. If M is set too small, many resource-consumer nodes need to wait. Thus, in our simulation, we set M at 50. Since P2P systems exist nodes heterogeneity, some nodes can support a bigger M , while some other nodes can only support a smaller M . Our future incentive mechanism would consider a dynamic integer M , that is, every node can support a different M . Also, M would be applied in an incentive value. This is, the bigger M wil l benefit an incentive value. 50 Bibliography [1] Anthony I. T. Rowstron, Peter Druschel. "Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems," in Proceedings of the I F I P / A C M International Conference on Distributed Systems Platforms, Heidelberg, p.329-350, November 12-16, 2001. [2] B . Cohen. "Incentives build robustness in BitTorrent," in Workshop on Economics of P2P Systems, Berkeley, California, June 2003. [3] Balakrishnan, H . , Kaashoek, M.F . , Karger, D., Morris, R., Stoica, I. "Looking up data in P2P systems," Communications of the A C M , 46(2): 43-48, 2003. [4] Ben Y . Zhao, John D. Kubiatowicz, Anthony D. Joseph. "Tapestry: A n Infrastructure for Fault-tolerant Wide-area Location and Routing," University of California at Berkeley, Berkeley, C A , 2001. [5] BitTorrent, http://www.bittorrent.com. [6] C. Buragohain, D. Agrawal, and S. Suri. " A game theoretic framework for incentives in P2P systems," in Proceedings P2P, Sweden, September 2003. 51 [7] D. Turner and K. Ross. "The lightweight currency protocol," Internet Draft, draft-turner-lcp-OO.txt, September 2003. [8] E . Adar and B. Huberman. "Free riding on Gnutella," Technical report, Xerox PARC, 2000. [9] Gnutella, http://gnutella.wego.com. [10] Ian Clarke, Oskar Sandberg, Brandon Wiley, and Theodore W. Hong, "Freenet: A distributed anonymous information storage and retrieval system," Lecture Notes in Computer Science, vol. 2009, p. 46+, 2001. [11] Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan. "Chord: A scalable peer-to-peer lookup service for internet applications," in Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p. 149-160, San Diego, CA, United States, August 2001. [12] IRIS Project, http://project-iris.net/, 2004. [13] JXTA, http://www.jxta.org. [14] KaZaA, http://www.KaZaA.com. 52 [15] Ledlie, J., Taylor, J., Serban, L . , Seltzer, M . "Self-Organization in Peer-to-Peer Systems," The 10 t h A C M SIGOPS European Workshop, 2002 [16] Limewire, http://www.limewire.com, 2004 [17] M . Gupta, P. Judge, and M . Ammar. " A reputation system for peer-to-peer networks," in Proceedings A C M N O S S D A V , California, June 2003. [18] M . Nowak and K . Sigmund. "Evolution of indirect reciprocity by image scoring," Nature, vol. 393, pp. 573-577, 1998. [19] Morpheus, http://www.musiccity.com, 2004. [20] Napster, http://www.napster.com. [21] P. Golle, K . Leyton-Brown, and I. Mironov. "Incentives for sharing in peer-to-peer networks," in Proceedings A C M Electronic Commerce (EC '01), Tampa, F L , October 2001. [22] p2pSim, http://pdos.csail.mit.edu/p2psim/. [23] Saroiu, S., Gummadi, P.K. , Gribble, S.D. " A Measurement Study of Peer-to-Peer File Sharing Systems," in Proceedings of Multimedia Conferencing and Networking. San Jose, C A , 2002. 53 [24] Sheng Zhong, Jiang Chen, and Yang Richard Yang. "Sprite: A Simple, Cheat-Proof, Credit-based System for Mobile Ad-Hoc Networks," Technical Report Yale/DCS/TR1235, Department of Computer Science, Yale University, July 2002. [25] Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Shenker. " A scalable content-addressable network," in Proc. A C M S I G C O M M , pp 161-172 San Diego, C A , U S A , August 2001. [26] T im Hing-ting Hu, K . Wongrujira, and A . Seneviratne. "Reputation in Peer-to-Peer Networks," ICC 2004, Paris, France, June 2004. [27] V . Vishnumurthy, S. Chandrakumar, and E . Gun Sirer. " K A R M A : A secure economic framework for P2P resource sharing," in Workshop on Economics of Peer-to-Peer Systems, Berkeley, California, June 2003. 54 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051991/manifest

Comment

Related Items