Metrics

Views
66

Routing and Wavelength Assignment

Authored by: Partha Pratim Sahu

Advances in Optical Networks and Components

Print publication date:  July  2020
Online publication date:  July  2020

Print ISBN: 9780367265656
eBook ISBN: 9780429293962
Adobe ISBN:

10.1201/9780429293962-3

 

Abstract

This chapter discusses long-haul wide coverage optical networks based on arbitrary (mesh) topology in which nodes use wavelength-routing switches/optical cross-connects (OXCs) for setting up wavelength-division 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 sub-problem 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 multi-commodity 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 graph-coloring techniques. Wavelength-routed optical networks are the backbone of networks for large regions nationwide or globally. Access stations/users are attached to the network via wavelength-sensitive nodes for switching/routing.

 Add to shortlist  Cite

Routing and Wavelength Assignment

This chapter discusses long-haul wide coverage optical networks based on arbitrary (mesh) topology in which nodes use wavelength-routing switches/optical cross-connects (OXCs) for setting up wavelength-division 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 sub-problem 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 multi-commodity 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 graph-coloring techniques. Wavelength-routed optical networks are the backbone of networks for large regions nationwide or globally. Access stations/users are attached to the network via wavelength-sensitive nodes for switching/routing.

3.1  Light paths

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 “circuit-switched” interconnection between two nodes. Each intermediate node in the light path essentially provides a circuit-switched optical bypass facility to support the light path. In an N-node 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 circuit-oriented; 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:

  • A set of light paths need to be set up for connection requests in the network.
  • For a constraint on the number of wavelengths, estimate the routes over which these light paths should be set up and also estimate the wavelengths assigned to these light paths so that the maximum number of light paths are set up.

While the shortest-path 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 wavelength-continuity 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 wavelength-continuity 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 multi-commodity 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 NP-complete where a number of heuristics are required to obtain the solutions of the RWA problem [3,4].

In this chapter, we mention well-known 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 sub-problems – each sub-problem 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 general-purpose 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.

3.2  LP Formulation of RWA and Its Reduction

Combinatorial formulations are made using mixed-integer linear programs (MILPs) for solving the RWA problem [6–9]. These formulations are used in resolving large problems by using sophisticated techniques such as branch-and-bound methods.

The RWA problem, without the wavelength-continuity constraint, is a straightforward multi-commodity 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.

  • λsd = 1, if there is a light path from s to d, where λsd = traffic (in terms of a light path) from any source s to any destination d.
  • = 0, otherwise
  • F i j s d = traffic (in terms of the number of light paths) that is flowing from source s to destination d on link ij. The LP formulation is written as follows [1]:
    3.1 Minimize F max such that F max Σ s , d F i j s d i j
    3.2 Σ i F i j s d Σ k F j k s d = λ s d if  s = j = λ s d if  d = j = 0 otherwise

where

λ s d = 0 , 1 F i j s d = 0 , 1

It is NP-complete and can be approximately written by using randomized rounding [1].

3.2.1  Reduction of Size of LP Formulation

A multi-commodity 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 (ij-pairs), and an average of 4 connections per node; i.e., 40 connections (SD pairs) need to be set up in the network.

Network having 10 nodes and 15 physical links in which links are
                           bidirectional.

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 i j s d 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 i j s d 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 i j s d variables for that particular SD pair. For a light path SD that passes through four links on average, there will be approximately 160 F i j s d 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.

3.2.2  Randomized Rounding

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 near-optimality 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 multi-commodity 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 multi-commodity 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 NP-complete [2] although the non-integral version can be solved using linear programming methods in polynomial time. The algorithm has the following three major steps:

  • resolving a non-integral multi-commodity flow problem
  • path stripping
  • randomized path choice.

Non-Integral Multi-Commodity Flow

The requirement of the 0–1 flows is relaxed to allow fractional flows in the interval [0,1]. The relaxed capacity-minimization problem is resolved by a suitable linear programming method. If the flow for each commodity i on edge e ϵ E is indicated by fi (e), a capacity constraint of the form [10]

3.3 Σ i = 1 k f i ( e ) C

is then satisfied for each edge in the network, where C is the optimal solution to the non-integral, edge-capacity optimization problem. The value of C is also a lower bound on the best possible integral solution.

Path Stripping

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:

  • Find a loop-free, depth-first, directed path e 1, e 2, …, ep from the source to the destination.
  • Let f m = min fi (ej ), where 1 ≤ jp. For 1 ≤ jp, substitute fi (ej ), by fi (ej ), − fm . Include path e l, e 2, …, ep to τ i along with its weight f m.
  • Remove any edge with zero flow from the set of edges that carry any flow for commodity i. If there is non-zero flow leaving si , repeat step b. Otherwise, continue to the next commodity i.

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.

Randomization

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]

C + 3 C   ln | E | ε

where 0 < E < 1 with a probability of 1 – ε at least.

In this problem, the F i j s d 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 coin-tossing 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.

3.2.3  Graph Coloring

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 wavelength-continuity 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 wavelength-continuity constraint, which is achieved by the following steps [10]:

  1. drawing the graph of G(V, E), which is a function of number of nodes V and number of edges connected between different nodes. There is an undirected edge between two nodes in graph G if the corresponding light paths pass through a common physical fiber link.
  2. coloring the nodes of the graph G in a light path such that no two adjacent nodes have the same color.

This problem is NP-complete, 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. Ai 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 Ai before any member of Aj for 1 ≤ ijx(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.

Theorem:

If G is a graph with V(G) = v 1, v 2, ..., vn , where deg(vi ) ≥ 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 largest-first algorithm [1].

The sequential coloring approach demonstrates that for a given ordering v 1, v 2, ..., vn of the vertices of a graph G, the corresponding sequential coloring algorithm does not need more than k colors where k = max1≤in {1 + deg<v 1,v 2vn >(vi )} and deg<v 1,v 2vn >(vi ) indicates the degree of node vi in the vertex-induced 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]:

  1. For n = │V(G)│, vn should be chosen such that it has minimum degree in G.
  2. For i = n − 1, n − 2, …, 2,1, vi should be chosen such that it has have minimum degree in <V(G)- vn , v n−1, …, v i+1>.

For any vertex ordering v 1, v 2, …, v n determined, we have

deg < v 1 , v 2 v n > ( v i ) = min 1 j i   deg < v 1 , v 2 v n > ( v j )

for 1 ≤ in, so that such an ordering is considered as a smallest-last (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).

Auxiliary graph,

Figure 3.2   Auxiliary graph, G(V,E), for the light paths in the network [1].

3.2.4  Analysis of ILP

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.

  • In case of static traffic [6], all traffic/connection requests are identified in advance, and the light paths are set up to satisfy the maximum number of traffic requests.
  • In case of incremental traffic [1], traffic/connection requests arrive in the system sequentially. The light path is set up for each traffic/connection request in indefinite time.
  • In case of dynamic traffic [13], traffic/connection requests arrive in the system randomly based on a statistical distribution [11], on the basis of mainly Poisson process, and a light path is set up for each traffic/connection request released after some finite amount of time.

The offered traffic follows the followings:

  1. A set of light paths are required to be established between randomly chosen SD pairs, and all SD pairs are considered equally.
  2. For each (source) node, d′ is an average number of light path connections provided by a source node. In an N-node network, the probability that a node has a light path with each of the remaining (N − 1) nodes equals d′/(N − 1), and d′ is taken as the average “logical degree” of a node.

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.

Static Light path Establishment (SLE)

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 i j s d variables, and a standard K-alternate-path 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 i j s d 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 i j s d , the path-stripping 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 wavelength-continuity 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.

