RESEARCH PAPER International Journal of Recent Trends in Engineering, Vol 1, No.

3, May 2009

Wavelength Assignment Problem in Optical WDM Networks

Abstract This paper analyses the wavelength assignment problem in optical WDM networks. First, the random wavelength assignment algorithm is compared with the first-fit wavelength assignment algorithm, later, the sparse wavelength conversion case is compared with no wavelength conversion and full wavelength conversion cases. These comparisons are done on the basis of blocking probability and number of links; numbers of channels are kept constant whereas the response is calculated by varying the load per link (in Erlangs). The blocking probability in case of random algorithm is always greater than first-fit wavelength assignment algorithm. The blocking probability is minimum in case of wavelength conversion, whereas in case of no conversion, the first-fit algorithm has better results as compared to that of random wavelength assignment algorithm.

1. Wavelength continuity constraint: A lightpath must use the same wavelength on all the links along the path from source to destination edge nodes. 2. Distinct wavelength constraint: All lightpaths using the same link must be allocated the distinct wavelengths. In wavelength routed network the light path must be wavelength continuous, if there is no common wavelength through out the length it results in blocking. This problem of blocking can be overcome to some extent by the use of wavelength converters. As converters are very expensive, it is not economically feasible to place converters at all nodes. Therefore, there is a trade-off between performance gain and cost. A more practical and cost effective solution is to use only a few converting nodes. This is known as sparse or limited wavelength conversion. Issues in Wavelength Routed Networks:

INTRODUCTION Transmitting light beams of different wavelengths in an optical fiber is known as Wavelength Division Multiplexing (WDM). A WDM optical network consists of wavelength routing nodes interconnected by point-topoint optical fiber links in an arbitrary topology. In a wavelength routed network, a message is sent from one node to another node using a wavelength continuous route called a lightpath, without requiring any opticalelectronic-optical conversion and buffering at the intermediate nodes. One must deal with both the selection of path (Routing) and allocating the available wavelengths for the connections (Wavelength Assignment). This resulting problem is known as routing and wavelength assignment (RWA) problem. There are two problems, one is the routing problem and the other is wavelength assignment problem. Here, our area of concern is the wavelength assignment problem. Two of the important wavelength assignment algorithms are: 1. Random wavelength assignment: A wavelength is selected randomly from the available wavelengths. 2. First-fit assignment: All the wavelengths are numbered. The wavelength with the lowest number is selected from the available wavelengths. The two constraints which are followed for the wavelength assignment are:

Normally, a lightpath operates on the same wavelength across all fiber links that it traverses, in which case the lightpath is said to satisfy the wavelength-continuity constraint. Thus, two lightpaths that share a common fiber link should not be assigned the same wavelength. However, if a switching/routing node is also equipped with a wavelength converter facility, then the wavelengthcontinuity constraints disappear, and a lightpath may switch between different wavelengths on its route from its origin to its termination. This particular problem is referred to as the Routing and Wavelength Assignment (RWA) problem. Static versus Dynamic Traffic Demand: In case of a static traffic demand, connection requests are known a priori. The traffic demand may be specified in terms of source-destination pairs. The problems this type are categorized under the static lightpath establishment (SLE) problem. As the optimal-time algorithms are ideal, polynomial-time algorithms which produce solutions close to the optimal one are preferred to solve the SLE problem. In case of a dynamic traffic demand, connection request arrive to and depart from a network one by one in a random manner. The lightpaths once established remain for a finite time. The dynamic traffic demand models

2009 ACADEMY PUBLISHER

201

RESEARCH PAPER International Journal of Recent Trends in Engineering, Vol 1, No. 3, May 2009

