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 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
Algorithm description table
| Algorithm inputs | Requires a topology (nodes and links) within the netPlan object. Algorithm parameters:
|
|---|---|
| Algorithm outputs | A 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 libraries | JOM library for solving the optimization problem |
| Keywords | Bandwidth assignment (BA), Convex formulation, Flow assignment (FA), JOM |
| Authors | Pablo Pavón Mariño, José Luis Izquierdo Zaragoza |
| Date | March 2013 |
| Code | FBA_maxAlphaFairness.java |
Detailed description
This algorithm sets the routing as shortest path (in number of hops or link length in km). Then, creates a demand between every node pair with an offered traffic \(h_d\) calculated as follows:
Each demand has an utility function \(U_{\alpha}\) given by:
- \(U_{\alpha}(h_d) = h_d\), if \(\alpha\) = 0
- \(U_{\alpha}(h_d) = log(h_d)\), if \(\alpha\) = 1
- \(U_{\alpha}(h_d) = h_d^{(1-\alpha)}/(1-\alpha)\), otherwise
The decision variables \(h_d\) are the bandwidth granted to each demand \(d\). The network utility is the sum of the utilities of the demands. The objetive function is to maximize the network utility. It is known that a bandwidth sharing that maximizes network utility with utility function \(U_{\alpha}\), is a sharing that is \(\alpha\)-fair.
