Brief description
Given a network topology, the capacities in the links and the offered traffic, this algorithm obtains the destination-based traffic routing that minimizes the average number of hops. Destination-based routing means that the routing could be implemented i.e. in an IP network.
Algorithm description table
| Algorithm inputs | Requires a topology (nodes and links) and a demand set within the netPlan object. 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 | Destination-based routing, Flow assignment (FA), JOM, LP formulation |
| Authors | Pablo Pavón Mariño, José Luis Izquierdo Zaragoza |
| Date | March 2013 |
| Code | FA_minAvNumHops_xte.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 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.
- \( TM \): Traffic matrix, where each position \( (i,j) \) represents the traffic generated in node \( i \) targeted to node \( j \). \( H_d \) is equal to the sum of all values of \( TM \).
Find:
- \( x_{te} , t \in N, e \in E \): Fraction \( \in [ 0 , 1 ] \) of the traffic targeted to node \( t \) that arrives (or is generated in) node \( a(e) \) (the initial node of link \( e \)), that is forwarded through link \( e \).
\(
\text{minimize } \left( \frac{\sum_{t \in T} \sum_{e \in E} x_{te}}{H_d} \right) \text{ subject to: } \\
\sum_{e \in \delta^+(n)} x_{te} - \sum_{e \in \delta^-(n)} x_{te} = TM(n,t)
\quad \forall n \in N, t \in N \\
\sum_{t \in T} x_{te} \leq u_e - \bar u \quad \forall e \in E \\
x_{te} \geq 0 \quad \forall t \in N, e \in E
\)
