Examples involving 'Convex formulation'

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

Keywords: Capacity assignment (CA), Convex formulation, JOM

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 \) ).

Minimum average network blocking probability routing, flow-link formulation

Keywords: Convex formulation, Flow assignment (FA), JOM

Given a network topology, the capacities in the links and the offered traffic, this algorithm obtains the traffic routing that minimizes the average network blocking \(B\), estimated according to the formula: \(B = \frac{1}{\sum_d h_d} \sum_e y_e B_e\), where \( h_d \) is the traffic offered by demand \( d \) (in Erlangs), and \(B_e\) is the Erlang-B blocking for link \(e\), assuming that the offered traffic in the link \( y_e \) is all the traffic routed to \( e \) (traffic does not shrink because of the blockings in the rest of the links)

Minimum average network delay routing, flow-link formulation

Keywords: Convex formulation, Flow assignment (FA), JOM

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.

Solve the Network Utility Maximization (NUM) problem

Keywords: Bandwidth assignment (BA), Convex formulation, Flow assignment (FA), JOM

Given a network topology and the capacities in the links, this algorithm creates one demand of traffic for each input-output node pair, routes the traffic of each demand through the shortest path in number of hops, and obtains the offered traffic for each demand (that is, assigns bandwidth) to each demand, so that global assignment is \(\alpha\)-fair, with the constraint that no network link is over-congested.

According to the Mo & Walrand paper (see reference below), the \(\alpha\)-fairness assignment is obtained by solving the NUM model (Network Utility Maximization) where the utility of a demand \(d\) which is assigned a bandwidth \(h_d\) is given by: \((r^{(1-\alpha)} / (1-\alpha))\), and the target is to maximize the sum of the utilities in all the demands in the network.

Reference: J. Mo, J. Walrand, "Fair end-to-end window-based congestion control," IEEE/ACM Transactions on Networking, vol. 8, no. 5, pp. 556–567, October 2000