Routing Wavelength Assignment (RWA)
Encyclopedia
The routing and wavelength assignment (RWA) problem is a optical networking
problem with the goal of maximizing the number of optical connections.
, provided a different wavelength is used.
The RWA problem can be formally defined in an integer linear program
(ILP). The ILP formulation given here is taken from .
Maximize:
subject to
is the number of source-destination pairs, while 
is the number of connections established for each source-destination pair. 
is the number of links and 
is the number of wavelengths. 
is the set of paths to route connections. 
is a matrix which shows which source-destination pairs are activate, 
is a matrix which shows which links are activate, and 
is a route and wavelength assignment matrix.
Note that the above formulation assumes that the traffic demands are known a priori. This type of problem is known as Static Lightpath Establishment (SLE). The above formulation also does not consider the signal quality.
It has been shown that the SLE RWA problem is NP-complete
in . The proof involves a reduction to the
-graph colorability problem. In other words, solving the SLE RWA problem is as complex as finding the chromatic number
of a general graph. Given that dynamic RWA is more complex than static RWA, it must be the case that dynamic RWA is also NP-complete.
Another NP-complete proof is given in . This proof involves a reduction to the Multi-commodity Flow Problem
.
The RWA problem is further complicated by the need to consider signal quality. Many of the optical impairments are nonlinear, so a standard shortest path algorithm can't be used to solve them optimally even if we know the exact state of the network. This is usually not a safe assumption, so solutions need to be efficient using only limited network information.
. While this approach is very simple, the performance is usually not sufficient. If resources along the fixed path are in use, future connection requests will be blocked even though other paths may exist.
The SP-1 (Shortest Path, 1 Probe) algorithm is an example of a Fixed Path Routing solution. This algorithm calculates the shortest path using the number of optical routers as the cost function. A single probe is used to establish the connection using the shortest path. The running time
is the cost of Dijkstra's algorithm:
, where 
is the number of edges and 
is the number of routers. The running time is just a constant if a predetermined path is used.
This definition of SP-1 uses the hop count
as the cost function. The SP-1 algorithm could be extended to use different cost functions, such as the number of EDFAs.
The SP-
(Shortest Path, 
Probes, 
) algorithm is an example of Fixed Alternate Routing. This algorithm calculates the 
shortest paths using the number of optical routers as the cost function. The running time using Yen's algorithm is 
where 
is the number of edges, 
is the number of routers, and 
is the number of paths. The running time is a constant factor if the paths are precomputed.
Adaptive algorithms fall into two categories: traditional and physically aware. Traditional adaptive algorithms do not consider signal quality, however, physically aware adaptive algorithms do.
(LORA) algorithm was proposed in . The main idea behind LORA is to route connection requests away from congested areas of the network, increasing the probability that connection requests will be accepted. This is accomplished by setting the cost of each link to be
where 
is parameter that can be dynamically adjusted according to the traffic load and 
is the number of wavelengths in use on link 
. A standard shortest path algorithm can then be used to find the path. This requires each optical switch
to broadcast recent usage information periodically. Note that LORA does not consider any physical impairments.
When
is equal to one, the LORA algorithm is identical to the SP algorithm. Increasing the value of 
will increase the bias towards less used routes. The optimal value of can be calculated using the well-known hill climbing
algorithm. The optimal values of
were between 1.1 and 1.2 in the proposal.
Note that PABR can only consider linear impairments. The nonlinear impairments, on the other hand, would not be possible to estimate in a distributed environment due to their requirement of global traffic knowledge.
PABR also considers signal quality when making the wavelength selection. It accomplishes this by removing from consideration all wavelengths with an unacceptable signal quality level. The approach is called Quality First Fit and it is discussed in the following section.
It should also be noted that both LORA and PABR can be implemented with either single-probing or multi-probing. The maximum number of probes
is denoted as LORA-
or PABR-
. With single-probing, only one path is selected by the route selection. With multi-probing, multiple paths are attempted in parallel, increasing the probability of connection success.
The multi-probing approach will allow IA-BF to outperform both PABR-1 and LORA-1. However, as the number of probes increases, the performance of the algorithms is similar.
IA-FF - Impairment Aware First Fit (IA-FF) is a simple extension
of IA-BF. Instead of picking the wavelengths in terms of the minimum cost, the wavelengths are selected in order according to their index. IA-BF tends to outperform IA-FF under most scenarios.
AQoS - Adaptive Quality of Service (AQoS) was proposed in . This algorithm is unique in a couple of ways. First, each node maintains two counters:
and 
. The purpose of each counter is to determine which issue is a bigger factor in blocking: Path and wavelength availability or Quality requirements. The algorithm chooses routes differently based upon the larger issue.
Another distinction is that AQoS uses the Q-factor
as the link cost. The cost of the
link is calculated by this formula 
where 
is the number of lightpaths on the 
link, 
and 
are the quality factor measurements of the 
lightpath at the source and destination nodes of the 
link, respectively. The repeated quality factor estimations are computationally very expensive.
This algorithm is single probing approach. The multi-probing approach, which the paper names ALT-AQoS (alternate AQoS) is a simple extension upon the same basic idea.
, where 
is the number of wavelengths. First Fit outperforms Random Fit.
An extension to First Fit and Random Fit was proposed in to consider signal quality. Quality First Fit and Quality Random Fit eliminate from consideration wavelengths which have an unacceptable signal quality. The complexity of these algorithms is higher though, as up to
calls to estimate the Q-factor are required.
There are several other wavelength assignment algorithms: Least Used, Most Used, Min Product, Least Loaded, Max Sum , and Relative Capacity Loss . Most Used outperforms Least Used use significantly, and slightly outperforms First Fit. Min Product, Least Loaded, Max Sum, and Relative Capacity Loss all try to choose a wavelength that minimizes the probability that future requests will be blocked.
A significant disadvantage of these algorithms is that they require a significant communication overhead, making them unpractical to implement unless you have a centralized network structure.
.
The ILP formulation listed above can be solved using a traditional ILP solver. This is typically done by temporarily relaxing the integer constraints, solving the problem optimally, and converting the real solution to an integer solution. Additional constraints can be added and the process repeated indefinitely using a branch and bound
approach.
Optical networking
Optical networking can refer to:* Optical communication* Fiber-optic communication* Synchronous optical networking* Optical Transport Network * Passive optical network...
problem with the goal of maximizing the number of optical connections.
Definition
The general objective of the RWA problem is to maximize the number of established connections. Each connection request must be given a route and wavelength. The wavelength must be consistent for the entire path, unless the usage of wavelength converters is assumed. Two connections requests can share the same optical linkOptical link
An optical link is a communications link that consists of a single end-to-end optical circuit. A cable of optical fiber, possibly concatenated into a dark fiber link, is the simplest form of an optical link....
, provided a different wavelength is used.
The RWA problem can be formally defined in an integer linear program
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
(ILP). The ILP formulation given here is taken from .
Maximize:
subject to
is the number of source-destination pairs, while is the number of connections established for each source-destination pair. is the number of links and is the number of wavelengths. is the set of paths to route connections. is a matrix which shows which source-destination pairs are activate, is a matrix which shows which links are activate, and is a route and wavelength assignment matrix.Note that the above formulation assumes that the traffic demands are known a priori. This type of problem is known as Static Lightpath Establishment (SLE). The above formulation also does not consider the signal quality.
It has been shown that the SLE RWA problem is NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
in . The proof involves a reduction to the
-graph colorability problem. In other words, solving the SLE RWA problem is as complex as finding the chromatic numberGraph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
of a general graph. Given that dynamic RWA is more complex than static RWA, it must be the case that dynamic RWA is also NP-complete.
Another NP-complete proof is given in . This proof involves a reduction to the Multi-commodity Flow Problem
Multi-commodity flow problem
The multi-commodity flow problem is a network flow problem with multiple commodities flowing through the network, with different source and sink nodes.-Definition:Given a flow network \,G, where edge \in E has capacity \,c...
.
The RWA problem is further complicated by the need to consider signal quality. Many of the optical impairments are nonlinear, so a standard shortest path algorithm can't be used to solve them optimally even if we know the exact state of the network. This is usually not a safe assumption, so solutions need to be efficient using only limited network information.
Methodology
Given the complexity of RWA, there are two general methodologies for solving the problem:- The first method is solving the routing portion first, and then assigning a wavelength second. Three types of route selection are Fixed Path Routing, Fixed Alternate Routing, and Adaptive RoutingAdaptive routingAdaptive routing describes the capability of a system, through which routes are characterized by their destination, to alter the path that the route takes through the system in response to a change in conditions...
. - The second approach is to consider both route selection and wavelength assignment jointly.
Fixed path routing
Fixed path routing is the simplest approach to finding a lightpath. The same fixed route for a given source and destination pair is always used. Typically this path is computed ahead of time using a shortest path algorithm, such as Dijkstra's AlgorithmDijkstra's algorithm
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
. While this approach is very simple, the performance is usually not sufficient. If resources along the fixed path are in use, future connection requests will be blocked even though other paths may exist.
The SP-1 (Shortest Path, 1 Probe) algorithm is an example of a Fixed Path Routing solution. This algorithm calculates the shortest path using the number of optical routers as the cost function. A single probe is used to establish the connection using the shortest path. The running time
Analysis of algorithms
To analyze an algorithm is to determine the amount of resources necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length...
is the cost of Dijkstra's algorithm:
, where is the number of edges and is the number of routers. The running time is just a constant if a predetermined path is used.This definition of SP-1 uses the hop count
Hop count
In computer networking, hop count refers to the number of routers through which data must pass between source and destination. Each router along the data path constitutes a hop, as the data is moved from one Layer 3 network to another...
as the cost function. The SP-1 algorithm could be extended to use different cost functions, such as the number of EDFAs.
Fixed alternate routing
Fixed alternate routing is an extension of fixed path routing. Instead of having just one fixed route for a given source and destination pair, several routes are stored. The probes can be sent in a serial or parallel fashion. For each connection request, the source node attempts to find a connection on each of the paths. If all of the paths fail, then the connection is blocked. If multiple paths are available, only one of them would be utilized.The SP-
(Shortest Path, Probes, ) algorithm is an example of Fixed Alternate Routing. This algorithm calculates the shortest paths using the number of optical routers as the cost function. The running time using Yen's algorithm is where is the number of edges, is the number of routers, and is the number of paths. The running time is a constant factor if the paths are precomputed.Adaptive routing
The major issue with both fixed path routing and fixed alternate routing is that neither algorithm takes into account the current state of the network. If the predetermined paths are not available, the connection request will become blocked even though other paths may exist. Fixed Path Routing and Fixed Alternate Routing are both not quality aware. For these reasons, most of the research in RWA is currently taking place in Adaptive algorithms. Five examples of Adaptive Routing are LORA, PABR, IA-BF, IA-FF, and AQoS.Adaptive algorithms fall into two categories: traditional and physically aware. Traditional adaptive algorithms do not consider signal quality, however, physically aware adaptive algorithms do.
Traditional adaptive RWA
The lexicographical routing algorithmRouting
Routing is the process of selecting paths in a network along which to send network traffic. Routing is performed for many kinds of networks, including the telephone network , electronic data networks , and transportation networks...
(LORA) algorithm was proposed in . The main idea behind LORA is to route connection requests away from congested areas of the network, increasing the probability that connection requests will be accepted. This is accomplished by setting the cost of each link to be
where is parameter that can be dynamically adjusted according to the traffic load and is the number of wavelengths in use on link . A standard shortest path algorithm can then be used to find the path. This requires each optical switchOptical switch
In telecommunication, an optical switch is a switch that enables signals in optical fibers or integrated optical circuits to be selectively switched from one circuit to another....
to broadcast recent usage information periodically. Note that LORA does not consider any physical impairments.
When
is equal to one, the LORA algorithm is identical to the SP algorithm. Increasing the value of will increase the bias towards less used routes. The optimal value of can be calculated using the well-known hill climbingHill climbing
In computer science, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by incrementally changing a single element of the solution...
algorithm. The optimal values of
were between 1.1 and 1.2 in the proposal.Physically aware adaptive RWA
The physically aware backward reservation algorithm (PABR) is an extension of LORA. PABR is able to improve performance in two ways: considering physical impairments and improved wavelength selection. As PABR is searching for an optical path, paths with an unacceptable signal quality due to linear impairments are pruned. In other words, PABR is LORA with an additional quality constraint.Note that PABR can only consider linear impairments. The nonlinear impairments, on the other hand, would not be possible to estimate in a distributed environment due to their requirement of global traffic knowledge.
PABR also considers signal quality when making the wavelength selection. It accomplishes this by removing from consideration all wavelengths with an unacceptable signal quality level. The approach is called Quality First Fit and it is discussed in the following section.
It should also be noted that both LORA and PABR can be implemented with either single-probing or multi-probing. The maximum number of probes
is denoted as LORA- or PABR-. With single-probing, only one path is selected by the route selection. With multi-probing, multiple paths are attempted in parallel, increasing the probability of connection success.Other routing approaches
IA-BF - The Impairment Aware Best Fit (IA-BF) algorithm was proposed in . This algorithm is a distributed approach that is dependent upon a large amount of communication to use global information to always pick the shortest available path and wavelength. This is accomplished through the use of serial multi-probing. The shortest available path and wavelength are attempted first, and upon failure, the second shortest available path and wavelength are attempted. This process continues until a successful path and wavelength have been found or all wavelengths have been attempted.The multi-probing approach will allow IA-BF to outperform both PABR-1 and LORA-1. However, as the number of probes increases, the performance of the algorithms is similar.
IA-FF - Impairment Aware First Fit (IA-FF) is a simple extension
Simple extension
In mathematics, more specifically in field theory, a simple extension is a field extension which is generated by the adjunction of a single element...
of IA-BF. Instead of picking the wavelengths in terms of the minimum cost, the wavelengths are selected in order according to their index. IA-BF tends to outperform IA-FF under most scenarios.
AQoS - Adaptive Quality of Service (AQoS) was proposed in . This algorithm is unique in a couple of ways. First, each node maintains two counters:
and . The purpose of each counter is to determine which issue is a bigger factor in blocking: Path and wavelength availability or Quality requirements. The algorithm chooses routes differently based upon the larger issue.Another distinction is that AQoS uses the Q-factor
Q factor
In physics and engineering the quality factor or Q factor is a dimensionless parameter that describes how under-damped an oscillator or resonator is, or equivalently, characterizes a resonator's bandwidth relative to its center frequency....
as the link cost. The cost of the
link is calculated by this formula where is the number of lightpaths on the link, and are the quality factor measurements of the lightpath at the source and destination nodes of the link, respectively. The repeated quality factor estimations are computationally very expensive.This algorithm is single probing approach. The multi-probing approach, which the paper names ALT-AQoS (alternate AQoS) is a simple extension upon the same basic idea.
Wavelength assignment
Two of the most common methods for wavelength assignment are First Fit and Random Fit. First Fit chooses the available wavelength with the lowest index. Random Fit determines which wavelengths are available and then chooses randomly amongst them. The complexity of both algorithms is, where is the number of wavelengths. First Fit outperforms Random Fit.An extension to First Fit and Random Fit was proposed in to consider signal quality. Quality First Fit and Quality Random Fit eliminate from consideration wavelengths which have an unacceptable signal quality. The complexity of these algorithms is higher though, as up to
calls to estimate the Q-factor are required.There are several other wavelength assignment algorithms: Least Used, Most Used, Min Product, Least Loaded, Max Sum , and Relative Capacity Loss . Most Used outperforms Least Used use significantly, and slightly outperforms First Fit. Min Product, Least Loaded, Max Sum, and Relative Capacity Loss all try to choose a wavelength that minimizes the probability that future requests will be blocked.
A significant disadvantage of these algorithms is that they require a significant communication overhead, making them unpractical to implement unless you have a centralized network structure.
Joint routing and wavelength assignment
An alternate approach to selecting a route and wavelength separately is to consider them jointly. These approaches tend to more theoretical and not very practical. As this is a NP-complete problem, any exact solution is likely not be possible. The approximation techniques usually aren't very useful either, as they will require centralized control and, usually, predefined traffic demands. Two joint approaches are ILP formulation and Island HoppingIsland hopping
Island hopping is a term that refers to the means of crossing an ocean by a series of shorter journeys between islands, as opposed to a single journey directly across the ocean to the destination.- Forms :...
.
The ILP formulation listed above can be solved using a traditional ILP solver. This is typically done by temporarily relaxing the integer constraints, solving the problem optimally, and converting the real solution to an integer solution. Additional constraints can be added and the process repeated indefinitely using a branch and bound
Branch and bound
Branch and bound is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization...
approach.