Ferkans — Interactive Telecom Tutor

Balancing Throughput and Fairness

The max-rate scheduler of Section 20.1 maximises sum throughput but is inherently unfair: users far from the base station — those who need the most help — are starved of resources. At the opposite extreme, round-robin scheduling ignores channel quality entirely and divides time equally, sacrificing the multiuser diversity gain. Real-world cellular networks require a middle ground that captures most of the multiuser diversity gain while ensuring every user receives acceptable service. The proportional fair (PF) scheduler, deployed in every 3G, 4G, and 5G system, achieves precisely this balance.

Definition:
Scheduling Policies

Consider $K$ users with instantaneous rates $R_k[t]$ in slot $t$ . Three canonical scheduling policies are:

Max-Rate (MR) Scheduler:

$k^{\star}[t] = \arg\max_{k} \; R_k[t]$

Maximises instantaneous sum throughput.

Round-Robin (RR) Scheduler:

$k^{\star}[t] = (t \bmod K) + 1$

Each user is served in turn regardless of channel conditions.

Proportional Fair (PF) Scheduler:

$k^{\star}[t] = \arg\max_{k} \; \frac{R_k[t]}{\bar{T}_k[t]}$

where $\bar{T}_k[t]$ is an exponentially weighted moving average (EWMA) of user $k$ 's past throughput:

$\bar{T}_k[t+1] = \begin{cases} (1 - \tfrac{1}{t_c})\bar{T}_k[t] + \tfrac{1}{t_c}R_k[t] & \text{if } k = k^{\star}[t], \\ (1 - \tfrac{1}{t_c})\bar{T}_k[t] & \text{otherwise}, \end{cases}$

with averaging window $t_c$ (typically $t_c = 100$ -- $1000$ slots).

The PF metric $R_k[t]/\bar{T}_k[t]$ serves a user when its current rate is high relative to its own average. A cell-edge user with a low absolute rate can still win the competition when it experiences a relative channel peak.

Definition:
The Alpha-Fair Utility Family

The $\alpha$ -fair utility function, for parameter $\alpha \geq 0$ , is defined as:

$U_{\alpha}(x) = \begin{cases} \dfrac{x^{1-\alpha}}{1-\alpha} & \alpha \neq 1, \\[6pt] \ln x & \alpha = 1. \end{cases}$

A scheduler that maximises $\sum_{k=1}^{K} U_{\alpha}(\bar{T}_k)$ over the long-term average throughputs $\bar{T}_k$ produces:

$\alpha = 0$ : max-rate scheduling (maximise sum throughput).
$\alpha = 1$ : proportional fairness (maximise sum of log throughputs).
$\alpha = 2$ : minimum potential delay fairness (harmonic mean).
$\alpha \to \infty$ : max-min fairness (maximise the minimum rate).

Increasing $\alpha$ trades aggregate throughput for greater equality among users.

The $\alpha$ -fair family provides a single-parameter knob that operators can tune to match their service-level agreements. In LTE and 5G NR, the scheduler is typically PF ( $\alpha = 1$ ) with adjustments for QoS-differentiated traffic classes.

Proportional Fair Scheduling Algorithm

Complexity:

O(K)

per slot (one comparison per user). The PF scheduler adds negligible overhead beyond the CQI acquisition cost.

Input:

K

users, rate estimates

\{R_k[t]\}

, window

t_c

Initialise:

\bar{T}_k[0] = \epsilon > 0

for all

k

1. for

t = 0, 1, 2, \ldots

do

2.

\quad

Obtain instantaneous rates

R_k[t]

from CQI reports

3.

\quad

Compute PF metric for each user:

4.

\quad\quad m_k[t] \leftarrow R_k[t] \;/\; \bar{T}_k[t]

5.

\quad

Select user:

k^{\star} \leftarrow \arg\max_k \; m_k[t]

6.

\quad

Transmit to user

k^{\star}

at rate

R_{k^{\star}}[t]

7.

\quad

for

k = 1, \ldots, K

do

8.

\quad\quad

