Genetic algorithm for finding minimal cost light-forest of multicast routing on WDM networks

Research output: Contribution to journalArticle

8 Citations (Scopus)

Abstract

Wavelength division multiplexing (WDM) is an important technique to make use of the large amount of bandwidth in optical fibers to meet the bandwidth requirements of applications. Multicast is the transmission of information from one source to multiple destinations simultaneously. Given a multicast request in a WDM network, the goal is to find a set of light-trees, the assigned wavelengths of light-trees, and construct a light-forest. In this paper, the Minimal cost multicast routing problem (MCMRP) on WDM networks with Tap-and-continue nodes is defined and studied. A new cost model which consists of thewavelength usage and communication cost is defined. The objective is to minimize the sum of the cost of used wavelengths and the communication cost of the light-forest. Specifically, the formulation for the WDM multicast routing problem is given. Because the MCMRP is NP-hard, two genetic algorithms (GAs) are proposed to solve this problem. In the proposed GAs, a path-oriented encoding chromosome is used to represent the routing paths. These routing paths are used to construct source-based light-forests to represent a feasible solution to the multicast request. Moreover, to speed up the convergence of GAs, a Farthest-first greedy heuristic algorithm is proposed and used to generate one of the initial chromosomes. Simulation results demonstrate that the proposed GAs can run efficiently.

Original languageEnglish
Pages (from-to)195-222
Number of pages28
JournalArtificial Intelligence Review
Volume29
Issue number3-4
DOIs
Publication statusPublished - 2008 Jun 1

Fingerprint

Wavelength division multiplexing
Genetic algorithms
costs
Costs
Chromosomes
Bandwidth
Wavelength
communication
Communication
Heuristic algorithms
Genetic Algorithm
Optical fibers
heuristics
Computational complexity
simulation

All Science Journal Classification (ASJC) codes

  • Language and Linguistics
  • Linguistics and Language
  • Artificial Intelligence

Cite this

@article{ed164066c579426887e55091cc2c2c14,
title = "Genetic algorithm for finding minimal cost light-forest of multicast routing on WDM networks",
abstract = "Wavelength division multiplexing (WDM) is an important technique to make use of the large amount of bandwidth in optical fibers to meet the bandwidth requirements of applications. Multicast is the transmission of information from one source to multiple destinations simultaneously. Given a multicast request in a WDM network, the goal is to find a set of light-trees, the assigned wavelengths of light-trees, and construct a light-forest. In this paper, the Minimal cost multicast routing problem (MCMRP) on WDM networks with Tap-and-continue nodes is defined and studied. A new cost model which consists of thewavelength usage and communication cost is defined. The objective is to minimize the sum of the cost of used wavelengths and the communication cost of the light-forest. Specifically, the formulation for the WDM multicast routing problem is given. Because the MCMRP is NP-hard, two genetic algorithms (GAs) are proposed to solve this problem. In the proposed GAs, a path-oriented encoding chromosome is used to represent the routing paths. These routing paths are used to construct source-based light-forests to represent a feasible solution to the multicast request. Moreover, to speed up the convergence of GAs, a Farthest-first greedy heuristic algorithm is proposed and used to generate one of the initial chromosomes. Simulation results demonstrate that the proposed GAs can run efficiently.",
author = "Der-Rong Din",
year = "2008",
month = "6",
day = "1",
doi = "10.1007/s10462-009-9146-1",
language = "English",
volume = "29",
pages = "195--222",
journal = "Artificial Intelligence Review",
issn = "0269-2821",
publisher = "Springer Netherlands",
number = "3-4",

}

Genetic algorithm for finding minimal cost light-forest of multicast routing on WDM networks. / Din, Der-Rong.

In: Artificial Intelligence Review, Vol. 29, No. 3-4, 01.06.2008, p. 195-222.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Genetic algorithm for finding minimal cost light-forest of multicast routing on WDM networks

AU - Din, Der-Rong

PY - 2008/6/1

Y1 - 2008/6/1

N2 - Wavelength division multiplexing (WDM) is an important technique to make use of the large amount of bandwidth in optical fibers to meet the bandwidth requirements of applications. Multicast is the transmission of information from one source to multiple destinations simultaneously. Given a multicast request in a WDM network, the goal is to find a set of light-trees, the assigned wavelengths of light-trees, and construct a light-forest. In this paper, the Minimal cost multicast routing problem (MCMRP) on WDM networks with Tap-and-continue nodes is defined and studied. A new cost model which consists of thewavelength usage and communication cost is defined. The objective is to minimize the sum of the cost of used wavelengths and the communication cost of the light-forest. Specifically, the formulation for the WDM multicast routing problem is given. Because the MCMRP is NP-hard, two genetic algorithms (GAs) are proposed to solve this problem. In the proposed GAs, a path-oriented encoding chromosome is used to represent the routing paths. These routing paths are used to construct source-based light-forests to represent a feasible solution to the multicast request. Moreover, to speed up the convergence of GAs, a Farthest-first greedy heuristic algorithm is proposed and used to generate one of the initial chromosomes. Simulation results demonstrate that the proposed GAs can run efficiently.

AB - Wavelength division multiplexing (WDM) is an important technique to make use of the large amount of bandwidth in optical fibers to meet the bandwidth requirements of applications. Multicast is the transmission of information from one source to multiple destinations simultaneously. Given a multicast request in a WDM network, the goal is to find a set of light-trees, the assigned wavelengths of light-trees, and construct a light-forest. In this paper, the Minimal cost multicast routing problem (MCMRP) on WDM networks with Tap-and-continue nodes is defined and studied. A new cost model which consists of thewavelength usage and communication cost is defined. The objective is to minimize the sum of the cost of used wavelengths and the communication cost of the light-forest. Specifically, the formulation for the WDM multicast routing problem is given. Because the MCMRP is NP-hard, two genetic algorithms (GAs) are proposed to solve this problem. In the proposed GAs, a path-oriented encoding chromosome is used to represent the routing paths. These routing paths are used to construct source-based light-forests to represent a feasible solution to the multicast request. Moreover, to speed up the convergence of GAs, a Farthest-first greedy heuristic algorithm is proposed and used to generate one of the initial chromosomes. Simulation results demonstrate that the proposed GAs can run efficiently.

UR - http://www.scopus.com/inward/record.url?scp=72449202601&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=72449202601&partnerID=8YFLogxK

U2 - 10.1007/s10462-009-9146-1

DO - 10.1007/s10462-009-9146-1

M3 - Article

VL - 29

SP - 195

EP - 222

JO - Artificial Intelligence Review

JF - Artificial Intelligence Review

SN - 0269-2821

IS - 3-4

ER -