This chapter discusses longhaul wide coverage optical networks based on arbitrary (mesh) topology in which nodes use wavelengthrouting switches/optical crossconnects (OXCs) for setting up wavelengthdivision multiplexer (WDM) channels between node pairs [1,2]. It finds a practical approach to resolve the routing and wavelength assignment (RWA) problem of light paths in networks. A large RWA problem has two smaller subproblem routings for selection of path and assignment of wavelength on routing path, each of which may be resolved independently and efficiently using different efficient techniques. A multicommodity flow formulation, along with randomized rounding and different constraints, is required to estimate the routes for light paths. Wavelength assignments (WAs) for light paths are carried out by different techniques such as graphcoloring techniques. Wavelengthrouted optical networks are the backbone of networks for large regions nationwide or globally. Access stations/users are attached to the network via wavelengthsensitive nodes for switching/routing.
This chapter discusses longhaul wide coverage optical networks based on arbitrary (mesh) topology in which nodes use wavelengthrouting switches/optical crossconnects (OXCs) for setting up wavelengthdivision multiplexer (WDM) channels between node pairs [1,2]. It finds a practical approach to resolve the routing and wavelength assignment (RWA) problem of light paths in networks. A large RWA problem has two smaller subproblem routings for selection of path and assignment of wavelength on routing path, each of which may be resolved independently and efficiently using different efficient techniques. A multicommodity flow formulation, along with randomized rounding and different constraints, is required to estimate the routes for light paths. Wavelength assignments (WAs) for light paths are carried out by different techniques such as graphcoloring techniques. Wavelengthrouted optical networks are the backbone of networks for large regions nationwide or globally. Access stations/users are attached to the network via wavelengthsensitive nodes for switching/routing.
Access stations transmit signals to each other via wavelength channels, called light paths [2]. In order to set up a “connection” between a source–destination (SD) pair, we need to have a “light path” between them. A light path is made using multiple fiber links to provide a “circuitswitched” interconnection between two nodes. Each intermediate node in the light path essentially provides a circuitswitched optical bypass facility to support the light path. In an Nnode network, if each node has (N − 1) transceivers and if there are enough wavelengths on all fiber links, then every node connection request should be set up by an optical light path, and a networking scheme is required to resolve this problem. The network size (N) should be scalable, and transceivers are expensive, so each node can have only a few of them, and technological constraints dictate that the number of WDM channels that can be supported in a fiber be limited to W (64 maximum). Thus, only a limited number of light paths may be set up on the network.
A virtual topology is developed based on a complete set of light paths in network over which virtual topology connection requests are established and routed. The design of virtual topology is discussed in the next chapter. In this chapter, the traffic/connection discussed for wide area network (WAN) is circuitoriented; i.e., the discussed traffic consists of a set of connections such that each connection requires the full bandwidth of a light path in order for it to be routed between its corresponding sd pair. The RWA problem can be stated as follows:
While the shortestpath routes may often be preferable, this choice allows more light paths to be set up. Thus, RWA algorithms generally estimate several alternate routes for each light path that needs to be established. Light paths are not set up due to constraints on routes and wavelengths and are said to be blocked, so the corresponding network optimization problem minimizes this blocking probability (BP).
Several constraints are required to implement routing and WAs in the network. In this regard, a light path operates on the same wavelength across all fiber links that it traverses, in which case the light path is said to satisfy the wavelengthcontinuity constraint. Thus, two light paths that share a common fiber link should not be used by the same wavelength. For a switching/routing node with a wavelength converter facility, the wavelengthcontinuity constraints are not satisfied. For such a network having a set of connection demands to be established, an integer linear programming (ILP) formulation of the RWA problem is taken as a multicommodity flow problem. There are lower and upper bounds in any generic RWA algorithm’s performance – an upper bound on the carried traffic (number of light paths established) and a lower bound on the light path. The approach uses wavelength conversion. The WA problem is NPcomplete where a number of heuristics are required to obtain the solutions of the RWA problem [3,4].
In this chapter, we mention wellknown algorithms for the RWA [1,5]. The RWA approach consists of algorithms to solve the RWA problem [5] for large network. In RWA, the main objective is to minimize the number of wavelengths for accommodating a certain number of connections in the network based on a certain physical topology. The RWA problem has four different subproblems – each subproblem is resolved independently with the results of one stage providing the input to the next stage. Firstly, a formulation is made by using a linear program (LP) relaxation based on the physical topology having the set of connections. One can use a generalpurpose LP solver to find out solutions to this problem. In this case, simple and specialized techniques are developed to drastically handle the size of the LP in terms of the number of variables and the number of equations that it needs to handle.
Combinatorial formulations are made using mixedinteger linear programs (MILPs) for solving the RWA problem [6–9]. These formulations are used in resolving large problems by using sophisticated techniques such as branchandbound methods.
The RWA problem, without the wavelengthcontinuity constraint, is a straightforward multicommodity flow problem with integer flows in each link [1]. The ILP with the objective function minimizing the flow in each link corresponds to minimizing the number of lightpaths passing through a particular link.
where
It is NPcomplete and can be approximately written by using randomized rounding [1].
A multicommodity formulation is made using a number of equations having a number of variables in the formulation. Figure 3.1 shows a network consisting of 10 nodes, 15 links (ijpairs), and an average of 4 connections per node; i.e., 40 connections (SD pairs) need to be set up in the network.
Figure 3.1 Network having 10 nodes and 15 physical links in which links are bidirectional.
In the simplest and most general formulation, the number of λ_{sd} variables for Figure 3.1 is estimated as 10 × 9 = 90. The number of ${F}_{ij}^{sd}$ variables are estimated as 90 SD pairs × 15 ij pairs = 1350. The number of variables and the number of equations grow proportionally with the square of the number of nodes. A solution is obtained only by considering the variables λ_{sd} = 1 and reducing the number of λ_{sd} variables from 90 to 40. Also, this approach also decreases the number of ${F}_{ij}^{sd}$ variables to be 40 × 15 = 600. For further reduction of the number of variables, the light path needs to pass through few ij links. The links make the path through which a light path passes and we can only consider those links as the ${F}_{ij}^{sd}$ variables for that particular SD pair. For a light path SD that passes through four links on average, there will be approximately 160 ${F}_{ij}^{sd}$ variables.
Hence, for a particular light path, the size of the LP problem formulation can be decreased, and hence the number of equations and number of variables can be reduced for large networks.
The randomized rounding technique is highly probabilistic providing an integer solution in which the objective function finds a value close to the optimum of the rational relaxation [10]. This is a sufficient condition to show the nearoptimality of our 0–1 solution since the optimal value of the objective function in the relaxed version is better than the optimal value of the objective function in the original 0–1 integer program. This technique has been effectively used in multicommodity flow problems.
In randomized rounding, there are two types of ILP relation – showing existence outcomes of feasible solutions to an ILP in terms of its fractional relaxation and using the information obtained from the solution of the relaxed problem in order to obtain a good solution to the original ILP.
The multicommodity flow problem is an undirected graph G(V,E) having k commodities required to find the path. Here, various vertices are different sources and sinks for a particular commodity. Each edge e ϵ E where E has a capacity c(e) as an upper limit on the total amount of flow in E. The flow of each commodity in each edge is either 0 or 1. The objective function is to reduce the common capacity in each link for unit flows for all commodities. The problem is known to be NPcomplete [2] although the nonintegral version can be solved using linear programming methods in polynomial time. The algorithm has the following three major steps:
The requirement of the 0–1 flows is relaxed to allow fractional flows in the interval [0,1]. The relaxed capacityminimization problem is resolved by a suitable linear programming method. If the flow for each commodity i on edge e ϵ E is indicated by f_{i} (e), a capacity constraint of the form [10]
is then satisfied for each edge in the network, where C is the optimal solution to the nonintegral, edgecapacity optimization problem. The value of C is also a lower bound on the best possible integral solution.
The concept in this step is to translate the edge flows for each commodity i into a set of possible paths. For each commodity i, the following steps are required to be performed:
The weights of all the paths in τ _{i} are considered to be 1. Path stripping gives a set of paths τ _{i} that send an optimum flow of commodity i.
For each i, obtain a τ _{i}  with face probabilities equal to the weights of the paths in τ _{i} . Assign to commodity i the path whose face comes up. The integer capacity of the solution produced by the above procedure does not exceed [10]
where 0 < E < 1 with a probability of 1 – ε at least.
In this problem, the ${F}_{ij}^{sd}$ variables are permitted to take fractional values. These values are required to find the fractional flow through each of a set of alternate paths. A cointossing experiment chooses the path over which to transmit the light path λ_{sd} as per the probability of the individual paths. This technique is very good to resolve the problems of routing in the networks having a large number of nodes.
Once the path is chosen for all connections, the number of light paths passing through any physical fiber link is called as congestion on that particular link. Now, the wavelengths are assigned to each light path in such a way that any two light paths passing through the same physical link are assigned different wavelengths. If the intermediate nodes cannot perform wavelength conversion, a light path having the same wavelength throughout is allotted. This is basically a wavelengthcontinuity constraint reducing the utilization of the wavelengths in the network, since a light path finds a free wavelength of the same color in all of the physical fiber links of the path. This wavelength utilization is enhanced by the use of wavelength converters in a switching node. In the graph coloring model, the objective is to minimize the number of wavelengths (colors) under the wavelengthcontinuity constraint, which is achieved by the following steps [10]:
This problem is NPcomplete, as it is not easy to minimize the number of colors (chromatic number x(G) of the graph G) needed to color. The efficient sequential graph coloring algorithms estimate the number of colors. In a sequential graph coloring approach, vertices are sequentially incorporated to the portion of the graph already colored, and new colorings are determined to take in each newly adjoined vertex. At each step, the total number of colors is needed to be kept as minimum as possible. A particular sequential node coloring gives an x(G) coloring. A_{i} is the set of the nodes colored i by a x(G) coloring of G. For any ordering of the vertices V(G), i.e., for all members of A_{i} before any member of A_{j} for 1 ≤ i ≤ j ≤ x(G), the corresponding sequential coloring is an x(G) coloring.
If A(G) is the maximum degree in a graph, then x(G) < A(G) + 1. If a graph contains only a few nodes of very large degree, then coloring of these nodes stays away from the requirement of using a very large set of colors. The following theorems are required for coloring.
If G is a graph with V(G) = v _{1}, v _{2}, ..., v_{n} , where deg(v_{i} ) ≥ deg(v _{ i+1}) for i = 1,2,..., n − 1, then, x(G) ≤ max _{l ≤ I ≤ n} min {i, 1 + deg(vi)}. Estimation of a sequential coloring procedure corresponding to such an ordering will be called as largestfirst algorithm [1].
The sequential coloring approach demonstrates that for a given ordering v _{1}, v _{2}, ..., v_{n} of the vertices of a graph G, the corresponding sequential coloring algorithm does not need more than k colors where k = max_{1≤i≤n } {1 + deg_{<v 1,v 2…vn >}(v_{i} )} and deg_{<v 1,v 2…vn >}(v_{i} ) indicates the degree of node vi in the vertexinduced subgraph represented by <v _{1}, v _{2}, …, v _{n}>. A vertex ordering that minimizes k was found and can be determined using the following procedure [1,11,12]:
For any vertex ordering v _{1}, v _{2}, …, v _{n} determined, we have
for 1 ≤ i ≤ n, so that such an ordering is considered as a smallestlast (SL) vertex ordering. Any SL vertex ordering minimizes k over the n! possible orderings estimated [12]. The SL coloring algorithm determines the color of the light paths for wavelength allotment (Figure 3.2).
Figure 3.2 Auxiliary graph, G(V,E), for the light paths in the network [1].
For static and dynamic traffic analyses, a randomly generated physical topology consists of N nodes, with each node having a physical nodal degree uniformly distributed between 2 and 5. All links are made to be unidirectional, and there are V number of directed links in our simulation network. In the RWA problem, mainly three types of traffic are reported in the literature [1,13] – (a) static traffic, (b) incremental traffic, and (c) dynamic traffic.
The offered traffic follows the followings:
There are enough transceivers at the destination nodes/source nodes to accommodate all of the light path requests that need to be established, so no light path request will be blocked due to the lack of transceivers at these nodes.
For static light path establishment (SLE) of the physical topology having the set of connections to be routed, an LP formulation is made to find a lower bound on the number of wavelengths for the RWA problem [14]. To reduce the size of the LP formulation, K alternate shortest paths between a given SD pair are taken. Only the links constituting these alternate paths are represented as the ${F}_{ij}^{sd}$ variables, and a standard Kalternatepath algorithm derives K number of alternate shortest paths of an SD pair. This LP problem is solved by a standard LP solver package [15], and the resultant flow values for the ${F}_{ij}^{sd}$ variables are input to the randomized rounding algorithm. The value of the objective function indicates the lower bound on congestion that is achieved by any RWA algorithm. Considering the individual variables ${F}_{ij}^{sd}$ , the pathstripping technique and the randomization technique (mentioned in the previous section) are used to assign physical routes for different light paths. Once the light paths have been allotted on physical routes, a wavelength is allotted on each individual light path. This is carried out by coloring the nodes of graph G such that adjacent nodes get different colors, and this corresponds to allotting wavelengths correctly to the light paths with the SL vertex coloring as mentioned in Section 3.2.3.
For larger values of K, a number of wavelengths are required to have coloring of all light paths,and this number is a little higher but very close to the maximum congestion in the network. The maximum network congestion gives the number of wavelengths required in the network for the intermediate switching nodes having wavelength converters in which no wavelengthcontinuity constraint is followed for a light path. To resolve the large time complexity required for solving larger LP problems having a large number of alternate paths, two or three alternate paths may be taken.
In static problems, light path requests are known in advance. LP formulation and subsequent algorithms are needed to determine the number of wavelengths used to assign all of the light path requests. When the light path requests are dynamic and are not known in advance, the optimal algorithms used in SLE are not advisable. A dynamic algorithm is required for dynamic light path establishment (DLE) where it is adaptive to find a route for the incoming traffic/connections over different paths based on congestion on the different links. A heuristic based on leastcongestedpath (LCP) algorithm [1] is used for DLE. In the LCP algorithm, a light path is allotted on the LCP selected from a set of alternate paths between an SD pair. The wavelength assigned on this path is the first wavelength available among all wavelength channels where wavelengths are numbered randomly.
The congestion and number of wavelengths for assignment of connection requests mainly depend on the order in which the connection requests reach. In the DLE case, existing connections are not rerouted to assign a new connection blocked due to lack of free wavelengths. The set of connections are the same as those in the static case. The congestion using LCP routing is optimal after verification using the static optimization case based on randomized rounding algorithm for the same set of connection requests in the network. So the LCP algorithm reduces the congestion as each connection arrives. As the congestion increases in the network, the number of wavelengths required in the dynamic case is more than that needed in the static case. In the static case, the coloring algorithm assigned wavelengths to the light paths in a specific order and minimized the number of wavelengths required. This approach of graph coloring for assigning a wavelength to a light path cannot be used in the dynamic case in which light paths arrive in a random order. Due to the wavelengthcontinuity constraint, the optimal allocation of wavelengths cannot be easily achieved in the dynamic case. There are some approaches to reassign existing connections to unused wavelengths in order to optimally assign the resources for new connections. This problem is resolved by an algorithm that uses a fundamental operation called color interchange in which two light paths interchange their wavelengths to create spare capacity in the network.
In an RWA, there are two subproblems – routing and WA – which together make a hard problem. The RWA problem becomes simple when it is divided into the routing subproblem and the WA subproblem. In this section, we focus on various approaches to routing connection requests by following the ILP for SLE and DLE. The WA subproblem is considered separately in Section 3.4.
There are many routing algorithms used for static and dynamic light path establishments such as Dijkstra algorithm, Bellman–Ford algorithm, genetic algorithm, and stimulated algorithm. The route/path has to be determined by the routing function which requires correctness, fairness, simplicity, optimality, robustness, efficiency, and stability. The performance of the routing is estimated based on the following parameters:
For analysis of the abovementioned routing algorithms, a simple cost factor is considered for each physical link of the network. On the basis of minimum cost, the route of each sd pair is estimated using routing algorithm.
One of the most commonly used algorithms for routing is Dijkstra’s algorithm [16–18]. Using this algorithm, the shortest path from a given source to all other nodes as destinations is estimated, and the paths are determined in order of increasing path length. Here, for easy representation and explanation, we consider the leastcost path. At the kth stage, the least cost paths to k nodes closest source node is estimated, and these nodes are in set M. At the (k + 1)th stage, the node that has leastcost path from source node is added to set M. As each node is added to set M, its path from source node is distinct. Before describing the procedure of the algorithm, the following definition and notation are to be noted:
The algorithm has three steps: step2 and step3 are repeated until M = N; i.e., step2 and step3 are repeated till final paths have been assigned to all the nodes except node s in the network. The algorithm procedure is given below.
One iteration of step2 and step3 adds one new node to M and defines leastcost path from s to that node. That path passes only through nodes that are in M. After k iterations, there are k nodes in M, and the leastcost paths from s to each of the k nodes are derived. Among these paths, there is one of least cost that passes exclusively through nodes in M, ending with a direct link from a node in M to a node not in M. This node is added to M, and the associated path is defined as the leastcost path for that node. Table 3.1 shows the routing table of leastcost routing paths for source node s = 1 to all other nodes in the network (Figure 3.3) derived by using Dijkstra’s algorithm. At each step, the path to each node and the cost of that path are estimated. After the final iteration, the leastcost path to each node from source node s = 1 is derived. Figure 3.4 shows routing paths at iteration 1 (fig(a)), iteration 2 (fig(b)), and iteration 3 (fig(c)) using Dijkstra’s algorithm [17].
Figure 3.3 Sample network with link cost.
Figure 3.4 Routing by Dijkstra’s algorithm: (a) iteration 1, (b) iteration 2, and (c) iteration 3.
Iteration 
M 
D_{2} Path_{2} 
D_{3} Path_{3} 
D_{4} Path_{4} 
D_{5} Path_{5} 
D_{6} Path_{6} 

