Lightpath routing and wavelength assignment in WDM networks

Steven Shi-Wei Lee; Cheng-Shong Wu; Ching-Lung Chang

doi:10.1117/12.445145

17 October 2001 Lightpath routing and wavelength assignment in WDM networks

Steven Shi-Wei Lee, Cheng-Shong Wu, Ching-Lung Chang

Proceedings Volume 4584, Optical Network Design and Management; (2001) https://doi.org/10.1117/12.445145
Event: Asia-Pacific Optical and Wireless Communications Conference and Exhibit, 2001, Beijing, China

Abstract

This paper consider the design of lightpath Routing and Wavelength Assignment (RWA) problem in Wavelength Division Multiplexing (WDM) networks with or without wavelength conversion. To minimize the required network cost, one has to device as few network devices and take the least network building cost with respect to the required demand requirements. In our model, the required cost including the one to install wavelengths in the network nodes and the building cost to use a specific wavelength in a specified optical link. The problem is formulated as a binary linear programming where the objective function is the minimization of network building cost. Many literatures have pointed out that solving the formulation of this kind is very computationally demanding and heuristic algorithms and/or relaxation techniques are needed for problems with nontrivial size. In this paper, a Lagrangian relaxation based solving procedure is developed for the RWA problem. In particular, We first transfer the RWA problem into a multicommodity integer flow problem using graph transformation technique by adding some artificial network nodes and links with proper cost on them. To achieve minimum network cost, two problem solving phases are developed for networks with and without wavelength converter respectively. In the first phase, we try to optimize the cost of routing without violating the wavelength continuity constraints. If no feasible solutions are obtained in this phase, it means there are no sufficient paths to route lightpaths without wavelength converter. We then take another graph extension with wavelength converter geared to the RWA problem and then applying a shortest path based heuristic algorithm to solve the problem based on the solution obtained from first phase. Two network topologies, GTE network and NSFNET network, are used to evaluate the computational results. Examining the Lagrangian based heuristic results and the lower bounds reveal that the proposed algorithm can efficiently provide a nearly optimal solution for our problem.

Citation Download Citation

Steven Shi-Wei Lee, Cheng-Shong Wu, and Ching-Lung Chang "Lightpath routing and wavelength assignment in WDM networks", Proc. SPIE 4584, Optical Network Design and Management, (17 October 2001); https://doi.org/10.1117/12.445145

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available