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.
NEW LINEAR FORMULATION FOR WAVELENGTH ASSIGNMENT
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 tij 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=[tij ] Let`s define a symmetric connection-link indication matrix
m as follows (Zhang and Acampora, 1995):
Let xij be a binary variable such that
The variable xij(k) indicates whether node i and node j are connected through a light path on wavelength k.
Subjects to the constraints as follows:
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, xij (k) and
xlm (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).
NEW HEURISTIC ALGORITHM FOR WAVELENGTH ASSIGNMENT
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 λ1
carries a one-optical signal from node 1 to node 4, wavelength λ2
carries one-optical signal from node 1 to node 2 and also wavelength λ3
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 λ1 and 4 to 3 on λ3.
||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 λ1 carries a one-optical signal from node
2 to node 4 and from node 1 to node 3, wavelength λ2 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 λ1 and 1 to 2 on
λ2. Wavelength λ1 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.
||Traffic demand t (i, j) for each connection from node i to
node j where i and j =1, 2,
||Common link matrix m (i, j, l, m) for connection from node i to j and
connection from node l to m where i, j, l, m = 1, 2,
||Number of wavelengths W and type of wavelength λk. k =1,
||Wavelength assignment matrix xij (k) for k= 1,
||Initialize. Set k to 1. k indicate type of wavelength λk.
k =1, 2,
||Search for connection that has highest traffic demand.
||Assign wavelength λk to that connection if it is first
assignment or this connection do not share common link with previous assignment.
Else go to step 2.
||Update the traffic demand for that connection. Traffic demand for that
connection is reduced by one after the assignment.
||If all the non-zero traffic demand connections do not share common link
with previous assigned connection, go to step 6, else go to step 2.
||k is replaced by k+1.
||If k<=W, then go to step 1 and repeat, else stop.
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 λ1 is assigned
to connection 2-4 and connection 1-3 and after the λ1 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).
||NSF physical topology
||Number of assignment versus available wavelengths for two
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.