Routing and wavelength assignment

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 Algorithm. 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: ${\displaystyle O(m+n\log n)}$, where ${\displaystyle m}$ is the number of edges and ${\displaystyle n}$ 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.

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-${\displaystyle p}$ (Shortest Path, ${\displaystyle p}$ Probes, ${\displaystyle p>1}$) algorithm is an example of Fixed Alternate Routing. This algorithm calculates the ${\displaystyle p}$ shortest paths using the number of optical routers as the cost function. The running time using Yen's algorithm[4] is ${\displaystyle O(pn(m+n\log n))}$ where ${\displaystyle m}$ is the number of edges, ${\displaystyle n}$ is the number of routers, and ${\displaystyle p}$ is the number of paths. The running time is a constant factor if the paths are precomputed.

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.

The lexicographical routing algorithm (LORA) algorithm was proposed in.[5] 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 ${\displaystyle cost(l)=\beta ^{usage(l)}}$ where ${\displaystyle \beta }$ is parameter that can be dynamically adjusted according to the traffic load and ${\displaystyle usage(l)}$ is the number of wavelengths in use on link ${\displaystyle l}$. 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 ${\displaystyle \beta }$ is equal to one, the LORA algorithm is identical to the SP algorithm. Increasing the value of ${\displaystyle \beta }$ will increase the bias towards less used routes. The optimal value of ${\displaystyle \beta }$ can be calculated using the well-known hill climbing algorithm. The optimal values of ${\displaystyle \beta }$ were between 1.1 and 1.2 in the proposal.

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.

Both LORA and PABR can be implemented with either single-probing or multi-probing. The maximum number of probes ${\displaystyle p}$ is denoted as LORA-${\displaystyle p}$ or PABR-${\displaystyle p}$. 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.

IA-BF - The Impairment Aware Best Fit (IA-BF) algorithm was proposed in.[6] 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 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.[7] This algorithm is unique in a couple of ways. First, each node maintains two counters: ${\displaystyle N_{BER}}$ and ${\displaystyle N_{wave}}$. 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 ${\displaystyle i_{th}}$ link is calculated by this formula ${\displaystyle D_{i}={\frac {\sum _{j=1}^{N_{i}}10\log[Q_{i,j}^{(s)}/Q_{i,j}^{(d)}]}{N_{i}}}}$ where ${\displaystyle N_{i}}$ is the number of lightpaths on the ${\displaystyle i_{th}}$ link, ${\displaystyle Q_{i,j}^{(s)}}$ and ${\displaystyle Q_{i,j}^{(d)}}$ are the quality factor measurements of the ${\displaystyle j_{th}}$ lightpath at the source and destination nodes of the ${\displaystyle i_{th}}$ 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.

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 ${\displaystyle O(w)}$, where ${\displaystyle w}$ is the number of wavelengths. First Fit outperforms Random Fit.

An extension to First Fit and Random Fit was proposed in [5] 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 ${\displaystyle w}$ 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,[8] and Relative Capacity Loss.[9] 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.