Example: 'Maximum idle bottleneck capacity routing, flow-link formulation, and link-disjoint backup path protection'

Brief description

Given a network topology, the capacities in the links and the offered traffic, this algorithm obtains a link-disjoint or a SRG-disjoint (depending on user's choice) primary and backup path for the traffic of each demand, that minimizes the network congestion, with the constraint of non-bifurcated routing. For that it solves an ILP flow-link formulation (more complex in the SRG-disjoint case). In this algorithm, congestion is minimized by maximizing the idle link capacity in the bottleneck (the link with less idle capacity).

Algorithm description table

Algorithm inputs

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

Algorithm parameters:

  • solverName: The solver name to be used by JOM. Default: "glpk"
  • solverLibraryName: The solver library full or relative path, to be used by JOM. Leave blank to use JOM default. Default: blank
  • type11: Type of 1:1 protection: linkDisjopint or srgDisjoint. Formulations are somewhat different for both (SRG-disjoint is more complex). Default linkDisjoint.
Algorithm outputsThe routes are added to netPlan object and one link-disjoint protection path per route is defined. Any previous routes are removed.
Required librariesJOM library for solving the optimization problem
KeywordsFlow assignment (FA), JOM, MILP formulation, Protection algorithm
AuthorsPablo Pavón Mariño, José Luis Izquierdo Zaragoza
DateMarch 2013
CodeFA_maxBottleneckIdleCapacity_xde_11pathProtection.java

Detailed description

Link-disjoint version

The algorithm solves the following formulation:

Given:

  • \( D \): The set of demands comprising the offered traffic. For each demand \( d \in D \), \( h_d \) is the demand volume, and \( a(d) \) and \( b(d) \) denote the input and output node of the demand.
  • \( G(N,E) \): The network topology, where \( N \) is the set of nodes, and \( E \) the set of unidirectional network links. For each link \( e \in E \), \( a(e) \) and \( b(e) \) denote its input and output nodes, \( u_e \) the link capacity (in the same units as the offered traffic). For each node \( n \in N \), \( \delta^+(n) \) and \( \delta^-(n) \) denote the set of links outgoing and incoming node \( n \), respectively.

Find:

  • \( x_{de} , d \in D, e \in E \): Binary variables indicating whether or not traffic of demand \( d \) traverses link \( e \) in the primary path.
  • \( xx_{de} , d \in D, e \in E \): Binary variables indicating whether or not traffic of demand \( d \) traverses link \( e \) in the backup path.
  • \( \bar u \): Idle capacity in the bottleneck link.

\( \text{maximize } \left( \bar u \right) \text{ subject to: } \\
\sum_{e \in \delta^+(n)} x_{de} - \sum_{e \in \delta^-(n)} x_{de} = \begin{cases} 1, &\text{if $n = a(d)$} \\ -1, &\text{if $n = b(d)$} \\ 0, &\text{otherwise} \end{cases} \quad \forall n \in N, d \in D \\ \sum_{e \in \delta^+(n)} xx_{de} - \sum_{e \in \delta^-(n)} xx_{de} = \begin{cases} 1, &\text{if $n = a(d)$} \\ -1, &\text{if $n = b(d)$} \\ 0, &\text{otherwise} \end{cases} \quad \forall n \in N, d \in D \\ \sum_d h_d (x_{de} + xx_{de}) \leq u_e - \bar u \quad \forall e \in E \\ x_{de} + xx_{de} \leq 1 \quad \forall d \in D, e \in E \\ x_{de}, xx_{de} \in \lbrace 0 , 1 \rbrace \quad \forall d \in D, e \in E\\ \)

SRG-disjoint version

The algorithm solves the following formulation:

Given:

  • \( D \): The set of demands comprising the offered traffic. For each demand \( d \in D \), \( h_d \) is the demand volume, and \( a(d) \) and \( b(d) \) denote the input and output node of the demand.
  • \( G(N,E) \): The network topology, where \( N \) is the set of nodes, and \( E \) the set of unidirectional network links. For each link \( e \in E \), \( a(e) \) and \( b(e) \) denote its input and output nodes, \( u_e \) the link capacity (in the same units as the offered traffic). For each node \( n \in N \), \( \delta^+(n) \) and \( \delta^-(n) \) denote the set of links outgoing and incoming node \( n \), respectively.
  • \( S \): Set of shared-risk groups. \( E_{s} \) denotes the set of links affected by a failure in SRG \( s \in S \)

Find:

  • \( x_{de} , d \in D, e \in E \): Binary variables indicating whether or not traffic of demand \( d \) traverses link \( e \) in the primary path.
  • \( xx_{de} , d \in D, e \in E \): Binary variables indicating whether or not traffic of demand \( d \) traverses link \( e \) in the backup path.
  • \( x_{ds} , d \in D, s \in S \): Binary variables indicating whether or not traffic of demand \( d \) traverses SRG \( s \) in the primary path.
  • \( xx_{ds} , d \in D, s \in S \): Binary variables indicating whether or not traffic of demand \( d \) traverses SRG \( s \) in the backup path.
  • \( \bar u \): Idle capacity in the bottleneck link.

\( \text{maximize } \left( \bar u \right) \text{ subject to: } \\
\sum_{e \in \delta^+(n)} x_{de} - \sum_{e \in \delta^-(n)} x_{de} = \begin{cases} 1, &\text{if $n = a(d)$} \\ -1, &\text{if $n = b(d)$} \\ 0, &\text{otherwise} \end{cases} \quad \forall n \in N, d \in D \\ \sum_{e \in \delta^+(n)} xx_{de} - \sum_{e \in \delta^-(n)} xx_{de} = \begin{cases} 1, &\text{if $n = a(d)$} \\ -1, &\text{if $n = b(d)$} \\ 0, &\text{otherwise} \end{cases} \quad \forall n \in N, d \in D \\ \sum_d h_d (x_{de} + xx_{de}) \leq u_e - \bar u \quad \forall e \in E \\ |E| \cdot x_{ds} \geq \sum_{e \in E_{s}} x_{de} \quad \forall d \in D, s \in S \\ |E| \cdot xx_{ds} \geq \sum_{e \in E_{s}} xx_{de} \quad \forall d \in D, s \in S \\ x_{ds} + xx_{ds} \leq 1 \quad \forall d \in D, se \in S \\ x_{de}, xx_{de} \in \lbrace 0 , 1 \rbrace \quad \forall d \in D, e \in E\\ x_{ds}, xx_{ds} \in \lbrace 0 , 1 \rbrace \quad \forall d \in D, s \in S\\ \)