Proportionally fair

For the resource allocation problem, see Proportional division.

Proportional fair is a compromise-based scheduling algorithm. It is based upon maintaining a balance between two competing interests: Trying to maximize total [wired/wireless network] throughput while at the same time allowing all users at least a minimal level of service. This is done by assigning each data flow a data rate or a scheduling priority (depending on the implementation) that is inversely proportional to its anticipated resource consumption.[1] [2]

Weighted fair queuing

Proportionally fair scheduling can be achieved by means of weighted fair queuing (WFQ), by setting the scheduling weights for data flow i to w_i = 1 / c_i, where the cost c_i is the amount of consumed resources per data bit. For instance:

User prioritization

Another way to schedule data transfer that leads to similar results is through the use of prioritization coefficients.[3] Here we schedule the channel for the station that has the maximum of the priority function:

P=\frac{T^\alpha}{R^\beta}

By adjusting \alpha and \beta in the formula above, we are able to adjust the balance between serving the best mobiles (the ones in the best channel conditions) more often and serving the costly mobiles often enough that they have an acceptable level of performance.

In the extreme case (\alpha=0 and \beta=1) the scheduler acts in a round-robin fashion and serves all mobiles equally often, with no regard for resource consumption. If \alpha=1 and \beta=0 then the scheduler will always serve the mobile with the best channel conditions. This will maximize the throughput of the channel while stations with low T are not served at all.[2]

Using \alpha\approx1 and \beta\approx1 will yield the proportional fair scheduling algorithm used in 3G networks.[3]

This technique can be further parametrized by using a "memory constant" that determines the period of time over which the station data rate used in calculating the priority function is averaged. A larger constant generally improves throughput at the expense of reduced short-term fairness.

See also

References

  1. Kushner, H. J.; Whiting, P.A. (July 2004), "Convergence of proportional-fair sharing algorithms under general conditions", IEEE Transactions on Wireless Communications 3 (4): 1250–1259, doi:10.1109/TWC.2004.830826. Cite uses deprecated parameter |coauthors= (help)
  2. 1 2 G. Miao, J. Zander, K-W Sung, and B. Slimane, Fundamentals of Mobile Data Networks, Cambridge University Press, ISBN 1107143217, 2016.
  3. 1 2 Yang, Ji; Zhang Yifan; Wang Ying; Zhang Ping (2004-11-29), "Average rate updating mechanism in proportional fair scheduler for HDR", IEEE Global Telecommunications Conference, 2004. 6, IEEE, pp. 3464–3466, doi:10.1109/GLOCOM.2004.1379010 Cite uses deprecated parameter |coauthors= (help)

Additional reading

This article is issued from Wikipedia - version of the Tuesday, April 26, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.