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.