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