PPSP W. Zeng Internet-Draft Huawei Technologies Intended status: Informational June 29, 2010 Expires: December 31, 2010 P2P Streaming Protocol Pro-incentive Parameters draft-zeng-ppsp-protocol-pro-incentive-para-00 Abstract This document analyzes the common parameters that are essential for deriving incentive mechanisms to promote peer cooperation and system robustness in a P2P system, and proposes to incorporate these pro- incentive parameters in information exchanges in the P2P streaming protocols to be specified, e.g., in the tracker protocol proposed in [draft-gu-ppsp-tracker-protocol], and in the future in the peer protocol to be specified. Status of this Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." This Internet-Draft will expire on December 31, 2010. Copyright Notice Copyright (c) 2010 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of Zeng Expires December 31, 2010 [Page 1] Internet-Draft Pro-incentive Parameters June 2010 the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Document Conventions . . . . . . . . . . . . . . . . . . . . . 3 2.1. Notational Conventions . . . . . . . . . . . . . . . . . . 3 2.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Incentives in P2P Systems . . . . . . . . . . . . . . . . . . . 4 3.1. Measurement of peer contribution . . . . . . . . . . . . . 4 4. Pro-incentive Protocol Parameters . . . . . . . . . . . . . . . 6 5. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 7 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 7 7. Security Considerations . . . . . . . . . . . . . . . . . . . . 7 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 7 8.1. Normative References . . . . . . . . . . . . . . . . . . . 7 8.2. Informative References . . . . . . . . . . . . . . . . . . 7 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 8 Zeng Expires December 31, 2010 [Page 2] Internet-Draft Pro-incentive Parameters June 2010 1. Introduction Lack of cooperation (free riding) is one of the key problems that confront today's P2P systems. What makes this problem particularly difficult is the unique set of challenges that P2P systems pose: large populations, high turnover, asymmetry of interest, collusion, zero-cost identities, and traitors [RobustIncentives]. Many incentive mechanisms have been proposed in the literature to promote cooperation and system robustness of a P2P system. The goal of this contribution however is not to choose a particular incentive mechanism to specify in the P2P streaming protocol, but instead is to analyze the common parameters that are essential for various incentive mechanisms, and propose to incorporate these pro-incentive parameters in information exchanges in the P2P streaming protocols. 2. Document Conventions 2.1. Notational Conventions The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119] 2.2. Terminology The draft uses the terms defined in [draft-gu-ppsp-tracker-protocol] The draft also uses some new terms, as defined below. Piece: equivalent to Chunk, a basic unit of partitioned stream, which is used by a peer for the purpose of storage, advertisement and exchange among peers. As the term "Piece" has been widely used in the literature, Piece and Chunk are used interchangably in this draft. Unchoking: uploading data to a selected peer in a P2P system. Rarest First: When selecting which piece to start downloading next, peers generally download pieces which the fewest of their own peers have first Free Riding: downloading data from peers without uploading any data to peers. Tit-for-Tat: peers exchange chunks preferentially with other peers with whom they have successfully exchanged chunks in the past at high Zeng Expires December 31, 2010 [Page 3] Internet-Draft Pro-incentive Parameters June 2010 bandwidth Discount Parameter: the weight of the next move compared to the current one. It measures the degree to which the payoff of each move is discounted relative to the previous move. Honest Piece Revelation: peers truthfully reveal which pieces they have. Under-Reporting: peers not revealing some pieces they have in order to make profit. 3. Incentives in P2P Systems Several works have demonstrated the limitations of P2P protocols in the presence of selfish or malicious users [RobustIncentives, Free- riding]. Rewarding peer contributions has been suggested to overcome these limitations, e.g., in [ContributionAware, RobustIncentives]. A well known example is the tit-for-tat mechanism used in BitTorrent [BitTorrent]. 3.1. Measurement of peer contribution A typical metric for measuring peer's contribution is the amount of upload a peer has contributed. For example, BitTorrent uses a bilateral mechanism called tit-for-tat. The amount of data a peer would upload to another peer depends on how much it has downloaded from that peer in the past. Despite its pro-incentive approach, recent study [prTorrent] has empirically shown that BitTorrent is vulnerable to strategic manipulation by its constituent peers in a swarm. For example, the Discount Parameter (DP) attack is an incentive threat that exploits the core of BitTorrent cooperation - the tit-for-tat based unchoking. The weight (or importance) of the next move compared to the current is called Discount Parameter, because it measures the degree to which the payoff of each move is discounted relative to the previous move. If the DP is small, peers might defect and not worry about future consequences. In BitTorrent-like file sharing systems, piece rarity is a DP. This means if the pieces available for download to peer B from A are not lucrative enough (possibly because B can get them from somewhere else at cheaper uploads, i.e. the piece rarity of pieces that A holds are low), then B has sufficient incentive to defect. Defect would mean that B will not upload to A in the "tat" phase, denying A one round of legitimate download. Then B will break connection with A, leaving A with no opportunity to snub him. Zeng Expires December 31, 2010 [Page 4] Internet-Draft Pro-incentive Parameters June 2010 Moreover, Honest Piece Revelation and Free-Riding is becoming an increasing concern. As explained in [BTAuction], Honest Piece Revelation is not enforced in BitTorrent and peers have sufficient incentive to stray from truthfulness. The results in [BTAuction] indicate that selfish BitTorrent clients can benefit from under- reporting pieces. Under reported pieces keep getting rarer in the swarm and therefore, the demand of peers holding those pieces increases due to the rarest first piece selection approach. It has been discovered in [prTorrent] that if a colluding group of peers are involved in under-reporting over a considerable period to improve their demand in the swarm, it might lead the whole swarm into premature starvation in which all peers have all the pieces of a file, except a few. The findings in [prTorrent] indicate that it is the orthogonal treatment of piece rarity and unchoking that has encouraged strategic manipulation enabling unfair maximization of incentives in p2p systems. Note that BitTorrent uses rarest first approach for piece selection but not for peer selection (unchoking). The prTorrent protocol [prTorrent] unifies a Piece Rarity factor with the BitTorrent Unchoking Algorithm, i.e., peer selection for unchoking not only depends on the uploading bandwidth of the candidate peers, but also how valuable the pieces they have uploaded are. It is shown how strategic formulation of the Piece Rarity parameter can optimize incentives in a swarm, and help its constituent peers in achieving the equilibrium facilitating truly co-operative behavior. The Piece Rarity factor depends on a number of other variables measured at the piece, peer and swarm levels, as summarized below. o the global availability (in all swarms of the tracker): the high availability of a piece outside the swarm may result in peers leaving the swarm. o local availability (in the target swarm) of a piece: a rarer downloaded piece has more value to the swarm o number of upload slots a candidate peer has: long term benefit can be expected from a peer with more uploading potential o the completion factor (i.e., the ratio of the number of pieces of the file that a peer has to total number of pieces of that file) of the candidate peer: a peer with high completion factor is a good one to maintain a good upload/download relation with. o the contention in the swarm (i.e., the ratio of total number of peers to total number of seeds): high contention implies more strategic value of a piece. Zeng Expires December 31, 2010 [Page 5] Internet-Draft Pro-incentive Parameters June 2010 Several studies (e.g., [RobustIncentives, Incentives, Peer-assisted]) however have pointed out the limitations of bilateral mechanisms (e.g., in the case of asymmetry of interest), and make the case for designing more global contribution-aware mechanisms. This is especially an issue in real-time streaming. Many systems that distribute content with the help of P2P overlays measure peer contribution and incentivize participation. Peers who contribute more are rewarded with better performance via different mechanisms such as higher priority in the distribution overlay (e.g., [ContributionAware, Collusion]) or priority service through server- assisted downloads (e.g., [CooperativeCD]), or discount coupons [CooperativeCD]). Such systems are referred to as contribution aware peer-assisted content distribution systems. A typical metric to measure peer's contribution to the swarm is again the amount of upload a peer has contributed to the swarm (as opposed to individual peers). 4. Pro-incentive Protocol Parameters The above analysis suggests that it is important for a p2p streaming protocol to support the exchange/report of necessary information based on which a p2p streaming system can optimize incentives in a swarm to provide robust and improved services. Some of the basic pro-incentive parameters are listed below. o no_upload_slots: a peer's upload bandwidth (i.e., number of upload slots a peer has). o bytes_uploaded: total amount of data that a peer has uploaded o bytes_downloaded: total amount of data that has been downloaded from a peer o chunk_nos: total number of chunks of a file that a peer has. o seed_nos: total number of seeds. o peer_nos: total number of peers. o chunk_copies_swarm: chunk availability, i.e., total number of copies of a chunk available in the swarm. Exchanges of these parameters between tracker and peers SHALL be supported in the tracker protocol, e.g., through the methods defined in [draft-gu-ppsp-tracker-protocol]. A subset, e.g., a peer's no_upload_slots and the chunk_nos of a file that a peer has, SHOULD be supported in the peer protocol. Some of these parameters (e.g., Zeng Expires December 31, 2010 [Page 6] Internet-Draft Pro-incentive Parameters June 2010 no_upload_slots) may have already been specified in [draft-gu-ppsp-tracker-protocol] for the purpose of facilitating optimization of the system performance. 5. Acknowledgements The author would like to thank the following people for their help and comments: Robins George and Yingjie Gu. 6. IANA Considerations This draft includes no request to IANA. 7. Security Considerations Trustworthiness of these pro-incentive parameters is critical to the effectiveness of the incentive mechanisms. Security will be considered in future versions of this draft. 8. References 8.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. 8.2. Informative References [BTAuction] D. Levin, K. LaCurts, N. Spring, and B. Bhattacharjee, "BitTorrent is an Auction: Analyzing and Improving BitTorrent's Incentives", ACM Special Interest Group on Data Communication, 2008. [BitTorrent] B. Cohen, "Incentives build robustness in BitTorrent", in Proc. of P2P-Econ, Berkeley, California, USA, June 2003. [Collusion] Q. Lian, Z. Zhang, M. Yang, B. Y. Zhao, Y. Dai, and X. Li, "An empirical study of collusion behavior in the Maze P2P file-sharing system", In Proc. ICDCS, 2007. [ContributionAware] Zeng Expires December 31, 2010 [Page 7] Internet-Draft Pro-incentive Parameters June 2010 Y. Sung, M. Bishop, and S. Rao, "Enabling Contribution Awareness in an Overlay Broadcasting System", In Proc. ACM SIGCOMM, 2006. [CooperativeCD] M. Sirivianos, J. H. Park, X. Yang, and S. Jarecki, "Dandelion: Cooperative Content Distribution with Robust Incentives", In Proc. USENIX ATC, 2007. [Free-riding] M. Sirivianos, J. H. Park, R. Chen, and X. Yang, "Free- riding in BitTorrent networks with the large view exploit", In Proc. IPTPS, 2007. [Incentives] K. Lai, M. Feldman, I. Stoica, and J. Chuang, "Incentives for cooperation in peer-to-peer networks", In Proc. P2P Econ, 2004. [Peer-assisted] C. Aperjis, M. J. Freedman, and R. Johari, "Peer-Assisted Content Distribution with Prices", In Proc. CoNeXT, 2008. [RobustIncentives] M. Feldman, K. Lai, I. Stoica, and J. Chuang, "Robust Incentive Techniques for Peer-to-Peer Networks", In Proc. ACM EC, 2004. [draft-gu-ppsp-tracker-protocol] Gu, Y., Bryan, D., Zhang, Y., and H. Liao, "Tracker Protocol", (IETF Work in Progress) February 2010, . [prTorrent] Roy, S. D. and W. Zeng, "prTorrent: On Establishment of Piece Rarity in the BitTorrent Unchoking Algorithm", International Conference on Peer-to-Peer Computing (P2P2009), September 2009. Zeng Expires December 31, 2010 [Page 8] Internet-Draft Pro-incentive Parameters June 2010 Author's Address Wenjun Zeng Huawei Technologies US Phone: +1 214 538 7823 Email: zengw@huawei.com Zeng Expires December 31, 2010 [Page 9]