1 
[1] 
1 12 
4 13 
3 14 
– 
– 
2 
1 12 
2 123 
3 14 
4 145 
6 126 

3 
1 12 
2 123 
3 14 
4 145 
5 1456 

4 
1 12 
2 123 
3 14 
4 145 
5 1456 

5 
1 12 
2 123 
3 14 
4 145 
5 1456 

6 
1 12 
2 123 
3 14 
4 145 
5 1456 
The following may be a disadvantage of Dijkstra’s algorithm: there may be more number of iterations or steps required to achieve routing of all destination nodes for a large network having more number of nodes as the number of iterations is equal to the number of destination nodes.
Another of the most commonly used routing algorithms is Bellman–Ford algorithm [17–19]. Using this algorithm, one can find the leastcost path from a given source subject to the constraint that the path contains at most one link; find the leastcost path with the constraint that the path contains at the most two links; and compare the costs; and then find the least cost between those of the paths of two links, one link, and so on. Before describing the procedure of the algorithm, the following definitions and notation are mentioned.
The algorithm has two steps: step2 is repeated until none of the costs change. The algorithm’s procedure is given below.
For repeating step2 with h = K and each destination node n, the algorithm compares paths from s to n of K + 1 length that are less costly with the path that exists at the end of the previous iteration. If the previous path is less costly, then that path is selected; otherwise it is updated with a new path with more length K + 1; i.e., a new path consists of a path of K length plus a direct hop from node j to n. Table 3.2 shows the routing table of leastcost routing paths from source node s = 1 to all other nodes in the network (Figure 3.3) derived by using Bellman–Ford algorithm. The iterations are continued till the paths of all destination nodes are the same as those of the previous iteration. After the final iteration, the leastcost path to each node from source node s = 1 is derived. Figure 3.5 represents routing paths at iteration 1 (fig(a)), iteration 2 (fig(b)), and iteration 3 (fig(c)) using Bellmen–Ford’s algorithm.
h 
D_{2} Path_{2} 
D_{3} Path_{3} 
D_{4} Path_{4} 
D_{5} Path_{5} 
D_{6} Path_{6} 
0 
∞ – 
∞ – 
∞ – 
∞ – 
∞ – 
1 
1 12 
4 13 
3 14 
∞ – 
∞ – 
2 
1 12 
2 123 
3 14 
4 145 
5 126 
3 
1 12 
2 123 
3 14 
4 145 
5 1456 
4 
1 12 
2 123 
3 14 
4 145 
5 1456 
Figure 3.5 Routing by Bellman–Ford’s algorithm: (a) iteration 1, (b) iteration 2, and (c) iteration 3.
It is seen from Tables 3.1 and 3.2 that the number of iterations in Bellman–Ford’s algorithm is less than that in Dijkstra’s algorithm. Still Dijkstra’s algorithm is preferred because of its less time complexity [17]. Although these routing paths are determined on the basis of the cost of links, practically, the routing of paths for SD pairs is determined based on the shortest path of the signal or minimum time delay (where time delay consists of propagation time delay and queuing time delay).
In case of routing, many approaches are used for both static and dynamic routing such as fixed routing, fixedalternatepath routing, and adaptive routing [1].
The most simple approach of routing a connection request is fixed routing for a given sd pair. The fixed shortestpath routing for each sd pair is made offline using standard shortestpath algorithms such as either Dijkstra’s algorithm or the Bellman–Ford’s algorithm discussed in the previous section [17]. Dijkstra’s algorithm is preferred because of its less complexity compared to Bellman–Ford’s algorithm [17]. The routing table values for a node (source node) are found in that node considering other nodes in the network as destination nodes. As an example, the routing table values for node 1 as a source node of the sample network (Figure 3.3) estimated by using Dijkstra’s offline algorithm are given below.
Node1 


