Example: 'Solve the routing and wavelength assignment problem assuming no wavelength conversion capabilities'

Brief description

Given a network topology of OADM optical nodes connected by WDM fiber links, and a traffic demand of lightpath requests, this algorithm optimally computes the RWA (Routing and Wavelength Assignment) that carries all the lightpaths minimizing the average propagation delay, solving an Integer Linear Program (ILP). Wavelength conversion is not allowed. Only those routes with a length below a user-defined threshold maxLightpathLengthInKm are accepted. All the channels are of the same binaryRatePerChannel_Gbps capacity. The offered traffic demand is supposed to be measured in Gbps, and is rounded up to a multiple of binaryRatePerChannel_Gbps.

Algorithm description table

Algorithm inputs

Requires a topology (nodes and links) and a demand set within the netPlan object.

Algorithm parameters:

  • binaryRatePerChannel_Gbps: Binary rate of all the lightpaths. Default: 1
  • K: Maximum number of admissible paths per demand. Default: 3
  • maxLightpathLengthInKm: Maximum allowed lightpath length in km. Default: 5000
  • numWavelengthsPerFiber: Number of wavelengths per link. Default: 40
  • solverName: The solver name to be used by JOM. Default: "cplex"
  • solverLibraryName: The solver library full or relative path, to be used by JOM. Leave blank to use JOM default. Default: blank
Algorithm outputsLink capacities and traffic routing updated within the netPlan object
Required librariesJOM library for solving the optimization problem
KeywordsCapacity assignment (CA), Flow assignment (FA), JOM, MILP formulation, WDM
AuthorsPablo Pavón Mariño, José Luis Izquierdo Zaragoza
DateMarch 2014
CodeCFA_WDM_basicRWA.java

Detailed description

The algorithm solves the following formulation:

Given:

  • \( G(N,E) \): The network topology, where \( N \) is the set of nodes, and \( E \) the set of unidirectional fibers, each of them providing \( w \in nW \) WDM channels.
  • \( D \): Set of lightpath demands.
  • \( P \): Set of candidate paths. Each path \( p \in P \) is assumed to have an associated length (in km) equal to \( l_{p} \). \( P_{e} \) and \( P_{d} \) represent the set of paths traversing fiber \( e \in E \) and carrying traffic of demand \( d \in D \), respectively.

Find:

  • \( x_{pw}, p \in P, w \in nW \): Binary variables indicating whether or not path \( p \) is active and using wavelength \( w \) for a lightpath.

\( \text{minimize } \left( \sum_{w \in nW}\sum_{p \in P} l_{p}\cdot x_{pw} \right) \text{ subject to: } \\
\sum_{w\in nW}\sum_{p \in P_{d}} x_{pw} = h_{d} \quad \forall d \in D\\ \sum_{p \in P_{e}} x_{pw} \leq 1 \quad \forall e \in E, w\in nW\\ x_{pw} \in \lbrace 0 , 1 \rbrace \quad \forall p \in P, w\in nW\\ \)