Abstract
We investigate the allocation of multicast nodes and formalize it as splitter placement in wavelength-routed networks (SP-WRN) problem. The SP-WRN problem entails the placement of multicast nodes so that the overall network blocking probability is minimized. 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 CPLEX, the second heuristic is based on a greedy approach, and the third heuristic employs Simulated Annealing. Numerical examples demonstrate that: i) no more than 50% of the cross-connects need to be multicast-capable, and ii) the iterative simulated annealing heuristic provides fast near-optimal solutions.
Original language | English (US) |
---|---|
Pages (from-to) | 614-618 |
Number of pages | 5 |
Journal | IEEE International Conference on Communications |
Volume | 2 |
State | Published - 2001 |
Externally published | Yes |
Event | International Conference on Communications (ICC2001) - Helsinki, Finland Duration: Jun 11 2000 → Jun 14 2000 |
ASJC Scopus subject areas
- Computer Networks and Communications
- Electrical and Electronic Engineering