The Design and Evaluation of Routing Algorithms for Real-time Channels


                        Ron Widyono
                 Computer Science Division
 Department of Electrical Engineering and Computer Science
            University of California at Berkeley
		    Berkeley, CA 94720 
		 widyono@cs.berkeley.edu

		       ICSI TR-94-024

                          ABSTRACT


The Tenet Scheme specifies a real-time communication service
that  guarantees  performance  through  network con nections
with reserved resources, admission control,  and  rate  con-
trol.  Within this framework, we develop and eval uate algo-
rithms that find routes for these multicast connections. The
main  goals  are  to  maximize the probability of successful
establishment of the routed connection, to maximize the use-
ful  utilization of the network, and to be timely. The prob-
lem to be solved is finding a minimum cost tree  where  each
source to destination path is con strained by a delay bound.
This problem is NP-complete, so heuristics based  mainly  on
minimum  incremental  cost  are  developed.   Algorithms  we
develop use those heuristics to  calculate  paths  that  are
merged  into  a  tree.  We  evalu  ate  our design decisions
through simulation, measuring success through the number  of
successfully established connections.