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.
Title
Towards Efficient Distribution of High-Volume Content
Published
2006-12-11
Full Collection Name
Electrical Engineering & Computer Sciences Technical Reports
Other Identifiers
EECS-2006-167
Type
Text
Extent
173 p
Archive
The Engineering Library
Usage Statement
Researchers may make free and open use of the UC Berkeley Library’s digitized public domain materials. However, some materials in our online collections may be protected by U.S. copyright law (Title 17, U.S.C.). Use or reproduction of materials protected by copyright beyond that allowed by fair use (Title 17, U.S.C. § 107) requires permission from the copyright owners. The use or reproduction of some materials may also be restricted by terms of University of California gift or purchase agreements, privacy and publicity rights, or trademark law. Responsibility for determining rights status and permissibility of any use or reproduction rests exclusively with the researcher. To learn more or make inquiries, please see our permissions policies (https://www.lib.berkeley.edu/about/permissions-policies).
