ABSTRACT |
This research aims to design a delay-constrained minimum cost multicast routing algorithm used to support the real-time multimedia multicast application. My process of developing the model for my Delay Constrained Multicast Routing (DCMR) is separated into two parts. The first part is designed for finding a multicast tree with minimum cost, whereas the second part is mainly to discover the process of iterative path switching. It aims to find new paths within the delay bound by iteratively replacing the old ones with new ones. The computation complexity of this approach is moderate, in the order of O(n3log(n)). After designing the DCMR algorithm, we initially test the work with some fixed graphs. We further perform the experiment with the Random Graph based on Waxman’s algorithm with 9 graph sizes at 10, 15, 20, 25, 30, 60, 90, 120 and 150 nodes. Each size consists of 100 different forms of network graphs, with one randomly selected source node and four destination nodes. The results obtained from DCMR are then compared with another approach . Bounded Shortest Multicast Algorithm. First, as to the cost issue, the cost of the trees obtained from DCMR algorithm is approximately 20% higher. Secondly, as to the issue of delay, DCMR is much less efficient, however, in some cases, the results are just the opposite, depending on the delayed bound, the graph structures, and the positions of both source and destination nodes. Finally, as to the computation time, the DCMR algorithm is about 2-4 times faster simply because it requires fewer iterations. In conclusion, my Delay-Constrained Multicast Routing algorithm is suitable for real-time multimedia multicast applications because it generates multicast trees that requires less computation time than any other algorithms and most likely cost less for an equal level of performance. |