Comparison of Routing and Wavelength Assignment Algorithms in WDM Networks

We design and implement various algorithms for solving the static RWA problem with the objective of minimizing the maximum number of requested wavelengths based on LP relaxation formulations. We present a link formulation, a path formulation and a heuristic that breaks the problem in the two constituent subproblems and solves them individually and sequentially. The flow cost functions that are used in these formulations result in providing integer optimal solutions despite the absence of integrality constraints for a large subset of RWA input instances, while also minimizing the total number of used wavelengths. We present a random perturbation technique that is shown to increase the number of instances for which we find integer solutions, and we also present appropriate iterative fixing and rounding methods to be used when the algorithms do not yield integer solutions. We comment on the number of variables and constraints these formulations require and perform extensive simulations to compare their performance to that of a typical min-max congestion formulation.