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 number of hops, between the demand end nodes. k is a user-defined parameter. The fraction of the demand volume that is carried by a path that carries traffic, is constrained to be higher or equal than a user-defined parameter tMin. That is, a path ( p \) can carry no traffic, or an amount of traffic equal or greater than \( tMin \cdot h_{d(p)}\), where \( d(p) \) is the demand associated to path \( p \). Finally, the user-defined parameter BIFMAX sets the maximum number of paths of a demand that can carry traffic.
Algorithm description table
| Algorithm inputs | Requires a topology (nodes and links) and a demand set within the netPlan object. Algorithm parameters:
|
|---|---|
| Algorithm outputs | Routes are added to netPlan object. No protection segments are defined. Any previous routes are removed. |
| Required libraries | JOM library for solving the optimization problem |
| Keywords | Flow assignment (FA), JOM, MILP formulation |
| Authors | Pablo Pavón Mariño, José Luis Izquierdo Zaragoza |
| Date | May 2013 |
| Code | FA_minBottleneckUtilizationBifurcationConstraints_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 \).
- \( xx_{p}, p \in P \): Indicates whether or not path \( p \) carries traffic.
- \( \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 \\
\sum_{p \in P_{d}} xx_{p} <= BIFMAX \quad \forall d \in D \\
x_{p} \geq tMin\cdot xx_{p} \quad \forall p \in P \\
xx_{p} \in \lbrace 0 , 1 \rbrace \quad \forall p \in P
\)