if

k = k^{\star}

then

9.

\quad\quad\quad \bar{T}_k[t+1] \leftarrow (1 - 1/t_c)\,\bar{T}_k[t] + (1/t_c)\,R_k[t]

10.

\quad\quad

else

11.

\quad\quad\quad \bar{T}_k[t+1] \leftarrow (1 - 1/t_c)\,\bar{T}_k[t]

12.

\quad\quad

end if

13.

\quad

end for

14. end for

The EWMA window $t_c$ controls the memory of the scheduler. Small $t_c$ reacts quickly to changing conditions but is more variable; large $t_c$ provides more stable fairness at the expense of slower adaptation.

Theorem: PF as Gradient Ascent on Sum Log-Utility

The PF scheduling rule $k^{\star}[t] = \arg\max_k R_k[t]/\bar{T}_k[t]$ converges, in the limit of large $t_c$ , to the solution of:

$\max_{\bar{\mathbf{T}} \in \mathcal{C}} \sum_{k=1}^{K} \ln \bar{T}_k$

where $\mathcal{C}$ is the ergodic rate region (the set of achievable long-term average throughput vectors). At each step, the PF rule selects the user that provides the steepest ascent direction for the objective $\sum_k \ln \bar{T}_k$ .

The gradient of $\sum_k \ln \bar{T}_k$ with respect to $\bar{T}_k$ is $1/\bar{T}_k$ . Allocating one slot to user $k$ increases $\bar{T}_k$ by approximately $R_k[t]/t_c$ . The marginal gain is $(R_k[t]/t_c) \cdot (1/\bar{T}_k) \propto R_k[t]/\bar{T}_k$ , which is exactly the PF metric. Hence PF performs stochastic gradient ascent on the log-utility.

Proof

Stochastic approximation framework

The EWMA update can be written as a stochastic approximation:

$\bar{T}_k[t+1] = \bar{T}_k[t] + \frac{1}{t_c}\left(\mathbf{1}_{k=k^{\star}[t]}\,R_k[t] - \bar{T}_k[t]\right)$

With step size $\eta = 1/t_c$ , this is a Robbins--Monro iteration tracking the mean-field ODE:

$\dot{\bar{T}}_k = \mathbb{E}[\mathbf{1}_{k=k^{\star}}\,R_k] - \bar{T}_k$

Optimality at the fixed point

At the fixed point $\bar{T}_k^{\star} = \mathbb{E}[\mathbf{1}_{k=k^{\star}}\,R_k]$ , the scheduling rule $k^{\star} = \arg\max_k R_k/\bar{T}_k^{\star}$ satisfies the KKT conditions of:

$\max_{\bar{\mathbf{T}} \in \mathcal{C}} \sum_{k=1}^{K} \ln \bar{T}_k$

This is because $1/\bar{T}_k^{\star}$ acts as the dual variable (shadow price) for user $k$ 's throughput, and the scheduling rule greedily maximises the Lagrangian $\sum_k R_k \mathbf{1}_{k=k^{\star}} / \bar{T}_k^{\star}$ in each slot. By the results of Kushner and Whiting (2004), the stochastic iterates converge almost surely to this fixed point. $\blacksquare$

,

Proportional Fair Scheduling Dynamics

Simulate PF scheduling for $K$ users over $T$ time slots. The plot shows each user's moving-average throughput $\bar{T}_k[t]$ converging over time, the fraction of slots allocated to each user, and the resulting sum log-throughput. Compare the PF outcome to max-rate and round-robin by observing how PF balances between the extremes. Increasing the SNR widens the dynamic range of channel gains across users.

Parameters

K

(number of users)8

SNR (dB)15

T

(number of time slots)500

Scheduling Decisions Over Time

Watch how the PF scheduler allocates time slots to users in real time. Each frame shows the instantaneous channel gains, the PF metric $R_k[t]/\bar{T}_k[t]$ , and which user is selected. Notice how even users with poor average channels periodically win the scheduling competition when they experience relative channel peaks.

Parameters

K

