Analysis of Peer-to-Peer File Dissemination amongst Users of Different Upload Capacities

In recent years, overlay networks have proven an effective way of disseminating a file from a single source to a group of end users via the Internet. A number of algorithms and protocols have been suggested, implemented and studied. In particular, much attention has been given to peer-to-peer (P2P) systems such as BitTorrent, Slurpie, SplitStream and Bullet. The key idea is that the file is divided into M parts of equal size and that a given user may download any one of these either from the server or from a peer who has previously downloaded it. More recently, a scheme based on network coding has been suggested. Here, users download linear combinations of file parts rather than individual file parts. Performance evaluation of such systems has typically been limited to comparing one system relative to another. Our results give the minimal time required to fully disseminate a file of M parts from a server to N end users. In the scheduling literature this completion time is referred to as makespan. We thus provide a lower bound which can be used as a performance benchmark for any P2P file dissemination system.