Routing, wavelength assignment, and spectrum allocation algorithms in transparent flexible optical WDM networks

Current fixed grid wavelength routed networks are limited in terms of spectral efficiency due to the rigid nature of wavelength assignment. We propose the Flexible Optical WDM (FWDM) network architecture for flexible grid optical networks in which the constraint on fixed spectrum allocation to channels is removed and network resources can be dynamically provisioned with an automated control plane. In this paper, we address the routing, wavelength assignment, and spectrum allocation problem (RWSA) in transparent FWDM networks with the objective of maximizing spectral efficiency. We formulate the RWSA problem using an Integer Linear Program (ILP). We also prove the NP-completeness of the RWSA problem, and propose three efficient polynomial time algorithms; namely the Greedy-Routing, Wavelength Assignment, and Spectrum Allocation algorithm (Greedy-RWSA); the K-Alternate Paths Routing, Wavelength Assignment, and Spectrum Allocation algorithm (KPaths-RWSA); the Shortest Path Routing, Wavelength Assignment, and Spectrum Allocation algorithm (SP-RWSA). We analyze the lower bound on the required spectrum for the given network topology and a set of requests. Simulation results demonstrate that FWDM networks are efficient in terms of spectrum, cost, and energy compared to fixed grid networks. The performance of the proposed algorithms is very close to the lower bound, and approaches to the lower bound as problem size increases. (C) 2012 Elsevier B.V. All rights reserved.