Proportional-fair scheduling

For the resource allocation problem, see Proportional division.

Proportional-fair scheduling is a compromise-based scheduling algorithm. It is based upon maintaining a balance between two competing interests: Trying to maximize the total throughput of the network (wired or not) 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 ${\displaystyle i}$ to ${\displaystyle w_{i}=1/c_{i}}$, where the cost ${\displaystyle c_{i}}$ is the amount of consumed resources per data bit. For instance:

• In CDMA spread spectrum cellular networks, the cost may be the required energy per bit in the transmit power control (the increased interference level).
• In wireless communication with link adaptation, the cost may be the required time to transmit a certain number of bits using the modulation and error coding scheme that this required. An example of this is EVDO networks, where reported SNR is used as the primary costing factor.
• In wireless networks with fast Dynamic Channel Allocation, the cost may be the number of nearby base station sites that can not use the same frequency channel simultaneously, in view to avoid co-channel interference.

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:

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

• ${\displaystyle T}$ denotes the data rate potentially achievable for the station in the present time slot.
• ${\displaystyle R}$ is the historical average data rate of this station.
• ${\displaystyle \alpha }$ and ${\displaystyle \beta }$ tune the "fairness" of the scheduler.

By adjusting ${\displaystyle \alpha }$ and ${\displaystyle \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 (${\displaystyle \alpha =0}$ and ${\displaystyle \beta =1}$) the scheduler acts in a "packet" round-robin fashion and serves all mobiles one after the other (but not equally often in time), with no regard for resource consumption, and such that each user gets the same amount of data. The (${\displaystyle \alpha =0}$ and ${\displaystyle \beta =1}$) scheduler could be called "maximum fairness scheduler" (to be used to provide equal throughout to voice users for example). If ${\displaystyle \alpha =1}$ and ${\displaystyle \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 ${\displaystyle T}$ are not served at all. The (${\displaystyle \alpha =1}$ and ${\displaystyle \beta =0}$) scheduler could be called "max rate" scheduler. ^[2] Using ${\displaystyle \alpha \approx 1}$ and ${\displaystyle \beta \approx 1}$ will yield the proportional fair scheduling algorithm used in 3G networks. ^[3] The (${\displaystyle \alpha =1}$ and ${\displaystyle \beta =1}$) scheduler could be implemented by providing the same amount of time & spectrum for each user, irrespective of the desired packet size, channel quality and data rate (MCS) used. The proportional fair (${\displaystyle \alpha =1}$ and ${\displaystyle \beta =1}$) scheduler could be called "equal effort scheduler" or "time/spectrum Round Robin scheduler".

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

• Scheduling (computing) - an introduction to the general topic of scheduling.
• Round-robin scheduling - a different scheduling algorithm.
• Proportional-fair rule - a more general rule for selecting among different alternatives, based on the same principle of balancing efficiency and fairness.

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, CiteSeerX   10.1.1.8.6408 , doi:10.1109/TWC.2004.830826, S2CID   6780351.
2. Guowang Miao, Jens Zander, Ki Won Sung, and Ben Slimane, Fundamentals of Mobile Data Networks, Cambridge University Press, ISBN   1107143217, 2016.
3. Ji Yang; Zhang Yifan; Wang Ying; Zhang Ping (2004), "Average rate updating mechanism in proportional fair scheduler for HDR", IEEE Global Telecommunications Conference, 2004. GLOBECOM '04, vol. 6, pp. 3464–3466, doi:10.1109/GLOCOM.2004.1379010, ISBN   0-7803-8794-5

Further reading

• Andrews, Matthew (September 2004), "Instability of the Proportional Fair Scheduling Algorithm for HDR", IEEE Transactions on Wireless Communications, 3 (5): 1422–1426, CiteSeerX   10.1.1.73.4092 , doi:10.1109/TWC.2004.833419, S2CID   34595035.
• Andrews, Matthew; Kumaran, K.; Ramanan, K.; Stoyar, A.; Whitting, Phil (February 2001), "Providing Quality of Service over a Shared Wireless Link", IEEE Communications, 39 (2): 150–154, doi:10.1109/35.900644.
• Parruca, Donald; Grysla, Marius; Gortzen, Simon; Gross, James (2013), "Analytical Model of Proportional Fair Scheduling in Interference-Limited OFDMA/LTE Networks", 2013 IEEE 78th Vehicular Technology Conference (VTC Fall), pp. 1–7, arXiv: 1303.1778 , Bibcode:2013arXiv1303.1778P, doi:10.1109/VTCFall.2013.6692106, ISBN   978-1-4673-6187-3, S2CID   8236469