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] (Gu, Y., Bryan, D., Zhang, Y., and H. Liao, “Tracker Protocol,” July 2010.), and in the future in the peer protocol proposed in [draft‑gu‑ppsp‑peer‑protocol] (Gu, Y. and D. Bryan, “Peer Protocol,” July 2010.).

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 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
2.  Document Conventions
    2.1.  Notational Conventions
    2.2.  Terminology
3.  Incentives in P2P Systems
    3.1.  Measurement of peer contribution
4.  Pro-incentive Protocol Parameters
    4.1.  Suggested Changes in the Tracker Protocol
    4.2.  Suggested Changes in the Peer Protocol
5.  Acknowledgements
6.  IANA Considerations
7.  Security Considerations
8.  References
    8.1.  Normative References
    8.2.  Informative References
§  Authors' Addresses

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] (Feldman, M., Lai, K., Stoica, I., and J. Chuang, “Robust Incentive Techniques for Peer-to-Peer Networks,” 2004.).

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] (Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels,” March 1997.).

2.2.  Terminology

The draft uses the terms defined in [draft‑gu‑ppsp‑tracker‑protocol] (Gu, Y., Bryan, D., Zhang, Y., and H. Liao, “Tracker Protocol,” July 2010.).

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 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] (Feldman, M., Lai, K., Stoica, I., and J. Chuang, “Robust Incentive Techniques for Peer-to-Peer Networks,” 2004.) [Free‑riding] (Sirivianos, M., Park, J., Chen, R., and X. Yang, “Free-riding in BitTorrent networks with the large view exploit,” 2007.). Rewarding peer contributions has been suggested to overcome these limitations, e.g., in [ContributionAware] (Sung, Y., Bishop, M., and S. Rao, “Enabling Contribution Awareness in an Overlay Broadcasting System,” 2006.)[RobustIncentives] (Feldman, M., Lai, K., Stoica, I., and J. Chuang, “Robust Incentive Techniques for Peer-to-Peer Networks,” 2004.). A well known example is the tit-for-tat mechanism used in BitTorrent [BitTorrent] (Cohen, B., “Incentives build robustness in BitTorrent,” June 2003.).

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] (Roy, S. and W. Zeng, “prTorrent: On Establishment of Piece Rarity in the BitTorrent Unchoking Algorithm,” September 2009.) 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.

Moreover, Honest Piece Revelation and Free-Riding is becoming an increasing concern. As explained in [BTAuction] (Levin, D., LaCurts, K., Spring, N., and B. Bhattacharjee, “BitTorrent is an Auction: Analyzing and Improving BitTorrent's Incentives,” 2008.), Honest Piece Revelation is not enforced in BitTorrent and peers have sufficient incentive to stray from truthfulness. The results in [BTAuction] (Levin, D., LaCurts, K., Spring, N., and B. Bhattacharjee, “BitTorrent is an Auction: Analyzing and Improving BitTorrent's Incentives,” 2008.) 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] (Roy, S. and W. Zeng, “prTorrent: On Establishment of Piece Rarity in the BitTorrent Unchoking Algorithm,” September 2009.) 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] (Roy, S. and W. Zeng, “prTorrent: On Establishment of Piece Rarity in the BitTorrent Unchoking Algorithm,” September 2009.) 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] (Roy, S. and W. Zeng, “prTorrent: On Establishment of Piece Rarity in the BitTorrent Unchoking Algorithm,” September 2009.) 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.

• 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.
• local availability (in the target swarm) of a piece: a rarer downloaded piece has more value to the swarm
• number of upload slots a candidate peer has: long term benefit can be expected from a peer with more uploading potential
• 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.
• 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.

Several studies (e.g., [RobustIncentives] (Feldman, M., Lai, K., Stoica, I., and J. Chuang, “Robust Incentive Techniques for Peer-to-Peer Networks,” 2004.)[Incentives] (Lai, K., Feldman, M., Stoica, I., and J. Chuang, “Incentives for cooperation in peer-to-peer networks,” 2004.)[Peer‑assisted] (Aperjis, C., Freedman, M., and R. Johari, “Peer-Assisted Content Distribution with Prices,” 2008.)) 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] (Sung, Y., Bishop, M., and S. Rao, “Enabling Contribution Awareness in an Overlay Broadcasting System,” 2006.)[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,” 2007.)[Contracts] (Piatek, M., Krishnamurthy, A., Venkataramani, A., Yang, R., Zhang, D., and A. Jaffe, “Contracts: Practical Contribution Incentives for P2P Live Streaming,” April 2010.)) or priority service through server- assisted downloads (e.g., [CooperativeCD] (Sirivianos, M., Park, J., Yang, X., and S. Jarecki, “Dandelion: Cooperative Content Distribution with Robust Incentives,” 2007.)), or discount coupons [CooperativeCD] (Sirivianos, M., Park, J., Yang, X., and S. Jarecki, “Dandelion: Cooperative Content Distribution with Robust Incentives,” 2007.)). 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] (Li, H., Clement, A., Marchetti, M., Kapritsos, M., Robison, L., Alvisi, L., and M. Dahlin, “FlightPath: Obedience vs. Choice in Cooperative Services,” Dec. 2008.) 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.

• no_upload_slots: a peer's upload bandwidth (i.e., number of upload slots a peer has).
• bytes_uploaded: total amount of data that a peer has uploaded
• bytes_downloaded: total amount of data that has been downloaded from a peer
• chunk_nos: total number of chunks of a file that a peer has.
• seed_nos: total number of seeds.
• peer_nos: total number of peers.
• 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] (Gu, Y., Bryan, D., Zhang, Y., and H. Liao, “Tracker Protocol,” July 2010.). 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.,no_upload_slots) have already been proposed in [draft‑gu‑ppsp‑tracker‑protocol] (Gu, Y., Bryan, D., Zhang, Y., and H. Liao, “Tracker Protocol,” July 2010.) 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] (Gu, Y., Bryan, D., Zhang, Y., and H. Liao, “Tracker Protocol,” July 2010.).

4.2.  Suggested Changes in the Peer Protocol

It is recommended that exchange of the following statistics 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] (Roy, S. and W. Zeng, “prTorrent: On Establishment of Piece Rarity in the BitTorrent Unchoking Algorithm,” September 2009.)). 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] (Piatek, M., Krishnamurthy, A., Venkataramani, A., Yang, R., Zhang, D., and A. Jaffe, “Contracts: Practical Contribution Incentives for P2P Live Streaming,” April 2010.). Security will be further considered in future versions of this draft.

8.  References

8.1. Normative References

8.2. Informative References

Authors' Addresses