Converter placement in all-optical networks using genetic algorithms

Wavelength routed optical networks have emerged as a technology that can effectively utilize the enormous bandwidth of the optical fiber. Wavelength converters play an important role in enhancing the fiber utilization and reducing the overall call blocking probability of the network. Placement of wavelength converters is an NP-complete problem (K.C. Lee, V.O.K. Li, IEEE Journal of Lightwave Technology 11(5/6) (1993) 962-970) in an arbitrary mesh network. In this paper, new Integer Linear Program (ILP) formulations have been proposed for the static and dynamic routing and wavelength assignment problem to reduce the number of conversions. We use Genetic Algorithms (GAs) for placing limited range wavelength converters in arbitrary mesh wavelength routed optical networks. The objective is to achieve near optimal placement of full and limited range wavelength converters resulting in reduced blocking probabilities and low distortion of the optical signal. Certain heuristics are used to obtain starting solutions for the GAs to enable it to converge faster. The results obtained using GAs are compared with the heuristic method of placement. We study the range of loads for which converters are useful. We observe that limited range converters placed near optimally at a few nodes can provide almost the same blocking probability as full range wavelength converters placed at all the nodes and that increasing the number of converters yields only a marginal improvement in blocking probability. We also observe that uniform placement of converters can be adopted in ring networks at low offered loads. We study the effect of uniform placement at higher loads and suggest that when used with reservation in the routing algorithm, converters ensure fairness to all nodes, Simulations have been carried out on a 12-node ring network and 14-node NSFNET. (C) 2000 Elsevier Science B.V. All rights reserved.