Feedback
A game theoretic approach to provide incentive and service differentiation in P2P networks
Full text
Pdf (279 KB)
Source
ACM SIGMETRICS Performance Evaluation Review archiveVolume 32 , Issue 1 (June 2004) table of contents
SESSION: P2P and sensor networks table of contents
Pages: 189 - 198
Year of Publication: 2004
ISSN:0163-5999 Also published in ...
Authors
Richard T. B. Ma
Chinese University of Hong Kong
Sam C. M. Lee
Chinese University of Hong Kong
John C. S. Lui
Chinese University of Hong Kong
David K. Y. Yau
Purdue University, West Lafayette, IN
Publisher
ACM New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 16, Downloads (12 Months): 120, Citation Count: 6
Additional Information:
abstract references cited by index terms review collaborative colleagues
Tools and Actions:
Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref
DOI Bookmark:
Use this link to bookmark this Article: http://doi.acm.org/10.1145/1012888.1005711What is a DOI?
ABSTRACT
Traditional peer-to-peer (P2P) networks do not provide service differentiation and incentive for users. Consequently, users can obtain services without themselves contributing any information or service to a P2P community. This leads to the "free-riding" and "tragedy of the commons" problems, in which the majority of information requests are directed towards a small number of P2P nodes willing to share their resources. The objective of this work is to enable service differentiation in a P2P network based on the amount of services each node has provided to its community, thereby encouraging all network nodes to share resources. We first introduce a resource distribution mechanism between all information sharing nodes. The mechanism is driven by a distributed algorithm which has linear time complexity and guarantees Pareto-optimal resource allocation. Besides giving incentive, the mechanism distributes resources in a way that increases the aggregate utility of the whole network. Second, we model the whole resource request and distribution process as a competition game between the competing nodes. We show that this game has a Nash equilibrium and is collusion-proof. To realize the game, we propose a protocol in which all competing nodes interact with the information providing node to reach Nash equilibrium in a dynamic and efficient manner. Experimental results are reported to illustrate that the protocol achieves its service differentiation objective and can induce productive information sharing by rational network nodes. Finally, we show that our protocol can properly adapt to different node arrival and departure events, and to different forms of network congestion.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

1
The Gnutella Protocol Specification v0.4 1, document revision 1.2.

2
Limewire : a Gnutella client software.

3
E. Adar and B. Huberman. Free riding on Gnutella. FirstMonday, 2000.

4
Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987

5
J.-Y. Boudec. Rate adaptation, congestion control and fairness: A tutorial, http://icapeople.epfl.ch/leboudec.

6
Ian Clarke , Oskar Sandberg , Brandon Wiley , Theodore W. Hong, Freenet: a distributed anonymous information storage and retrieval system, International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, p.46-66, January 2001, Berkeley, California, United States

7
A. C. Fuqua, T. Ngan, and D. S. Wallach. Economic behavior of peer-to-peer storage networks. Workshop on Economics of Peer-to-Peer Systems, June 2003.
8
Philippe Golle , Kevin Leyton-Brown , Ilya Mironov, Incentives for sharing in peer-to-peer networks, Proceedings of the 3rd ACM conference on Electronic Commerce, p.264-267, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501193]

9
G. Hardin. The tragedy of the commons. Science, 162:1243--1248, 1968.

10
R. Ma, S. Lee, J. Lui, and D. Yau. Incentive P2P Networks: Theory and implementation. Technical report of Dept. of CSE, Chinese University of Hong Kong.

11
A. Mas-Colell, M. D. Whinston, and J. R. Green. Microeconomic theory. Oxford University Press, 1995.

12
N. Nisan and A. Ronen. Algorithmic mechanism design, 1999.

13
David Christopher Parkes , Lyle H. Ungar, Iterative combinatorial auctions: achieving economic and computational efficiency, 2001
14
Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States

15
Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001

16
S. Shenker. Fundamental design issues for the future internet. IEEE Journal on Selected Areas in Communication, 13(7), September 1995.

17
J. Shneidman and D. Parkes. Rationality and self-interest in peer to peer networks. International Workshop on Peer-to-Peer Systems (IPTPS), 2003.
18
Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States

19
W. Wang and B. Li. To play or to control: a game-based control-theoretic approach to peer-to-peer incentive engineering. IWQoS, 2003.

20
Ben Y. Zhao , John D. Kubiatowicz , Anthony D. Joseph, Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and, University of California at Berkeley, Berkeley, CA, 2001

21
S. Zhong, Y. Yang, and J. Chen. Sprite: A simple, cheat-proof, credit-based system for mobile ad hoc networks, 2002.
CITED BY 6

Sachin Agarwal , Jatinder Pal Singh , Shruti Dube, Analysis and implementation of Gossip-based P2P streaming with distributed incentive mechanisms for peer cooperation, Advances in Multimedia, v.2007 n.2, p.1-12, April 2007

Thanasis G. Papaioannou , George D. Stamoulis, Reputation-based policies that provide the right incentives in peer-to-peer environments, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.4, p.563-578, 15 March 2006

Xiangying Yang , Gustavo de Veciana, Performance of peer-to-peer networks: service capacity and role of resource sharing policies, Performance Evaluation, v.63 n.3, p.175-194, March 2006

Jinpeng Huai , Tianyu Wo , Yunhao Liu, Resource management and organization in CROWN grid, Proceedings of the 1st international conference on Scalable information systems, p.10-es, May 30-June 01, 2006, Hong Kong

Hyuk Lim , Chaegwon Lim , Jennifer C. Hou, A coordinate-based approach for exploiting temporal-spatial diversity in wireless mesh networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA

Nazareno Andrade , Francisco Brasileiro , Walfredo Cirne , Miranda Mowbray, Automatic grid assembly by promoting collaboration in peer-to-peer grids, Journal of Parallel and Distributed Computing, v.67 n.8, p.957-966, August, 2007
INDEX TERMS
Primary Classification: C. Computer Systems Organization C.2 COMPUTER-COMMUNICATION NETWORKS C.2.4 Distributed Systems
Additional Classification: C. Computer Systems Organization C.4 PERFORMANCE OF SYSTEMS Subjects: Design studies
REVIEW "Takeshi Takahashi : Reviewer"
Thanks to the massive development of peer-to-peer (P2P) technologies, we can easily exchange files among many users by using specific applications such as Gnutella. The P2P file-sharing system depends on users' willingness to share their files. Cu more...
Collaborative Colleagues:
Richard T. B. Ma: colleagues
Sam C. M. Lee: colleagues
John C. S. Lui: colleagues
David K. Y. Yau: colleagues
This Article has also been published in:
Joint International Conference on Measurement and Modeling of Computer SystemsProceedings of the joint international conference on Measurement and modeling of computer systems
2004 , New York, NY, USA