Analysis of Optimal Scheduling in Tit-for-Tat-Based P2P File Distribution

Masashi HASEGAWA  Masahiro SASABE  Tetsuya TAKINE  

Publication
IEICE TRANSACTIONS on Communications   Vol.E97-B   No.12   pp.2650-2657
Publication Date: 2014/12/01
Online ISSN: 1745-1345
Type of Manuscript: Special Section PAPER (Special Section on Technologies and Architectures for Improving Scalability, Reliability, and Robustness for Future Information Networks)
Category: 
Keyword: 
P2P file distribution,  tit-for-tat strategy,  analysis of optimal scheduling,  integer linear programming problem (ILP problem),  

Full Text: PDF(674KB)
>>Buy this Article


Summary: 
Peer-to-Peer (P2P) file distribution systems can efficiently disseminate massive contents, such as disk images of operating systems, from a server to many users in a piece-by-piece manner. In particular, the BitTorrent protocol optimizes each peer's download speed by applying the tit-for-tat (TFT) strategy, where each peer preferentially uploads piece(s) to peer(s) from which it can download missing pieces faster. To the best of our knowledge, however, the optimality of TFT-based P2P file distribution has not been studied sufficiently. In this paper, we aim to understand the optimal scheduling in TFT-based P2P file distribution. First, we develop a discrete-time model of TFT-based P2P file distribution and formulate its optimal scheduling as a two-step integer linear programming problem. The first step is to minimize the average file retrieval time among peers, and the second step is to improve fairness among peers. We analyze the optimal solution obtained by the existing solver and reveal the characteristics of the optimal scheduling. Specifically, we show that it is crucial to distribute pieces from the server indirectly to peers with large upload capacity via those with small upload capacity.