Destination Node 
Path 
2 
12 
3 
123 
4 
14 
5 
145 
6 
1456 
The routing table values for nodes 2, 3, 4, 5, and 6 estimated by using Dijkstra’s offline algorithm are given below.
Node2 
Node3 
Node4 
Node5 
Node6 

Destination Node 
Path 
Destination Node 
Path 
Destination Node 
Path 
Destination Node 
Path 
Destination Node 
Path 
1 
21 
1 
31 
1 
41 
1 
541 
1 
6541 
3 
23 
2 
32 
2 
412 
2 
5412 
2 
62 
4 
214 
4 
3214 
3 
4123 
3 
53 
3 
63 
5 
2145 
5 
35 
5 
45 
4 
54 
4 
654 
6 
26 
6 
36 
6 
416 
6 
56 
5 
65 
The connections of different sd pairs are set up with the predetermined route. Although this approach to routing connections is simple, there are drawbacks in this approach. WA (discussed later in this chapter) along the path is also fixed; i.e., there is no flexibility of WA if some paths have congestion. In fact, it provides high blocking probabilities in the dynamic case. Secondly fixed routing is unable to handle fault situations in which there are one or more link failures in the network. To handle link faults, the routing scheme must either consider alternate paths to the destination or find the route dynamically.
Fixedalternate routing is a method to routing that derives multiple paths. In fixedalternate routing, each node in the network retains a routing table that has an ordered list of a number of fixed routes to each destination node. The order is based on different parameters such as path length, time delay, and number of hops. For example, these routes for sd pair consist of the shortestpath route, the secondshortestpath route, the thirdshortestpath route, etc. A primary route for an sd pair is the first route in the list of routes to destination node d in the routing table at node s. An alternate route between s and d is any route that does not share any links (or is linkdisjoint) with the first route in the routing table at s. The term “alternate routes” is also used to describe all routes (including the primary route) from a source node to a destination node. All the alternate paths including the primary in the routing table from source node s to other nodes as destinations are determined by using the modified form of offline Dijkstra’s algorithm [17].
Node1  
Destination Node  Path1  Cost  Path2  Cost 
2  12  1  132  5 
3  123  2  13  4 
4  14  3  1354  10 
5  145  4  135  9 
6  1456  5  136  8 
Similarly, routing table values for other source nodes to corresponding destinations are estimated by using the modified form of Dijkstra’s algorithm [20]. When a connection request reaches a source node, the source node has to set up a connection on each of the routes in the routing table in sequence, until a route with a valid wavelength is allotted. If no route is obtained from the list of alternate routes, then the connection request is blocked and lost. The routing tables at each node have light paths ordered on the basis of hop numbers/shortest distance/minimum delay. So, the shortest/leastcost path to the destination is the first route in the routing table. When the distance/cost between different routes is the same, any one path may be considered randomly. The advantage of fixedalternate routing is that it can significantly reduce the connection BP compared to fixed routing [21].
Flooding is another simple routing technique which does not need any information/parameter values and by which a packet is sent from a source node to every neighboring node [17,22]. At each node, the incoming packet is transmitted on all outgoing links except the link through which it reaches the node. Due to this, multiple copies of the same packet reach the destination node. Figure 3.6 shows the transmission of a packet from node1 to destination node5.
Figure 3.6 Flooding in the network from node1 to node5.
Flooding approach is used to collect traffic information in dynamic routing for updating routing table based on the collection of traffic information. Flooding is highly robust and may be used to send messages especially in military applications. The principal disadvantage of flooding is that it causes more congestion/traffic overload, even for a small number of connection requests.
In adaptive routing, the route of sd pair is found dynamically, depending on the network state. The network state is established by the set of all connections currently in progress. The network state is represented by the following conditions:
For adaptive routing, information about the state of the network is exchanged between the nodes. There is a tradeoff between the quality of information regarding network state and the amount of overload.
One approach is an adaptive shortestcostpath routing which is suitable to wavelengthconverted networks. Under this approach, each unused link in the network has a cost of 1 unit, each used link in the network has an infinite cost, and each wavelengthconverter link has a cost of c units. If wavelength conversion is not available, then c is infinity. When a connection is established, the shortestcost path of an sd pair needs to be determined. If there are multiple paths with the same distance, one is selected randomly. By selecting the wavelengthconversion cost c appropriately, paths with wavelength conversion are selected only when paths with wavelength continuity are not found. In shortestcost adaptive routing, a connection is blocked only when there is no wavelength continuity or wavelength conversion from a source node to a destination node in the network. Adaptive routing path requires control and management protocols to continuously update the routing tables at the nodes.
In the approach based on LCP routing [1,23] for each sd pair, the succession of paths is preestimated. Upon the arrival of a connection request, the LCP among the preestimated paths is chosen. The congestion on a link is estimated by the number of wavelengths available on the link. Links that have fewer accessible wavelengths are said to be more congested. The congestion on a path is indicated by the congestion on the most congested link in the path. The priority to shortest paths is used in LCP to break any tie that occurs. A disadvantage of LCP is its computational complexity. In choosing the LCP, all links on all candidate paths have to be considered. A variant of LCP is proposed in [24] which only considers the first k links on each path (referred to as the source’s neighborhood information), where k is a parameter of the algorithm. Another approach is the distributed adaptive algorithm which estimates the paths as per time delay as performance criteria. Bellman–Ford’s algorithm is used for the estimation of routing paths. Each node of the network maintains two vectors:
where
This approach of distributed adaptive routing has the following shortcomings [17]:
This distributed approach of adaptive routing can be modified for the improvement of performance. In this modified approach, in every time interval (10 s), the node computes the average delay on each outgoing link. If there are any significant changes in delay, the information is sent to all other nodes using flooding. Each node maintains an estimate of delay on every network link. When new information arrives, it recomputes its routing table by using Dijkstra’s algorithm. Even after modification, there is a shortcoming: little correlation between reported values of delay and those already experienced after routing under heavy traffic load. This is because some links are loaded with heav traffic and some links are loaded with less traffic. This situation can be avoided if the threshold value of maximum traffic load is fixed for each link and the effect of this maximum value is to dictate that the traffic should not be routed around a heavily utilized line by more additional hops.
While establishing the connections in an optical WDM network, it also provides some degree of protection against link and node failures in the network by considering a portion of spare capacity [25–27]. Two approaches to faulttolerant routing are protection and restoration. The most commonly used approach is protection needed to establish two linkdisjoint light paths for the routes sharing any common link used in primary paths for every connection request. One light path, treated as a primary light path, is used for transmitting data, while the other light path is stored as a backup in the event that a link in the primary light path fails. To further protect against node failures, the primary and alternate paths are nodedisjoint. Fixedalternate routing is employed for protection. By selecting the alternate paths on the basis of the fact that their routes are linkdisjoint from the primary path, the connection is protected from any singlelink failures by allocating one of the alternate paths as a backup path. In adaptive routing, the backup path is also established immediately along with the primary path. The same routing algorithm determines the backup path. The resulting path should be linkdisjoint from the primary path.
In restoration, the restoration path is established dynamically as and when the failure occurs. Restoration is successful if sufficient resources are available in the network. When a fault occurs, dynamic discovery and establishment of a backup path under the restoration approach are significantly longer than switching over to the preestablished backup path using the protection approach. The details of protection and restoration are discussed in Chapters 7 and 8, respectively.
The static formulation in Section 3.2 may also provide fault protection in the network. The modified formulation requires additional constraint equations for two light paths to be set up for each connection (one primary light path and one backup light path), and Chapters 7 and 8 may be referred to for protection and restoration.
Randomized routing is a kind of probabilistic technique which can be used for routing permutation traffic with a reduced number of wavelengths. Apart from these, randomized routing has the advantages of simplicity and suitability for both centralized and distributed routing techniques [17]. The technique is developed for the multistage ShuffleNet for k stages and 2^{ k } nodes per stage. It works in three steps:
The maximum length of the chosen route is 3k − 1. Two models are considered and used in their node architecture and wavelength selection.
The model M _{1} has wavelength conversion capability. Each link has 3k − 1 disjoint sets of equal number of wavelength channels. Once the route has been chosen by the above routing algorithm, the following wavelength selection is used. A free wavelength in the set, S_{i} , 1 ≤ i ≤ (3k − 1), is used by the route in the step i. A routing node can convert wavelengths in S _{i} to those in S _{ i+1} for 1 ≤ i ≤ (3k − 1) and wavelengths in S _{ k+1}, S _{ k+2}, …, S _{3k−1} to those in S _{2k }. Using O(log^{2} N) wavelengths, the permutation routing problem can be solved using a high probabilistic (success) guarantee of 11/poly(N) for the model, where poly(N) is a polynomial in N.
The model M _{2} does not need the routing node having wavelength conversion capability. When a route is found using the above routing algorithm, it chooses randomly a wavelength which is free on all the links of the route. Using O(log^{2} N) wavelengths, the permutation routing problem can be solved using a high probabilistic (success) guarantee of 11/poly(N) for the model.
There are two types of WA approaches – static WA and dynamic WA. Assigning wavelengths to different light paths in a manner that minimizes the number of wavelengths under the wavelengthcontinuity constraint using the graphcoloring problem was discussed in Section 3.2.3.
By considering the routing approaches in Section 3.3, WA heuristics are discussed in dynamic WA after selecting paths by routing. These heuristics are also considered for the static WA by ordering the light paths, and then the paths are assigned wavelengths as per the order. The heuristic methods allot wavelengths to light paths as soon as the connection request arrive. For the dynamic problem, the number of wavelengths are also minimized, whereas in the static case, the number of wavelengths is fixed (this is the practical situation), and we have to minimize connection blocking.
The following heuristics are reported in the literature [1–5]: (1) random, (2) firstfit (FF), (3) leastused/spread, (4) mostused/pack, (5) minproduct, (6) leastloaded, (7) maxsum, (8) relative capacity loss (RCL), (9) distributed relative capacity loss (DRCL), (10) wavelength reservation (WRSV), (11) protecting threshold, (12) prioritybased WA, and (11) dispersion reduction WA. These heuristics can all be implemented as online algorithms and can be combined with different routing schemes. Most of the schemes attempt to reduce the overall BP for new connections, while the last two approaches aim to reduce the BP for connections that traverse more than one link. In our discussions, we use the following notation and definitions:
For assigning wavelengths, available wavelengths are searched in a path. Most of the search algorithms are based on graph coloring. Some of the constraints used in graphcoloring problems were discussed in Section 3.2.3. In this section, different searching algorithms are discussed.
The algorithm providing the optimum coloring of a given graph is presented in Figure 3.7. The algorithm splits the possible colorings into two different cases in which each step until the graph is perfect where each node is a neighbor of all the other nodes. In each step, a pair of nodes which are not neighbors are searched [28,29]. Now these nodes can be colored with the same color or with different colors. If the nodes are given the same color, we can clearly merge them into one node inheriting all the neighbors of the merged nodes. Otherwise, if different colors are provided to the nodes, we can make an edge between them (right subtree in the figure). At the end, among all the perfect graphs, we pick the one which has the smallest number of nodes as shown in Figure 3.7.
Figure 3.7 Coloring of nodes using exhaustive search.
Tabu search (TS) is a relatively new heuristic method. It is a random local search in which some movements are forbidden (i.e., tabu) [29,30]. Usually a move leading back to the previous point is classified as a tabu move for certain number of rounds. This should make it possible to get away from local minima. The search is ended when the cost function reaches a certain predefined value or a certain number of rounds has elapsed. This algorithm differs from all the previous ones in that it considers finding not the minimum coloring but a legal kcoloring for the given graph, i.e., it tries to select for each node one of the k colors in such a way that no neighboring nodes get the same color.
We consider s = (V _{1}, V _{2} … V_{k} ) be a partition of graph G, where subset V_{i} of nodes represents those nodes having color i. Define a cost function as $f\left(s\right)=\underset{i}{\mathrm{\Sigma}}\text{}E\left({V}_{i}\right)$ , where E(V_{i} ) is the number of edges in subgraph V_{i} . If there is an edge in some subgraph, it means there are neighbors sharing the same color. So when f(s) = 0, we have a legal kcoloring for the graph. We are given a graph G, target number of colors k, length of tabu list │T│, number of neighbors rep, and maximum number of iterations nmax [30].
In the neighborhood of a partition, we define partitions where one node is moved to another subset. In order to find the minimum k for which the algorithm finds a legal coloring, we must run the algorithm several times with decreasing values of k until the algorithm fails. On the other hand, if we are only interested in getting a feasible kcoloring, the iteration is not required.
Simulated annealing (SA) is one of the techniques for wavelength coloring [28,29]. The idea is based on simulated annealing of some object. The objective function represents the energy of the system, and the control variable T represents its temperature. In the algorithm, the higher the temperature is, the greater is the probability of acceptance of a move leading to a higher energy state. The node coloring problem is solved with SA: The energy E of the system is the number of used colors. Following are the steps in the SA algorithm:
Also other kinds of formulations have been suggested for the energy function. A drawback with this formulation is that energy can only have discrete values, and this makes it hard for the algorithm to find the right direction to advance.
The genetic algorithm (GA) is another widely used method for wavelength search in graph coloring. In GA, the idea is to simulate evolution. Here vectors represent genotypes, and the node coloring problem, which can be solved by GA, has to be found [28]. In this case, the vectors define the order in which the nodes are colored. So the best ordering to color the nodes has to be found with the greedy algorithm. The choice of crossover operation for permutations is not straightforward, and several different schemes have been proposed. Let A and B be the parents. A is chosen randomly, but those that give good coloring are favored. B is chosen randomly from the whole population. The length of both vectors is N.
The algorithm procedure is as follows:
So basically the order of both parents is combined to get the child. In each step, the next element of randomly chosen parent is copied to the child if it is not there yet. Index i_{A} points to the next element of parent A and i_{B} to that of parent B. As a mutation operator, we simply exchange the places of two random nodes in the vector.
There are many approaches used for WA/selection: randomized approach, first fit, least used, most used, minproduct approach, least loaded, maxsum, relative capacity loss, distributed relative capacity loss, prioritybased approach, dispersion reduction assignment, etc.
In this scheme, the first search is to determine the set of all wavelengths available on the path chosen by routing. Among the available wavelengths, a wavelength (usually with uniform probability) is chosen in the following manner [1,3,5].
All the wavelengths are indexed, and all the indices can be selected when generating the order randomly. The wavelength usage factor is not used and thus does not require any global state of information.
In this approach, we index all wavelengths. For searching the available wavelengths, a lowerindexed wavelength is chosen before a highernumbered wavelength. Its time complexity is lower than that of random WA since there is no need to search the entire wavelength space for each connection request allotted to the path. The idea of FF is to orient all the inuse wavelengths toward the lower end of the wavelength indices so that the probability of continuous and longer paths being available toward the higher end of the wavelength is high. In FF, BP and fairness, computational overhead, and time complexity are decreased and are also less than those of other schemes [1,3].
LU approach chooses the wavelength which is less used in the network for giving the load balancing of all the wavelengths. This approach considers breaking the long wavelength paths quickly. Here connection requests are set up only on a small number of links serviced in the network. The performance of LU is worse than that of the random approach, because of additional communication overhead needed to compute the LU wavelength). This approach also needs additional storage and has higher computation complexity [1,5].
This approach operates in a way opposite to that of the LU approach. It chooses the MU wavelength in the network. Its performance is better than LU approach [31,32]. The overhead, storage, and computational complexity are the same as those in the LU approach. The MU approach performs slightly better than the FF approach in packing connections into fewer wavelengths and conserving the extra capacity of lessused wavelengths.
This approach is employed in multifiber networks [33]. MP approach to a singlefiber network basically operates with a concept similar to that of the FF approach. Here MP approach is based on packing wavelengths into fibers, and it minimizes the number of fibers in the network. MP approach first computes:
for each wavelength j, i.e., 1 ≤ j ≤ W. If X represents the set of wavelengths that minimize the above value, then MP approach considers the lowestnumbered wavelength in X. This approach has additional computation costs/complexity.
Like MP, the LL heuristic is also employed in multifiber networks [34]. This heuristic selects the wavelength having the largest residual capacity on the mostloaded link along route p. While using in singlefiber networks, the residual capacity is either 1 or 0, and it chooses the lowestindexed wavelength with residual capacity 1. Thus, it is also used as an FF approach in singlefiber networks. The LL approach chooses the lowestindexed wavelength j in S_{p} .
The LL approach’s BP performance is slightly better than those of MU and FF approaches in a multifiber network.
This approach [35] was employed in multifiber networks, but it is also used in singlefiber networks. It uses all possible paths (light paths with their preselected routes) in the network for path selection and maximizes the remaining path capacities after light path establishment. The traffic matrix (set of possible connection requests) is known in advance, and the route for each connection is preselected. This condition is fulfilled if the traffic matrix is stable for a period of time. To describe the heuristic, the following notations are taken.
φ represents the network state specifying the existing light paths (routes and WAs) in the network. In this approach, the link capacity on link l and wavelength j in state φ, r(φ, l, j), is considered as the number of fibers on which wavelength j is unused on link l, i.e.,
where D(φ) = D matrix in state φ. The path capacity r(φ, p, j) on wavelength j represents the number of fibers on which wavelength j is available on the mostcongested link along the path p, i.e.,
We consider
P is the number of all potential paths for the connection request in the current state. Once the light path is set up for the connection, the network state is changed, and the processing of the next connection request starts.
RCL approach [36] can be viewed as an MS approach that chooses the wavelength j to minimize the capacity loss on all light paths expressed as
where φ is the network state before the light path is set up. The capacity on wavelength j reduces after the light path is set up on wavelength j; MS chooses wavelength j by minimizing the total capacity loss on this wavelength. Total capacity loss is written as
In RCL, wavelength j is chosen to minimize the relative capacity loss written as
It is estimated that RCL approach minimizes capacity loss, but it may not give the best choice of wavelength. Choosing wavelength i may block one light path p _{1}, whereas choosing wavelength j decreases the capacities of light paths p _{2} and p _{3} but does not block them. So wavelength j should be chosen over wavelength i, even though the total capacity loss for wavelength j is more than the capacity loss of wavelength i. Thus, the RCL approach calculates the relative capacity loss for each path on each available wavelength and then selects the wavelength that minimizes the sum of the relative capacity losses on all the paths. Both MS and RCL approaches are employed for nonuniform traffic by taking a weighted sum over the capacity losses.
There are additional costs in applying all the mentioned algorithms – LU, MU, MP, LL, MS, and RCL – as per global knowledge of the network state in a distributed control network. Information on the network state is exchanged frequently between the nodes to ensure accurate calculations, by using linkstate routing protocol. Although the MS and RCL approaches perform better, the implementation of these is not easy but cost effective in a distributed environment, and also MS and RCL both employ fixed routing that does not improve network performance. Two issues have to be dealt with:
Here, each node in the network keeps record of information on the capacity loss on each wavelength on the basis of table lookup; a small amount of calculation is required upon the arrival of a connection request. To obtain a valid table, the related values are changed after updating the network state. To simplify the computation, the DRCL algorithm is employed. The routing is performed using Bellman–Ford’s algorithm [1]. As per Bellman–Ford’s algorithm, routing tables are determined in each node with its neighboring nodes as a destination and updates its own routing table as per information of update network state. An RCL table is needed at each node, and the nodes are allowed to exchange their RCL tables as well. The RCL tables are exchanged in a similar manner as the routing tables. Each entry in the RCL table has information of wavelength w, destination d, and rcl(w, d). When a connection request arrives, more than one wavelength is available on the selected path by computation carried out among these wavelengths on the basis of the information acquired at each node. The MS and RCL approaches consider a set of potential paths for future connections. DRCL approach considers all the paths from the source node of the arriving connection request to every other node in the network, excluding the destination node of the arriving connection request. DRCL approach then chooses the wavelength minimizing the sum of rcl(w, d) over all possible destinations d calculated at source node as follows.
Most of the WA schemes minimize BP considering that longer light paths have a higher probability of getting blocked than shorter paths and some schemes attempt to protect longer paths. The schemes mentioned in this section need wavelength reservation (WRSV) and wavelength threshold protection (WThr) [37]. Normally, an RWA algorithm gives priority to shorter hop counts in comparison to longer hop counts, blocking longer hop connections. This gives rise to the fairness problem. In order to improve fairness among connections, an appropriate control is employed to regulate the admission of a connection request. There is a BP associated with each sd pair having longer hop connections and the corresponding arrival stream. In the next section, we discuss the same.
A global measure is required to control overreduction of blocking of longer hop connections for fairness improvement. The use of wavelength converters improves blocking performance. A wavelength converter is capable of shifting one wavelength of incoming signal to another wavelength to relax wavelength constraints. Wavelength rerouting is another option to improve BP performance. Although both wavelength converter and wavelength rerouting increase fairness, in both the cases, time complexity and cost of the network increase. A fairness improvement algorithm has the following properties in addition to improving fairness:
For achieving fairness in wavelength routing, the following issues must be addressed [1]:
In wavelength reservation, to lower the BP of traffic stream on a longer route, one or more wavelengths are kept solely for this purpose on every link of the route. The links used for the route are called logical links. When a connection is allowed to try for other wavelengths, others are not allowed to use the reserved logical link. Since an exclusive logical link is reserved for a traffic stream, the chance of being blocked is reduced, and at the same time, setup time is also reduced. Hence, it increases fairness. It is difficult to reserve logical links always. A complex procedure will be required to optimally choose logical links for a topology and a fixed number of wavelengths per fiber. WRSV is either centralized or distributed. There are two ways of WRSV to assign a wavelength for a route: forward reservation and backward reservation. Since these two reservations are used for mesh topology, they are based on a distributed approach because connection requests arrive at the node at which a connection request has to be established and allocated with wavelength.
The forward reservation method is based on alternate path routing, and it reserves the wavelengths on the links while the control message is passed forward from the source to the destination seeking for a free wavelength on a route. The message carries along with it the set of wavelengths denoted by S _{free} that is free on all the links. When a node is visited by a message through the incoming link of the node, S _{free} is updated by taking the intersection of this set with the set of wavelengths that are free on the outgoing link of the node. Every node maintains a table having the state of each outgoing link with available wavelengths. The light path is the connection_id having the source, destination, and seq_no. The following control messages are used by the forward reservation protocol [1].
The different parameters used in designing the forward reservation method are mentioned below [1]:
Protocol Mechanism
There are two situations used for processing requests in forward reservation: successful reservation of a wavelength and reservation failure. The following procedure is used for processing requests arriving from nodes to establish and release light paths [3,5].
The above procedure is repeated for MAX_TRIES number of times leaving a GAP between two successive tries. If everything fails, the connection request is rejected. When data transmission on the allocated light path is complete, the source node s prepares a Rel message carrying the connection_id and route information of the light path. This message is transmitted toward the destination d. When a node receives Rel message, it updates the table with the information that the wavelength used by the light path on the specified link can no longer be used and is now available for another connection request. When the Rel message reaches d, the release operation is completed. Figure 3.8a shows the forward reservation situation, where there is a free wavelength and the reservation is successful. Figure 3.8b shows the forward reservation situation, where there is no free wavelength and the reservation fails.
Figure 3.8 Forward reservation: (a) free wavelength and successful reservation and (b) unsuccessful reservation.
In the forward reservation method, wavelengths are reserved on the links of the specified route using control messages during forward transmission from source s to destination d. There may be wavelength conflicts during reservation, since the set of wavelengths denoted by S _{free} participate during reservation in intermediate nodes. This may provide poor wavelength or bandwidth utilization. To remove these shortcomings, backward reservation is used. In this technique, there is no reservation during forward transmission of control messages; rather all the wavelengths are collected during forward transmission. Once the set of wavelengths are known to the destination node, it sends the control message with the set of available wavelengths. While the control message travels backward from destination to source, it reserves the wavelength on the link, and ultimately one wavelength is reserved after the control message reaches the source node. The following control messages are used by backward reservation protocol [1].
Protocol Description
When a connection request arrives at the source node, the following steps are to be taken in backward reservation [1].
When the message is at intermediate node i, it selects the next link from route information, and S _{free} is updated by considering common wavelengths on the outgoing link. The above procedure is repeated for MAX_TRIES number of times leaving a GAP between two successive tries. If everything fails, the connection request is rejected. When the data transmission on the allocated light path is complete, the source node s prepares a Rel message carrying the connection_id and route information of the light path. This message is transmitted toward the destination d. When a node receives a Rel message, it performs the necessary table update that the wavelength used by the light path on the specified link can no longer be used and is now available for another connection request. Figure 3.9a shows the backward reservation situation, where there is a free wavelength and the reservation is successful. Figure 3.9b shows the forward reservation situation, where there is no free wavelength and the reservation fails. Figure 3.9c represents the situation where the reservation fails due to nonavailability of free wavelengths which the Res control message is trying to reserve. This failure of reservation is due to the fact that during the forward transmission of the Collect message the wavelength is free but during backward reservation it is not free.
Figure 3.9 Backward reservation: (a) successful reservation of wavelength, (b) failure due to the nonavailability of free wavelength, and (c) failure of WRSV.
Congestionbased routing WRSV is an extension of backward reservation technique [1,38] for a given sd pair; the leastcongested route among all the candidate routes is selected. The congestion of a route is measured by the number of light paths that are currently used in the route.
In this case, when a connection request arrives at node s, it starts searching a parallel route. The source node generates Collect messages, one for each candidate route corresponding to the destination node d. All these messages are transmitted to the destination, collecting all the free wavelengths on various links of the candidate routes. When the node d receives Collect messages transmitted from all the candidate routes, it chooses the best route among them on the basis of least congestion. The best route having least congestion is estimated on the basis of the fact that the route has the maximum number of free wavelengths available. The destination node generates a Res message and transmits it to the source along the selected route. S _{free} of the Res message is set to that of the Collect message received on the selected route. When the Res message reaches the source, one wavelength is chosen for assigning the connection request. The situation may arise that the wavelength which is available during forward transmission is not available during backward transmission. This results in reservation conflicts because of attempting reservation for many connection requests. In order to reduce these reservation failures during backward transmission, the Collect message can collect the conflicts for each of the wavelengths on various links. At the same time, each node keeps track of the number of connection requests. On the basis of all the above information, the Collect message chooses appropriate wavelengths on the route for reservation. If there is no free wavelength, then the destination node sends Collect_Fail toward the source node s [1].
For LCP routing, all the candidate routes are searched in parallel. In fact, this results in the increase of both control message traffic and connection setup time. The kneighborhood routing method [1] attempts to overcome the increase of the above difficulties. When a connection request reaches the node, the two steps are followed: route selection and wavelength selection.
In the route selection step, the best route is chosen among all the candidate routes by collecting congestion information about the routes on the first k links. This method ensures that the control traffic and setup time are reduced. The source node s prepares Collect messages, one for each candidate route, and sends them along the candidate routes. Every collect message passes through k links on the route gathering wavelength availability and conflict information. The kth node sends to the source a message with a set of wavelengths available on the first k links. When the source receives a message containing the above information from k neighborhood nodes, the leastcongested route is chosen. Instead this information could be collected when the actual demand arises. When another connection request arrives, the route is selected based on the locally available information.
The next phase of kneighborhood routing is wavelength selection in which a free wavelength is chosen by using forward reservation method and is reserved on the selected route. If no wavelength is available on the chosen route, other routes can be considered in the nondecreasing order of congestion. Backward reservation may also be used for WRSV. In backward reservation, the Collect message is taken for collecting conflict information on the basis of which the wavelength is chosen [1].
In WThr protection, connections of shorter hops are allocated with a wavelength only if the number of the idle wavelengths on the link is at or above a given threshold. Some free wavelengths can be used by longer hop connections. By increasing the chance of acceptance, the setup time of more longer hops becomes shorter. This results in assignment of longer hop connections. In this situation, a number of wavelengthdiscontinuous routes may be generated.
If the traffic load for longer hops in the network is lower, preventing shorter hop connections from sharing some wavelengths will result in poor wavelength utilization and unnecessary degradation in the performance of shorter hop connections. A connection with the longest route among the designated shorter hop connections may acquire more penalties in comparison to a connection using the shortest route among the designated longer hop connections.
In this method, shorter hop connections are provided with few alternate routes, whereas longer hop connections are provided with more alternate routes. By limiting the number of alternate routes for shorter hop connections, more longer hop connections are accommodated [39–41]. It provides moderate setup time and also increases fairness. In case of sparse network having high traffic load, the fairness may deteriorate. When traffic load is low, the provision of additional routes assigns wavelengths for both shorter and longer hop connections as the chance of finding a free wavelength on an additional route is enhanced. As traffic load increases, WA to longer hop connections is an important issue. Additional alternate routes may not provide significant improvement because additional routes have many hops sharing many links resulting in the use of more wavelengths for a connection request.
In this method, the available wavelengths are divided into two subsets – F set and P set. Accessing the wavelengths from F set is free, whereas accessing the wavelengths from P set is prioritized [42–44]. Every connection request (sd) has priority associated with it fixed a priori. This method first searches wavelengths from F set. If no free wavelength is available from F set, then the connection registers its priority on the links of the route and tries to get wavelengths from P set as per the priority level along the route. WRSV fails if higherpriority connections are registered. The wavelength utilization increases as no request is prevented from using any wavelength. In fact, the longer hop connections have more chances to get wavelengths from P set.
The disadvantages of this method are various connection requests need to be determined and the higher the P set, higher is the penalty of shorter hop connections. The connection setup time is more because of the registration of priorities.
This method overcomes the shortcomings of static priority method by updating the priority of various streams. The priority of traffic stream at an instant of time depends on the past information – average, minimum, and maximum of estimated values of the streams in the network [44]. Every node can estimate the performance of the outgoing streams in terms of their BP. The average, minimum, and maximum of estimated values are transmitted periodically to other nodes in the network. Reservation is done in the same way as done in the static priority method. Since the priorities are estimated on the performance, shorter hop connections are not over penalized. If the performance degrades for some connections, the priorities of these connections should be increased. In turn, the performance increases.
In this case, the wavelengths are divided into two sets – free access set (F set) and priority access set (P set). A connection request is assigned with free wavelength from F set on the link of the route, whereas it can access a wavelength from P set as per priority estimated on the basis of information updated periodically. Every node keeps a table of precomputed candidate routes. The priority information on a link includes a number of computing requests with their priority level. So the connection_id includes source, destination, and seq_no. The following control messages are used by the routing protocol.
Protocol Mechanism
The procedure of the protocol for light path establishment and release is given below [44].
When data transmission on an assigned light path is completed, the source node s generates a Rel message carrying the route and wavelength information used by the light path up to the destination. When the nodes receive the release messages, the messages are updated in the table. The proposed protocol and various control messages are shown in Figure 3.10. Figure 3.10a shows successful reservation of a wavelength in F set, whereas Figure 3.10b shows successful reservation of a wavelength in P set and Figure 3.10c represents reservation failure.
Figure 3.10 Dynamic priority reservation: (a) successful reservation of wavelength in F set, (b) successful reservation of wavelength in P set, and (c) failure of WRSV.
Priority Computation
Since the wavelength reservation is also made on the basis of the priority level of sd pair from P set, it is required to know how the priority level of sd pair is computed [41–44]. This method uses three priority levels – low, medium, and high. The priority levels are computed dynamically by estimating periodically the global network performance of the traffic streams. Every node keeps track of the BP performance of the traffic streams originating from it and destined to other nodes. This is measured with reference to a predefined start time. This information is updated at regular intervals of time. Thus, each node keeps track of the minimum (min), maximum (max), and average (avg) of the blocking probabilities of the traffic streams originating from it. At regular intervals of UPDATE (a protocol design parameter) time units, the values of min, max, and avg are updated. These values are kept in the Blk_Info message broadcasted to other nodes through links of a precomputed spanning tree over the shadow network having the same number of nodes.
When a node receives a Blk_Info message, it computes a new estimate of the global minimum (gmin), global maximum (gmax), and global average (gavg) of the blocking performance of various traffic streams. These values are used to determine the priority level sd pairs. Two threshold values, Lthr (lower threshold) and Uthr (upper threshold), are computed as functions of gmin, gmax, and gavg. If the observed BP of an sd pair is above Uthr, its priority level is set to be high. If the observed BP of an sd pair is below Lthr, its priority level is set to be low. If the observed BP of an sd pair is in between Uthr and Lthr, its priority level is set to be medium. Thus, priority levels are changed adaptively. This provides several advantages: First it avoids over penalizing for shorter hop connections where for the degradation of the performance of shorter hop connections, the priority level increases.
The physical topology of the network has been modeled as a unidirectional graph G (V, E), where V is the set of nodes and E is the set of links between nodes in network. We consider each link consists of two unidirectional fibers (two fibers carrying the same wavelengths in the reverse direction). It is assumed that each fiber link can carry the same number of wavelengths. We first introduce the following notation:
The following inputs are supplied to the problem:
The time delay (T _{d}) experienced by the traffic is a combination of propagation time delay (T _{p}) and queuing time delay (T _{q}). The propagation time delay can be computed as follows [3]:
The queuing delay can be computed as follows:
where C_{m} = maximum capacity per light path.
Equation (3.11) shows that the traffic offered in the light path is the sum of the traffic on to the light paths due to all node pairs.
Minimize
The traffic flow constraints pertain to the traffic routed over the light paths in the network [3].
Equation (3.13) defines network congestion; i.e., the component of traffic on a light path due to a node pair can be at the most the amount of traffic flow between the nodes in a pair. Equation (3.14) shows that the traffic can flow only through the existing light path. Equation (3.15) expresses the conservation of traffic flow at the end nodes of a light path.
The wavelength constraints pertain to the assignment of wavelengths to the light paths [1,3,45].
Equation (3.16) shows that the wavelength used by a light path is unique. Equation (3.17) expresses the wavelengthcontinuity constraint. Equation (3.18) shows that two light paths cannot use the same wavelength on a link. Equation (3.19) expresses the conservation of wavelengths at the end nodes of physical links on a light path.
To reduce the BP in the network, a prioritybased RWA (PRWA) scheme [44,45] is considered in which connection requests for RWA are served according to their priority. The priority order of each connection request is determined on the basis of the following two criteria: type of path (direct link or indirect link physical path) and volume of traffic. Using these criteria, direct link connection requests are assigned with higher priority compared to connection requests having indirect link. Then after, the connection requests with direct or indirect link are served in the descending order of their traffic volume. Our goal is to reduce the overall blocking probability (BP)and hence to enhance the effective utilization of a given capacity optical network. To achieve our goal, we consider the type of path and traffic volume as the criteria for priority ordering of connection requests, which is required due to the wavelengthcontinuity constraint of the network. The wavelengthcontinuity constraint needs the use of the same wavelength on all hops in the endtoend path of a connection. Use of a conventional RWA approach under the wavelengthcontinuity constraint may lead to a situation where wavelengths may be available but connection requests cannot be established due to the unavailability of the required wavelengths. Therefore, if the priority order of connection requests is estimated using these criteria, blocking of connection requests due to the wavelengthcontinuity constraint can be reduced to a great extent, which will in turn lead to better performance of the network in terms of lower BP. The overall concept of the scheme is explained in Figure 3.11. In the figure, random connection requests arrive at the system based on Poisson process. Then, the connection requests are enqueued into the priority queue to estimate their priority order. Finally, connection requests are served based on the RWA approach according to their priority order. If the connection request is not served within the holding time (t _{H}), it is treated as a blocked connection. The detailed procedure of the proposed scheme is given in Algorithm 1, and the functionality of the algorithm is explained by considering an example of the National Science Foundation Network (NSFNET) (Figure 3.12) and also assumes a few connection requests that are shown in Table 3.3.
Figure 3.11 Prioritybased WRA concept.
Figure 3.12 NSFNET T1 optical backbone with distance matrix.
According to Algorithm 1, two clustered sets of connection requests (R′ and R″) [44] are estimated such that
Then, the priority order of each connection request is estimated and is given in Table 3.4. Finally, connection requests are served based on the RWA approach according to their priority order.
Connection Request 
Traffic (kbps) 
Connection Request 
Traffic (kbps) 
Connection Request 
Traffic (kbps) 

