Example: 'Find link capacities which minimizes the average network delay under a given budget'

Brief description

Given a network topology, a known amount of traffic carried in each link, and an available budget, this algorithm computes the capacities in the links that minimize the average network delay (considering only queuing and transmission delays in the links, using the M/M/1 model), with the constraint that the cost does not exceeds the available budget. The total network cost is given by the sum of the costs of the links, where the cost in each link is given by \( u_e ^ \alpha \), being \( \alpha \) a positive parameter. If \( \alpha \) is between 0 and 1, the link cost function is concave respect to the capacities.

We solve the problem using a convex formulation, where the decision variables are the utilizations \( \rho_e \) in the links. Note that thanks to this change of variable, the problem is convex (in the variables \( \rho_e \) ) even if it was not originally convex (in the variables \( u_e \) ).

Algorithm description table

Algorithm inputs

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

Algorithm parameters:

  • alpha: Alpha factor for the cost function (greater than zero). Default: 1
  • C: Available budget. Default: 100
  • solverName: The solver name to be used by JOM. Default: "ipopt"
  • solverLibraryName: The solver library full or relative path, to be used by JOM. Leave blank to use JOM default. Default: blank
Algorithm outputsLink capacities updated within the netPlan object.
Required librariesJOM library for solving the optimization problem
KeywordsCapacity assignment (CA), Convex formulation, JOM
AuthorsPablo Pavón Mariño, José Luis Izquierdo Zaragoza
DateMarch 2013
CodeCA_minDelayConcaveCost.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.
  • \( y_{e} , e \in E \): Carried traffic per link (in the same units as the offered traffic).

Find:

  • \( \rho_e, e \in E \): Link utilizations. Then, link capacities are \(u_e = y_e / \rho_e\)

\( \text{minimize } \left( \sum_{e\in E}\frac{\rho_e}{1-\rho_e} \right) \text{ subject to: } \\
\sum_{e \in E} \left(\frac{y_e}{\rho_e}\right)^{\alpha} \leq C \quad \forall e \in E\\ 0 \leq \rho_e \leq 1 \quad \forall e \in E \)