Understanding and Improving Piece-Related Algorithms in the BitTorrent Protocol

Piece-related algorithms, including piece revelation, selection, and queuing, play a crucial role in the BitTorrent (BT) protocol, because the BT system can be viewed as a market where peers trade their pieces with one another. During the piece exchanging, a peer selects some pieces revealed by neighbors, and queues them up for downloading. In this paper, we provide a deep understanding of these algorithms, and also propose some improvements to them. Previous study has shown that the piece revelation strategy is vulnerable to under-reporting. We provide a game-theoretic analysis for this selfish gaming, and propose a distributed credit method to prevent it. Existing piece selection strategies, though long believed to be good enough, may fail to balance piece supply and demand. We propose a unified strategy to shorten the download time of peers by applying utility theory. The design of the piece queuing algorithm has a conflict with that of piece selection strategy, because it is not possible to assume that the queued requests for a selected piece can always be available on multiple neighbors. We give a possible fix to address the conflict by allowing peers to dynamically manage their unfulfilled requests. To evaluate the performance of the proposed algorithms, we run several experiments in a live swarm. Our primary results show that they can achieve fast individual and system-wide download time.