Wavelength Translation in WDM Networks: Optimization Models and Solution Procedures

by
Jeffery L. Kennington
and
Eli V. Olinick


Abstract

Wavelength-Division Multiplexing (WDM) is the best technology currently available to handle the rapidly increasing demand for bandwidth in fiber-optical telecommunications networks. In a WDM wavelength-routed network, end users communicate with one another using all-optical channels called lightpaths. Such lightpaths are used to support point-to-point connections and may span multiple fiber links. In the absence of wavelength translators, a ligthpath must use the same wavelengths from origin to destination along each fiber span. Translators located at nodes permit wavelength translation within a lightpath. This investigation presents an empirical study comparing solutions that forbid translation with those that permit translation. For our twenty test problems, the extreme cases of no translation and translation everywhere are solvable using CPLEX. For the more difficult intermediate cases, a special tabu search heuristic was developed. For those difficult cases, excellent solutions were obtained with the tabu search procedure which runs approximately twenty-five times faster than CPLEX using the default settings.

Data and Model Files
Optimization Model AMPL Model File
RWA with Translation Everywhere ftrans_model
RWA with No Translation notrans_model
RWA with Partial Translation ptrans_model
Tabu Search Algorithm AMPL Files

 
AMPL Data Files
Problem Instance None/Full Translation Translation At Switches Translation on Protection Path
A01 A01_data.txt A01_pts.txt A01_ptp.txt
A02 A02_data.txt A02_pts.txt A02_ptp.txt
A03 A03_data.txt A03_pts.txt A03_ptp.txt
J01 J01_data.txt J01_pts.txt J01_ptp.txt
J02 J02_data.txt J02_pts.txt J02_ptp.txt
J03 J03_data.txt J03_pts.txt J03_ptp.txt
J04 J04_data.txt J04_pts.txt J04_ptp.txt
J05 J05_data.txt J05_pts.txt J05_ptp.txt
J06 J06_data.txt J06_pts.txt J06_ptp.txt
J07 J07_data.txt J07_pts.txt J07_ptp.txt
ATT01 ATT01_data.txt ATT01_pts.txt ATT01_ptp.txt
ATT02 ATT02_data.txt ATT02_pts.txt ATT02_ptp.txt
ATT03 ATT03_data.txt ATT03_pts.txt ATT03_ptp.txt
ATT04 ATT04_data.txt ATT04_pts.txt ATT04_ptp.txt
ATT05 ATT05_data.txt ATT05_pts.txt ATT05_ptp.txt
EUR01 EUR01_data.txt EUR01_pts.txt EUR01_ptp.txt
EUR02 EUR02_data.txt EUR02_pts.txt EUR02_ptp.txt
EUR03 EUR03_data.txt EUR03_pts.txt EUR03_ptp.txt
EUR04 EUR04_data.txt EUR04_pts.txt EUR04_ptp.txt
EUR05 EUR05_data.txt EUR05_pts.txt EUR05_ptp.txt

The Perl program create_data_file.pl and AMPL script write_data_file.run covert the files in the problem instance format to AMPL data files.  On a Unix system with Perl and AMPL, the following command would be used to convert the data for the problem instance EUR03 with translation at the switches into AMPL format:

perl create_data_file.pl EUR03.txt 2 > EUR03.pts.txt