PPSP W. Zeng Internet-Draft Y. Gu Intended status: Informational Huawei Technologies Expires: April 25, 2011 October 22, 2010 P2P Streaming Protocol Pro-incentive Parameters draft-zeng-ppsp-protocol-pro-incentive-para-01 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 proposed in [draft-gu-ppsp-peer-protocol]. 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 April 25, 2011. 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 & Gu Expires April 25, 2011 [Page 1] Internet-Draft ppsp-pro-incentive-para October 2010 the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. This document may contain material from IETF Documents or IETF Contributions published or made publicly available before November 10, 2008. The person(s) controlling the copyright in some of this material may not have granted the IETF Trust the right to allow modifications of such material outside the IETF Standards Process. Without obtaining an adequate license from the person(s) controlling the copyright in such materials, this document may not be modified outside the IETF Standards Process, and derivative works of it may not be created outside the IETF Standards Process, except to format it for publication as an RFC or to translate it into languages other than English. 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 4.1. Suggested Changes in the Tracker Protocol . . . . . . . . 7 4.2. Suggested Changes in the Peer Protocol . . . . . . . . . . 7 5. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 8 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8 7. Security Considerations . . . . . . . . . . . . . . . . . . . 8 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 9 8.1. Normative References . . . . . . . . . . . . . . . . . . . 9 8.2. Informative References . . . . . . . . . . . . . . . . . . 9 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 10 Zeng & Gu Expires April 25, 2011 [Page 2] Internet-Draft ppsp-pro-incentive-para October 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 & Gu Expires April 25, 2011 [Page 3] Internet-Draft ppsp-pro-incentive-para October 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 & Gu Expires April 25, 2011 [Page 4] Internet-Draft ppsp-pro-incentive-para October 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 & Gu Expires April 25, 2011 [Page 5] Internet-Draft ppsp-pro-incentive-para October 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][Contracts]) 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). Approximate equilibria has also been proposed in [FlightPath] to guide how one designs systems to incentivize selfish (or rational) peers to obey protocols. 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 Zeng & Gu Expires April 25, 2011 [Page 6] Internet-Draft ppsp-pro-incentive-para October 2010 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.,no_upload_slots) have already been proposed in [draft-gu-ppsp-tracker-protocol] for the purpose of facilitating optimization of the system performance. 4.1. Suggested Changes in the Tracker Protocol It is recommended that exchange of the following statistics be supported in the tracker protocol, e.g., by adding them to Table 3 (Section 4.1.10.1) in the proposed tracker protocol [draft-gu-ppsp-tracker-protocol]. +-----------------+-------------------------------------------------+ | XML Value | Definitions/Description | +-----------------+-------------------------------------------------+ | BytesUploaded | Total amount of data that a reporting peer has | | | uploaded. This is to be reported by a peer to | | | the tracker. | | ChunkMAP | Indicates which chunks of a file that a peer | | | has. This is to be reported by a peer to the | | | tracker. | | SeedNumber | Total number of seeds in the swarm. This is to | | | be updated by the tracker to peers periodically | | | or upon request by a peer. | | PeerNumber | Total number of peers in the swarm. This is to | | | be updated by the tracker to peers periodically | | | or upon request by a peer. | | ChunkCopies | Total number of copies of a chunk available in | | | the swarm. Each ChunkCopies should be paired | | | with a ChunkID. This is to be updated by the | | | tracker to peers periodically or upon request | | | by a peer. | | BytesDownloaded | Total amount of data reported by a peer that | | | has been downloaded from a different peer. | | | Each BytesDownloaded should be paired with a | | | PeerID. This is to be reported by a peer to | | | the tracker. | +-----------------+-------------------------------------------------+ Table 1: Additional Property Types to be supported in the tracker protocol 4.2. Suggested Changes in the Peer Protocol It is recommended that exchange of the following statistics be supported in the peer protocol. Zeng & Gu Expires April 25, 2011 [Page 7] Internet-Draft ppsp-pro-incentive-para October 2010 +-------------+-----------------------------------------------------+ | XML Value | Definitions/Description | +-------------+-----------------------------------------------------+ | UploadBW | A peer's upload bandwidth (i.e., number of upload | | | slots a peer has). | | ChunkNumber | Total number of chunks of a file that a peer has. | | | This is necessary in case ChunkMAP reported is not | | | a complete map. | | ChunkMAP | Indicates which chunks of a file that a peer has. | +-------------+-----------------------------------------------------+ Table 2: Additional Property Types to be supported in the peer protocol 5. Acknowledgements The author would like to thank the following people for their help and comments: Robins George, Richard Yang, and Suman D. Roy. 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. For example, ChunkMap defined above may be essential, and may need to be accurate. The P2P system should be designed in a way such that a peer will have the incentive to report truthfully its ChunkMap (otherwise it may penalize itself, as in the case of under-reporting addressed in [prTorrent]). Furthermore, both the amount of upload and download should be reported to the tracker to allow the tracker to check if there is any inconsistency between the upload and download report, and establish an appropriate credit/trust system. Alternatively, exchange of cryptographic receipts signed by receiving peers can be used to attest to the upload contribution of a peer to the swarm, as was suggested in [Contracts]. Security will be further considered in future versions of this draft. 8. References Zeng & Gu Expires April 25, 2011 [Page 8] Internet-Draft ppsp-pro-incentive-para October 2010 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] Levin, D., LaCurts, K., Spring, N., and B. Bhattacharjee, "BitTorrent is an Auction: Analyzing and Improving BitTorrent's Incentives", ACM Special Interest Group on Data Communication , 2008. [BitTorrent] Cohen, B., "Incentives build robustness in BitTorrent", Proc. of P2P-Econ, Berkeley, California, USA , June 2003. [Collusion] Lian, Q., Zhang, Z., Yang, M., Zhao, B., Dai, Y., and X. Li, "An empirical study of collusion behavior in the Maze P2P file-sharing system", In Proc. ICDCS , 2007. [Contracts] Piatek, M., Krishnamurthy, A., Venkataramani, A., Yang, R., Zhang, D., and A. Jaffe, "Contracts: Practical Contribution Incentives for P2P Live Streaming", USENIX Symposium on Networked Systems Design and Implementation (NSDI) , April 2010. [ContributionAware] Sung, Y., Bishop, M., and S. Rao, "Enabling Contribution Awareness in an Overlay Broadcasting System", In Proc. ACM SIGCOMM , 2006. [CooperativeCD] Sirivianos, M., Park, J., Yang, X., and S. Jarecki, "Dandelion: Cooperative Content Distribution with Robust Incentives", In Proc. USENIX ATC , 2007. [FlightPath] Li, H., Clement, A., Marchetti, M., Kapritsos, M., Robison, L., Alvisi, L., and M. Dahlin, "FlightPath: Obedience vs. Choice in Cooperative Services", the USENIX Symposium on Operating System Design and Implementation (OSDI) , Dec. 2008. [Free-riding] Sirivianos, M., Park, J., Chen, R., and X. Yang, "Free- Zeng & Gu Expires April 25, 2011 [Page 9] Internet-Draft ppsp-pro-incentive-para October 2010 riding in BitTorrent networks with the large view exploit", In Proc. IPTPS , 2007. [Incentives] Lai, K., Feldman, M., Stoica, I., and J. Chuang, "Incentives for cooperation in peer-to-peer networks", In Proc. P2P Econ , 2004. [Peer-assisted] Aperjis, C., Freedman, M., and R. Johari, "Peer-Assisted Content Distribution with Prices", In Proc. CoNeXT , 2008. [RobustIncentives] Feldman, M., Lai, K., Stoica, I., and J. Chuang, "Robust Incentive Techniques for Peer-to-Peer Networks", In Proc. ACM EC , 2004. [draft-gu-ppsp-peer-protocol] Gu, Y. and D. Bryan, "Peer Protocol", (IETF Work in Progress) http:// tools.ietf.org/html/draft-gu-ppsp-peer-protocol-00, July 2010. [draft-gu-ppsp-tracker-protocol] Gu, Y., Bryan, D., Zhang, Y., and H. Liao, "Tracker Protocol", (IETF Work in Progress) http:// tools.ietf.org/html/draft-gu-ppsp-tracker-protocol-01, July 2010. [prTorrent] Roy, S. and W. Zeng, "prTorrent: On Establishment of Piece Rarity in the BitTorrent Unchoking Algorithm", International Conference on Peer-to-Peer Computing (P2P2009) , September 2009. Authors' Addresses Wenjun (Kevin) Zeng Huawei Technologies USA Email: zengw@huawei.com Zeng & Gu Expires April 25, 2011 [Page 10] Internet-Draft ppsp-pro-incentive-para October 2010 Yingjie Gu Huawei Technologies No.101 Software Avenue Nanjing, Jiangsu Province 210012 P.R. China Email: guyingjie@huawei.com Zeng & Gu Expires April 25, 2011 [Page 11]