Skip to content

RSA Instances
Compare
Choose a tag to compare
@exactasmache exactasmache released this 13 Oct 02:17
· 7 commits to master since this release
v1.0
bb2df56

RSA instances

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.

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

Formally

Given a directed graph G=(V,E) representing the optical fiber network, a set of demands D = {(s_1, t_1, v_1), ..., (s_k, t_k, v_k)} --such that each demand i in {1, ..., k} has a source s_i in V, a target t_i in V, and a volume v_i (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 P_i beloging to E in G between s_i and t_i and an interval I_i consisting of v_i consecutive slots in [1,S] in such a way that if the intersection of P_i with P_j is not empty then the intersetion of I_i with I_j 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).

Parameters

From the literature we obtained the most used data for the RSA problem:

  • The slot bandwith most of the cases is 12.5 GHz. However it could be smaller (sometimes 5 GHz) or larger, but not much larger, due to the fact that for the RWA problem with WDM, the minimum bandwidth of the slot 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 use that information to define the available number of slots per link and the maximal amount of slots used by each demand. This is stored in the variables:

avaliable_S   &   max_slots_by_demand

To define the number of demands of each instance, we estimate an upper limit using the density of the graph, the number of slots per link and the average of slots per demand trying to make the majority of instances feasible, but not all.

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.

Data Format

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 got the data. In those cases the weight of each edge is added when 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 starts with a header explaining the format briefly. Then it has the amount of slots available for each edge and the number of the requested demands.

# Comment
S     |D|
<src d1>    <dst d1>      <n of slots required by d1>
<src d2>    <dst d2>      <n of slots required by d1>
...

Usage

To generate the instances just run the script:

python instances_generator.py

The instances are going to be placed on a new folder called instances into the main directory. Each one of those files with its asociated topology are the input for the RSA problem.

Assets 2
Loading