An efficient heuristic for routing and wavelength assignment in optical WDM networks

We propose an efficient heuristic algorithm that sets up and releases lightpaths for connection requests dynamically. We partition the routing and wavelength assignment (commonly known as RWA) problem into two subproblems and solves both of them using a well-known shortest path routing algorithm. For solving the routing subproblem, an auxiliary graph is created whereby the nodes and links in the original network are transformed to the edges and vertices, respectively, and the availability of each wavelength on the input and output links of a node as well as the number of available wavelength converters are taken into account in determining the weights of edges. Furthermore, for solving the wavelength assignment subproblem, an auxiliary graph is also utilized and the cost for wavelength conversion is taken into consideration in the edge weight function. A distinguished feature of our algorithm is that it employs more accurate network information on the availability of both the wavelengths and the wavelength converters than the existing algorithms in deciding the routing and the wavelength assignment. Simulation results show that our algorithm performs much better than previously proposed algorithms with comparable computation time, especially when the number of wavelengths is large while the number of converters at each node is limited.