An Efficient Heuristic Algorithm for Wavelength Assignment in WDM Network

INTRODUCTION

Determining routes for a set of light path demands and assigning wavelengths to these routes subject to a subset of constraints is known as the Routing and Wavelength Assignment (RWA) problem. The subset of constraints can be wavelength continuity constraint (the light path must use the same wavelength along its entire physical path) or wavelength clash constraints (two light paths that share a common physical link cannot be assigned the same wavelength). Basically there are two generic approaches of RWA. The first one is to consider RWA as a coupled problem consisting of wavelength assignment and routing problem. Generally it is a NP- hard problem. To reduce the complexity of problem, it could be decoupled into two separate subproblems, routing subproblem and wavelength assignment subproblem. Heuristics exist for both subproblems (Mukherjee, 1997; Zang et al., 2000; Shiva and Sreenivasa, 2002). There are various approaches that can be classified into two main groups: heuristic methods and exact methods. The heuristic methods give sub-optimal solutions that in many cases are acceptable and have the advantages of requiring only limited computational effort. The exact methods are much more computationally intensive and do not scale well with the network size, being even not applicable in some cases. But since they are able to identify the exact absolute optimal solution, they play a fundamental role as benchmarks to validate and test the heuristic methods. For wavelength assignment sub-problem, a number of heuristics have been proposed such as Random Wavelength Assignment, first-fit, least used, most used, least loaded, Max-Sum, Relative Capacity loss, Wavelength reservation and Protecting Threshold (Zang et al., 2000).

In this study, we proposed a linear formulation for wavelength assignment problem in Wavelength Division Multiplexing (WDM) network by incorporating the wavelength clash constraint. Then, we proposed a new heuristic algorithm for wavelength assignment and we compare with an exact method using ILP.

Our new proposed formulation is based on two objectives: First, is to take into account wavelength assignment constraints presented by the physical medium which was ignored earlier (Banerjee et al., 1997). The second objective is to formulate a linear form which can be solved for small size problem to check the validity of the proposed formulation using ILP solver (Zhang and Acampora, 1995). Keeping the above objectives in mind, the following linear programming formulation is proposed to maximize one-hop traffic in WDM network as follows:

