Example: 'Minimum bottleneck utilization routing, path formulation'

Brief description

Given a network topology, the capacities in the links and the offered traffic, this algorithm obtains the traffic routing that minimizes the worst link utilization using a flow-path formulation. For each demand, the set of admissible paths is composed of the ranking of (at most) k-shortest paths in km, between the demand end nodes. k is a user-defined parameter. Paths for which its propagation time sums more than maxPropDelayMs, a user-defined parameter, are considered not admissible. The routing may be constrained to be non-bifurcated setting the user-defined parameter nonBifurcated to true.

Algorithm description table

Algorithm inputs

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

Algorithm parameters:

  • k: Maximum number of admissible paths per demand. Default: 5
  • maxPropDelayMs: Maximum propagation delay in miliseconds allowed in a path. Default: 30
  • nonBifurcated: True if the routing is constrained to be non-bifurcated. Default: "false"
  • 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
Algorithm outputsRoutes are added to netPlan object. No protection segments are defined. Any previous routes are removed.
Required librariesJOM library for solving the optimization problem
KeywordsFlow assignment (FA), JOM, LP formulation, MILP formulation
AuthorsPablo Pavón Mariño, José Luis Izquierdo Zaragoza
DateMarch 2013
CodeFA_minBottleneckUtilization_xp.java

Detailed description

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.
  • \( P \): A list of candidate paths for each demand

Find:

  • \( x_{p} , p \in P \): Fraction \( \in [ 0 , 1 ] \) of the traffic of demand \( d \) that traverses path \( p \). If the routing is non-bifurcated, this variable is constrained to get integer numbers: \( x_{p} \in \lbrace 0 , 1 \rbrace \).
  • \( \rho \): Utilization in the bottleneck link.

\( \text{minimize } \left( \rho \right) \text{ subject to: } \\
\sum_{p \in P_{d}} x_{p} = 1 \quad \forall d \in D \\ \sum_{d\in D}h_{d} \sum_{p \in P_{e}\cap P_{d}} x_{p} \leq \rho\cdot u_{e} \quad \forall e \in E \\ 0 \leq x_{p} \leq 1 \quad \forall p \in P \\ x_{p} \in \lbrace 0 , 1 \rbrace \quad \forall p \in P \text{ (if routing is non-bifurcated) } \)