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.