Browsing by Author "Chen, MT"

Now showing 1 - 2 of 2

A genetic algorithm for Multicast Routing under Delay Constraint in WDM network with different light splitting
(2005-01-01)
Chen, MT
;
Tseng, SS
;
資訊工程學系
;
Department of Computer Science
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 call obtain a near optimal solution.
Dynamic multicast routing under delay constraints in WDM networks with heterogeneous light splitting capabilities
(2006-05-31)
Chen, MT
;
Tseng, SS
;
Lin, BMT
;
資訊工程學系
;
資訊管理與財務金融系註：原資管所+財金所
Because optical WDM networks will be realized as network backbone in the near future, multicasting in WDM networks needs to be supported for various network applications. In this paper, we propose a new dynamic multicast routing problem under delay constraints (DMR-DC) for finding an optimal light-forest with the minimum multicast cost from these links with available wavelengths for routing a multicast request that arrives in random with a given delay bound in a WDM network with heterogeneous light splitting capabilities, where a light-forest is a set of light-trees used to set up switches to route the request. Multicast cost is defined by communication cost ratio and wavelength consumption ratio. The problem is to determine a light-forest with less wavelength consumption and less communication cost. This problem is NP-hard because it can be reduced from the minimum Steiner tree problem. In this paper, we propose an efficient three-phase (generation, refinement, and conversion) solution model to find approximate solutions in a reasonable time. (C) 2005 Elsevier B.V. All rights reserved.