Report Number: CSL-TR-94-653
Institution: Stanford University, Computer Systems Laboratory
Title: Routing of Video/Audio Streams In Packet-Switched Networks
Author: Noronha, Ciro A., Jr.
Date: December 1994
Abstract: The transport of multimedia streams in computer communication networks raises issues at all layers of the OSI model. This thesis considers some of the issues related to supporting multimedia streams at the network layer; in particular, the issue of appropriate routing algorithms. New routing algorithms, capable of efficiently meeting multimedia requirements, are needed. We formulate the optimum multipoint stream routing problem as a linear integer programming problem and propose an efficient solution technique. We show that the proposed solution technique significantly decreases the time to compute the solution, when compared to traditional methods. We use the optimum multicast stream routing problem as a benchmark to characterize the performance of existing heuristic algorithms under realistic network and traffic scenarios, and derive guidelines for using their usage and for upgrading the network capacity. We also consider the problem of routing multimedia streams in a Wavelength-Division Multiplexing (WDM) optical network, which has an additional degree of freedom over traditional networks - its topology can be changed by the routing algorithm to create routes as needed, by tuning optical transmitters and/or receivers. We show that the optimum reconfiguration and routing problem can formulated as a linear integer programming problem. Since this is a complex solution, we also propose a set of heuristic algorithms, both for unicast and multicast routing. We evaluate the performance of the proposed heuristics and derive guidelines for their usage.