Allocation of Splitting Nodes in All-Optical Wavelength-Routed Networks |
| |
Authors: | Ali Maher Deogun Jitender |
| |
Affiliation: | (1) Department of Computer Science & Engineering, University of Nebraska-Lincoln, Lincoln, NE 68588-0115, USA;(2) Department of Computer Science & Engineering, University of Nebraska-Lincoln, Lincoln, NE 68588-0115, USA |
| |
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. |
| |
Keywords: | multicasting splitter placement genetic algorithms simulated annealing routing and wavelength assignment optical amplifica-tion and power considerations |
本文献已被 SpringerLink 等数据库收录! |
|