Brief description
Given a network topology, the capacities in the links and the offered traffic, this algorithm obtains the traffic routing that minimizes the average network delay T, estimated according to the formula: \( T = \frac{1}{\sum_d h_d} \sum_e y_e T_e \), where \( h_d \) is the offered traffic by demand \( d \) (in bps), and \( T_e \) is the average link delay estimated for link \( e \), given by \( d_e + \frac{L}{u_e - y_e} \). For each link \( e \), \( d_e \) is the propagation delay, \( y_e \) is the average traffic in the link and \( u_e \) is the link capacity (both in bps). \(L\) is the average packet length in bits.
Algorithm description table
| Algorithm inputs | Requires a topology (nodes and links) and a demand set within the netPlan object. Net2Plan-wide options used:
Algorithm parameters:
|
|---|---|
| Algorithm outputs | The routes are added to netPlan object. No protection segments/routes are defined. Any previous routes are removed. |
| Required libraries | JOM library for solving the optimization problem |
| Keywords | Convex formulation, Flow assignment (FA), JOM |
| Authors | Pablo Pavón Mariño, José Luis Izquierdo Zaragoza |
| Date | March 2013 |
| Code | FA_minAvNetDelay_xde.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), and \( d_e \) is the propagation delay (in seconds). For each node \( n \in N \), \( \delta^+(n) \) and \( \delta^-(n) \) denote the set of links outgoing and incoming node \( n \), respectively.
- \(L\): Average packet length in bits.
Find:
- \( x_{de} , d \in D, e \in E \): Fraction \( \in [ 0 , 1 ] \) of the traffic of demand \( d \) that traverses link \( e \).
- \( y_e, e\in E \): Carried traffic per link (in the same units as the offered traffic).
\(
\text{minimize } \left( \sum_{e\in E} y_e \cdot [d_e + \frac{L}{u_e - y_e}]\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_d h_d x_{de} = y_e \quad \forall e \in E \\
y_e <= u_e \quad \forall e \in E \\
0 \leq x_{de} \leq 1 \quad \forall d \in D, e \in E \\
0 \leq y_{e} \quad \forall e \in E \\
\)
