Analysis of minimum distribution time of tit-for-tat-based P2P file distribution: Linear programming based approach

In recent years, software update has become one of the essential functions in the current Internet to maintain devices safe from a various types of attacks. If the number of software users is enormous, distribution servers tend to be bottlenecks, due to the access concentration. To alleviate this problem, several systems (e.g., Windows update) have started applying peer-to-peer (P2P) file distribution where clients (peers) assist the distribution by uploading retrieved fragments of the file (i.e., pieces) to others. However, it has been pointed out that many peers tend to be free riders, which are not willing to upload pieces to others, so as to save their upload capacities. Tit-for-tat (TFT) strategy in game theory is one of the practical mechanisms to build reciprocity between each pair of peers. In this paper, we first develop a linear program (LP) as a tool to analyze the minimum distribution time of the TFT-based P2P file distribution under arbitrary upload capacity distribution. Focusing on the fact that access links can be categorized into multiple classes in the current Internet, we further extend the general formulation to multi-class formulation, which does not depend on the system scale. Through numerical results, we reveal the fundamental characteristics of the TFT-based P2P file distribution.