Allocation of Splitting Nodes in All-Optical Wavelength-Routed Networks

Research output: Contribution to journalArticle

39 Scopus citations

Abstract

In this paper, we introduce the splitter placement problem in wavelength-routed networks (SP-WRN). Given a network topology, a set of multicast sessions, and a fixed number of multicast-capable cross-connects, the SP-WRN problem entails the placement of the multicast-capable cross-connects so that the blocking probability is minimized. The SP-WRN problem is NP-complete as it includes as a subproblem the routing and wavelength assignment problem which is NP-complete. To gain a deeper insight into the computational complexity of the SP-WRN problem, we define a graph-theoretic version of the splitter placement problem (SPG), and show that even SPG is NP-complete. We develop three heuristics for the SP-WRN problem with different degrees of trade-off between computation time and quality of solution. The first heuristic uses the CPLEX general solver to solve an integer-linear program (ILP) of the problem. The second heuristic is based on a greedy approach and is called most-saturated node first (MSNF). The third heuristic employs simulated annealing (SA) with route-coordination. Through numerical examples on a wide variety of network topologies we demonstrate that: (1) no more than 50% of the cross-connects need to be multicast-capable, (2) the proposed SA heuristic provides fast near-optimal solutions, and (3) it is not practical to use general solvers such as CPLEX for solving the SP-WRN problem.

Original languageEnglish (US)
Pages (from-to)247-265
Number of pages19
JournalPhotonic Network Communications
Volume2
Issue number3
DOIs
StatePublished - 2000

Keywords

  • And power considerations
  • Genetic algorithms
  • Multicasting
  • Optical amplification
  • Routing and wavelength assignment
  • Simulated annealing
  • Splitter placement

ASJC Scopus subject areas

  • Software
  • Atomic and Molecular Physics, and Optics
  • Hardware and Architecture
  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Allocation of Splitting Nodes in All-Optical Wavelength-Routed Networks'. Together they form a unique fingerprint.

  • Cite this