Routing and wavelength assignment

Last updated

The routing and wavelength assignment (RWA) problem is an optical networking problem with the goal of maximizing the number of optical connections.

Contents

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

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 active, is a matrix which shows which links are active, 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. [2] 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. [3] 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:

First routing, then wavelength assignment

Routing algorithms

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 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: , 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.

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

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.

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. [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: 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.

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

Joint routing and wavelength assignment

An alternate approach to selecting a route and wavelength separately is to consider them jointly. These approaches tend to be more theoretical and not as practical. As this is an NP-complete problem, an exact solution is likely not 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 Hopping.

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.

In [10] the authors report on the algorithm which can be used to solve efficiently and optimally a constrained RWA problem. The authors study a constrained routing and spectrum assignment (RSA) problem, which can be reduced to a constrained RWA problem by requesting one slice. The constriction limits the path length.

In [11] the authors report on the generalized Dijkstra algorithm, which can be used to efficiently and optimally solve the RWA, RSA, and the routing, modulation, and spectrum assignment (RMSA) problems, without the limit on the path length.

Related Research Articles

<span class="mw-page-title-main">Travelling salesman problem</span> NP-hard problem in combinatorial optimization

The travelling salesman problem, also known as the travelling salesperson problem (TSP), asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.

<span class="mw-page-title-main">Shortest path problem</span> Computational problem of graph theory

In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized.

<span class="mw-page-title-main">Dijkstra's algorithm</span> Algorithm for finding shortest paths

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

<span class="mw-page-title-main">Breadth-first search</span> Algorithm to search the nodes of a graph

Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory, usually a queue, is needed to keep track of the child nodes that were encountered but not yet explored.

<span class="mw-page-title-main">Dynamic programming</span> Problem optimization method

Dynamic programming is both a mathematical optimization method and an algorithmic paradigm. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.

<span class="mw-page-title-main">Bellman–Ford algorithm</span> Algorithm for finding the shortest paths in graphs

The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers. The algorithm was first proposed by Alfonso Shimbel, but is instead named after Richard Bellman and Lester Ford Jr., who published it in 1958 and 1956, respectively. Edward F. Moore also published a variation of the algorithm in 1959, and for this reason it is also sometimes called the Bellman–Ford–Moore algorithm.

In computer science, the Floyd–Warshall algorithm is an algorithm for finding shortest paths in a directed weighted graph with positive or negative edge weights. A single execution of the algorithm will find the lengths of shortest paths between all pairs of vertices. Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm. Versions of the algorithm can also be used for finding the transitive closure of a relation , or widest paths between all pairs of vertices in a weighted graph.

<span class="mw-page-title-main">Ant colony optimization algorithms</span> Optimization algorithm

In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. Artificial ants stand for multi-agent methods inspired by the behavior of real ants. The pheromone-based communication of biological ants is often the predominant paradigm used. Combinations of artificial ants and local search algorithms have become a method of choice for numerous optimization tasks involving some sort of graph, e.g., vehicle routing and internet routing.

In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge (u,v) from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. Precisely, a topological sort is a graph traversal in which each node v is visited only after all its dependencies are visited. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time. Topological sorting has many applications, especially in ranking problems such as feedback arc set. Topological sorting is possible even when the DAG has disconnected components.

Johnson's algorithm is a way to find the shortest paths between all pairs of vertices in an edge-weighted directed graph. It allows some of the edge weights to be negative numbers, but no negative-weight cycles may exist. It works by using the Bellman–Ford algorithm to compute a transformation of the input graph that removes all negative weights, allowing Dijkstra's algorithm to be used on the transformed graph. It is named after Donald B. Johnson, who first published the technique in 1977.

<span class="mw-page-title-main">Pathfinder network</span>

A method for pruning dense networks to highlight key links

<span class="mw-page-title-main">Optical add-drop multiplexer</span> Device used to route channels in optical communication systems

An optical add-drop multiplexer (OADM) is a device used in wavelength-division multiplexing (WDM) systems for multiplexing and routing different channels of light into or out of a single-mode fiber (SMF). This is a type of optical node, which is generally used for the formation and the construction of optical telecommunications networks. "Add" and "drop" here refer to the capability of the device to add one or more new wavelength channels to an existing multi-wavelength WDM signal, and/or to drop (remove) one or more channels, passing those signals to another network path. An OADM may be considered to be a specific type of optical cross-connect.

The multi-commodity flow problem is a network flow problem with multiple commodities between different source and sink nodes.

<span class="mw-page-title-main">Optical mesh network</span> Optical network using a mesh topology

An optical mesh network is a type of optical telecommunications network employing wired fiber-optic communication or wireless free-space optical communication in a mesh network architecture.

<span class="mw-page-title-main">Betweenness centrality</span> Measure of a graphs centrality, based on shortest paths

In graph theory, betweenness centrality is a measure of centrality in a graph based on shortest paths. For every pair of vertices in a connected graph, there exists at least one shortest path between the vertices such that either the number of edges that the path passes through or the sum of the weights of the edges is minimized. The betweenness centrality for each vertex is the number of these shortest paths that pass through the vertex.

The k shortest path routing problem is a generalization of the shortest path routing problem in a given network. It asks not only about a shortest path but also about next k−1 shortest paths. A variation of the problem is the loopless k shortest paths.

In graph theory, Yen's algorithm computes single-source K-shortest loopless paths for a graph with non-negative edge cost. The algorithm was published by Jin Y. Yen in 1971 and employs any shortest path algorithm to find the best path, then proceeds to find K − 1 deviations of the best path.

<span class="mw-page-title-main">Multicast lightpaths</span> Type of computer communication

A multicast session requires a "point-to-multipoint" connection from a source node to multiple destination nodes. The source node is known as the root. The destination nodes are known as leaves. In the modern era, it is important to protect multicast connections in an optical mesh network. Recently, multicast applications have gained popularity as they are important to protecting critical sessions against failures such as fiber cuts, hardware faults, and natural disasters.

Segment protection is a type of backup technique that can be used in most networks. It can be implemented as a dedicated backup or as a shared backup protection. Overlapping segments and non-overlapping segments are allowed; each providing different advantages.

In network theory, the Wiener connector is a means of maximizing efficiency in connecting specified "query vertices" in a network. Given a connected, undirected graph and a set of query vertices in a graph, the minimum Wiener connector is an induced subgraph that connects the query vertices and minimizes the sum of shortest path distances among all pairs of vertices in the subgraph. In combinatorial optimization, the minimum Wiener connector problem is the problem of finding the minimum Wiener connector. It can be thought of as a version of the classic Steiner tree problem, where instead of minimizing the size of the tree, the objective is to minimize the distances in the subgraph.

References

  1. H. Zang, J. Jue, and B. Mukherjee, "A Review of Routing and Wavelength Assignment Approaches for Wavelength Routed Optical WDM Networks," {\it Optical Networks Magazine}, January 2000.
  2. I. Chlamtac, A. Ganz, and G. Karmi, "Lightpath communications: an approach to high bandwidth optical WAN's," {\it IEEE Transactions on Communications}, Vol 40, No 7, pp. 1171-1182, July 1992.
  3. S. Evan, A. Itai, and A. Shamir, "On the Complexity of Timetable and Multicommodity Flow Problems," SIAM Journal on Computing, Vol 5, pp 691-703, 1976
  4. M. Pascoal and E. Martins. "A new implementation of Yen's ranking loopless paths algorithm." 4OR–Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 2003
  5. 1 2 W. Lin, "Physically Aware Agile Optical Networks," Ph.D. Dissertation, Montana State University, Bozeman, July 2008.
  6. Y. Huang, J. Heritage, and B. Mukherjee, "Connection Provisioning With Transmission Impairment Consideration in Optical WDM Networks With High-Speed Channels," Journal of Lightwave Technology, Vol 23, No 3, March 2005.
  7. T. Deng and S. Subramaniam, "Adaptive QoS Routing in Dynamic Wavelength-Routed Optical Networks," Broadband Networks 2005, pp. 184-193, 2005
  8. R. Barry and S. Subramaniam, "The MAX-SUM Wavelength Assignment Algorithm for WDM Ring Networks," Proceedings of Optical Fiber Conference, February 1997.
  9. X. Zhang and C. Qiao, "Wavelength Assignment for Dynamic Traffic in Multi-Fiber WDM Networks," Proceedings of International Conference on Communications, Vol 1, pp 406-410, June 1997.
  10. Ireneusz Szcześniak and Bożena Woźna-Szcześniak, "Adapted and Constrained Dijkstra for Elastic Optical Networks", Proceedings of the 20th Optical Network Design and Modeling Conference, Cartagena, Spain, May 2016
  11. Ireneusz Szcześniak, Andrzej Jajszczyk and Bożena Woźna-Szcześniak, "Generic Dijkstra for Optical Networks", October 2018