Routing and wavelength assignment in optical networks using bin packing based algorithms

This paper addresses the problem of routing and wavelength assignment (RWA) of static lightpath requests in wavelength routed optical networks. The objective is to minimize the number of wavelengths used. This problem has been shown to be NP-complete and several heuristic algorithms have been develo...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2007-03, Vol.177 (2), p.1167-1179
Main Author: Skorin-Kapov, Nina
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Bin packing
Correlation analysis
Exact sciences and technology
Heuristic
Operational research. Management science
Optical networks
OR in telecommunications
Routing
Routing and wavelength assignment
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper addresses the problem of routing and wavelength assignment (RWA) of static lightpath requests in wavelength routed optical networks. The objective is to minimize the number of wavelengths used. This problem has been shown to be NP-complete and several heuristic algorithms have been developed to solve it. We suggest very efficient, yet simple, heuristic algorithms for the RWA problem developed by applying classical bin packing algorithms. The heuristics were tested on a series of large random networks and compared with an efficient existing algorithm for the same problem. Results indicate that the proposed algorithms yield solutions significantly superior in quality, not only with respect to the number of wavelength used, but also with respect to the physical length of the established lightpaths. Comparison with lower bounds shows that the proposed heuristics obtain optimal or near optimal solutions in many cases.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2006.01.003