Description
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 possible time. We first tackle it under the assumption that the order of data delivery is immaterial. 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 analyze and simulate a non-cooperative scenario in which the clients need incentives to upload data to each other. Specifically we consider different algorithms based on "barter" and find that certain relaxations of barter perform almost as well as the optimal cooperative algorithm. Our work is inspired by the popular BitTorrent protocol, which loosely incorporates mechanisms for efficiency and incentives. We explore BitTorrent's performance via simulation, studying the impact of different parameters. We find that BitTorrent's completion time is around twice that of an optimal algorithm. BitTorrent's scaling behavior can be improved closer to the optimal algorithm's, but only if carefully tuned.
Finally, we propose an architecture that allows applications to customize the content delivery algorithms we develop. We propose that the delivery mechanism be divided into two layers, one application-specific, and one application-independent. The former interfaces to the latter via a narrow block prioritization channel. We argue that this is simple and powerful enough to accommodate a wide variety of applications. We design two different application-specific schemes as proof of concept, and evaluate them via simulations. These results indicate that our priority-based algorithms allow high rates of delivery of streaming or ordered data.