This is a repository to store several topologies and a script to generate the instances for the NP-complete problem called Routing and Spectrum Allocation problem.
The Routing and Spectrum Assignment problem (RSA) consists in establishing the lightpaths for a set of end-to-end traffic demands that are expressed in terms of the number of required slots. Since lightpaths are determined by a route and a selected channel, RSA involves finding a route and assigning frequency slots to each demand. To comply with the ITU recommendation, the following constraints must to be respected in this setting:
- slot continuity: the slots assigned to a certain demand must remain the same on all the links of the corresponding route;
- slot contiguity: the slots allocated to each demand must be contiguous;
- non-overlapping slot: a slot can be assigned to various demands if the routes assigned to these demands do not share any link.
Given a directed graph G = (V, E) representing the optical fiber network, a set of demands D = {(s1, t1, v1), ..., (sk, tk, vk)} --such that each demand i in {1, ..., k} has a source si in V, a target ti in V, and a volume vi (positive integer) -- and a fixed number s* (positive integer) of available slots, RSA consists in establishing a lightpath associated to each demand, in such a way that lightpaths do not overlap. In other words, each demand i in {1, ..., k} must be assigned a path Pi beloging to E in G between si and ti and an interval Ii consisting of vi consecutive slots in [1, s*] in such a way that if the intersection of Pi with Pj is not empty then the intersetion of Ii with Ij must, for any two demands i not equal to j (i.e., if the paths assigned to i and j share an arc, then the assigned slot intervals must be disjoint).
Twelve integer linear programming models to solve this version of RSA can be found in [1], and a branch-and-cut algorithm using several families of valid equalities, inequalities and optimality cuts can be found in [2].
Since RSA is a problem that appears on the optical fiber networks, we selected 20 topologies used in the literature to solve several communication problems, most of them being real optical fiber networks. Their parameters are summarized in the following table:
| Topology | Nodes | Arcs | Δ | min_v ∈ VΔ(v)_ | max_v∈ V Δ(v)_ |
|---|---|---|---|---|---|
| 6n-9m-n6s9 | 6 | 18 | 0.60 | 4 | 8 |
| 10n-42m-SmallNet | 10 | 42 | 0.47 | 4 | 12 |
| 10n-44m-SmallNet | 10 | 44 | 0.49 | 6 | 12 |
| 11n-52m-COST239 | 11 | 52 | 0.47 | 8 | 12 |
| 14n-42m-NSF | 14 | 42 | 0.23 | 4 | 8 |
| 14n-46m-DT | 14 | 46 | 0.25 | 4 | 12 |
| 15n-46m-NSF | 15 | 46 | 0.22 | 4 | 8 |
| 16n-46m-EURO | 16 | 46 | 0.19 | 4 | 8 |
| 19n-76m-EON19 | 19 | 76 | 0.22 | 4 | 12 |
| 20n-62m-ARPANet | 20 | 62 | 0.16 | 6 | 8 |
| 20n-78m-EON20 | 20 | 78 | 0.21 | 4 | 14 |
| 21n-70m-Spain | 21 | 70 | 0.17 | 4 | 8 |
| 21n-72m-Italian | 21 | 72 | 0.17 | 4 | 12 |
| 21n-78m-UKNet | 21 | 78 | 0.19 | 4 | 14 |
| 22n-70m-BT | 22 | 70 | 0.15 | 6 | 8 |
| 24n-86m-UBN24 | 24 | 86 | 0.16 | 4 | 10 |
| 28n-68m-EON | 28 | 68 | 0.09 | 4 | 8 |
| 28n-82m-EURO28 | 28 | 82 | 0.11 | 4 | 10 |
| 30n-112m-Spain | 30 | 112 | 0.13 | 6 | 10 |
| 43n-176m-Euro | 43 | 176 | 0.10 | 4 | 12 |
A particularity of this type of network is that most of them are representable by strongly connected planar graphs. This fact makes sense if we think that such a structure is more fault tolerant.
In order to get an instance for RSA, besides the topology, we must define the maximum amount of available slots per arc and the set of demands, given as the number of slots that each demand needs, as well as their sources and destinations. From the literature we obtained some real data used when the RSA problem is studied:
- The slot bandwith, in most of the cases, is 12.5 GHz according to the ITU recommendation. However it could be smaller (sometimes 6.5 GHz) or larger (25 Ghz), but not much larger, due to the fact that for RWA with WDM, the minimum bandwidth of the wavelenght is 50 GHz, and the main objective of RSA is to improve granularity.
- The bandwidth of the optical fiber used on average is 4800 GHz, (although the theoretical maximum bandwidth of the optical fiber is around 231 THz).
- We can have up to 3200 slots in a 5THz spectrum using 6.25 GHz slots.
- The arc capacity s* is normaly fixed in range [170, 320].
- The amount of demands |D| is normaly in the range [10,100] except for some outliers that use 552, or even a thousand. But these large values are used for heuristic experimentations.
- The volume needed by each demand d ∈ D usually belongs to the range [1,20], but it depends on the value of s*. \end{itemize}
The generator uses two different definitions to the term density, namely,
- Arcs-density: amount of links of the topology over a complete graph.
- Demands-Density: Relation between the maximum volume required by the demands and the arc capacity, i.e., s*.
To calculate the arcs-density for each topology, we interpret it as a directed graph G = (V, E), which is the natural way, even though there are several works that assume symmetrical demands using the same spectrum, thus simplifying the number of edges in half by using undirected graphs.
The arcs-density of a graph G, called as Δ(G), then is calculated as
Let i be an instance for RSA and let Di, s*i and vi : D → ℕ be the demands set, the arcs capacity and the function that receives a demand and returns its volume, respectively. We define
as the maximum volume required by all the demands for a given instance i. In order to generate each instance, the script, in addition to s* and the topology G=(V,E), receives a real parameter p ∈ (0,1] used to calculate
in such a way that each demand uses a random number in
and an optional factor F to limit the number of demands, namely,
with Δ(G) the arc-density of the graph G and F = 1 by default.
The source and destination of each demand is randomly selected taking two nodes of the graph. We allow multiple demands for the same pair source destination depending on a parameter passed by the user.
In this section we present the characteristics of the software developed as well as the way to execute it, its scripts, directories, parameters and its input and output files.
The main scrip called instances_generator.py reads the topologies stored in the topologies/ directory and generates a serie of instances files for the RSA for each topology based on the data of the literature. It depends on the modulation level the optical fiber used, the graph density among other paramters.
The format of the data is commented in the header of each file. The separator used is the tabulation, and the line starting with # is a comment.
The topology file is preceded by the number of nodes and the number of edges followed by the list of these one by line.
# Comment
|N| |M|
<node i> <node j>
<node k> <node l>
...
Most of the instances belong to capacitated networks and we were able to obtain that data. In those cases, the weight of each edge is added when it is defined.
<node i> <node j> <weight ij>
As well as the problem is stated over directed graphs and due to the way in which the networks are made we asume all the links have both senses.
The instance file also begins with a header that briefly explains the format. The version of this software and the used seed are shown there. The number of slots available for each edge and the number of demands requested are shown below followed by the list of demands.
# Comment
s* |D|
<src d1> <dst d1> <n of slots required by d1>
<src d2> <dst d2> <n of slots required by d1>
...
The requirements are stored in requirements.txt. They can be installed via
pip install -r requirements.txt
To generate the instances just run the script:
python instances_generator.py
By default the instances are going to be placed on a new folder called instances into the directory of the script into subfolders according to the maximum percent of slots used by demands and the topology. Each one of those files with its asociated topology are the input for the RSA problem.
Run the following to see how to configure the parameters:
python instances_generator.py -h
optional arguments:
-h, --help show this help message and exit
-mdir MDIR The main directory or path. If no tdir or idir parameters are used, mdir must contain the 'topologies' and/or 'instances' folder. The
default value is the location of this script
-tdir TDIR The topologies directory or path.
-idir IDIR The directory or path for the created instances.
-s SEED, --seed SEED The random seed. Default is 1988.
-S SLOTS [SLOTS ...], --slots SLOTS [SLOTS ...]
List of amounts of available slots.
-p PERCENTS [PERCENTS ...], --percents PERCENTS [PERCENTS ...]
List of maximum percentage of total available slots that a demand can use. Must be in (0, 1].
-d DENSITY, --density DENSITY
Density factor. The maximum amount of demands is multiplied by this factor. Default is 1.0
-m, --multiple If set, multiple demands between a source and a destination are allowed.
The following line will generate instances for S in [10, 25] and p in [10%, 20%, 30%, 50%]. They will be saved in ./instances/.
python instances_generator.py -S 10 25 -p .1 .3 .5 .2
This one will generate instances with S in [10, 15, 20, 30, 40, 60, 80, 100, 150, 200, 300, 400, 600, 800, 1000] and p in [10%, 20%, 30%, ..., 90%] in the directory /home/instances, allowing multiple demands between each pair (src, dst).
python instances_generator.py -idir /home/instances -m
[1] Bertero, F., M. Bianchetti, and J. Marenco, Integer programming models for the routing and spectrum allocation problem, TOP 26 (2018), 465–488.
[2] Bianchetti M. and J. Marenco, Valid inequalities and a branch-and-cut algorithm for the Routing and Spectrum Allocation problem, Procedia Computer Science 195 (2021), 523-531.
[3] Bianchetti M. and J. Marenco, A branch-and-cut algorithm for the routing and spectrum allocation problem, Discrete Applied Mathematics 339 (2023), 107-126.
[4] Bianchetti M. Un algoritmo branch-and-cut para el routing and spectrum allocation problem, PhD Thesis, University of Buenos Aires, Argentina (2023).