Genetic Algorithm techniques to solve Routing and Wavelength Assignment problem in Wavelength Division Multiplexing all-optical networks

Routing and Wavelength Assignment (RWA) problem in Wavelength Division Multiplexed (WDM) optical networks assumes assigning the routes and wavelengths to be used to create the lightpaths on behalf of the connection requests. The RWA problem belongs to the class of combinatorial optimization problems. The optimal solution to the RWA problem is found to be NP-hard and thus suited to heuristic approaches. We formulate an Integer Linear Programming (ILP) problem to model the RWA problem as an optimization problem and solve the formulated ILP using Genetic Algorithm (GA) heuristic to obtain a near optimal solution in polynomial time. Our primary optimization objective is the establishment of connection requests with minimum congestion among the individuals. The secondary targets are to minimize the hop count, route length, the number of fiber links utilized to honor all the lightpath requests. The GA based heuristic approach is simulated on ARPANET (Advanced Research Project Agency NETwork) and the results obtained for the multi objective GA are compared with the single objective GA. The results show that multi objective GA performs better than single objective GA while optimizing different network parameters.

I. Introduction

The bandwidth demand of Internet users has been increasing rapidly due to the growth of the population of Internet users and the popularization of online applications and services that require high bandwidth, such as voice chat, video streaming, P2P file sharing, grid computing, HDTV programming and optical storage area networks [1], [2]. Wavelength Division Multiplexing (WDM) is a promising technology to serve as the backbone for future Wide Area Networks (WAN) because of its capability to exploit the huge bandwidth of optical fibers [3], [4], [5], [6], [7], [8], [9], [10]. WDM technique increases the transmission capacity by using multiple non interfering channels at different carrier wavelengths. In general networks to route, add and terminate wavelengths we need Wavelength Cross-connects (WXCs) [11], [12] (also known as Optical Cross-connects or OXCs) whose block diagram is depicted in Fig. 1. WDM optical networks use lightpaths [3], [4], [13], [14], [15] to exchange information between node pairs. A lightpath is an all-optical logical connection that does not require processing or buffering at intermediate nodes. In Fig. 2, we have considered a small optical network with five routing nodes and eight fiber links and analyzed the establishment of five lightpath requests using two carrier wavelengths. Fig. 1: Wavelength cross-connecting Switch Fig. 2: Switching strategy in WDM networks