An example where the volume of traffic to be carried by each demand, is an algorithm output.
Network design - Algorithms
| Example name | Description |
|---|---|
| FBA_maxAlphaFairness.java | 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 |
| FBA_projectedGradient.java | 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 |