several situations in transport networks. Unlike the static RWA problem, any solution to the dynamic problem is computationally simple. Dynamic RWA algorithms perform more poorly than static RWA algorithms because a dynamic algorithm has no knowledge about future connection requests, whereas all the connection requests are known a priori to a static RWA algorithm. Route and Wavelength Selection Methods The important routing methods considered in the literature are fixed routing, alternate routing, and exhaust routing. In the fixed routing method, only one route is provided for a node pair. Usually this route is chosen to be the shortest route. When a connection request arrives for a node pair, the route fixed for that node pair is searched for the availability of a free wavelength. In the alternate routing method, two or more routes are provided for a node pair. These routes are searched one by one in predetermined order. Usually these routes are ordered in non decreasing order of their hop length. In the exhaust method, all possible routes are searched for a node pair. The network state is represented as a graph and a shortestpath-finding algorithm is used on the graph. Based on the order in which the wavelengths are searched, the wavelength assignment algorithms are classified into most-used, least used, fixed order, and random order. In the most-used method, wavelengths are searched in non-increasing order of their utilization in the network. In the least used method, wavelengths are searched in non decreasing order of their utilization in the network. This method spreads the lightpaths over different wavelengths. In the fixed order method, the wavelengths may be indexed and the wavelength with the lowest index is examined first. In the random method, the wavelength is chosen randomly from among the free wavelengths. Wavelength Conversion: One possible way to overcome the bandwidth loss caused by the wavelength continuity constraint is to use wavelength converters at the routing nodes. A wavelength converter is an optical device which is capable of shifting one wavelength to another wavelength. As converters are very expensive, it is not economically feasible to place converters at all nodes. Therefore, there is a trade-off between performance gain and cost. A more practical and cost effective solution is to use only a few converting nodes. This is sparse or limited wavelength conversion. RWA PROBLEM
IN

different RWA algorithms can be compared for networks of moderate size. The amount of wavelength reuse achievable in large networks using the SP-RWA via simulation as a function of the number of wavelengths, number of edges, and number of nodes for randomly constructed networks as well as deBruijn networks is quantified. The difference in wavelength reuse between two different optical node architectures is also quantified. A. A Linear Programming Approach In linear programming approach a (quasi-)static view of the problem and propose new integer-linear programming formulations, which can be addressed with highly efficient linear (not integer) programming methods and yield optimal or near-optimal RWA policies. A new integer linear programming formulations, which tend to have integer optimal solutions even when the integrality constraints are relaxed, thereby allowing the problem to be solved optimally by fast and highly efficient linear (not integer) programming methods. The optimality of the resulting solutions for specific topologies. B. Joint and Adaptive RWA A routing and wavelength assignment in wavelengthrouted all-optical networks with circuit switching is followed. A more general approach in which we consider all paths between a sourcedestination (sd) pair and incorporate network state information into the routing decision is adopted. This approach performs routing and wavelength assignment jointly and adaptively, and out performs fixed routing techniques. We obtain an analytical technique to compute approximate blocking probabilities for networks employing fixed and alternate routing. The analysis can also accommodate networks with multiple fibers per link. The blocking performance of the proposed adaptive routing algorithms are compared along with their computational complexity. . In particular, AUR outperforms fixed routing by a significant margin. AUR also performs better than alternate routing; however, as the number of alternate routes increases, the performance approaches that of AUR. Complexity analysis of adaptive routing algorithms indicates that they achieve good results with a moderate increase in complexity. Alternate routing is found to be a good tradeoff between fixed routing and AUR. Multifiber networks are an attractive alternative for networks with wavelength conversion capability. The results indicate significant performance gains with two fibers per link over single-fiber links. C. Static Wavelength Assignment An off-line wavelength assignment problem in star and ring networks that deploy multiple fibers between nodes and use wavelength division multiplexing (WDM) for transmission is considered. In particular, sharper per-fiber bounds on the number of required wavelengths are derived for the multifiber version of the assignment problem in star and ring networks. The wavelength assignment problem in multifiber networks, in which each link has exactly parallel fibers is analyzed. 202

ALL OPTICAL NETWORKS

The problem of routing connections in a reconfigurable optical network using wavelength division multiplexing. The authors have derived an upper bound on the carried traffic of connections (or equivalently, a lower bound on the blocking probability) for any routing and wavelength assignment (RWA) algorithm in such a network. The bound scales with the number of wavelengths and is achieved asymptotically (when a large number of wavelengths is available) by a fixed RWA algorithm. Although computationally intensive, their bound can be used as a metric against which the performance of

2009 ACADEMY PUBLISHER

RESEARCH PAPER International Journal of Recent Trends in Engineering, Vol 1, No. 3, May 2009

