Lightpath Routing and Wavelength Assignment in WDM Networks

摘要

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.