Multicast routing algorithms for real-time communication on high speed networks

Abstract

In this dissertation, we propose an Optimal Constrained Steiner Tree (OCST) algorithm for finding optimal solutions for the constrained Steiner tree problem. In addition, we propose some pruning schemes to reduce the size of the solution space and the running time of our proposed algorithm. Empirical studies shows that our pruning schemes are indeed effective in reducing the running time of the proposed algorithm substantially, thus making it a viable approach for constructing optimal solutions to the constrained Steiner tree problem.