r ^{ WA.CA 2 } 
2500 
r ^{ WA.CA 1 } 
3500 
r ^{ WA.UT } 
40500 
r ^{ WA.CO } 
20500 
r ^{ WA.TX } 
22500 
r ^{ WA.NE } 
48500 
r ^{ WA.IL } 
800 
r ^{ WA.PA } 
25800 
r ^{ WA.GA } 
45500 
r ^{ WA.MI } 
24300 
r ^{ WA.NY } 
70300 
r ^{ WA.NJ } 
30700 
Connection Request 
Order 
Connection Request 
Order 
Connection Request 
Order 

r ^{ WA.CA 2 } 
1st 
r ^{ WA.CA 1 } 
2nd 
r ^{ WA.UT } 
3rd 
r ^{ WA.CO } 
4th 
r ^{ WA.TX } 
5th 
r ^{ WA }. NE 
6th 
r ^{ WA.IL } 
7th 
r ^{ WA.PA } 
8th 
r ^{ WA.GA } 
9th 
r ^{ WA.MI } 
10th 
r ^{ WA.NY } 
11th 
r ^{ WA.NJ } 
12th 
Algorithm 1: PRWA [44]
Input: Network configuration and a set of connection requests
Output: WA with total number of successful and unsuccessful connections in the network
Mathematical Formulation
We model the physical topology of an optical network as a directed connected graph G(V,E,W), where V is the set of nodes and E is the set of bidirectional optical fiber links or edges of the network. Here each link e ϵ E has a finite number of wavelengths, W. In the network, a nonnegative cost (distance between adjacent nodes) C(e) is assigned for every e.
The cost between nodes a and b is considered to be 1 if there exists no link between a and b. The following assumptions are considered in the model [44,45]:
The following notations are used in this formulation:
Constraints
The wavelength constraints used in priority RWA are the same as those used in Sections 3.6.1 and 3.6.2 (equations 3.14–3.19)
Traffic Flow Constraints
The traffic flow constraints related to the traffic routed over the light paths in the virtual topology are given below [44]:
Equation (3.21) states that the traffic on a light path is the total traffic due to all the node pairs. The congestion of the network is expressed by using equation (3.22).
Bandwidth Constraints
The bandwidth constraints related to the bandwidth of a connection request and the maximum capacity of a channel in the network are [44]
Equation (3.23) expresses the fact that the traffic flow between the source and the destination in an sd pair cannot exceed the maximum bandwidth of the connection request. Equation (3.24) expresses the fact that the total amount of traffic on a light path from node i to node j cannot exceed the capacity of the light path from i to j.
In order to control wavelength routing and multiplexing or demultiplexing the signal in the optical network, a network node is being designed according to the PRWA algorithm [44] (which will be discussed later in this chapter). Figure 3.13 shows the logical architecture of the network node which uses a number of devices such as F WDMs/wavelengthdivision demultiplexers (WDDMs) [46], W thermooptic switches (TOSWs) [47,48], W transceivers, W add–drop multiplexers (ADMs) [49,50], a SONET STS192 multiplexer/SONET STS192 demultiplexer [51], and a wavelength router based on the PRWA algorithm. In the figure, initially, a number of connection requests arrive at the system randomly based on a Poisson process. The connection requests (as per bandwidth) having the same sd pair are then groomed/grouped with the hierarchical time division multiplexer SONET STS192. (For example, if the connection requests of bandwidth 622.08 Mbps are groomed, then a maximum number of 16 connection requests are accommodated with SONET STS192.) The groomed connection requests are assigned the wavelengths using the PRWA algorithm. The signals of the assigned wavelengths are sent by using transmitters and added to TOSWs through ADMs. Then, the wavelengths are switched by TOSWs [48,49] and finally are multiplexed by WDMs to the output fiber link specified by the wavelength router based on the PRWA algorithm to deliver to the destination node. Further, the wavelengths from input fiber links are demultiplexed by WDDMs which are then switched by TOSWs and multiplexed to the corresponding output fiber link to deliver the signals to the destination node. The wavelength carrying the signal for the node itself is dropped through the ADM and demultiplexed by the SONET STS192 demultiplexer to send the signals to the users.
Figure 3.13 Network node architecture (WDDM: wavelengthdivision demultiplexer, WDM: wavelengthdivision multiplexer, TOSW: thermooptic switch, MUX: multiplexer, DMUX: demultiplexer, TX: transmitter, RX: receiver, ADD–DROP: add–drop multiplexer, PRWA: prioritybased routing and wavelength assignment).
Figure 3.14 shows BP versus the number of wavelengths (W) for different routing algorithms such as FR, fixed alternate path routing (FAR), and alternate path routing (AR) using FF method with 100,000 connection requests [5]. In this simulation, we do not consider low cost routing (LCR) because from the literature survey, it is seen that the performance of LCR in terms of BP is almost the same as that of FAR [5]. For comparison purpose, in this figure, we have included the result of PRWA scheme based on FF method with the same number of connection requests. It is seen from the figure that in all routing algorithms, BP decreases with the increase of number of wavelengths due to the establishment of more light paths, but the rate of decrease of BP for AR is more than that for other routing algorithms. This is because, in AR, all the possible routes (K > 2) are considered between the sourceand destination in an SD pair on the basis of link state information. Further, it is observed that BP for PWRA scheme (K = 2) is less than FR and FAR due to the incorporation of the prioritization concept with AR (K = 2). It is also seen from the figure that the BP of FAR is less than that of FR due to the consideration of alternate paths (K = 2) for establishing a connection request. We have also seen that the BP of AR with FF method is less than that of PRWA scheme based on FF method, but the average setup time of AR is much more higher compared to that of PRWA. This is mainly because, as the number of paths increases, the average setup time also increases (which is shown in the inner graph of Figure 3.7). AR algorithm considers all the possible routes/paths (in our simulation which is >2) for RWA, whereas in PRWA scheme, only two paths are considered for each connection request. Therefore, we incorporate prioritization concept with alternate path routing (K = 2) for the study of different WA schemes (Figure 3.15).
Figure 3.14 BP versus number of wavelengths for FR, AR, FAR, and PRWA.
Figure 3.15 BP versus number of wavelengths for FF, LU, and random WA.
BP performance of different WA heuristics are compared with respective traffic loads using simulation on NSFNET T1 optical backbone as shown in Table 3.5 [5]. Each link in the network contains M fibers, and each fiber supports W wavelengths. Z is the total number of connection requests, L _{2} is the total number of links, L _{1} is the length of longest route of any node pairs, and N is total number of nodes in the network. The MP approach and LL approach are exclusively used in the network having multiple fibers in each link, whereas other approaches are used in both multifiberlink and singlefiberlink networks. Under high loads, MS, LL, and RCL perform well in terms of BP, whereas LU, MP, and MU show less BP at low traffic loads. Although the average setup time of the random approach is the lowest compared to that of other approaches, the BP is higher than that of others under both high and low traffic loads. Both BP and average setup time of PRWA are lower than those for FF approach under high traffic load condition, but under low load condition, FF approach performs better than PRWA. The time complexity of PRWA is higher than that of others, because of more number of loops in PRWA having K number of alternate paths for each sd pair.
Approach 
Performance Analysis 
No. of Fibers 
Average Setup Time 


