#
**NC State University**

##
**Department of Computer Science Colloquia 2000-2001**

**Date:** Friday, January 26, 2001

**Time: 3**: 30 PM (talk)

**Place: **402A Withers, NCSU Historical Campus (click for
courtesy parking request)
**Speaker: **Rudra Dutta,
Computer Science, NCSU

**On Optimal Traffic Grooming in WDM Network**

**Abstract: **In the past few years, there has been growing interest
in wide area "All Optical Networks" with wavelength division multiplexing
(WDM), using wavelength routing. A virtual topology over a WDM WAN consists
of clear channels between nodes called lightpaths, with traffic carried
from source to destination without electronic switching as far as possible,
but some electronic switching may be performed. Virtual topology
design aims at combining the best of optical switching and electronic routing
abilities.

We consider the problem of designing a virtual topology to minimize
electronic

routing, that is, grooming traffic, with special reference to wavelength
routed optical rings. The full virtual topology design problem is NP-hard
even in the restricted case where the physical topology is a ring, and
various heuristics have been proposed in the literature for obtaining good
solutions, usually for different classes of problem instances. We present
a new framework which can be used to evaluate the performance of heuristics,
and which requires significantly less computation than evaluating the optimal
solution. This framework is based on a general formulation of the virtual
topology problem, and it consists of a sequence of bounds, both upper and
lower, in which each successive bound is at least as strong as the previous
one. The successive bounds take larger amounts of computation to evaluate,
and the number of bounds to be evaluated for a given problem instance is
only limited by the computational power available. The bounds are based
on decomposing the ring into sets of nodes arranged in a path, and adopting
the locally optimal topology within each set. While we only consider the
objective of minimizing electronic routing in this paper, our approach
to obtaining the sequence of bounds can be applied to many virtual topology
problems on rings. The upper bounds we obtain also provide a useful
series of heuristic solutions.

**Short Bio: **Rudra Dutta
is a Ph.D. candidate in the department of Computer Science, NCSU.

**Hosts: **H.
Perros, Computer Science, NCSU

Colloquia
Home Page.