Scalable and efficient algorithms for wavelength assignment and for traffic grooming in reconfigurable optical WDM mesh networks

Abstract

Wavelength division multiplexing (WDM) has emerged as the most promising technology for the next generation optical networks. Developing scalable and efficient algorithms for dynamic wavelength assignment and for traffic grooming is one of the most important concerns to meet the challenging operational requirements in future optical WDM mesh networks. Firstly, it is well known that wavelength converters are considered as one of the most critical resources because they can significantly reduce the blocking probability. However, wavelength converters still remain quite expensive. Therefore, the problem of wavelength assignment that can optimally utilize them is strongly desired. Unfortunately, previously proposed wavelength assignment algorithms are too simple or not practical due to their huge computational complexities. The first contribution of this thesis is that, for the first time, I propose a novel graph constructed with groups of available wavelengths, called lambda-runs, to represent the availabilities of wavelength converters, wavelength channels, and optical transceivers along a physical route selected for routing a new connection request. Then, the least-conversion lightpath for a new connection request can be found easily by applying the classical shortest-path routing Dijkstra``s algorithm. The analysis shows that my algorithm is much more scalable than existing algorithms because the graph constructed with lambda-runs can significantly simplify the required computations. Simulation results in a typical mesh network with different conversion capabilities demonstrate that my algorithm is significantly better than modified first-fit algorithm in terms of blocking performance. Secondly, dynamic traffic grooming is also one of the most important and practical problems for designing optical WDM mesh networks. Most of previous work solve that problem by applying the Dijsktra``s algorithm on an auxiliary graph. Although those approaches may give good ...