Team 6: Wavelength assignment and conversion in optical<br/><br/>networking
traffic over fiber optics at extremely high bit rates. The
such networks encompasses a range of challenging combinatorial
optimization problems. Typically, these problems are
hard even for restricted special cases. In this project we
study how to
assign wavelengths and place equipment so as to carry a set of
demands in large scale optical networks.
Our design problems are motivated by a popular optical
Wavelength Division Multiplexing (WDM). In this setting each
partitioned into a fixed number of wavelengths and demands
common fiber must be transported on distinct wavelengths. A
stays on the same wavelength along its routing path as much as
When this is infeasible, we can either deploy an extra fiber
demand to continue on the same wavelength; or place a
converter for the demand to continue on a different wavelength.
options incur cost. One objective is to assign wavelengths and
converters in an advantageous way so as to minimize the total
In this project we explore algorithms and heuristics for
wavelengths and placing converters. The goals include studying
tradeoff between optimality and complexity and understanding
between theoretical bounds and practical performance.
 Matthew Andrews and Lisa Zhang, Complexity of Wavelength
in Optical Network Optimization. (Please see Section VI.)
IEEE INFOCOM 2006. Barcelona, Spain, April 2006.
 C. Chekuri, et al. Design Tools for Transparent Optical
Bell Labs Technical Journal. Vol. 11, No. 2, pp. 129-143,
Required: One semester of algorithms; One semester of theory of
computing; One semester of programming.
Desired: Knowledge of Python and CPLEX.
Keywords: Analysis of algorithms, combinatorial optimization,
implementation of heuristics