Multicast Routing Algorithms for Multimedia Traffic
Vachaspathi P. Kompella · 1993
This thesis examines the problem of route construction for multimedia traffic directed at multiple destinations. Two significant properties of multimedia data, particularly audio and video, that are taken into account are the high sustained data rates and the low tolerance to delay. In particular, we examine solutions that construct a tree of low cost (which is a measure of the bandwidth utilized by the multicast), and bounded end-to-end delay from source to each destination in the multicast. We call a tree of minimum cost that adheres to the path delay constraints a constrained Steiner tree. The major contribution of this work is to present a better approach to multicast routing through this constrained Steiner tree. We show that the problem of finding the constrained Steiner tree is NP-complete, and present two approaches to construct approximate solutions. The first is a centralized one, wherein all nodes have complete knowledge of the topology and state of the network, in terms of the cost and delay of each link. The source then computes an approximate constrained Steiner tree. There are two variants of the centralized heuristic, each using a different selection function to determine which edges are desirable for the tree. One selection function, $f\sb{C},$ involves the cost of an edge, and the other, $f\sb{CD}$, involves both the cost and the delay of the edge. The second approach is a distributed algorithm, wherein each node knows the costs and delays on adjacent links, and can learn more information through communication. Again, there are two variants of the algorithm, based on the selection functions $f\sb{C}$ and $f\sb{CD}$. We show that the algorithms are guaranteed to terminate with an approximate delay-bounded solution. Furthermore, through extensive simulations, we demonstrate the performance of the centralized and distributed algorithms. To this end, we compare the solutions produced by these algorithms to the cost of the optimal solution. The centralized algorithms produce trees that are within 5-10% of the optimal cost. The distributed ones are within 20-30% of the optimal. Current routing strategies, based on minimum delay algorithms, produce trees that cost 70-80% more than optimal.