Mauro Brunato and Roberto Battiti

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

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

In: Proceedings of ONDM2002, Kluwer

Abstract:

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 \texttt{GRASP} family to minimise the number
of lightpaths.

At the end we present some experimental results that
compare our \texttt{GRASP} heuristic with other
greedy-based methods and with regular topologies.