Dynamic Light path Establishment (DLE)

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 least-congested-path (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 wavelength-continuity 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.

3.3  Routing

In an RWA, there are two sub-problems – 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.

3.3.1  Routing Algorithms

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:

  • number of hops
  • cost
  • time delay
  • propagation time delay.

For analysis of the above-mentioned 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.

3.3.1.1  Dijkstra’s 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 least-cost 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 least-cost 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:

  • N = set of nodes in the network
  • s = source node
  • M = set of nodes incorporated in the inclusion matrix
  • dij = link cost from node i to node j where dij = 0 and ∞ denotes that two nodes are not directly connected and dij ≥ 0 denotes that two nodes are connected physically
  • D n = total cost of least-cost path from source node s to node n that is currently known to be in the network.

The algorithm has three steps: step-2 and step-3 are repeated until M = N; i.e., step-2 and step-3 are repeated till final paths have been assigned to all the nodes except node s in the network. The algorithm procedure is given below.

Algorithm 1 Dijkstra’s Algorithm

  • Step-1: Initialize M = {s}, (i.e., the set of nodes so far incorporated in inclusion matrix M consists of the source node) Dn = dsn for ns (i.e., the initial path costs to neighboring nodes are simply link costs)
  • Step-2: Find the neighboring node not in M that has the least-cost path from source node s and incorporate that node into M. This can be expressed as Find wM such that D w = min j M D j
  • Step-3: Update least-cost paths: Dn = min [Dn , Dw + dwn ] for all nM If the term is the minimum, the path from s to n is now the path from s to w, concatenated with the link from w to n.
  • Step-4: Repeat step-2 and step-3 till M = N.

One iteration of step-2 and step-3 adds one new node to M and defines least-cost 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 least-cost 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 least-cost path for that node. Table 3.1 shows the routing table of least-cost 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 least-cost 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].

Sample network with link cost.

Figure 3.3   Sample network with link cost.

Routing by Dijkstra’s algorithm: (a) iteration 1, (b) iteration
                                 2, and (c) iteration 3.

Figure 3.4   Routing by Dijkstra’s algorithm: (a) iteration 1, (b) iteration 2, and (c) iteration 3.

Table 3.1   Least-Cost Routing Paths from Source Node s = 1 to All Destinations Using Dijkstra’s Algorithm in the Network Mentioned in Figure 3.3

Iteration

M

D2 Path2

D3 Path3

D4 Path4

D5 Path5

D6 Path6

1

[1]

1 1-2

4 1-3

3 1-4

2

[1, 2]

1 1-2

2 1-2-3

3 1-4

4 1-4-5

6 1-2-6

3

[1, 2, 3]

1 1-2

2 1-2-3

3 1-4

4 1-4-5

5 1-4-5-6

4

[1, 2, 3, 4]

1 1-2

2 1-2-3

3 1-4

4 1-4-5

5 1-4-5-6

5

[1, 2, 3, 4, 5]

1 1-2

2 1-2-3

3 1-4

4 1-4-5

5 1-4-5-6

6

[1, 2, 3, 4, 5, 6]

1 1-2

2 1-2-3

3 1-4

4 1-4-5

5 1-4-5-6

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.

3.3.1.2  Bellman–Ford Algorithm

Another of the most commonly used routing algorithms is Bellman–Ford algorithm [17–19]. Using this algorithm, one can find the least-cost path from a given source subject to the constraint that the path contains at most one link; find the least-cost 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.

  • N = set of nodes in the network
  • s = source node
  • M = set of nodes incorporated in inclusion matrix
  • dij = link cost from node i to node j where dij = 0 or ∞ denotes that two nodes are not directly connected and dij ≥ 0 denotes that two nodes are connected physically
  • h = maximum number of links in a path at current stage of algorithm = hop size
  • D n ( h ) = total cost of least-cost path from source node s to node n that is currently known to be in the network.

The algorithm has two steps: step-2 is repeated until none of the costs change. The algorithm’s procedure is given below.

Algorithm 2 Bellman–Ford Algorithm

  • Step-1: Initialize
    D n ( 0 ) = , for all  n s D n ( h ) = 0 , for all  h
  • Step-2: For each successive h ≥ 0
    D n ( h + 1 ) = min j [ D j ( h ) + d j n ]
    The path from s to i node terminates with the link from j to i.
  • Step-3: Repeat step-2 till paths for all destinations are the same as those of the previous iteration.

For repeating step-2 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 least-cost 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 least-cost 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.

Table 3.2   Least-Cost Routing Paths from Source Node s = 1 to All Destinations Using Bellman–Ford’s Algorithm in the Network Mentioned in Figure 3.3

h

D2 Path2

D3 Path3

D4 Path4

D5 Path5

D6 Path6

0

∞ –

∞ –

∞ –

∞ –

∞ –

1

1 1-2

4 1-3

3 1-4

∞ –

∞ –

2

1 1-2

2 1-2-3

3 1-4

4 1-4-5

5 1-2-6

3

1 1-2

2 1-2-3

3 1-4

4 1-4-5

5 1-4-5-6

4

1 1-2

2 1-2-3

3 1-4

4 1-4-5

5 1-4-5-6

Routing by Bellman–Ford’s algorithm: (a) iteration 1, (b)
                                 iteration 2, and (c) iteration 3.

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).

3.3.2  Routing Approaches

In case of routing, many approaches are used for both static and dynamic routing such as fixed routing, fixed-alternate-path routing, and adaptive routing [1].

3.3.2.1  Fixed Routing

The most simple approach of routing a connection request is fixed routing for a given sd pair. The fixed shortest-path routing for each sd pair is made offline using standard shortest-path 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.

Node-1

Destination Node

Path

2

1-2

3

1-2-3

4

1-4

5

1-4-5

6

1-4-5-6

The routing table values for nodes 2, 3, 4, 5, and 6 estimated by using Dijkstra’s offline algorithm are given below.

Node-2

Node-3

Node-4

Node-5

Node-6

Destination Node

Path

Destination Node

Path

Destination Node

Path

Destination Node

Path

Destination Node

Path

1

2-1

1

3-1

1

4-1

1

5-4-1

1

6-5-4-1

3

2-3

2

3-2

2

4-1-2

2

5-4-1-2

2

6-2

4

2-1-4

4

3-2-1-4

3

4-1-2-3

3

5-3

3

6-3

5

2-1-4-5

5

3-5

5

4-5

4

5-4

4

6-5-4

6

2-6

6

3-6

6

4-1-6

6

5-6

5

6-5

The connections of different sd pairs are set up with the pre-determined 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.

3.3.2.2  Fixed-Alternate Routing

Fixed-alternate routing is a method to routing that derives multiple paths. In fixed-alternate 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 shortest-path route, the second-shortest-path route, the third-shortest-path 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 link-disjoint) 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].

Routing path-1

  • Step-1: Initialize M = {s}, (i.e., the set of nodes so far incorporated in inclusion matrix M consists of source node) Dn = dsn for ns (i.e., the initial path costs to neighboring nodes are simply link costs)
  • Step-2: Find the neighboring node not in M that has the least-cost path from source nodes s and incorporate that node into M. This can be expressed as Find wM such that D w = min j M   D j
  • Step-3: Update least-cost paths: Dn = min [Dn , Dw + dwn ] for all nM If the term is the minimum, the path from s to n is now the path from s to w, concatenated with the link from w to n.
  • Step-4: Repeat step-2 and step-3 till M = N.

Routing path-2

  • Step-5: All routing paths-1 for all destination nodes are made infinity (very large value). M = {s}, (i.e., the set of nodes so far incorporated in inclusion matrix M consists of the source node) Dn = dsn for ns (i.e., the initial path costs to neighboring nodes are simply link costs)
  • Step-6: Repeat step-2 and step-3 till M = N.

Routing path-3

  • Step-6: Routing path-1 and routing path-2 for all destination nodes are made infinity (very large value). M = {s}, (i.e., the set of nodes so far incorporated in inclusion matrix M consists of the source node) Dn = dsn or ns (i.e., the initial path costs to neighboring nodes are simply link costs)
  • Step-7: Repeat step-2 and step-3 till M = N.         …        ….        ….        ….        …..         …        ….        ….        ….        …..

