Abstract: We consider the problem of a source distributing a large file, such as a software package or multimedia content, to a large number of clients in the least overall time. We first tackle this under the assumption that the order of data delivery is immaterial, and describe our results in this talk. We obtain a cooperative algorithm analytically, and prove that it is optimal for a simple homogeneous client model. This algorithm is at least twice as fast as the well-known multicast tree method. We also explore, by simulation, a simple randomized version, and find that this algorithm performs surprisingly close to optimal. We then consider a scenario with heterogeneous client bandwidths and design an algorithm to handle this case.

Next, we change our assumptions about client scenarios, and this talk briefly summarizes our work in these areas. For a non-cooperative client scenario, we propose algorithms based on "barter" and find that certain versions perform almost as well as the optimal cooperative algorithm. We also explore BitTorrent's performance via simulation, since it is the closest related work. With homogeneous clients, we find that BitTorrent's completion time is more than twice that of an optimal algorithm, but can be be improved by careful tuning. Finally, we propose a framework that allows applications to customize the data delivery order of our content distribution algorithms.