D. Wavelength Assignment in presence of Wavelength Converters Existing research has demonstrated that an effective Routing and Wavelength Assignment (RWA) algorithm and wavelength conversion are two primary vehicles for improving the blocking performance. A weighted leastcongestion routing and first-fit wavelength assignment (WLCR-FF) algorithm that considers both the current traffic load and the route lengths jointly is proposed. An analytical model that can evaluate the blocking performance for WLCR algorithm is modelled. They carry out extensive numerical studies over typical topologies including ring, mesh torus, and the 14-node NSFNET; and compare the performance of WLCR-FF with a wide variety of existing routing algorithms including static routing, fixed-alternate routing and leastloaded routing. The results conclusively demonstrate that the proposed WLCR-FF algorithm can achieve much better blocking performance in the presence of sparse or/and full wavelength conversion. WLCR-FF algorithm takes into account the distribution of free wavelengths and the hop lengths of each route jointly when it makes a route decision. The simulation results demonstrated that WLCR-FF algorithm could improve the blocking performance significantly compared with conventional dynamic RWA algorithms in the environment of sparse or/and full wavelength conversion. E. RWA when Limited or Sparse Wavelength Conversion An Integer Linear Program based algorithm and a K shortest path based heuristic algorithm for solving the Routing and Wavelength Assignment problem in All Optical Networks with Limited Wavelength Conversion is considered. These algorithms are executed on a random mesh National Science Foundation Network ( NSFNET). For solving the Max-RWA problem on random mesh networks, two algorithms were presented. One is computation intensive integer linear program and other is less computation intensive K-shortest path heuristic algorithm. The number of connections realized by the heuristic algorithm is less than that of the ILP based algorithm and vary when the lightpaths are arranged in ascending, descending and random order. The results show that use of wavelength converters reduces the wavelength blocking at switching nodes. PROGRAMMING METHODOLOGY ALGORITHM
STEP 1-START.

Step 6-Parameters like Number of channels, Number of Links, Load per link and number of generations are passed through LINK_SIM_NO_CONV() function to calculate the blocking probability without wavelength conversion. Step 7-Step 6 is repeated, LINK_SIM_CONV() function. this time for

Step 8-No. of channels and load per link (in Erlangs) are passed through P_L() function. Step 9-By varying the METHOD parameter, blocking probability is calculated for no, full and limited wavelength conversion. Step 10-If Sparse or Limited Wavelength Conversion is used, then enter the conversion degree of the node. Step 11-The above mentioned steps are repeated by varying the value of traffic load per link (in Erlangs). RESULTS AND ANALYSIS A. Comparison of First-fit and Random Algorithms In this section, we will present the simulation results for random wavelength assignment algorithm and first-fit wavelength assignment algorithm. These algorithms are compared with the case of wavelength conversion. In all the simulations, blocking probability of the network is compared depending upon the number of channels, number of links and traffic load per link (in Erlang). The number of wavelengths on all the links is kept constant. A very important assumption is the consideration of a network with an arbitrary topology. Static routing is assumed i.e. the route is selected off-line. When a request arrives, it is processed on the basis of some heuristics. The simulation is carried out on MATLAB of Mathworks. For better comparisons, we have fixed the values of the number of channels C=11, number of links=10 and traffic load per link (in Erlangs) is varied. The following figures show the variation in blocking probability of 10 links, for load ranging from 1 Erlang ,5Erlang and 10 Erlang per link.
25 Conversion No conversion - "first-fit" No conversion - "random"

20 Blocking propability [%]

15

10

Step 2-Initialize the number of channels in the optical fiber. Step 3-Initialize the number of links in the network. Step 4-Enter the traffic load per link (in Erlangs) value. Step 5-Number of simulation iterations value is stored in number generations.

5 6 Number of links

10

Fig.1 Blocking Probability for 10 links when load is 1 Erlang per link

203
2009 ACADEMY PUBLISHER

RESEARCH PAPER International Journal of Recent Trends in Engineering, Vol 1, No. 3, May 2009

100 90 80 Blocking propability [%] 70 60 50 40 30 20 10 0 Conversion No conversion - "first-fit" No conversion - "random"

probability of 10 links, for load ranging from 1 Erlang to 10 Erlang per link.
6 x 10
-3

No conversion Full conversion Limited conversion, D=2

Blocking propability
1 2 3 4 5 6 Number of links 7 8 9 10

Fig.2 Blocking Probability for 10 links when load is 5 Erlangs per link
100 90 80 Blocking propability [%] 70 Conversion No conversion - "first-fit" No conversion - "random"

5 6 Number of links

10

Fig.4 Blocking Probability for 10 links when load is 1 Erlangs per link
1 0.9 0.8 No conversion Full conversion Limited conversion, D=2

60
Blocking propability

0.7 0.6 0.5 0.4 0.3 0.2

50 40 30 20

0.1

10

5 6 Number of links

10

5 6 Number of links

10

Fig.3 Blocking Probability for 10 links when load is 10 Erlangs per link

Fig.5 Blocking Probability for 10 links when load is 5 Erlangs per link
1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 No conversion Full conversion Limited conversion, D=2