Routing path-k

  • Step-k+3 Routing paths-1, 2 … k − 1 for all destination nodes are made infinity (very large value). M = {s} (i.e., the set of nodes so far incorporated in inclusion matrix M consists of the source node) Dn = dsn for ns (i.e., the initial path costs to neighboring nodes are simply link costs)
  • Step-k+4: Repeat step-2 and step-3 till M = N. The routing table values of alternate fixed path routing (FR) for the source node are also determined by using the modified form of Bellmen–Ford’s algorithm. Consider two alternate routing paths (k = 2). The routing table values of fixed alternate path routing for source node s = 1 of the network in Figure 3.3 are estimated by using Dijkstra’s algorithm and given below.

    Node-1
    Destination Node Path-1 Cost Path-2 Cost
    2 1-2 1 1-3-2 5
    3 1-2-3 2 1-3 4
    4 1-4 3 1-3-5-4 10
    5 1-4-5 4 1-3-5 9
    6 1-4-5-6 5 1-3-6 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/least-cost 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 fixed-alternate routing is that it can significantly reduce the connection BP compared to fixed routing [21].

3.3.2.3  Flooding

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 node-1 to destination node-5.

Flooding in the network from node-1 to node-5.

Figure 3.6   Flooding in the network from node-1 to node-5.

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.

3.3.2.4  Adaptive Routing

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:

  • Node failure: When a node fails, it can no longer be used as part of a route.
  • Link failure: When a link fails, it can no longer be used as part of a route.
  • Congestion: When a particular portion of the network is heavily congested, it is desirable to route the traffic in another direction rather than through the congested area of the network.

For adaptive routing, information about the state of the network is exchanged between the nodes. There is a trade-off between the quality of information regarding network state and the amount of overload.

One approach is an adaptive shortest-cost-path routing which is suitable to wavelength-converted 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 wavelength-converter link has a cost of c units. If wavelength conversion is not available, then c is infinity. When a connection is established, the shortest-cost 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 wavelength-conversion cost c appropriately, paths with wavelength conversion are selected only when paths with wavelength continuity are not found. In shortest-cost 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 pre-estimated. Upon the arrival of a connection request, the LCP among the pre-estimated 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:

3.4 D i = ( d i 1 d i N )   S i = ( s i 1 s i N )

where

  • Di = delay vector for node i
  • dij = current estimate of minimum time delay from node i to node j (dij = 0)
  • N = number of nodes in the network
  • Si = successor node vector for node i
  • s ij = next node in the current minimum time delay route from node i to node j. Periodically (almost every 128 ms), each node exchanges its delay vector with all of its neighbors. On the basis of all incoming delay vectors, a node k updates both of its vectors as follows:
    3.5 d k j = min i A [ d i j + l k i ]
  • skj = i, using i that minimizes the expression above
  • A = set of neighbor nodes for k and lki = current estimate of delay from k to i.

This approach of distributed adaptive routing has the following shortcomings [17]:

  1. It does not consider line speed but simply queue length.
  2. Queue length is in any case an artificial measure of delay, as some variable amount of processing time elapses between the arrival of a packet at a node and its placement in outbound queue.
  3. The algorithm is not very accurate as congestion clears slowly with increase in delay.

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.

3.3.2.5  Fault-Tolerant Routing

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 fault-tolerant routing are protection and restoration. The most commonly used approach is protection needed to establish two link-disjoint 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 node-disjoint. Fixed-alternate routing is employed for protection. By selecting the alternate paths on the basis of the fact that their routes are link-disjoint from the primary path, the connection is protected from any single-link 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 link-disjoint 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 pre-established 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.

3.3.2.6  Randomized Routing

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:

  • In the first step, the route starts from a source node choosing one of the outgoing links randomly from every node on the route and reaches a random node in the source stage.
  • In the second step, the route goes on in the same manner till it arrives at a random node in the destination stage.
  • In third step, the route reaches the destination node by using the unique path with length k.

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, Si , 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(log2 N) wavelengths, the permutation routing problem can be solved using a high probabilistic (success) guarantee of 1-1/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(log2 N) wavelengths, the permutation routing problem can be solved using a high probabilistic (success) guarantee of 1-1/poly(N) for the model.

3.4  WA Subproblem (Heuristics)

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 wavelength-continuity constraint using the graph-coloring 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) first-fit (FF), (3) least-used/spread, (4) most-used/pack, (5) min-product, (6) least-loaded, (7) max-sum, (8) relative capacity loss (RCL), (9) distributed relative capacity loss (DRCL), (10) wavelength reservation (WRSV), (11) protecting threshold, (12) priority-based 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:

  • L: number of links.
  • Mt : number of fibers on link i.
  • M: number of fibers per link if all links contain the same number of fibers.
  • W: number of wavelengths per fiber.
  • π(p): set of links comprising path p.
  • Sp : set of available wavelengths along the selected path p.
  • D: L-by-W matrix, where Dij indicates the number of assigned fibers on link i and wavelength j. Note that the value of Dij varies between 0 and Mt .
  • Load: For dynamic traffic, the holding time is exponentially distributed with a normalized mean of one unit, and connection arrivals are Poisson; thus, load is expressed in units of Erlangs.

3.4.1  Wavelength Search Algorithm

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 graph-coloring problems were discussed in Section 3.2.3. In this section, different searching algorithms are discussed.

3.4.1.1  Exhaustive Search

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.

Coloring of nodes using exhaustive search.

Figure 3.7   Coloring of nodes using exhaustive search.

3.4.1.2  Tabu 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 k-coloring 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 2Vk ) be a partition of graph G, where subset Vi of nodes represents those nodes having color i. Define a cost function as f ( s ) = Σ i   E ( V i ) , where E(Vi ) is the number of edges in subgraph Vi . 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 k-coloring 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].

  1. Set some initial configuration s = (V 1, V 2Vk ).
  2. Set nbit = 0.
  3. Initialize tabu list T.
  4. As long as f(s) > 0 and nbit < nmax
    • Find nrep neighbors (where nrep is number of neighbors) si for which ssi T or f(si ) ≤ Af(s).
    • Choose the best among them (or the first for which f(si ) < f(s)).
    • Update tabu list T.
    • Set s = s 0 and nbit = nbit + 1.
  5. If f(s) = 0, we find a legal k-coloring for a given graph; otherwise increase k and repeat again.

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 k-coloring, the iteration is not required.

3.4.1.3  Simulated Annealing

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:

  1. In the beginning, assign each node a unique color.
  2. Set the temperature T = T 0 (e.g., T 0 = 1).
  3. Choose a random node and a random new color for it. Make sure that the new color does not lead to an illegal configuration.
  4. Compute the change of energy ΔE.
  5. If ΔE < 0 or eΔE/KT > random(0, 1), accept the change.
  6. If there have been at least M changes or N trials, then set T = α. (α is a small constant, e.g., 0.95.)
  7. If T > Ti , go back to 3.

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.

3.4.1.4  Genetic Algorithms

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:

  1. Initialization: Set indices iA = iB = 1, and set the child C to null.
  2. Choose vector A with probability of 0.75 and vector B with probability of 0.25 as parents.
  3. Add the next element, pointed to by iA or iB , of the chosen vector to the child vector C if it is not already there.
  4. Increment the value of index by 1 so that it points to the next element of the parent vector.
  5. Repeat this until the child C contains all the values 1, 2, …, N.

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 iA points to the next element of parent A and iB to that of parent B. As a mutation operator, we simply exchange the places of two random nodes in the vector.

3.4.2  WA Heuristics

