< JISE Vol.16 No.6 #7
Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol. 16, No. 6, pp. 885-901 (November 2000)

Multicast Routing Based on Genetic Algorithms

Ren-Hung Hwang, Wei-Yuan Do and Shyi-Chang Yang
Department of Computer Science and Information Engineering
National Chung Cheng University
Chiayi, Taiwan 621, R.O.C.
E-mail: rhhwang@cs.ccu.edu.tw

Due to the advent of many new multimedia applications in high speed networks, the issue of multicast routing has become more and more important. The multicast routing problem in computer networks is also known as the Steiner tree problem which has been shown to be NP-complete. In this paper, we propose a new multicast routing algorithm based on Genetic Algorithms. To apply this algorithm to real networks, we also propose several methods for reducing the computational complexity. Computer simulations were conducted on a random graph to evaluate the performance of the proposed algorithm. Our numerical results show that the proposed algorithm is able to find a better solution than the RSR algorithm, a very promising heuristic algorithm for the Steiner tree problem proposed by Rayward-Smith. Finally, since many multimedia applications require multiple Quality of Service (QOS) constraints, such as delay, jitter, and loss probability, we also address how to extend the proposed algorithm to obtain multiple constrained multicast trees.

Keywords: multicast, Steiner tree, genetic algorithm, routing, QOS

Full Text () Retrieve PDF document (200011_07.pdf )

Received September 2, 1998; revised November 30, 1998; accepted March 18, 1999.
Communicated by Chi Sung Laih.