Blocking Probability 
Time Complexity 

MS 
In multifiber networks, it performs better than the others for high traffic loads 
~ O(L _{1} W N ^{2} Z) 
Single/multiple 
Medium value 
RCL 
In single fiber networks, it performs well in comparison to others for high traffic loads 
~ O(L _{1} W N ^{2} Z) 
Single/multiple 
Medium value 
MP 
In multifiber networks, it performs well in comparison to others for low traffic loads 
~ O(L _{1 M} W N Z) 
Multiple 
Medium value 
LL 
In multifiber networks, it performs well in comparison to others for high traffic loads 
~ O(L _{1} M, W N Z) 
Multiple 
Slightly more than that of MP 
LU 
In both cases, it performs well for low traffic loads 
~ O(L _{1} L _{2 } N Z) 
Single/multiple 
Almost the same as that of LL 
MU 
In both cases, it performs well for low traffic loads 
~ O(L _{1} L _{2 } N Z) 
Single/multiple 
Almost the same as that of LL 
Random 
More BP than FF but almost same as that of others for low loads 
~ O(L _{1} W Z) 
Single/multiple 
Lowest among all 
FF 
Less BP than LU, MU, and random 
~ O(L _{1} W Z) 
Single/multiple 
More than that of random 
PRWA 
Less BP than LU, MU, FF, and random 
~ O(L _{1} L _{2} K W Z) 
Single/multiple 
Less than that of FF under high load 
MP – Min. Product, LL – Least Loaded, LU – Least Used, MU – Most Used, FF – first fit, PRWA – prioritybased RWA.
Computational Complexity of Heuristics
The computational complexities of various RWA approaches are compared [1–5]. Random and FF have less computational complexity than others, and their running times are ~ O(L _{1} W Z). LU and MU are more complex than Random and FF, and time complexities of LU and MU are ~ O(L _{1} L _{2} NZ). MP and LL are both used in multifiber networks. MP estimates Π_{ l∈π(p)} D_{lj} for all W wavelengths and selects the wavelength by minimizing the product. The number of links on a path is limited by O(N). Hence, the time complexity of computation in MP is ~ O(L _{1 M} W N Z), whereas that in LL is ~ O(L _{1 M} W N Z).
MaxSum and RCL are costly. The worstcase running time of these approaches is of the order of O(N ^{2}). To find the capacity of each path, all the links along that path are examined for the minimum number of available wavelengths. The number of links on a path is limited by O(K). Hence, in the worst case, time complexity is obtained as O(L _{1} W N ^{2} Z).
The time to perform PRWA for Z number of connection requests using K alternate paths is O(L _{1} L _{2} W K Z) which is more than that of the FF and random approaches. The combined RWA problem is formulated as an ILP, which is NPcomplete.
This chapter discusses longhaul widecoverage optical networks based on arbitrary (mesh) topology in which nodes employ wavelengthrouting switches (or optical crossconnects (OXCs)), which establish WDM channels, called light paths, between node pairs. We have discussed different static and dynamic RWA approaches. We have also mentioned LP formulation along with different constraints used in the implementation of these approaches. For the analysis of these approaches, first we have discussed routing algorithms/schemes, and then we have mentioned different WAs along with wavelength searching and WRSV used in these approaches. We have also discussed different priority schemes used for WA for performance improvement.
We have made a comparative study of performances of different RWA algorithms in optical network along with time complexity.
Given a graph G = (V,E), define
where v _{1}, v _{2}, ..., v _{n}ϵ V and <v _{1}, v _{2}, ...,v _{n}> is a vertex ordering. Define an SL vertex ordering <v _{1}, v _{2}, ..., v _{n}> such that deg (v _{i+} _{1}) ≤ deg (v _{i}), for 1 ≤ i ≤ n. Show that over all the n! possible vertex orderings, the SL vertex ordering minimizes the value of k.
Consider the network shown in Figure Exercise 3.1. Let the connection requests be as follows:
Figure Exercise 3.1 Sample network. □ Access station ○ node.
We know that the SLE problem is NPcomplete. Show a simple transformation that transforms an SLE problem into a graphcoloring problem.
Consider the network in Figure Exercise 3.1 and the following light paths:
Color the light paths using the minimum number of wavelengths.
Consider the NSFNET physical topology shown in Figure 3.12. Remove the nodes CA_{2} and TX. Consider the connection requests shown in Figure Exercise 3.2. What is the minimum number of wavelengths needed to satisfy all the connection requests?
Figure Exercise 3.2 Sample network having 11 nodes.
Compare the characteristics of various routing schemes.
Consider the Indian network physical topology shown in Ex Figure 3.3. What is the minimum number of wavelengths needed to satisfy all the connection requests? Assume that number of connection requests for each sd pair is the same and ~5000.
Figure Exercise 3.3 Indian network connecting major cities of India.
Consider the Indian network physical topology shown in Ex Figure 3.3. If node2 and node3 are removed or they fail, what is the minimum number of wavelengths needed to satisfy all the connection requests? Assume that the number of connection requests for each sd pair is the same and ~5000.
Compare the characteristics of different WAs heuristics.
Find the routing table for node1, node2, and node4 for the following network by using Dijkstra’s algorithm. The cost of each link is also shown in Ex Figure 3.4
Figure Exercise 3.4 Sample network having 6 nodes and 9 bidirectional links.
Find the routing table for node1, node2, and node3 for the network in Ex Figure 3.4 by using Dijkstra’s algorithm if node4 fails to work.
Find the routing table for node1, node2, and node4 for the following network by using Bellman–Ford’s algorithm. The cost of each link is also shown in Ex Figure 3.5.
Find the routing table for node1, node2, and node4 for the following network by using genetic algorithm. The cost of each link is also shown in Ex Figure 3.5.
Find the routing table for node1 and node2 for the network in Ex Figure 3.5 by using simulatedannealing algorithm.
Figure Exercise 3.5 Sample network 6 nodes and 8 bidirectional links.
Update the routing table for node1 and node2 for the network in Ex Figure 3.5 by using Bellman–Ford’s algorithm if node4 fails.