Report Number: CSL-TR-94-618
Institution: Stanford University, Computer Systems Laboratory
Title: Optimum Routing of Multicast Audio and Video Streams in
Author: Noronha, Ciro A., Jr.
Author: Tobagi, Fouad A.
Date: April 94
Abstract: In this report, we consider the problem of routing multicast
audio and video streams in a communications network. After
describing the previous work in the area and identifying its
shortcomings, we show that the problem of optimally routing
multicast streams can be formulated as an integer programming
problem. We propose an efficient solution technique, composed
of two parts: (i) an extension to the decomposition
principle, to speed up the linear relaxation of the problem,
and (ii) enhanced value-fixing rules, to prune the search
space for the integer problem. We characterize the reduction
in run time gained using these techniques. Finally, we
compare the run times for the optimum multicast routing
algorithm and for existing heuristic algorithms.