Let t_ij denote the traffic demand from node i to node j that can always be accommodated into a wavelength path from node i to node j and let T=[t_ij ] Let`s define a symmetric connection-link indication matrix m as follows (Zhang and Acampora, 1995):

Let x_ij be a binary variable such that

The variable x_ij(k) indicates whether node i and node j are connected through a light path on wavelength k.

Objective function:

Subjects to the constraints as follows:

(1)

(2)

	(3)

W is number of wavelengths and N is number of nodes in network. For each wavelength, constraints (1) and (2) state that there should be at most one connection starting from node i and at most one connection is terminating at node j respectively. Constraints (3) indicates that if connection (i, j) and (l, m) use a common link, x_ij (k) and x_lm (k) cannot be equal to 1 at the same time, i.e., connection (i, j) and (l, m) cannot use wavelength k at the same time. The premises of this proposed formulation are it is in linear form, which can be solved using ILP solver and in addition producing a realizable connection graph (i.e., one which reflects the wavelength assignment constraints presented by the physical medium).

Considering the optical network topology shown in Fig. 1a (Zhang and Acampora, 1995), a simulation study is carried out to derive wavelength policy based on ILP formulation. Figure 1b shown the result obtained from the ILP solver based on the four nodes network given in Fig. 1a by applying demand traffic of Fig. 1c. This traffic demand is generated based on the fact that two connections share common link have the traffic demand (connection from node 4 to node 3 and connection from node 1 to node 2). The purpose of this is to test whether the connection that share common link is assigned to different wavelength. Wavelength λ₁ carries a one-optical signal from node 1 to node 4, wavelength λ₂ carries one-optical signal from node 1 to node 2 and also wavelength λ₃ from node 4 to node 3. While the signal from node 1 to node 3 is carried in two optical-hops: 1 to 4 on λ₁ and 4 to 3 on λ₃.

Fig. 1:	Four-node case study

Figure 1d shows the results obtained from the ILP solver by applying traffic demand of Fig. 1e. Traffic demand in Fig. 1e is generated based on the fact that there is only traffic request at the connection that do not share common link. The connections from node 2 to node 4, node 1 to node 3 and node 1 to node 2 are all do not share common link with each others. The purpose of this is to ensure that the same wavelength can be re-assigned to the connection that do not share common link. In Fig. 1d, wavelength λ₁ carries a one-optical signal from node 2 to node 4 and from node 1 to node 3, wavelength λ₂ carries a one-optical signal from node 1 to node 2. While a signal from node 1 to node 4 is carried in two optical-hops: 2 to 4 on λ₁ and 1 to 2 on λ₂. Wavelength λ₁ is reused twice which on node 1 to 3 and again in node 2 to 4. From the results it can conclude that the first wavelength always assigned to the optical connection that has highest traffic demand regardless whether it shares common link with others connection or not. Next, the same wavelength will be assigned to the connection which has second highest traffic demand and does not share common link with first connection. If there is none of the connections do not share common link with first connection, then the second wavelength will be assigned to the second highest traffic demand connection. The process will continue until there is not more wavelength available. In the following, we defined the variables requests for the simulation and present a new heuristic based on ILP simulation results presented in earlier for wavelength assignment problem in WDM network.

This new heuristic algorithm will continue search for highest traffic demand and assign wavelength while there is any available wavelength (k = W) or there are non-zero value traffic demand in any of the connections. Thus, this will ensure either one of the condition be fulfilled. There is either all the wavelengths have been assigned or all the traffic demand have been satisfied. The first wavelength is always assigned to the optical connection which has highest traffic demand rather than assigned to the multiple disjoint connections whose sum of traffic demand is highest because the objective function of the proposed linear formulation is to maximize one-hop traffic in WDM network and to minimize the average propagation delay encountered by all packet.

By applying the proposed heuristic algorithm on the traffic demand shown in Fig. 1e, we obtained the wavelength assignment pattern as in Fig. 1d. It can be seen that for λ₁ is assigned to connection 2-4 and connection 1-3 and after the λ₁ assignment, the connection 2-4 and connection 1-2 have the same traffic demands. Thus, the proposed heuristic may selects the connection 2-4 instead of connection 1-2.

Furthermore, we applied our new heuristic algorithm into National Science Foundation (NSF) network shown in Fig. 2. We consider two classes of traffic demands in the simulation. In each traffic demand of first class, the number of required traffic demands for each pair of nodes is generated according to the uniformly distributed random numbers in the range of 0 to W. and In second class of traffic demand, the number of required connections for each pair of nodes is set to 1 with probability 0.5 and 2 with the same probability 0.5 (Kyungsik et al., 2002).

Fig. 2:	NSF physical topology

Fig. 3:	Number of assignment versus available wavelengths for two traffic demands

Figure 3 shows the average value of 11 problem instances of assignment versus the number of wavelengths W for two Classes of traffic demand. As expected, the number of assignment increases with increasing the number of wavelengths. From the result, we can observe that class 2 shows the more stable (less variation) results for all cases of W compared with class 1 and the average value of assignment obtained in class 1 higher than class 2 for all the cases of W. This is due to the traffic demands in class 1(0-W) higher than class 2(1-2). This reveals that the proposed heuristic is effective when the traffic demand increased and highly adapt to different traffic demand.

In this study, a new linear formulation for wavelength assignment and an efficient heuristic based on the linear programming formulation for RWA have been proposed. The premised of this proposed formulation are it is in linear form, which can be solved using ILP solver and in addition it producing a realizable connection graph. The simulation results reveal that the proposed heuristic is effective when the traffic demand increased and can be highly adapted to different traffic demand. This study provides a general guideline of static RWA which arises in the network design phase for capacity planning and the sizing of network resources.