Guaranteeing Performance through Fairness in Peer-to-Peer File-Sharing and Streaming Systems

Ph.D. Thesis, Department of Computer Science, Columbia University, July 2010

Abstract

Over the past decade, Peer-to-Peer (P2P) file-sharing and streaming systems have evolved as a cheap and effective technology in distributing content to users. Guar- anteeing a level of performance in P2P systems is, therefore, of utmost importance. However, P2P file-sharing and streaming applications suffer from a fundamental prob- lem of unfairness, where many users have a tendency to free-ride by contributing little or no upload bandwidth while consuming much download bandwidth. By taking away an unfair share of resources, free-riders deteriorate the quality of service experienced by other users, by causing slower download times in P2P file-sharing networks and higher stream updates’ miss rates in P2P streaming networks. Previous attempts at addressing fair bandwidth allocation in P2P, such as BitTorrent-like systems, suf- fer from slow peer discovery, inaccurate predictions of neighboring peers’ bandwidth allocations, under-utilization of bandwidth, and complex parameter tuning. We present FairTorrent, a new deficit-based distributed algorithm that accurately rewards peers in accordance with their contribution in a file-sharing P2P system. In a nutshell, a FairTorrent peer uploads the next data block to a peer to whom it owes the most data. FairTorrent is resilient to exploitation by free-riders and strategic peers, is simple to implement, requires no bandwidth over-allocation, no prediction of peers’ rates, no centralized control, and no parameter tuning. We implemented FairTorrent in a BitTorrent client without modifications to the BitTorrent protocol, and evaluated its performance against other widely-used BitTorrent clients using various scenarios including live BitTorrent swarms. Our results show that FairTorrent provides up to two orders of magnitude better fairness, up to five times better download performance for contributing peers, and 60-100% better performance on average in live BitTorrent swarms. We show analytically that for a number of upload capacity distributions, in an n-node FairTorrent network, no peer is ever owed more than O(log n) data blocks with high probability. Achieving fair bandwidth allocation in a P2P streaming scenario is even more difficult, as it comes with an additional constraint: each stream update must be received before its playback deadline. P2P live streaming systems require global re- source over-provisioning to deliver adequate streaming performance. When there is not enough bandwidth to accommodate all users for a particular stream, such as due to free-riders or low-contributing peers, all users, including high-contributing peers, observe poor performance. We present FairStream, a new P2P streaming system that delivers a good quality stream to peers that upload data at a rate above the stream rate, even in the presence of free-riders or malicious users. FairStream achieves this with three mechanisms. First, it provides a new peer reply policy framework that enables file sharing incentive mechanisms to be adapted for streaming. Second, it uses this framework to incorporate a deficit-based peer reply policy that enables each peer to reply first to the neighbor to whom it owes the most data as measured by a deficit counter. Third, it introduces a collusion-resistant mechanism to ensure ef- fective data distribution of a stream despite a large fraction of free-riders who do not forward received data. We prove that FairStream is resilient to free-riders and rewards peers with streaming performance correlated with their contributions. We have also implemented FairStream as a BitTorrent client and evaluated its perfor- mance against other popular streaming systems. Our results on PlanetLab show that FairStream, similar to other systems, provides good quality streaming performance when resources are over-provisioned, but it also provides orders of magnitude better streaming performance for peers uploading above the stream rate when resources are constrained, in the presence of free-riders and low-contributing peers.

PDF

shermanthesis

Columbia University Department of Computer Science