Back

G-2004-12

Routing and Wavelength Assignment in Single Hop All Optical Networks with Minimum Blocking

and

BibTeX reference

WDM networks offer a technology that can transferred several optical signals into a single optical fiber. This allows for more efficient use of the huge capacity of optical fibers but it also poses new network design and management problems such as routing and wavelength planning. This paper discusses the RWA problem, i.e., the routing and wavelength assignment problem in WDM networks. Given a set of requests and the number of available wavelengths the fibers support, we are to find, through the network, a route for each connection and assign wavelengths to them. In this paper, we consider the objective of minimizing the number of connections that have to be denied. We propose a multi-phase heuristic algorithm called RWABOU. It begins with an initialization step in which we compute for each connection, r-shortest paths from each source to their destination. It is followed by an algorithm with two interactive phases. The first phase integrates a Tabu Search heuristic for the wavelength assignment followed by and interacting with a partial rerouting heuristic phase for the blocked connections. Computational experience shows that the RWABOU heuristic outperforms some recently published work on traffic instances run on the NSF and the EON networks. Moreover, comparing the lower bound of the RWABOU heuristic with the best known upper bound allows to conclude to the optimality of the RWA solution for several benchmark problems and to the very high quality of several others.

, 25 pages

Document

G-2004-12.pdf (300 KB)