Open AccessAn Optimization Approach to Routing and Wavelength Assignment in WDM All‐Optical Mesh Networks without Wavelength Conversion
Author(s) -
Lee Kyungsik,
Kang Kug Chang,
Lee Taehan,
Park Sungsoo
Publication year - 2002
Publication title -
etri journal
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.295
H-Index - 46
eISSN - 2233-7326
pISSN - 1225-6463
DOI - 10.4218/etrij.02.0402.0206
Subject(s) - routing and wavelength assignment , wavelength division multiplexing , column generation , integer programming , computer science , routing (electronic design automation) , wavelength , path (computing) , mesh networking , division (mathematics) , integer (computer science) , algorithm , mathematical optimization , mathematics , computer network , optics , telecommunications , physics , arithmetic , wireless , programming language
This paper considers a routing and wavelength assignment problem (RWAP) for the implementation of efficient Wavelength Division Multiplexing all‐optical mesh networks without wavelength conversion. For a given physical network and required connections, the solution to the RWAP consists in how to select a suitable path and wavelength among the many possible choices for each connection so that no two paths using the same wavelength pass through the same link, while minimizing the number of required wavelengths. We introduce an integer programming formulation of the RWAP, which has an exponential number of variables, and propose an algorithm to solve it based on the column generation technique. The proposed algorithm can yield high quality solutions and tight lower bounds at the same time. Though the proposed algorithm cannot guarantee optimal solutions, computational results show that the algorithm yields provably good solutions within a reasonable time.