A Solver for the Wavelength Assignment Problem (RWA) in WDM networks
In optical networks, the Wavelength Divison Multiplexing (WDM) technology is used to increase the capacity of fibers to transmit information, by splitting a beam of light into different wavelengths, which travel simultaneously.
In an all-optical network, a wavelength can cross an optical switch without Optical-Electrical-Optical (OEO) conversion. While this is a step forward towards cheaper and "greener" networks, a trade-off is that there has to be an end-to-end "wavelength continuity": a wavelength stays the same from the source edge to the destination edge, and it cannot be used by different lightpaths on the same optical fiber.
The wavelength allocation problem consists in finding the minimum number of wavelengths that are required, and how to allocate them to lightpaths.
Swap is a solver for the Routing and Wavelength Assignment Problem (RWA).
Two methods were implemented to solve the wavelength assignment problem:
You can find a demo of Swap applied to the BBN Planet backbone in the USA:
Let's consider a situation with 5 optical switch in a line, and 5 traffic paths:
(image from Linear Programming and Algorithms for Communication Networks by Eiji Oki)
We will assign wavelength sequentially in increasing order of the traffic paths indices, and always choose the smallest available wavelength index.
We write the n-th wavelength Ln (lambda x), and the n-th path Pn.
With this naive strategy, 4 wavelengths are required. The resulting assignment is the following:
(image from Linear Programming and Algorithms for Communication Networks by Eiji Oki)
Another strategy consists in assigning wavelengths sequentially in decreasing order of the number of other paths with overlapping fibers:
Therefore, we assign wavelengths sequentially in the following order of paths: P3, P2, P5, P1, P4:
With this new strategy, 3 wavelengths are required. The resulting assignment is the following:
(image from Linear Programming and Algorithms for Communication Networks by Eiji Oki)
The number of wavelengths required depends on the order in which wavelengths are assigned to the traffic paths.
The Wavelength Assignment Problem aims at minimizing the number of wavelengths.
To solve the RWA, we consider that the traffic paths are known a priori, and that they all use the shortest distance path. This is called the Static Lightpath Establishment Routing and Wavelength Assignment problem (SLE RWA).
The SLE RWA is NP-complete, it can be reduced to a graph coloring problem with a simple graph transformation, as demonstrated below.
To solver the SLE RWA, we will go through the following steps:
We can reduce the Wavelength Assignment Problem to a graph coloring problem with a simple graph transformation:
Let's apply the graph transformation to our first example:
We obtain the following result:
The linear programming solution, while it always yields an optimal solution, is not scalable: it cannot be applied to large networks. The "Largest degree first" is a simple heuristic that assigns colors in decreasing order of vertex degree in the transformed graph:
git clone https://github.com/afourmy/swap.git
cd swap
pip install -r requirements.txt
(Windows) set FLASK_APP=app.py
(Unix) export FLASK_APP=app.py
flask run --host=0.0.0.0
docker run -d -p 5000:5000 --name swap --restart always afourmy/swap
Linear Programming and Algorithms for Communication Networks by Eiji Oki.
Leaflet: JavaScript library for mobile-friendly interactive maps.
Leaflet-polyline: A leaflet plugin to define patterns on Polylines.
Vis: A dynamic, browser based JavaScript visualization library.