Wavelength and Routing Assignment in All Optical Networks Using Ant Colony Optimization

Wavelength and Routing Assignment in All Optical Networks Using Ant Colony Optimization

Ana Maria Sarmiento (Tecnológico de Monterrey, México), Gerardo Castañón (Tecnológico de Monterrey, México) and Fernando Lezama (Tecnológico de Monterrey, México)
DOI: 10.4018/978-1-4666-3652-1.ch010

Abstract

Routing and Wavelength Assignment (RWA) in an arbitrary mesh network is an NP-complete problem. So far, this problem has been solved by linear programming for network topologies with a few nodes, and sub-optimally solved for larger networks by heuristic strategies and the application of optimization algorithms such as Genetic Algorithms (GA), Particle Swarm Optimization (PSO), Differential Evolution (DE), etc. In this chapter, the authors present the use of Ant Colony Optimization (ACO) to find near optimal solutions to the routing and wavelength assignment problem in real sized networks with up to 40 nodes and 65 connecting links. They compare their results to the lower bounds obtained by the Nagatsu’s method, finding them to be equal or very close (one wavelength over) to them.
Chapter Preview
Top

Introduction

Optical networks using Dense Wavelength Division Multiplexing (DWDM) technology are the ideal candidates to handle the problem of the ever-increasing growth of traffic and demand for bandwidth. DWDM systems are popular with telecommunication companies because they allow them to expand their network's capacity without laying out additional fiber. By using DWDM and optical amplifiers, companies can accommodate several generations of technology developments in their optical infrastructure without having to overhaul the backbone network. Worldwide networking and communication systems and applications use high-speed optical transport networks as appropriate backbones for connecting buildings, cities and countries such as PAN EUROPEAN, NSFNET and COST optical networks (Kavian et al., 2012) and (Ramaswami and Sivarajan, 2009).

To send data from one access node to another in a DWDM network, one needs to establish a connection in the optical layer similar to the one in a circuit-switched network. This can be done determining a path in the network between the two nodes and allocating a free wavelength on all the links on the path. Such an all-optical path is commonly referred to as a lightpath and may span multiple fiber links without any intermediate electronic processing, while using one WDM channel per link. The entire bandwidth on the lightpath is reserved for this connection until it is terminated, at which time the associated wavelengths become available on all the links along the route. It is thus important to provide routes to the lightpath requests and to assign wavelengths on each of the links along this route among all the possible choices so as to optimize a certain performance metric. This is known as the Routing and Wavelength Assignment (RWA) problem. The wavelengths assigned must be such that no two lightpaths that share a physical link use the same wavelength on that link. The RWA problem is critically important in increasing the efficiency of wavelength-routed optical networks. As provisioning of an extra wavelength involves considerable increase in the network's cost, the objective is to minimize the number of wavelengths required, known as the Network Wavelength Requirement (NWR).

The traffic assumptions generally fall into one of two categories: static or dynamic. In static RWA models, it is assumed that the demand is fixed and known, i.e., all the lightpaths that are to be set up in the network are known beforehand. The objective is typically to accommodate the demand while minimizing the number of wavelengths used in all links. By contrast, in a stochastic/dynamic setting, it is assumed that lightpath requests between source-destination pairs arrive one by one at random, and have random terminating times. A typical objective in this case would be to minimize the call blocking probability, or the total (perhaps weighted) number of blocked calls over a given period of time.

Complete Chapter List

Search this Book:
Reset