A Multistart Randomized Greedy Algorithm for Traffic Grooming on Mesh Logical Topologies

In this paper we consider a logical topology design problem on DWDM optical networks where the traffic is quantized at sub-wavelength resolution and the critical factor to determine the fitness of a solution is the number of lightpaths required, that is proportional to the number of hardware modules to handle the traffic. The problem has been shown to be NP-hard. We review some of the previous work in the field, examine a number of regular but unsatisfactory solutions and describe a greedy-based iterated heuristic belonging to the GRASP family to minimise the number of lightpaths. At the end we present some experimental results that compare our GRASP heuristic with other greedy-based methods and with regular topologies. © 2003 by Springer Science+Business Media Dordrecht.