We study the problem of routing and wavelength assignment (RWA) in a WDM optical network under different hop assumptions, i.e., with and without wavelength converters, considering the objective of minimizing the blocking rate. We design a heuristic with two interactive phases for respectively the routing and the wavelength assignment, which generalizes a previous algorithm by Noronha and Ribeiro (2006), based on a Tabu Search scheme using a partition coloring reformulation, for uniform traffic and single-hop connections. Considering non uniform traffic, we explore a reformulation of the RWA problem as a generalized partition coloring problem and develop a Tabu Search algorithm to solve it. We also explore how to integrate multi-hop connections, with the addition of conversion features at some or at all optical nodes. Experiments are done on several traffic and network instances. Most heuristic solutions are excellent as illustrated by the very small gap between the values provided by the heuristic and the optimal values of the linear relaxation. We next show that conversion features, although very often considered as an added value, are of little help to improve on the blocking rate except for some very particular traffic instances, even on realistic network topologies.
Paru en janvier 2006 , 40 pages
Ce cahier a été révisé en juillet 2006