The Design and Evaluation of Routing Algorithms for Real-Time Channels
Title | The Design and Evaluation of Routing Algorithms for Real-Time Channels |
Publication Type | Technical Report |
Year of Publication | 1994 |
Authors | Widyono, R. |
Other Numbers | 894 |
Abstract | The Tenet Scheme specifies a real-time communication service that guarantees performance through network connections with reserved resources, admission control, and rate control. Within this framework, we develop and evaluate algorithms that find routes for these multicast connections. The main goals a establishment of the routed connection, to maximize the useful utilization of the network, and to be timely. The problem to be solved is finding a minimum cost tree where each source to destination path is constrained 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 evaluate our design decisions through simulation, measuring success through the number of successfully established connections. |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1994/tr-94-024.pdf |
Bibliographic Notes | ICSI Technical Report TR-94-024 |
Abbreviated Authors | R. Widyono |
ICSI Publication Type | Technical Report |