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

TitleThe Design and Evaluation of Routing Algorithms for Real-Time Channels
Publication TypeTechnical Report
Year of Publication1994
AuthorsWidyono, R.
Other Numbers894

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.

Bibliographic Notes

ICSI Technical Report TR-94-024

Abbreviated Authors

R. Widyono

ICSI Publication Type

Technical Report