Examples involving 'Projected gradient/subgradient algorithm'

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

Keywords: Bandwidth assignment (BA), Projected gradient/subgradient algorithm

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