Optimal Peer-Assisted File Distribution: Single and Multi-Class Problems

CDNs, peer-assisted file distribution has become a prominent Internet application, both in terms of user popularity and traffic volumes. We consider the following fundamental problem for peer-assisted file distribution. There are seed nodes, each of which has a copy of the file, and leecher nodes, each of which wants a copy the file. The goal is to distribute the file to all the leechers – with the assistance of the upload capacity of the leechers – in order to minimize the time to get the file to all the leechers (the distribution time). We obtain explicit expressions for the minimum distribution time of a general heterogeneous peer-assisted file distribution system. Derived with fluid-flow arguments, the expressions are in terms of the file size, the seeds ’ upload rates and the leechers ’ upload and download rates. We demonstrate the utility of the result by comparing the optimal distribution time with the measured distribution time when BitTorrent is used to distribute a file from a seed to ten leechers. In the second part of this paper, we explore file distribution with application-level differentiated service. Specifically, we suppose there are two classes of leechers, with the goal being to get the file as quickly as possible to all the first-class leechers. We again derive explicit expressions for the distribution time, and argue that differentiated service quality can be provisioned at the application level. Index Terms — P2P, BitTorrent, file distribution, minimum distribution time. I