Mauro Brunato and Roberto Battiti

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

Università di Trento
Dipartimento di Matematica
via Sommarive 14
I-38050 Pantè di Povo (TN)
Italy
Email: brunato|battiti@science.unitn.it

Preprint Università di Trento UTM609, November 2001

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 minimize 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.