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 blocking performance, they are not practical due to their scalability problem. Therefore, another important contribution of this thesis is that, for the first time, I propose a heuristic algorithm to reduce the required computations by shrinking the auxiliary graph, i.e., the lightpath for a new connection request should be searched within a small network zone. Furthermore, in order to maintain the flexibility for searching a lightpath, the zone can be dynamically enlarged basing on the availabilities of groomable existing lightpaths and new lightpaths, and the physical connectivity between network nodes. I develop a mathematical model to estimate the possibility that a node, when included into the zone to enlarge the searching space, is able to make the source and destination connected and to ensure that the selected lightpath is resource-efficient. My proposed algorithm is also aware of different grooming architectures of different nodes, therefore, it can work well in heterogeneous multi-vendor networks with sparse grooming capability. The simulation results demonstrate that my algorithm is scalable and it can improve the blocking performance.