There are many approaches used for WA/selection: randomized approach, first fit, least used, most used, min-product approach, least loaded, max-sum, relative capacity loss, distributed relative capacity loss, priority-based approach, dispersion reduction assignment, etc.

3.4.2.1  Random WA (R)

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.

3.4.2.2  First-Fit (FF) Approach

In this approach, we index all wavelengths. For searching the available wavelengths, a lower-indexed wavelength is chosen before a higher-numbered 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 in-use 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].

3.4.3.3  Least-Used (LU) Approach

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].

3.4.3.4  Most-Used (MU) Approach

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 less-used wavelengths.

3.4.3.5  Min-Product (MP) Approach

This approach is employed in multi-fiber networks [33]. MP approach to a single-fiber 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:

Π l π ( p )   D l j

for each wavelength j, i.e., 1 ≤ jW. If X represents the set of wavelengths that minimize the above value, then MP approach considers the lowest-numbered wavelength in X. This approach has additional computation costs/complexity.

3.4.3.6  Least-Loaded (LL) Approach

Like MP, the LL heuristic is also employed in multi-fiber networks [34]. This heuristic selects the wavelength having the largest residual capacity on the most-loaded link along route p. While using in single-fiber networks, the residual capacity is either 1 or 0, and it chooses the lowest-indexed wavelength with residual capacity 1. Thus, it is also used as an FF approach in single-fiber networks. The LL approach chooses the lowest-indexed wavelength j in Sp .

3.6 max j S p   min l π ( p ) ( M l D l j )

The LL approach’s BP performance is slightly better than those of MU and FF approaches in a multi-fiber network.

3.4.3.7  MAX-SUM (MS) Approach

This approach [35] was employed in multi-fiber networks, but it is also used in single-fiber networks. It uses all possible paths (light paths with their pre-selected 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 pre-selected. 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.,

3.7 r ( φ , l , j ) = M l D ( φ ) l j

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 most-congested link along the path p, i.e.,

3.8 R ( φ , p ) = Σ j = 1 max min l π ( p ) c ( φ , l , j )

We consider

  • Ω(φ, p) = no of possible wavelengths that are available for the light path that is routed on path p.
  • φ′(j) represents the next state of the network if wavelength j is allotted to the connection. The MS approach chooses the wavelength j to maximize the quantity expressed as
    Σ p P R ( φ ( j ) , p )

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.

3.4.3.8  Relative Capacity Loss (RCL) Approach

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

Σ p P { R ( φ ( j ) ) R ( φ ( j ) , p ) }

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

Σ p P { r ( φ ( j ) ) r ( φ ( j ) , p ) }

In RCL, wavelength j is chosen to minimize the relative capacity loss written as

Σ p P { R ( φ ( j ) ) r ( φ ( j ) , p ) } / r ( φ , p , j )

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 non-uniform traffic by taking a weighted sum over the capacity losses.

3.4.3.9  Distributed Relative Capacity Loss (DRCL) Approach

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 link-state 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:

  • how information of network state is exchanged.
  • how the amount of calculation is reduced upon receiving a connection request.

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.

  • – If there is no path from node s to node d on wavelength w, then rcl (w, d) = 0; otherwise
  • if there is a direct link from node s to node d, and the path from s to d on wavelength w is routed through this, then rcl(w, d) = 1/k, where k is the number of available wavelengths on this link through which s can reach d; otherwise
  • If the path from source node s to node d on wavelength w starts with node n (n is s node’s next node for destination d on wavelength w), and there are k wavelengths available on link of s node to next node n through which s can arrive, then rcl(w, d) at node s is set to be (l/k) and similarly, rcl(w, d) is estimated at next node n.

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.

3.5  Fairness Improvement

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:

  • Wavelength channel utilization must be high.
  • The algorithm must be flexible enough to choose the desired trade-off between fairness level and global performance loss.
  • It must be suitable for networks with different degrees of connectivity.
  • The fairness improvement algorithm makes shorter hop connection more penalized than longer hop connections.

For achieving fairness in wavelength routing, the following issues must be addressed [1]:

  • WRSV
  • WThr
  • limited alternate routing (LArout)
  • static priority
  • dynamic priority.

3.5.1  Wavelength Reservation

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.

3.5.1.1  Forward Reservation

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].

  • Res: This control message is used for reserving wavelengths on the links of a route. It consists of various fields – connection_id, S free, and route. The route contains the route information specifying links. It travels from the source to destination along the route.
  • Res_Succ: This control message indicates that the reservation of some wavelength has been successful. It consists of various fields – connection_id, S free, and w res, where w res = free wavelength that can be used by the connection request. It travels from the source to destination along the route.
  • Res_Fail: This control message indicates that the reservation of a wavelength has failed. It consists of various fields – connection_id, S free, and route. This message travels from intermediate nodes to the source node along the route.
  • Rel: This control message is sent to release the light path on some wavelength. It consists of the connection_id of the light path released. This message travels from the source node to the destination node along the route.

The different parameters used in designing the forward reservation method are mentioned below [1]:

  • Max_WL: Max_WL is the maximum number of wavelengths in set S free at the time of starting a new search for a free wavelength on some route. In other words, it is the initial size of the set S free. In this case, the protocol always tries to reserve as many wavelengths as possible on the links of a route. This will reduce setup time and increase the chance of getting a free wavelength. But the reservation conflict increases because a connection request attempts to reserve some wavelengths which are already reserved by other connection requests.
  • Max_TRIES: Max_TRIES is the maximum number of times a free wavelength is searched before the source node gives up. The more the tries, the higher the chance of finding a free wavelength.
  • GAP: GAP is the retransmission time gap between two successive tries by the source. A small gap time increases control traffic and reservation conflicts. On the other hand, a large gap time makes the state of the network during subsequent tries more uncertain. Moreover, a large gap time increases connection setup time.
  • BUF_TIME: BUF_TIME is the buffer time of the control message, i.e., the time till which it is held at the intermediate node. Zero BUF_TIME is simple to implement as there is no need for buffers to queue the pending messages. A non-zero BUF_TIME will increase the chance of finding a free wavelength on the outgoing link.

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].

  • Step-1: When a connection request arrives at node s to some other node d, the source node s prepares a Res message with the required information. A new sequence number, seq_no, is obtained. The S free with MAX_WL wavelengths is constructed. The control message is transmitted through the first route on the control channel.
  • Step-2: When the message is at intermediate node i, it selects the outgoing route from the route information. The set S free is updated by considering set of common available wavelengths with the outgoing link. If S free has available wavelengths, the node forwards the message to the next neighbor node with updated S free along the outgoing link chosen from the route information; otherwise go to the next step.
  • Step-3: If S free has no available wavelength, the Res message is temporarily queued in the local buffer for BUF_TIME till some required common wavelength is free in the same outgoing link before the expiry of BUF_TIME. After expiry of BUF_TIME, the Res message is removed, and Res_Fail message is generated and sent back to the node (from where Res message comes) along the incoming link and ultimately reaches the source. If Res message is released to the next node of the route, go to the next step.
  • Step-4: Repeat step-2 and step-3. Res message reaches the destination node d along the links via intermediate nodes of the route selected as primary path. Once the Res reaches the destination d, Res_Succ message is released toward the source with the selection of wavelength W res from available wavelengths in set S free.

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.

Forward reservation: (a) free wavelength and successful
                              reservation and (b) unsuccessful reservation.

Figure 3.8   Forward reservation: (a) free wavelength and successful reservation and (b) unsuccessful reservation.

