Optimal Distribution Tree for Internet Streaming Media

Min Sik Kim, Simon S. Lam, and Dong-Young Lee

In Proceedings of the 23rd IEEE International Conference on Distributed Computing Systems, May 2003.

Abstract

Internet radio and television stations require significant bandwidth to support delivery of high quality audio and video streams to a large number of receivers. IP multicast is an appropriate delivery model for these applications. However, widespread deployment of IP multicast on the Internet is unlikely in the near future. An alternative is to build a multicast tree in the application layer. Previous studies have addressed tree construction in the application layer. However, most of them focus on reducing delay. Few systems have been designed to achieve a high throughput for bandwidth-intensive applications. In this paper, we present a distributed algorithm to build an application-layer tree. We prove that our algorithm finds a tree such that the average incoming rate of receivers in the tree is maximized (under certain network model assumptions). We also describe protocols that implement the algorithm. For implementation on the Internet, there is a tradeoff between the overhead of available bandwidth measurements and fast convergence to the optimal tree. This tradeoff can be controlled by tuning some parameters in our protocols. Our protocols are also designed to maintain a small number, O(log n), of soft states per node to adapt to network changes and node failures.

Download

Paper in the proceedings
Technical Report TR-02-48, Department of Computer Sciences, The University of Texas at Austin, revised, April 2003