Content Distribution in Overlay Multicast

Cui, Yi

Permalink

https://hdl.handle.net/2142/11063 Copy

Description

Title

Content Distribution in Overlay Multicast

Author(s)

Cui, Yi

Issue Date

2005-10

Keyword(s)

computer networking multimedia

Abstract

Multicast is an important communication paradigm, upon which many distribution applications are built, such as video-on-demand, live broadcasting, teleconferencing, large-volume content dissemination, etc. The efforts to support multicast at IP layer, however, have proved to be slow and painful, due to factors such as ISP's lack of incentives, shortage of address space, difficulty to support reliable transmission and congestion control, and others. Recently proposed overlay multicast appears to be a more practical solution to address above problems. In this approach, end hosts, instead of routers, organize themselves into a logical overlay network and relay data to each other via unicast transport services. The fundamental difference between these two approaches, is that in IP multicast, the data forwarding/replication task is performed by the routers, while in overlay multicast, the same task is performed by participating end hosts of the overlay network. Although seemingly it just elevates the multicast functionality into application layer, overlay network actually revolutionizes the way network applications can be built. In IP network, except for nodes at the edge, the network is composed of routers, whose task is no more than forwarding packets. In contrast, each node in overlay network is an intelligent one that can collaborate and contribute various resources (CPU, storage, access bandwidth, etc.). Our argument is validated by our study on supporting multimedia content distribution, a classical multicast-based application, via overlay-based solution. We identify two key challenges of this application: on-demand user requests, where different users may request to view the same multimedia content at different times, and high throughput requirement}, where the multicast solution is demanded to maintain data distribution structure with high throughput to each user. Regarding the on-demand challenge, how to design overlay-based on-demand media distribution solution by utilizing the flexibilities offered by overlay network (each host contributing its own resources)? Furthermore, how do we quantify the performance tradeoff between the new overlay-based solution to the traditional IP-multicast-based solutions? Regarding the high throughput challenge, a theoretical framework needs to be established to model overlay multicast, which gives answers to the following questions. What is the theoretical upper bound to maximize throughput of an overlay multicast session, and what is the optimal solution (construction of multicast trees) to achieve so? When multiple sessions exist, can fairness be achieved? Given answers to these questions, can we use this model to analytically and quantitatively evaluate existing overlay multicast solutions and offer theoretical guidance to the design of new ones? Given the fact that both challenges need to be addressed in practice, how to design practical overlay-based content distribution solution, which combines previously developed techniques to each individual challenge? How to analyze the performance bound of our solution, given the insights obtained when studying previous problems? In this thesis, we report our solutions to the aforementioned challenges. Our work is built on the overlay graph model. An overlay graph is a virtual network connecting end hosts of an overlay multicast session. In the graph, an edge bridging two end hosts corresponds to their unicast route in the physical network. Our objective is to find optimal data distribution path, i.e., optimal spanning tree(s) (minimum cost, maximum throughput, etc.), on the given overlay graph. Our application is on-demand multimedia distribution. The contributions of this thesis are as follows. We propose an overlay-based on-demand media distribution solution. Through extensive analytical and experimental analysis, we exhibit the great potential of overlay-based solution at saving server load and network bandwidth consumption compared to the ideal IP-multicast-based solutions. Using multicommodity flow theory, we establish the theoretical foundation for multi-tree overlay multicast. We note that such a foundation works for all kinds of distribution applications such as large-volume file downloading, teleconferencing, etc. Based on this foundation, we propose a series of algorithms, which are able to derive the optimal solutions to achieve (1) maximum throughput for a given multicast session, (2) maximum throughput for multiple sessions, while maintaining weighted max-min fairness among them. Combining the techniques developed to individually address the on-demand and high throughput challenges, we propose an overlay-based dynamic high-bandwidth content distribution solution. Theoretically, we prove the approximation bound of our solution regarding the optimal throughput. Experimentally, we show our solution to greatly outperform the theoretical bound, and give consistent performance to various node dynamics and network topologies.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/11063

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections