Heuristic and hybrid methods for solving optimal multiple multicast problem on WDM ring network

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

The Optimal Multiple Multicast Problem (OMMP) on wavelength division multiplexing (WDM) ring networks without wavelength conversion is considered in this paper. When the physical network and the set of multicast requests are given, OMMP is the problem that selects a suitable path (or paths) and wavelength (or wavelengths) among the many possible choices for each multicast request such that not any pair of paths using the same wavelength pass through the same link. In this paper, a formulation of OMMP is given; this problem is NP-hard since the famous RWA problem which has been proved NP-hard is a special case of OMMP. In this paper, the OMMP is divided into two subproblems: path routing and wavelength assignment subproblems. For each subproblem, two heuristic algorithms are proposed to solve it. Moreover, a hybrid method which combines heuristic and simulated annealing algorithm is proposed to find the near optimal solution. Experimental results indicate that these algorithms are efficient.

Original languageEnglish
Pages (from-to)245-262
Number of pages18
JournalTelecommunication Systems
Volume28
Issue number2
DOIs
Publication statusPublished - 2005 Feb 1

Fingerprint

Wavelength division multiplexing
Wavelength
Optical frequency conversion
Heuristic algorithms
Simulated annealing
Computational complexity

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering

Cite this

@article{3b2562799f9e4f81bfa53ba7fb5046e8,
title = "Heuristic and hybrid methods for solving optimal multiple multicast problem on WDM ring network",
abstract = "The Optimal Multiple Multicast Problem (OMMP) on wavelength division multiplexing (WDM) ring networks without wavelength conversion is considered in this paper. When the physical network and the set of multicast requests are given, OMMP is the problem that selects a suitable path (or paths) and wavelength (or wavelengths) among the many possible choices for each multicast request such that not any pair of paths using the same wavelength pass through the same link. In this paper, a formulation of OMMP is given; this problem is NP-hard since the famous RWA problem which has been proved NP-hard is a special case of OMMP. In this paper, the OMMP is divided into two subproblems: path routing and wavelength assignment subproblems. For each subproblem, two heuristic algorithms are proposed to solve it. Moreover, a hybrid method which combines heuristic and simulated annealing algorithm is proposed to find the near optimal solution. Experimental results indicate that these algorithms are efficient.",
author = "Der-Rong Din",
year = "2005",
month = "2",
day = "1",
doi = "10.1007/s11235-004-5019-8",
language = "English",
volume = "28",
pages = "245--262",
journal = "Telecommunication Systems",
issn = "1018-4864",
publisher = "Springer Netherlands",
number = "2",

}

Heuristic and hybrid methods for solving optimal multiple multicast problem on WDM ring network. / Din, Der-Rong.

In: Telecommunication Systems, Vol. 28, No. 2, 01.02.2005, p. 245-262.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Heuristic and hybrid methods for solving optimal multiple multicast problem on WDM ring network

AU - Din, Der-Rong

PY - 2005/2/1

Y1 - 2005/2/1

N2 - The Optimal Multiple Multicast Problem (OMMP) on wavelength division multiplexing (WDM) ring networks without wavelength conversion is considered in this paper. When the physical network and the set of multicast requests are given, OMMP is the problem that selects a suitable path (or paths) and wavelength (or wavelengths) among the many possible choices for each multicast request such that not any pair of paths using the same wavelength pass through the same link. In this paper, a formulation of OMMP is given; this problem is NP-hard since the famous RWA problem which has been proved NP-hard is a special case of OMMP. In this paper, the OMMP is divided into two subproblems: path routing and wavelength assignment subproblems. For each subproblem, two heuristic algorithms are proposed to solve it. Moreover, a hybrid method which combines heuristic and simulated annealing algorithm is proposed to find the near optimal solution. Experimental results indicate that these algorithms are efficient.

AB - The Optimal Multiple Multicast Problem (OMMP) on wavelength division multiplexing (WDM) ring networks without wavelength conversion is considered in this paper. When the physical network and the set of multicast requests are given, OMMP is the problem that selects a suitable path (or paths) and wavelength (or wavelengths) among the many possible choices for each multicast request such that not any pair of paths using the same wavelength pass through the same link. In this paper, a formulation of OMMP is given; this problem is NP-hard since the famous RWA problem which has been proved NP-hard is a special case of OMMP. In this paper, the OMMP is divided into two subproblems: path routing and wavelength assignment subproblems. For each subproblem, two heuristic algorithms are proposed to solve it. Moreover, a hybrid method which combines heuristic and simulated annealing algorithm is proposed to find the near optimal solution. Experimental results indicate that these algorithms are efficient.

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

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

U2 - 10.1007/s11235-004-5019-8

DO - 10.1007/s11235-004-5019-8

M3 - Article

AN - SCOPUS:17444365088

VL - 28

SP - 245

EP - 262

JO - Telecommunication Systems

JF - Telecommunication Systems

SN - 1018-4864

IS - 2

ER -