Mahidol University Logo
Faculty of ICT, Mahidol University
 

Admissions

Printable Version

 

A DESIGN OF MINIMUM COST MULTICAST ROUTING ALGORITHM

 

TITLE A DESIGN OF MINIMUM COST MULTICAST ROUTING ALGORITHM.
AUTHOR SUMONSAK THOJUN
DEGREE MASTER OF SCIENCE PROGRAMME IN COMPUTER SCIENCE
FACULTY FACULTY OF SCIENCE
ADVISOR SUPACHAI TANGWONGSAN
CO-ADVISOR CHOMTIP PRONPANOMCHAI
THANWADEE SUNETNANTA
 
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.
KEYWORD MULTICAST ROUTING / DELAY-CONSTRAINED

 

Go to Top

 

ICT Building, Mahidol University, 999 Phuttamonthon 4 Road, Salaya, Nakhonpathom 73170 Tel. +66 02 441-0909 Fax. +66 02 849-6099
Mahidol University Computing Center, The Faculty of ICT, Mahidol University , Rama 6 Road, Rajathevi, Bangkok 10400 Tel. +66 02 354-4333 Fax. +66 02 354-7333