Scalable Overlay Multicast Tree Construction for QoS-Constrained Media Streaming
Gabriel Parmer, RICHARD R. WEST, Gerald W. Fry · 2006
Overlay networks have become popular in recent times for content distribution and end-system multicasting of me-dia streams. In the latter case, the motivation is based on the lack of widespread deployment of IP multicast and the ability to perform end-host processing. However, construct-ing routes between various end-hosts, so that data can be streamed from content publishers to many thousands of sub-scribers is still a challenging problem. First, any routes be-tween end-hosts using trees built on top of overlay networks can increase stress on the underlying physical network, due to multiple instances of the same data traversing a given physical link. Second, because overlay routes between end-hosts may traverse physical network links more than once, they increase the end-to-end latency compared to IP-level routing. Third, algorithms for constructing efficient, large-scale trees that reduce link stress and latency are typically more complex. This paper therefore compares various methods to con-struct multicast trees between end-systems, that vary in terms of implementation costs and their quality of mapping from logical overlay to physical network. We describe sev-eral algorithms that make trade-offs between algorithmic complexity, physical link stress and latency. While no al-gorithm is best in all three cases we show how it is possi-ble to efficiently build trees for several thousand subscribers with latencies within a factor of two of the optimal, and link stresses comparable to, or better than, existing technolo-gies.