3.5.1.2  Backward 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].

  • Collect: This message is used to collect the set of free wavelengths on the links of a route. It consists of three fields – connection_id, route, and S free. Since the message does not reserve any wavelength, S free contains initially all the wavelengths. It travels along the route from the source to the destination node.
  • Collect_Fail: This message represents the collection of free wavelengths on a route. It consists of two fields – connection_id and route. It traverses back from intermediate nodes to source node along the route.
  • Res: This control message is used for reserving wavelengths on the links of a route. It consists of three fields – connection_id, S free, and route. The route contains the route information specifying links. It travels from the source to destination.
  • Res_Succ: This control message indicates that the reservation of some wavelength has been successful. It consists of three fields: connection_id, route, and w res where w res = free wavelength can be used by the connection request. It travels from the source to destination along the route.
  • Res_Fail: This control message indicates that the reservation of a wavelength has failed. It consists of two fields – connection_id and route. This message travels from the intermediate node to the source node along the route.
  • Rel: This control message is sent to release the light path on some wavelength. It carries the connection_id of light path to be released. This message travels from the source node to the destination node along the route.

Protocol Description

When a connection request arrives at the source node, the following steps are to be taken in backward reservation [1].

  • Step-1: When a request arrives at node s for connection to some other node d, the source node s prepares a Collect message with the required information. A new sequence number seq_no is obtained. S free contains all the wavelengths. The control message is transmitted through the first candidate route on the control channel.
  • Step-2: When the message is at intermediate node i, it selects the outgoing route from the route information. The set S free is updated by considering a set of common available wavelengths with the outgoing link. If S free has available wavelengths, the node forwards the message to the next neighbor node with updated S free along the outgoing link chosen from the route information; otherwise it goes to the next step.
  • Step-3: If S free has no available wavelength at node i, the Res message is temporarily queued in the local buffer for BUF_TIME till some required common wavelength is free in the same outgoing link before the expiry of BUF_TIME. After expiry of BUF_TIME, the Res message is removed, Res_Fail message is generated and sent to the destination node along the outgoing link, and Fail_Info is sent to the source node. The Collect_Fail message is also generated so that it can try other routes and go back to the source node along the incoming links which are determined from the route information. When the source node receives Collect_Fail message, it goes to the next step.
  • Step-4: It searches the next candidate node, when the source node receives Collect_Fail message.
  • Step-5: Step-2, step-3, and step-4 are repeated with a GAP till the number of retransmissions has reached MAX_TRIES. When the Collect message reaches the destination node d, it generates Res message having a new set of S free consisting of the subset of free wavelengths indicated by the Collect message. The message is transmitted from destination d to source node s.

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 non-availability 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.

Backward reservation: (a) successful reservation of wavelength,
                              (b) failure due to the non-availability of free wavelength, and (c)
                              failure of WRSV.

Figure 3.9   Backward reservation: (a) successful reservation of wavelength, (b) failure due to the non-availability of free wavelength, and (c) failure of WRSV.

3.5.1.3  Congestion-Based Routing WRSV Method

Congestion-based routing WRSV is an extension of backward reservation technique [1,38] for a given sd pair; the least-congested 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].

3.5.1.4  k-Neighborhood Routing

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 k-neighborhood 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 least-congested 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 k-neighborhood 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 non-decreasing 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].

3.5.2  WThr Protection

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 wavelength-discontinuous 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.

3.5.3  Limited Alternate Routing

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.

3.5.4  Static Priority Method

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 higher-priority 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.

3.5.5  Dynamic Priority Method

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 pre-computed 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.

  • F_Res is used to reserve wavelengths in F set on the link of the routes. It consists of connection_id, route, and S free. Since the message does not reserve any wavelength, S free initially contains all the wavelengths. It travels along the route from the source node to the destination node.
  • F_Res_Succ indicates the successful reservation of wavelengths in F set on the link of the routes. It consists of connection_id, route, and w res. w res represents the free wavelength that is assigned to the connection request. It travels back along the route from the destination node to the source node.
  • F_Res_Fail indicates the unsuccessful reservation of wavelengths in F set on the link of the routes. It consists of connection_id and route. It travels back along the route from an intermediate node to the source node.
  • Rel is sent to release the light path on some wavelength. It consists of only connection_id. It travels along the route from the source node to the destination node.
  • Pri_Reg is used to register the priority of the connection request on the links of a route. It consists of connection_id, route, and pri_level. The pri_level indicates the priority level of the connection request. It travels along the route from the source node to the destination node.
  • Pri_Cancel is used to cancel the priority of the connection request registered earlier by the request on the links of a route. It carries connection_id, route, and pri_level. The pri_level indicates the priority level of the connection request. It also travels along the route from the source node to the destination node.
  • P_Res is used to reserve wavelengths in P set on the link of the routes. It consists of connection_id, route, S free, and pri_level. It travels along the route from the source node to the destination node.
  • P_Res_Succ indicates the successful reservation of wavelengths in P set on the link of the routes. It consists of connection_id, route, and w res. It travels back along the route from the destination node to the source node.
  • P_Res_Fail indicates the unsuccessful reservation of some wavelengths in P set on the link of the routes. It consists of connection_id and route. It travels back along the route from the intermediate node to the source node.
  • Blk_Info carries information about the blocking performance of different traffic streams originating from a particular node. It broadcasts this information to other nodes in the network along the links of a pre-computed spanning tree over the shadow network. This message is sent periodically from every node to all the other nodes for computing priority level.

Protocol Mechanism

The procedure of the protocol for light path establishment and release is given below [44].

  • Step-1: When a request arrives at node s for connection to some other node d, the source node s prepares an F_Res message with the required information. A new sequence number seq_no is obtained. S free has a maximum of MAX_WL wavelengths. The control message is transmitted through the first candidate route on the control channel.
  • Step-2: When the message is at intermediate node i, it selects the outgoing route from the route information. The set S free is updated by considering the set of common available wavelengths with outgoing link from F set. If the new S free has available wavelengths from F set, the node forwards the message to the next neighbor node with updated S free along the outgoing link chosen from the route information. If the F_Res message reaches the destination node d, the reservation is successful, and node d transmits an F_Res_Succ. A wavelength in S free is chosen and assigned to the field w res. This message is sent back to the neighbor along the incoming link. This moves toward the source, updating table entries at the intermediate nodes and releasing wavelengths reserved except the selected wavelength. Otherwise it goes to the next step.
  • Step-3: If S free has no available wavelengths at node i, the F_Res_Fail message is prepared to be transmitted and sent to the neighbor along the incoming link determined from the route information and ultimate sent back to the source node. When the source node receives the F_Res_Fail message, it goes to the next step.
  • Step-4: It creates a new S free and again sends the F_Res along the route. If all the wavelengths in F set have been searched, then step-2 and step-3 are repeated for the remaining candidate routes one by one up to a maximum of MAX_TRIES leaving the GAP. If everything fails, it goes to the next step.
  • Step-5: The F_Res starts searching for a free wavelength from P set. The source node generates Pri_Reg message which includes its estimated priority level and sends it along the candidate routes. This message registers the priority on the links by incrementing the count associated with the appropriate priority level. Finally, it reaches the destination. The source node sends P_Res along the route. When an intermediate node i receives the same, it first determines the outgoing link by examining the number of competing requests registered on the outgoing link at the priority level higher than that mentioned in the received message. If no such registration exists at the higher priority levels and the intersections of S free with the set of wavelengths from P set on the outgoing link is not empty, then the message is forwarded to the next intermediate node after performing necessary updates in the tables. Finally, it reaches the destination node d, and after it reaches there, the destination node transmits the P_Res_Succ message toward the source node along the same route passing through the same intermediate node. After receiving this message, the source node transmits Pri_Cancel along the same route before the transmission of the date through the same route. If the reservation fails, then it goes to the next step.
  • Step-6: The node i generates a P_Res_Fail message to be sent to the previous node along the incoming link, and the same message propagates toward the source through various intermediate nodes updating the state information in the tables. If the source node receives the same, it creates a new S free and again sends the P_Res message along the route. If all the wavelengths in P set have been searched, then the same procedure for MAX_TRIES is repeated a number of times with the GAP between two successive tries. If everything fails, the connection request is rejected, and the source node generates the Pri_Cancel message which is sent along the routes.

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.