(number of users)4

SNR (dB)15

Number of animated slots40

Throughput--Fairness Frontier

Explore the Pareto frontier between aggregate throughput and fairness as the parameter $\alpha$ sweeps from 0 (max-rate) through 1 (proportional fair) to large values (max-min fair). The plot shows the achievable throughput vector $(\bar{T}_1, \ldots, \bar{T}_K)$ for each $\alpha$ , along with the sum throughput and Jain's fairness index. Increasing $K$ or SNR changes the shape of the frontier.

Parameters

K

(number of users)8

SNR (dB)15

Example: PF Scheduling Step-by-Step

Three users have the following channel conditions in slot $t = 100$ :

User	$R_k[100]$ (bits/s/Hz)	$\bar{T}_k[99]$ (bits/s/Hz)
1	5.0	4.0
2	2.5	1.0
3	3.0	3.5

The EWMA window is $t_c = 100$ .

(a) Compute the PF metric for each user and determine who is scheduled. (b) Update $\bar{T}_k[100]$ for all three users. (c) What would a max-rate scheduler choose instead?

Solution

PF metric computation

(a) PF metric $m_k = R_k/\bar{T}_k$ :

$m_1 = 5.0 / 4.0 = 1.25$ $m_2 = 2.5 / 1.0 = 2.50$ $m_3 = 3.0 / 3.5 = 0.857$

User 2 has the highest PF metric and is scheduled, even though user 1 has the highest absolute rate.

EWMA update

(b) With $1/t_c = 0.01$ :

$\bar{T}_1[100] = 0.99 \times 4.0 = 3.96$ $\bar{T}_2[100] = 0.99 \times 1.0 + 0.01 \times 2.5 = 1.015$ $\bar{T}_3[100] = 0.99 \times 3.5 = 3.465$

User 2's average throughput increases slightly; the others decay toward zero (they would receive service in future slots).

Max-rate comparison

(c) A max-rate scheduler would choose user 1 ( $R_1 = 5.0$ ). Over many slots, this would starve user 2 (who always has poor absolute rates), concentrating throughput on user 1. PF avoids this starvation. $\blacksquare$

Quick Check

In proportional fair scheduling, why is user $k$ scheduled when $R_k[t] / \bar{T}_k[t]$ is maximised rather than when $R_k[t]$ is maximised?

To reduce computational complexity

To ensure each user is served when its channel is near its own peak, providing both diversity gain and fairness

To guarantee equal time-slot allocation to all users

To maximise the minimum user throughput

Correction:

To ensure each user is served when its channel is near its own peak, providing both diversity gain and fairness

Dividing by $\bar{T}_k$ normalises each user's rate by its own long-term average. A cell-edge user with low absolute rate but a relative channel peak wins the competition, ensuring fairness while still exploiting multiuser diversity.

Common Mistake: PF Requires Sufficient Fading Variability

Mistake:

Assuming that PF always provides a large multiuser diversity gain, regardless of channel conditions.

Correction:

PF gains come from the relative channel fluctuations of each user. If all users have nearly deterministic channels (e.g., strong LoS with little fading), the PF metric $R_k/\bar{T}_k$ is nearly constant for each user, and PF degenerates to round-robin. The multiuser diversity gain is proportional to the dynamic range of each user's fading, which is maximal under Rayleigh fading and minimal under Rician fading with large $\kappa$ . In practice, 5G mmWave channels with narrow beams may exhibit less fading variability, reducing PF gains.

Why This Matters: Scheduling in LTE and 5G NR

Both LTE and 5G NR implement channel-aware scheduling at the MAC layer, operating on a 1 ms TTI (LTE) or configurable slot duration (5G NR, down to 0.125 ms at 120 kHz SCS):

