The Delay Region for P2P File Transfer

Yunnan Wu, Y. Charlie Hu, Jin Li, and Philip A. Chou

Abstract

Motivated by P2P file transfer applications (e.g.,

BitTorrent) on the Internet, this paper considers the problem

of delivering a file from a server to multiple receivers in a P2P

network. Each receiver has an associated delay in receiving the

file. We aim at understanding the optimal delay region, i.e., the

set of all possible delay vectors that can be achieved. Previous

work has addressed the problem of delivering the file to all

receivers in minimum amount of time (equivalently, minimizing

the maximum delay to the receivers), assuming peer uplinks are

the only bottleneck in the network. This paper shows that it is in

fact possible to significantly reduce the average delay at a slight

increase in the maximum delay. Moreover, given an order at

which the receivers finish downloading, the optimal delay region

is characterized by a system of linear inequalities. Any point

in the optimal delay region can be achieved by linear network

coding. We also propose a simple routing scheme that has nearoptimal

empirical performance.

Details

Publication typeInproceedings
Published in2009 IEEE International Symposium on Information Theory
PublisherIEEE
> Publications > The Delay Region for P2P File Transfer