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.

PDF file

In: 2009 IEEE International Symposium on Information Theory

Publisher: IEEE
© 2008 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. http://www.ieee.org/

Details