Optimality Analysis of Locality-aware Tit-for-Tat-based P2P File Distribution

Yohei Nishi

Master's Thesis, 2020

Abstract

In the current Internet, periodic software update is essential to maintain systems secure from malicious attacks. In case of proliferated software, e.g., Operating System (OS), the distribution server for update tends to be a bottleneck, due to the concentration of users' requests. To tackle this problem, several systems, e.g., Windows Update, have been applying the Peer-to-Peer (P2P) file distribution technique where clients called peers upload retrieved fragments of the original file, i.e., pieces, to other peers. However, peers may not be willing to upload pieces to others, due to communication overhead. BitTorrent first adopted the Tit-for-Tat (TFT) strategy in game theory, which encourages peers to exchange an equivalent number of pieces among each pair of peers. In recent years, the optimality of TFT-based P2P content distribution, i.e., file distribution and streaming, has been analyzed with the help of Integer Linear Programming (ILP). In this thesis, we focus on the fact that communication overhead inside group, e.g., LAN or AS, is much less than that of between groups, and modeled the locality-aware TFT-based P2P file distribution where the TFT constraint is relaxed for intra-group communications. We further formulate the optimal piece flow determination problem as ILP in the similar way to the existing work. Through numerical results, we show that the locality-aware TFT-based P2P file distribution can achieve quasi-optimal average file download time when the upload capacity of the server is bottleneck and the number of groups is moderate.

Downloads

    Text Reference

    Yohei Nishi, Optimality Analysis of Locality-aware Tit-for-Tat-based P2P File Distribution, Master's Thesis, March 2020.

    BibTex Reference

    @mastersthesis{nishi20mthesis,
    author = "Nishi, Yohei",
    title = "Optimality {{Analysis}} of {{Locality-aware Tit-for-Tat-based P2P File Distribution}}",
    year = "2020",
    month = "March",
    school = "Nara Institute of Science and Technology"
}