B. Effects of Sparse Wavelength Conversion In this section, we will present the simulation results of comparison of sparse or limited wavelength conversion with no and full wavelength conversion. These algorithms are compared with the case of wavelength conversion. In all the simulations, blocking probability of the network is compared depending upon the number of channels, number of links and traffic load per link (in Erlang). The number of wavelengths on all the links is kept constant. A very important assumption is the consideration of a network with an arbitrary topology. Static routing is assumed i.e. the route is selected off-line. When a request arrives, it is processed on the basis of some heuristics. The simulation is carried out on MATLAB of Mathworks. For better comparisons, we have fixed the values of the number of channels C=11, number of links=10 and traffic load per link (in Erlangs) is varied. The following figure shows the variation in blocking 204
2009 ACADEMY PUBLISHER

Blocking propability

The blocking probability increased with the increase in load. With no wavelength conversion the blocking probability is high. Compared to random wavelength assignment, first fit algorithm yielded a high blocking probability. According to the results random wavelength assignment was found to yield low blocking probability.

0.2 0.1

5 6 Number of links

10

Fig.6 Blocking Probability for 10 links when load is 10 Erlangs per link

The above shown simulation results shows how the blocking probability increases with the number of nodes. The blocking probability in case of random algorithm is always greater than that of first-fit wavelength assignment algorithm. The simulation figures show the blocking probability of 10 links both with and without wavelength conversion as well as the case of limited conversion, for load ranging from 1 Erlang to 10 Erlang per link. The probability is minimum in case of wavelength conversion, whereas in case of no conversion the first-fit algorithm has better results as compared to that of random wavelength assignment algorithm. Also, for lower load values, sparse wavelength conversion and full wavelength conversion gives similar results but as load per link

RESEARCH PAPER International Journal of Recent Trends in Engineering, Vol 1, No. 3, May 2009

increases, sparse wavelength conversion has less blocking as compared to even full wavelength conversion. In the literature [7], comparisons are done between random wavelength assignment algorithm and first-fit wavelength assignment algorithm i.e. no wavelength conversion case with full wavelength conversion. We have extended it to sparse or limited wavelength conversion. It is found that blocking probability for 10 links when the load is 10 erlangs per link with limited wavelength conversion is low and with full connection it is found to be high and with no connection the value is one. Sparse Wavelength conversion, having WCRs at a small fraction of nodes is typically sufficient for a desired performance compared to full wavelength conversion. CONCLUSION We have analyzed the response of blocking probability of a network having 10 links and for varying load. The simulation figures show the blocking probability of 10 links both with and without wavelength conversion as well as the case of limited conversion, for load ranging from 1 Erlang to 10 Erlang per link. As load per link (in Erlang) increases, the blocking probability increases. The results show that the response of first-fit wavelength assignment algorithm is better than random wavelength assignment algorithm, whereas the response of wavelength conversion is much better than without conversion i.e. with first-fit and random algorithm. For lower load values, sparse wavelength conversion and full wavelength conversion gives similar results but as load per link increases, sparse wavelength conversion has less blocking as compared to even full wavelength conversion. REFERENCES
[1] Rajiv Ramaswami and [Link], Routing and wavelength assignment in all-optical networks, IEEE/ACM Transactions on Networking, vol.3 pp 489-500, Oct. 1995. [2] Ahmed Mokhtar and Murat Azizoglu, Adaptive Wavelength Routing in All-Optical Networks, IEEE/ACM Transactions on Networking, vol. 6, No. 2, pp. 197-206, April 1998. [3] R. A. Barry and P .A. Humblet, Models of blocking Probability in All-Optical Networks with and without Wavelength Changers, IEEE Journal of Selected Areas of Communication, volume 14, pp. 878-867, June 1996. [4]Asuman E. Ozdaglar and Dimitri P. Bertsekas, Routing and Wavelength Assignment in Optical Networks, IEEE/ACM Transactions on Networking, vol. 11 No.2, pp 259-272, April 2003. [5] Xiaowen Chu and Bo Li, Dynamic Routing and Wavelength Assignment in the Presence of Wavelength Conversion for All-Optical Networks, IEEE/ACM Transactions on Networking,vol.13, No.3, June2005. [6] [Link] and [Link], Practical Routing and Wavelength Assignment Algorithm for All-Optical Networks with Limited Wavelength Conversion, IEEE/ACM Transactions on Networking, 2002.

[7] Amit Wason and Dr. R. S. Kaler, Wavelength Assignment Problem in Optical WDM Networks, IJCSNS International Journal of Computer Science and Network Security, vol.7 No.4, April 2007. 205
2009 ACADEMY PUBLISHER