Heuristic algorithms for finding light-forest of multicast routing on WDM network

Research output: Contribution to journalArticle

12 Citations (Scopus)

Abstract

Wavelength Division Multiplexing (WDM) is an important technique to make use of the large amount of bandwidths in optical fibers to meet the bandwidth requirements of applications. In this paper, two new models (MWDCRP and MCRP) of multicast routing on WDM networks are studied. In these models, it is assumed that each switch on WDM network can perform 'drop,' 'continue' and 'drop and continue' operations. In MWDCRP, given the multicast request and the delay constraint, the goal is to find a minimal wavelength light-forest to route the multicast request under the delay constraint. In MCRP, the objective cost of the multicast routing problem has two components: one is the transmitting cost, the other is the number of used wavelengths. Given the WDM network and the multicast request, the goal is to find a minimal cost light-forest to route the multicast request. Since these problems are NP-hard, four heuristic algorithms (named as Maximal-Delay-First (MDF), miNimal-Delay-First (NDF), Farthest-Greedy (FG), and Nearest-Greedy (NG)) are proposed to solve these problems. Simulation results demonstrate that the proposed algorithms can generate good solutions.

Original languageEnglish
Pages (from-to)83-103
Number of pages21
JournalJournal of Information Science and Engineering
Volume25
Issue number1
Publication statusPublished - 2009 Jan 1

Fingerprint

Heuristic algorithms
Wavelength division multiplexing
heuristics
costs
Bandwidth
Costs
Wavelength
Optical fibers
Computational complexity
simulation
Switches

All Science Journal Classification (ASJC) codes

  • Software
  • Human-Computer Interaction
  • Hardware and Architecture
  • Library and Information Sciences
  • Computational Theory and Mathematics

Cite this

@article{17abc63f86c74c958eac2a2421d3bcd2,
title = "Heuristic algorithms for finding light-forest of multicast routing on WDM network",
abstract = "Wavelength Division Multiplexing (WDM) is an important technique to make use of the large amount of bandwidths in optical fibers to meet the bandwidth requirements of applications. In this paper, two new models (MWDCRP and MCRP) of multicast routing on WDM networks are studied. In these models, it is assumed that each switch on WDM network can perform 'drop,' 'continue' and 'drop and continue' operations. In MWDCRP, given the multicast request and the delay constraint, the goal is to find a minimal wavelength light-forest to route the multicast request under the delay constraint. In MCRP, the objective cost of the multicast routing problem has two components: one is the transmitting cost, the other is the number of used wavelengths. Given the WDM network and the multicast request, the goal is to find a minimal cost light-forest to route the multicast request. Since these problems are NP-hard, four heuristic algorithms (named as Maximal-Delay-First (MDF), miNimal-Delay-First (NDF), Farthest-Greedy (FG), and Nearest-Greedy (NG)) are proposed to solve these problems. Simulation results demonstrate that the proposed algorithms can generate good solutions.",
author = "Der-Rong Din",
year = "2009",
month = "1",
day = "1",
language = "English",
volume = "25",
pages = "83--103",
journal = "Journal of Information Science and Engineering",
issn = "1016-2364",
publisher = "Institute of Information Science",
number = "1",

}

Heuristic algorithms for finding light-forest of multicast routing on WDM network. / Din, Der-Rong.

In: Journal of Information Science and Engineering, Vol. 25, No. 1, 01.01.2009, p. 83-103.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Heuristic algorithms for finding light-forest of multicast routing on WDM network

AU - Din, Der-Rong

PY - 2009/1/1

Y1 - 2009/1/1

N2 - Wavelength Division Multiplexing (WDM) is an important technique to make use of the large amount of bandwidths in optical fibers to meet the bandwidth requirements of applications. In this paper, two new models (MWDCRP and MCRP) of multicast routing on WDM networks are studied. In these models, it is assumed that each switch on WDM network can perform 'drop,' 'continue' and 'drop and continue' operations. In MWDCRP, given the multicast request and the delay constraint, the goal is to find a minimal wavelength light-forest to route the multicast request under the delay constraint. In MCRP, the objective cost of the multicast routing problem has two components: one is the transmitting cost, the other is the number of used wavelengths. Given the WDM network and the multicast request, the goal is to find a minimal cost light-forest to route the multicast request. Since these problems are NP-hard, four heuristic algorithms (named as Maximal-Delay-First (MDF), miNimal-Delay-First (NDF), Farthest-Greedy (FG), and Nearest-Greedy (NG)) are proposed to solve these problems. Simulation results demonstrate that the proposed algorithms can generate good solutions.

AB - Wavelength Division Multiplexing (WDM) is an important technique to make use of the large amount of bandwidths in optical fibers to meet the bandwidth requirements of applications. In this paper, two new models (MWDCRP and MCRP) of multicast routing on WDM networks are studied. In these models, it is assumed that each switch on WDM network can perform 'drop,' 'continue' and 'drop and continue' operations. In MWDCRP, given the multicast request and the delay constraint, the goal is to find a minimal wavelength light-forest to route the multicast request under the delay constraint. In MCRP, the objective cost of the multicast routing problem has two components: one is the transmitting cost, the other is the number of used wavelengths. Given the WDM network and the multicast request, the goal is to find a minimal cost light-forest to route the multicast request. Since these problems are NP-hard, four heuristic algorithms (named as Maximal-Delay-First (MDF), miNimal-Delay-First (NDF), Farthest-Greedy (FG), and Nearest-Greedy (NG)) are proposed to solve these problems. Simulation results demonstrate that the proposed algorithms can generate good solutions.

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

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

M3 - Article

VL - 25

SP - 83

EP - 103

JO - Journal of Information Science and Engineering

JF - Journal of Information Science and Engineering

SN - 1016-2364

IS - 1

ER -