Report Number: CSL-TR-94-618
Institution: Stanford University, Computer Systems Laboratory
Title: Optimum Routing of Multicast Audio and Video Streams in Communications Networks
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.