Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12]


Journal of Information Science and Engineering, Vol. 21 No. 1, pp. 85-108 (January 2005)

A Genetic Algorithm for Multicast Routing under Delay
Constraint in WDM Network with Different Light Splitting*

Ming-Tsung Chen and Shian-Shyong Tseng
Department of Computer and Information Science
National Chiao Tung University
Hsinchu, 300 Taiwan

Because optical WDM networks will become a realistic choice for buildings backbones, multicasting in the WDM network should be supported for various network applications. In this paper, a new multicast problem, Multicast Routing under Delay Constraint Problem (MRDCP), routing a request with delay bound to all destinations in a WDM network with different light splitting is solved by genetic algorithms (GAs), where different light splitting means that nodes in the network can transmit one copy or multiple copies to other nodes by using the same wavelength. The MRDCP can be reduced to the Minimal Steiner Tree Problem (MSTP) which has been shown to be NP-Complete. We propose a destination-oriented representation to represent chromosomes, three general genetic operators (selection, crossover, and mutation), four types of operators (Chromosome Crossover, Individual Crossover, Chromosome Mutation, and Individual Mutation). Four mutation heuristics (Random Mutation (RM), Cost First Mutation (CFM), Delay First Mutation (DFM), and Hybrid Mutation (HM)) are employed in the GA method. Finally, experimental results show that our solution model can obtain a near optimal solution.

Keywords: genetic algorithm, multicast routing, WDM network, delay constraint, splitting degree, NP-hard

Full Text () Retrieve PDF document (200501_05.pdf)

Received April 16, 2003; revised November 4, 2003; accepted February 25, 2004.
Communicated by Chu-Sing Yang.
* This work was partially supported by MOE Program for Promoting Academic Excellence of Universities under grant No. 89-E-FA04-1-4, High Confidence Information Systems.