Routing and wavelength assignment with converter

Abstract

Given a set of connection requests, the problem of setting up a lightpath by routing and assigning a wavelength to each connection is called the RWA problem. It is known to be NP-complete. As a result, various heuristics have been proposed and evaluated under different networking assumptions. We prove that RWA with converter is NP-hard. And present heuristics also. We solve the minimizing the number of wavelengths problem and analyze trade off between the cost of a converter and a wavelength. We present IP formulation and heuristic both of them. We compare our heuristic with CPLEX. Our heuristic is more powerful than CPLEX. CPLEX can solve the problem of small size only. But our heuristic can solve the problem of large size although the computational time is small by far. We present LP bound using LP relaxation also. Consequently, one can be aware of upper bound and lower bound of the minimizing the numbder of wavelengths problem.