Campuses:

Team 6: Wavelength assignment and conversion in optical<br/><br/>networking

Wednesday, August 8, 2007 - 11:40am - 12:00pm
EE/CS 3-180
Lisa Zhang (Alcatel-Lucent Technologies Bell Laboratories)
Today's optical telecommunication networks carry audio, video
and data
traffic over fiber optics at extremely high bit rates. The
design of
such networks encompasses a range of challenging combinatorial
optimization problems. Typically, these problems are
computationally
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
traffic
demands in large scale optical networks.


Our design problems are motivated by a popular optical
technology called
Wavelength Division Multiplexing (WDM). In this setting each
fiber is
partitioned into a fixed number of wavelengths and demands
sharing a
common fiber must be transported on distinct wavelengths. A
demand
stays on the same wavelength along its routing path as much as
possible.
When this is infeasible, we can either deploy an extra fiber
for the
demand to continue on the same wavelength; or place a
wavelength
converter for the demand to continue on a different wavelength.
Both
options incur cost. One objective is to assign wavelengths and
place
converters in an advantageous way so as to minimize the total
cost.


In this project we explore algorithms and heuristics for
assigning
wavelengths and placing converters. The goals include studying
the
tradeoff between optimality and complexity and understanding
the gap
between theoretical bounds and practical performance.


References:


[1] Matthew Andrews and Lisa Zhang, Complexity of Wavelength
Assignment
in Optical Network Optimization. (Please see Section VI.)
Proceedings of
IEEE INFOCOM 2006. Barcelona, Spain, April 2006.
href=http://cm.bell-labs.com/~ylz/2006.coloring4.pdf>http://cm.bell-labs.com/~ylz/2006.coloring4.pdf


[2] C. Chekuri, et al. Design Tools for Transparent Optical
Networks.
Bell Labs Technical Journal. Vol. 11, No. 2, pp. 129-143,
2006.


Prerequisite:


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