An efficient approach to optimal wavelength routing in WDM optical networks

The problem of wavelength routing and assignment in WDM optical networks is NP-hard. To date, problems of wavelength routing and wavelength assignment have been solved separately to obtain optimal or near-optical solutions. In this paper, we propose a heuristic approach to wavelength routing that achieves optimal or near optimal solutions with much faster computational time compared to the classical ILP formulation. A two steps approach including K shortest paths (KSP) and integer linear programming selection (ILPS) formulation is presented. This approach can deal with larger network sizes. Tune complexity and optimality of solution are two performance metrics considered in our study. The computational time in ILP formulation increases rapidly (nearly exponential) while those in our approach are nearly flat. The optimality of solutions in our approach depends on the value of the constant K in the KSP process, and in most cases optimal solutions can be achieved when K > 4. For NSFNET with 14 nodes, 21 bidirectional links, 16 wavelengths per link and 100 random traffic matrices of 115 connections, it yields one hundred percent of 46 feasible and optimal solutions when K > 4.