  Peer-to-peer (P2P) overlay networks such as BitTorrent and Avalanche are
increasingly used for disseminating potentially large files from a server to
many end users via the Internet. The key idea is to divide the file into many
equally-sized parts and then let users download each part (or, for network
coding based systems such as Avalanche, linear combinations of the parts)
either from the server or from another user who has already downloaded it.
However, their performance evaluation has typically been limited to comparing
one system relative to another and typically been realized by means of
simulation and measurements. In contrast, we provide an analytic performance
analysis that is based on a new uplink-sharing version of the well-known
broadcasting problem. Assuming equal upload capacities, we show that the
minimal time to disseminate the file is the same as for the simultaneous
send/receive version of the broadcasting problem. For general upload
capacities, we provide a mixed integer linear program (MILP) solution and a
complementary fluid limit solution. We thus provide a lower bound which can be
used as a performance benchmark for any P2P file dissemination system. We also
investigate the performance of a decentralized strategy, providing evidence
that the performance of necessarily decentralized P2P file dissemination
systems should be close to this bound and therefore that it is useful in
practice.