Dynamic priority reservation: (a) successful reservation of
                           wavelength in

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 pre-computed 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.

3.6  Mathematical Formulation of RWA

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:

  • i, j represent the end points of the physical link that occurs in the route of a connection.
  • l is used as an index for the link number, where l = 1, 2, 3, …, L; L = total number of links.
  • w is used as an index for the wavelength number, where w = 1, 2, 3 … W; W = total number of wavelengths carried by each fiber link.

The following inputs are supplied to the problem:

  • An N × N distance matrix, where N = total number of nodes in the network and d i j = (i, j)th element of distance matrix = distance between i and j nodes. Note that d i j = d j i if and only if there exists a physical fiber link between i and j nodes and d i j = ∞ if there is no fiber link.
  • An N × N traffic matrix where the (i, j)th element, αi, j , is the traffic flow rate from i node to j node.

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]:

3.9 T p = Σ i j Σ x , y Σ w w = 1 α i , j P i , j , w x , y d x , y L v
  • where P i , j , w x , y = light path-wavelength-link indicator
    • = 1, if there is a light path from node i to node j and it uses wavelength w on a physical link from node x to node y
    • = 0, otherwise
  •      Lv = velocity of light.

The queuing delay can be computed as follows:

3.10 T q = Σ i j α i , j C m α i , j

where Cm = maximum capacity per light path.

3.11 α i , j = Σ s , d α i , j s , d i , j

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

3.12 T d = T q + T p

3.6.1  Traffic Flow Constraints

The traffic flow constraints pertain to the traffic routed over the light paths in the network [3].

3.13 α i , j C m ( i , j )
3.14 α i , j s , d P i , j t s , d
  • where Pi,j = light path indicator
    • = 1, if there is a light path from node i to node j
    • = 0, otherwise.
  • ts,d = average traffic flow rate from source node s to destination node d
3.15 Σ j α i , j s , d Σ j α j , i s , d = t s , d ,  if  s = i = t s , d ,  if  d = i = 0 ,  if  s i  and  d i . }

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.

3.6.2  Wavelength Constraints

The wavelength constraints pertain to the assignment of wavelengths to the light paths [1,3,45].

3.16 P i , j = Σ w = 0 W 1 P i , j , w ( i , j )
3.17 P i , j , w x , y P i , j , w ( i , j ) , ( x , y ) , w
3.18 Σ i , j P i , j , w x , y 1 ( x , y ) , w
3.19 Σ w = 0 W 1 Σ x P i , j , w x , y l x , y Σ w = 0 W 1 Σ P i , j , w y , x l y , x = P i , j ,  if  y = j = P i , j ,  if  y = i = 0 ,  if  y i  and  y j . }

Equation (3.16) shows that the wavelength used by a light path is unique. Equation (3.17) expresses the wavelength-continuity 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.

3.7  Priority-Based RWA

To reduce the BP in the network, a priority-based 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 wavelength-continuity constraint of the network. The wavelength-continuity constraint needs the use of the same wavelength on all hops in the end-to-end path of a connection. Use of a conventional RWA approach under the wavelength-continuity 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 wavelength-continuity 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.

Priority-based WRA concept.

Figure 3.11   Priority-based WRA concept.

NSFNET T1 optical backbone with distance matrix.

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

3.20 R = { r W A . C A 2 , r W A . C A 1 , r W A . I L }  and R " = { r W A . N Y , r W A . N E , r W A . G A , r W A . U T , r W A . N J , r W A . P A , r W A . M I , r W A . T X , r W A . C O }

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.

Table 3.3   Connection Requests and Traffic Volumes

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

Table 3.4   Connection Requests with their Priority Order

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

  • Step-1: Enqueue all the connection requests in the priority queue to estimate their priority order.
  • Step-2: Cluster all the connection requests into two categories – direct physical link connection requests and indirect physical link connection requests.
    R = { r D , 1 S 1 , d 1 , r D , 2 S 2 , d 2 , ... , r D , x S x , d x }
    R " = { r I , 1 S 1 , d 1 , r I , 2 S 2 , d 2 , ... , r I , Y S Y , d Y }
    such that
    Vol ( r D , 1 S 1 , d 1 ) Vol ( r D , 2 S 2 , d 2 ) .... Vol ( r D , x S x , d x )
    Vol ( r I , 1 S 1 , d 1 ) vol ( r I , 2 S 2 , d 2 ) ... Vol ( r D , Y S Y , d Y )
    where R′ and R″ are the two ordered sets of connection requests having direct physical link (D) and indirect physical link (I), respectively. X and Y are the total numbers of connection requests having direct and indirect physical links, respectively. The priority order of each connection request is assigned according to its position, i.e., either in R′ or in R″. Connection requests in R′ have higher priorities compared to those in R″. Vol ( r D , 1 S 1 , d 1 ) , Vol ( r I , 1 S 1 , d 1 ) indicate the volumes of traffic for the connection requests of r D , 1 S 1 , d 1 , r I , 1 S 1 , d 1 , respectively.
  • Step-3: Compute K numbers of shortest paths (including primary path) using Dijkstra’s algorithm for each of the connection requests on the basis of link state information.
  • Step-4: For each of the connection requests in R′ and R″, selected based on their priority order, perform the following in the given sequence:
    • First, try to assign a wavelength according to wavelength constraints [2] to the primary path based on FF method.
    • If no WA is possible in step-4(a), consider the alternate paths in the ascending order of their light path distance for assigning a wavelength (with a constraint on wavelength similar to that in step-4(a)) till an alternate path is assigned a wavelength.
    • If no WA is possible in either step-4(a) or step-4(b) within tH, the connection request is treated as a blocked one. Otherwise, add the established connection to the total number of established connections in the network.
    • Drop the connection request from 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 non-negative 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]:

  • Each fiber link can carry an equal number of wavelengths, and the network is without wavelength conversion capabilities.
  • All the light paths using the same fiber link must be allocated distinct wavelengths.
  • Each node can work as both an access node and a routing node.
  • Each node is equipped with a fixed number of tunable transceivers.
  • Each node is capable of multiplexing/demultiplexing as many connection requests (having the same SD pair) within the channel capacity.
  • All the channels have the same bandwidth.
  • The connection requests arrive in the system randomly based on a Poisson process.
  • The holding times of all connection requests having the same sd pair are equal.

The following notations are used in this formulation:

  • N and E are the total numbers of nodes and links, respectively, in the network. s and d are the source and destination of a connection request.
  • A is the total number of different sd pairs for all connection requests (A = N(N − 1)).
  • W is the total number of wavelengths per fiber link.
  • L is the number of links between an sd pair.
  • Z is the total number of connection requests in the network.
  • Y is the total number of groomed connection requests in the network (YZ).
  • αs,d is the total volume of traffic for a connection request between the source and the destination in an sd pair.
  • α i , j s , d is the component of traffic due to an sd pair on a light path from node i to node j.
  • αi,j is the total amount of traffic on a light path from node i to node j.
  • C B s , d is the maximum bandwidth of a connection request between the source and the destination in an sd pair.
  • CB is the maximum bandwidth or capacity of a channel.
  • tH is the holding time of a connection request C(s,d).
  • K is the number of alternate paths.
  • P i , j , λ x , y is the light path-wavelength-link indicator.
    • P i , j , λ x , y = 1, if there exists a light path from node i to node j and it uses wavelength λ, on a physical link between node x and node y
      • = 0, otherwise
  • Pi,j,λ is the light path-wavelength indicator.
    • Pi,j = 1, if there exists a light path from node i to node j
      • = 0, otherwise
  • Pi,j is the light path indicator.
    • Pi,j = 1, if there exists a light path from node i to node j
      • = 0, otherwise
  • f max is the maximum traffic flow on any light path in the network.

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.143.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]:

