Net2Plan

Example: Capacity assignment minimizing network delay, with linear cost constraints

ca_minAvNetDelayLinearCost

This algorithm obtains the capacity assignment that minimizes the average network delay T in the network, so that the network cost is limited to a maximum budget C_{max}.

Average network delay considers the queueing delay and the transmission delay. Propagation delay is not included since it is not affected by the link capacities. Average network delay T is estimated as:

 T =  frac{L}{sum_d h_d} sum_e frac{rho_e}{1 - rho_e}

Where:

  • h_d is the offered traffic in bps of demand d

  • L: is the average packet length in bits

  • rho_e: is the utilization of link e

The network cost C is the sum of the costs of the links C_e, where the cost in a link grows in a linear form respect to capacities:

 C = sum_e C_e
 C_e = (alpha + d_e beta ) u_e

Where:

  • alpha, beta: are cost factors, input parameters to the problem.

  • d_e: is the length in km of link e

  • u_e: is the link capacity in Erlangs

The algorithm solves the following formulation:

Decision variables:

  • lbrace rho_e, e in E rbrace: Utilization in the links

 min sum_e frac{rho_e}{1 - rho_e}
 sum_e (alpha + d_e beta ) y_e frac{1}{rho_e} leq C_{max}
 rho_e geq 0 quad forall e in E
 rho_e leq 1 quad forall e in E

The previous formulation is a convex program respect to the rho_e variables, and is solved using CVX. The algorithm requires CVX solver installed and running.

Download .m file: ca_minAvNetDelayLinearCost.m