Hierarchical Optimization Procedure for Traffic Grooming in WDM Optical Networks

The traffic grooming, routing and wavelength assignment (GRWA) problem in wavelength division multiplexed (WDM) networks has been the focus of many studies over the past years. Under fixed grooming ratio and ring network topology assumptions, researchers have been able to provide exact or near optimal solutions. However, all practical cases in mesh networks have been addressed with heuristic algorithms without providing any hint on the quality of the solutions, i.e., no evaluation of the distance between the heuristic and the exact solutions through the estimation of an optimality gap. Moreover, restrictions on the number of optical hops per lightpath, a critical parameter for the end-to-end delays, have never been taken into account. We propose a new hierarchical optimization procedure to solve the GRWA problem for mesh topology, subject to a limit on the number of optical hops, where we first solve the grooming (G) problem and then the routing and wavelength assignment (RWA) one. Both G and RWA problems are formulated with integer linear programs (ILPs) and a lower bound on the optimal solution of the GRWA problem is computed during the two-phase solution process. Computational tests are made on various network and traffic instances and show that the new hierarchical optimization procedure outputs solutions that clearly outperforms those obtained with the hierarchical approach of Hu and Leida (2004). We also compare solutions obtained with single-hop, two-hop, three-hop and unlimited hop routing. Two-hop routing offers the best compromise between network design cost and delay constraints. Indeed, GRWA solutions obtained with a 2-hop routing are about 20 % cheaper than the solutions with single-hop routing, while three-hop routing solutions are slightly cheaper but with longer end-to-end delays.