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 language | English (US) |
---|---|
Pages (from-to) | 247-265 |
Number of pages | 19 |
Journal | Photonic Network Communications |
Volume | 2 |
Issue number | 3 |
DOIs | |
State | Published - 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