The routing and wavelength assignment (RWA) problem is an optical networking 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 link, 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:
C 0 ( ρ , q ) = ∑ i = 1 N s d m i {\displaystyle C_{0}(\rho ,q)=\sum _{i=1}^{N_{sd}}m_{i}}
subject to
m i ≥ 0 , i n t e g e r , i = 1 , 2 , . . . , N s d {\displaystyle m_{i}\geq 0,integer,i=1,2,...,N_{sd}}
c i j ∈ 0 , 1 , i = 1 , 2 , . . . , P , j = 1 , 2 , . . . , W {\displaystyle c_{ij}\in {0,1},i=1,2,...,P,j=1,2,...,W}
C T B ≤ l W × L {\displaystyle C^{T}B\leq l_{W\times L}}
m ≤ 1 W C T A {\displaystyle m\leq 1_{W}C^{T}A}
m i ≤ q i ρ , i = 1 , 2 , . . . , N s d {\displaystyle m_{i}\leq q_{i}\rho ,i=1,2,...,N_{sd}}
N s d {\displaystyle N_{sd}} is the number of source-destination pairs, while m i {\displaystyle m_{i}} is the number of connections established for each source-destination pair. L {\displaystyle L} is the number of links and W {\displaystyle W} is the number of wavelengths. P {\displaystyle P} is the set of paths to route connections. A : P × N s d {\displaystyle A:P\times N_{sd}} is a matrix which shows which source-destination pairs are active, B : P × L {\displaystyle B:P\times L} is a matrix which shows which links are active, and C : P × W {\displaystyle C:P\times W} 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 n {\displaystyle n} -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.
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 Routing. The second approach is to consider both route selection and wavelength assignment jointly.
First routing, then wavelength assignment
Routing algorithms
… excerpt ends here. Continue reading the full article.