LTE: The eNodeB scheduler receives CQI reports every 1--10 ms and makes per-TTI, per-RB scheduling decisions. Most vendors implement PF or weighted PF with QoS-aware priority adjustments. The scheduler also handles HARQ retransmissions and semi-persistent scheduling for VoIP.
5G NR: The gNB scheduler operates at sub-slot granularity with support for grant-free transmissions (configured grant) and dynamic scheduling via DCI. Enhanced QoS frameworks (5QI) allow differentiated scheduling for URLLC, eMBB, and mMTC traffic. The proportional fair metric is augmented with delay-aware terms for latency-critical traffic.
Cross-layer design: Both systems tightly couple the scheduler with link adaptation (AMC), HARQ, and buffer status reports (BSR), forming a cross-layer control loop that adapts to channel, traffic, and QoS conditions jointly.

PF Scheduler Convergence

Watch the EWMA throughputs

\bar{T}_k

of

K

users converge under proportional fair scheduling. Users with weaker average channels receive lower throughput but are not starved — each user's trace stabilises at a level that maximises the sum of log-throughputs.

PF scheduler throughput convergence for 4 users with heterogeneous average channel qualities. The proportional fair equilibrium balances multiuser diversity against fairness.

Proportional Fair Scheduler Architecture — Block diagram of the proportional fair scheduler. CQI reports from $K$ users feed the PF metric computation $m_k = R_k/\bar{T}_k$ . The user with the highest metric is selected, and its EWMA throughput $\bar{T}_k$ is updated. The selected user's data is read from the buffer and transmitted using the MCS corresponding to its CQI. The HARQ feedback (ACK/NACK) drives the outer-loop link adaptation bias $\Delta_k$ .

Common Mistake: Round-Robin Is Not Throughput-Fair

Mistake:

Believing that round-robin scheduling provides fair throughput because it gives equal time to all users.

Correction:

Round-robin allocates equal time but not equal throughput. A cell-edge user receiving 0.5 bits/s/Hz for 1 ms gets 0.5 kbits; a cell-centre user receiving 5.0 bits/s/Hz for 1 ms gets 5.0 kbits. The 10:1 throughput disparity persists despite equal time allocation.

For throughput-fair allocation, the scheduler must give more time to cell-edge users (compensating for their lower rates), which is what max-min fair scheduling ( $\alpha \to \infty$ ) achieves — at the cost of significant sum-throughput loss. Proportional fairness ( $\alpha = 1$ ) is the practical compromise deployed in real systems.

Proportional Fair Scheduling

A scheduling policy that selects user $k^{\star} = \arg\max_k R_k[t]/\bar{T}_k[t]$ in each time slot, maximising the sum of log-throughputs $\sum_k \ln \bar{T}_k$ . PF balances multiuser diversity gain against fairness by normalising each user's instantaneous rate by its own average.

Alpha-Fair Utility

A parametric family of utility functions $U_\alpha(x) = x^{1-\alpha}/(1-\alpha)$ (with $U_1(x) = \ln x$ ) that interpolates between sum-rate maximisation ( $\alpha = 0$ ), proportional fairness ( $\alpha = 1$ ), and max-min fairness ( $\alpha \to \infty$ ). The parameter $\alpha$ controls the trade-off between aggregate throughput and fairness.

Related: Proportional Fair Scheduling

Scheduling Algorithms

Balancing Throughput and Fairness

Definition: Scheduling Policies

Definition: The Alpha-Fair Utility Family

Proportional Fair Scheduling Algorithm

Theorem: PF as Gradient Ascent on Sum Log-Utility

Stochastic approximation framework

Optimality at the fixed point

Proportional Fair Scheduling Dynamics

Parameters

Scheduling Decisions Over Time

Parameters

Throughput--Fairness Frontier

Parameters

Example: PF Scheduling Step-by-Step

PF metric computation

EWMA update

Max-rate comparison

Quick Check

Common Mistake: PF Requires Sufficient Fading Variability

Why This Matters: Scheduling in LTE and 5G NR

PF Scheduler Convergence

Proportional Fair Scheduler Architecture

Common Mistake: Round-Robin Is Not Throughput-Fair

Proportional Fair Scheduling

Alpha-Fair Utility

Definition:
Scheduling Policies

Definition:
The Alpha-Fair Utility Family