3.21 α i , j = Σ s , d α i , j s , d ( i , j )
3.22 α i , j s , d f max

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]

3.23 α i , j C B ( s , d )
3.24 α i , j s , d C B . P i , j

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/wavelength-division demultiplexers (WDDMs) [46], W thermo-optic switches (TOSWs) [47,48], W transceivers, W add–drop multiplexers (ADMs) [49,50], a SONET STS-192 multiplexer/SONET STS-192 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 STS-192. (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 STS-192.) 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 STS-192 demultiplexer to send the signals to the users.

Network node architecture (WDDM: wavelength-division demultiplexer, WDM:
                        wavelength-division multiplexer, TOSW: thermo-optic switch, MUX:
                        multiplexer, DMUX: demultiplexer, TX: transmitter, RX: receiver, ADD–DROP:
                        add–drop multiplexer, PRWA: priority-based routing and wavelength
                        assignment).

Figure 3.13   Network node architecture (WDDM: wavelength-division demultiplexer, WDM: wavelength-division multiplexer, TOSW: thermo-optic switch, MUX: multiplexer, DMUX: demultiplexer, TX: transmitter, RX: receiver, ADD–DROP: add–drop multiplexer, PRWA: priority-based routing and wavelength assignment).

3.8  Comparative Study of Different RWA Algorithms on NSFNET T1 Backbone

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).

BP versus number of wavelengths for FR, AR, FAR, and PRWA.

Figure 3.14   BP versus number of wavelengths for FR, AR, FAR, and PRWA.

BP versus number of wavelengths for FF, LU, and random WA.

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 multi-fiber-link and single-fiber-link 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.

Table 3.5   Comparison between Different Approaches Such as MS, RCL, MP, LL, LU, LU, Random, FF, and PRWA

Approach

Performance Analysis

No. of Fibers

Average Setup Time

Blocking Probability

Time Complexity

MS

In multi-fiber 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 multi-fiber networks, it performs well in comparison to others for low traffic loads

~ O(L 1 M W N Z)

Multiple

Medium value

LL

In multi-fiber 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 – priority-based 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 multi-fiber networks. MP estimates Π l∈π(p) Dlj 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).

Max-Sum and RCL are costly. The worst-case 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 NP-complete.

Summary

