Example: 'Assign routes and a proportionally fair bandwidth to each demand, using a distributed algorithm based on projected gradient'

Brief description

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 km or in number of hops, and obtains the offered traffic for each demand (that is, assigns bandwidth to each demand), using a projected gradient algorithm, that permits a distributed implementation (per demand). The optimization problem to solve is: min sum_e F_e - sum_d log h_d, subject to h_d >= h^{min} e is the index for the links, d the index for the demands. The h^{min} value is set to the minimum link capacity divided by the number of demands. Then, it is guaranteed that if all the demands are set to this value, the resulting traffic does not oversubscribe any link. This means: h^{min} = min_e u_e / |D|, where u_e are the link capacities. The F_e functions are F_e = M_e / (u_e-y_e), if link utilization is below 99% and its linear projection if not. M_e is set so that if the link utilization is 99%, any demand traversing the link will have a gradient coordinate which makes it reduce its rate h_d. We use M_e = u_e^2 / (h^{min} 1E4) According to [1], the logarithmic functions tend to enforce a bandwidth distribution that approximates (not exactly, given the noise added by F_e penalizations) the proportionally-fair bandwidth sharing. The algorithm permits testing several projected gradient flavors: constant step, 1/k diminishing rule, w/o diagonal scaling. In this latter case, each demand multiplies its movement by the inverse of the associated diagonal value in the hessian matrix. [1] 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

Algorithm description table

Algorithm inputs

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

Algorithm parameters:

  • maxNumIterations: Maximum number of iterations. Default: 1000
  • shortestPathType: Each demand is routed according to the shortest path according to this type. Can be 'km' or 'hops'. Default: "km"
  • beta: Constant factor multiplying the gradient in each iteration. Default: 1
  • diminishingSteps: If 'yes', the steps at iteration k is multipled by 1/k. Default: "no"
  • diagonalScaling: If 'yes', the steps for demand d is multiplied by 1/h_dd, being h_dd the second partial derivative respect to h_d. Default: "no"
Algorithm outputsA new demand from each node to each other and corresponding routes are added to netPlan object. No protection segments/routes are defined. Any previous demands, routes and protection segments are removed.
Required librariesNone
KeywordsBandwidth assignment (BA), Projected gradient/subgradient algorithm
AuthorsPablo Pavón Mariño, José Luis Izquierdo Zaragoza
DateApril 2014
CodeFBA_projectedGradient.java