This chapter discusses long-haul wide-coverage optical networks based on arbitrary (mesh) topology in which nodes employ wavelength-routing switches (or optical cross-connects (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.

Exercises

 
 
3.1 

Given a graph G = (V,E), define

k = max 1 i n ( 1 + dag v 1 , v 2 , ... , v n ( v i ) )

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 ≤ in. Show that over all the n! possible vertex orderings, the SL vertex ordering minimizes the value of k.

 
3.2 

Consider the network shown in Figure Exercise 3.1. Let the connection requests be as follows:

  • B-H, A-E, B-D, D-F, B-F, C-E, C-H, A-G, A-C.
  • Set up light paths to satisfy the above connection requests using at most three wavelengths per link. Assume no wavelength conversion.

Sample network. □ Access station ○ node.

Figure Exercise 3.1   Sample network. □ Access station ○ node.

 
3.3 

We know that the SLE problem is NP-complete. Show a simple transformation that transforms an SLE problem into a graph-coloring problem.

 
3.4 

Consider the network in Figure Exercise 3.1 and the following light paths:

  • C-7-8-9-E
  • A-1-5-8-9-E
  • H-2-1-5-8-7-C
  • B-6-7-8-9-E
  • A-1-6-7-10-D
  • G-3-2-1-6-B
  • H-2-3-4-F.

Color the light paths using the minimum number of wavelengths.

 
3.5 

Consider the NSFNET physical topology shown in Figure 3.12. Remove the nodes CA2 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?

Sample network having 11 nodes.

Figure Exercise 3.2   Sample network having 11 nodes.

 
3.6 

Compare the characteristics of various routing schemes.

 
3.7 

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.

Indian network connecting major cities of India.

Figure Exercise 3.3   Indian network connecting major cities of India.

 
3.8 

Consider the Indian network physical topology shown in Ex Figure 3.3. If node-2 and node-3 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.

 
3.9 

Compare the characteristics of different WAs heuristics.

 
3.10 

Find the routing table for node-1, node-2, and node-4 for the following network by using Dijkstra’s algorithm. The cost of each link is also shown in Ex Figure 3.4

Sample network having 6 nodes and 9 bidirectional
                                    links.

Figure Exercise 3.4   Sample network having 6 nodes and 9 bidirectional links.

 
3.11 

Find the routing table for node-1, node-2, and node-3 for the network in Ex Figure 3.4 by using Dijkstra’s algorithm if node-4 fails to work.

 
3.12 

Find the routing table for node-1, node-2, and node-4 for the following network by using Bellman–Ford’s algorithm. The cost of each link is also shown in Ex Figure 3.5.

 
3.13 

Find the routing table for node-1, node-2, and node-4 for the following network by using genetic algorithm. The cost of each link is also shown in Ex Figure 3.5.

 
3.14 

Find the routing table for node-1 and node-2 for the network in Ex Figure 3.5 by using simulated-annealing algorithm.

Sample network 6 nodes and 8 bidirectional links.

Figure Exercise 3.5   Sample network 6 nodes and 8 bidirectional links.

 
3.15 

Update the routing table for node-1 and node-2 for the network in Ex Figure 3.5 by using Bellman–Ford’s algorithm if node-4 fails.

References

1
B. Mukherjee , Optical WDM Networks, Springer-Verlag, 2006.
2
I. Chlamtac , A. Ganz , and G. Karmi , “Lightnets: Topologies for high speed optical networks,” IEEE/OSA Journal of Lightwave Technology, vol. 11, pp. 951–961, 1993.
3
H. Zang , J. P. Jue , and B. Mukherjee , “A review of routing and wavelength Assignment approaches for wavelength-routed optical WDM networks,” SPIE Optical Networks Magazine, vol. 1, pp. 47–60, 2000.
4
H. Zang , J. P. Jue , and B. Mukherjee , “Capacity allocation and contention resolution in a photonic slot routing all-optical WDM mesh network,” IEEE/OSA Journal of Lightwave Technology, vol. 18, no. 12, pp. 1728–1741, 2000.
5
B. C. Chatterjee , N. Sarma , and P. P. Sahu , “Review and performance analysis on routing and wavelength assignment approaches for optical networks”, IETE Technical Review, vol. 30, pp. 12–23, 2013.
6
R. Ramaswami and K. Sivarajan , “Optimal routing and wavelength assignment in all-optical networks,” IEEE/ACM Transactions on Networking, vol. 3, pp. 489–500, 1995.
7
R. Ramaswami and K. Sivarajan , “Design of logical topologies for wavelength-routed all-optical networks,” Proceedings, IEEE INFOCOM’95, Boston, MA, pp. 1316–1325, April 1995.
8
R. Ramaswami and K. N. Sivarajan , “Design of logical topologies for wavelength-routed optical networks,” IEEE Journal on Selected Areas in Communications, vol. 14, no. 5, pp. 840–851, 1996.
9
P. Raghavan and C. D. Thonlpson , “Randomized rounding: A technique for provably good algorithms and algorithmic proofs,” Combinatorica, vol. 7, no. 4, pp. 365–374, 1987.
10
C. Ou , H. Zang , N. Singhal , B. Mukherjee , et al., “Sub-path protection for scalability and fast recovery in optical WDM mesh networks,” IEEE Journal on Selected Areas in Communications, vol. 22, no. 11, pp. 1859–1875, 2004.
1112
D. W. Matula , G. Marble , and J. D. Isancson , “Graph coloring algorithms,” Graph Theory and Computing ( R. C. Read , ed.), New York and London: Academic Press, 1972.
13
D. W. Matula , “k-components, clusters and slicings in graphs,” SIAM Journal of Applied Mathematics, vol. 22, pp. 459–480, 1972.
14
M. Berkelaar , “lpsolve: Readme file,” Documentation for the lP Solve program, 1994.
15
K. M. Chan and T. S. Yum , “Analysis of least congested path routing in WDM lightwave networks,” Proceedings, IEEE INFOCOM’94, Toronto, Canada, pp. 962–969, June 1994.
16
R. Bhandari , Survivable Networks: Algorithms for Diverse Routing, Kluwer Academic Publishers, 1999.
17
W. Stalling , Data and Computer Communication, PHI, 1999.
18
J. J. Garcia-Luna-Aceves , “Distributed routing with labeled distances,” Proceedings, IEEE INFO COM’92, Florence, Italy, pp. 633–643, May 1992.
19
S. Rarnamurthy , “Optical design of WDM network architectures,” Ph.D. Dissertation, University of California, Davis, 1998.
20
R. Libeskind-Hadas , “Efficient collective communication in WDM networks with a power budget,” Proceedings, Ninth, IEEE International Conference on Computer Communications and Networks (ICCCN), Las Vegas, Nevada, pp. 612–616, October 2000.
21
B. Rarnamurthy and B. Mukherjee , “Wavelength conversion in optical networks: Progress and challenges,” IEEE Journal on Selected Areas in Communications, vol. 16, pp. 1040–1050, 1998.
22
Y. Huang , J. P. Heritage and B. Mukherjee , “Connection provisioning with transmission impairment consideration in optical WDM networks with high-speed channels,” IEEE/OSA Journal of Lightwave Technology, vol. 23, no. 3, pp. 982–993, 2005.
23
S. Ramamurthy and B. Mukherjee , “Survivable WDM mesh networks, part I-protection,” Proceedings, IEEE INFOCOM ‘99, New York, pp. 744–751, March 1999.
24
L. Li and A. K. Somani , “Dynamic wavelength routing using congestion and neighborhood information,” IEEE/ACM Transactions on Networking, vol. 7, no. 5, pp. 779–786, 1999.
25
D. Banerjee and B. Mukherjee , “Practical approaches for routing and wavelength assignment in large all-optical wavelength-routed networks,” IEEE Journal on Selected Areas in Communications, vol. 14, pp. 903–908, 1996.
26
D. Banerjee and B. Mukherjee , “Wavelength-routed optical networks: Linear formulation, resource budgeting tradeoffs, and a reconfiguration study,” IEEE/ACM Transactions on Networking, vol. 8, no. 5, pp. 598–607, 2000.
27
S. Subramaniam , R.A. Barry , “Wavelength assignment in fixed routing WDM networks,” IEEE International Conference on Communications, 1997, pp. 406–410.
28
C.R. Reeves , Modern Heuristic Techniques for Combinatorial Problems, McGraw-Hill, 1995.
29
V.J. Rayward-Smith , I.H. Osman , C.R. Reeves , and G.D. Smith , Modern Heuristic Search Methods, John Wiley & Sons, 1996.
30
A. Hertz and D. de Werra , “Using Tabu search techniques for graph coloring”, Computing, vol. 39, pp. 345–351, 1987.
31
R. Ramaswami , K. N. Sivarajan , Routing and wavelength assignment in all-optical networks, Tech Rep. RC 19592, IBM Research Report, 1994.
32
Y. Sun , J. Gu , and D. H. K. Tsang , “Multicast routing in all optical wavelength routed networks,” Optical Networks Magazine, vol. 2, pp. 101–109, 2001.
33
G. Jeong and E. Ayanoglu , “Comparison of wavelength interchanging and wavelength- selective cross-connects in multiwavelength all-optical networks,” Proceedings, IEEE INFOCOM’96, San Francisco, CA, pp. 156–163, March 1996.
34
E. Karasan and E. Ayanoglu , “Effects of wavelength routing and selection algorithms on wavelength conversion gain in WDM optical networks,” IEEE/ACM Transactions on Networking, vol. 6, no. 2, pp. 186–196, 1998.
35
R. A. Barry and S. Subramaniam , “The MAX-SUM wavelength assignment algorithm for WDM ring networks,” Proceedings, OFC’97, Dallas, TX, pp. 121–122, February 1997.
36
X. Zhang and C. Qiao , “Wavelength assignment for dynamic traffic in multi-fiber WDM networks,” Proceedings, 7th International Conference on Computer Communications and Networks, Lafayette, LA, pp. 479–485, October 1998.
37
A. Birman and A. Kershenbaum , “Routing and wavelength assignment methods in single-hop all- optical networks with blocking,” Proceedings, IEEE INFOCOM’95, Boston, MA, pp. 431–438, April 1995.
38
X. Yuan , R. Melhem , R. Gupta , Y. hlei , and C. Qiao , “Distributed control protocols for wavelength reservation and their performance evaluation,” Photonic Network Communications, vol. 1, no. 3, pp. 207–218, 1999.
39
N. Charbonneau and V. M. Vokkarane , “A survey of advance reservation routing and wavelength assignment in wavelength-routed WDM networks,” IEEE Communications Surveys & Tutorials, vol. 14, pp. 1037–1064, 2012.
40
N. Fazlollahi and D. Starobinski , “Distributed advance network reservation with delay guarantees,” IEEE International Symposium on Parallel Distributed Processing (IPDPS), pp. 1–12, 2010.
41
C. Xie , H. Alazemi , and N. Ghani , “Routing and scheduling in distributed advance reservation networks,” Proc. IEEE GLOBECOM, 2010.
42
B. C. Chatterjee , N. Sarma , and P. P. Sahu , “Priority based routing and wavelength assignment with traffic grooming for optical networks,” IEEE/OSA Journal of Optical Communication and Networking, vol. 4, no. 6, pp. 480–489, 2012.
43
B. C. Chatterjee , N. Sarma , and P. P. Sahu , “Priority based dispersion-reduced wavelength assignment for optical networks”, IEEE/OSA Journal of Lightwave Technology, vol. 31, no. 2, pp. 257–263, 2013.
44
D. M. Shan , K. C. Chua , G. Mohan , and M. H. Phunq , “Priority-based offline wavelength assignment in OBS networks,” IEEE Transactions on Communications, vol. 56, no. 10, pp. 1694–1704, 2008.
45
B. C. Chatterjee , N. Sarma , and P. P. Sahu , “A heuristic priority based wavelength assignment scheme for optical networks,” Optik –International Journal for Light and Electron Optics, vol. 123, no. 17, pp. 1505–1510, 2012.
46
P. P. Sahu , “Compact optical multiplexer using silicon nano-waveguide,” IEEE Journal of Selected Topics in Quantum Electronics, vol. 15, no. 5, pp. 1537–1541, 2009.
47
P. P. Sahu , “Thermooptic two mode interference photonic switch,” Fiber and Integrated Optics, vol. 29, pp. 284–293, 2010.
48
P. P. Sahu and A. K. Das , “Polarization-insensitive thermo-optic Mach Zehnder based on silicon oxinitride waveguide with fast response time” Fiber and Integrated Optics, vol. 29, no. 1, pp. 10–20, 2010.
49
P. P. Sahu , “Tunable optical add/drop multiplexers using cascaded Mach Zehnder Coupler,” Fiber and Integrated Optics, vol. 27, no. 1, pp. 24–34, 2008.
50
P. P. Sahu “Polarization insensitive thermally tunable Add/Drop multiplexer using cascaded Mach Zehnder coupler,” Applied Physics: Lasers and Optics, vol. B92, pp. 247–252, 2008.
51
G. Keiser , Optical Fiber Communication, McGraw Hill, 2002.
Search for more...
Back to top

Use of cookies on this website

We are using cookies to provide statistics that help us give you the best experience of our site. You can find out more in our Privacy Policy. By continuing to use the site you are agreeing to our use of cookies.