RAN Scheduling Algorithms
The per-slot decision at the heart of the RAN: given many users, a shared radio, and channels that fluctuate every millisecond, which users get which resource blocks right now? Every scheduler is an answer to one question — how to trade total throughput against fairness — and proportional fair is the answer that won.
What · How · Why
What it is
The MAC scheduler in the DU allocates the cell's time-frequency resource blocks to users every slot. It reads each user's reported channel quality (CQI) and buffer state, then picks who transmits on which RBs. It is a real-time optimizer that must decide within the slot deadline — microseconds to a millisecond.
How it works
Each candidate user gets a metric, and the RB goes to the highest metric. Round robin ignores channel and rotates turns (max fairness). Max C/I always picks the best channel (max throughput). Proportional fair (PF) picks the user whose instantaneous rate is highest relative to its own recent average — riding each user's channel peaks while keeping everyone served.
Why it matters
The scheduler is where spectral efficiency and user experience are actually decided, slot by slot. Max C/I starves cell-edge users; round robin wastes capacity; PF captures most of the multi-user diversity gain while guaranteeing no one is starved. It is also the natural target for RL — a hand-tuned utility function deciding a sequential resource-allocation problem under uncertainty.
Round 1 — Mental Model
Imagine a single delivery van (the radio) serving many customers (users) whose roads change quality every minute — sometimes a customer has a clear highway (good channel), sometimes gridlock. A naive fair dispatcher visits customers strictly in turn regardless of traffic (round robin): nobody is neglected, but the van sits in jams. A greedy dispatcher only ever serves whoever currently has the clearest road (max C/I): total packages delivered is maximal, but a customer on a permanently bad road never gets anything.
Proportional fair is the clever middle: serve the customer whose road is best compared to how good their road usually is. A customer having an unusually good moment gets priority — you exploit their temporary highway — but because it's relative to their own baseline, even customers with generally bad roads get served when they hit their personal best. You harvest the good moments of everyone, which is more total throughput than round robin and far more fairness than greedy.
Round 2 — Internal Mechanics & Mathematical Model
The general scheduler
Every RB, for every eligible user \(i\), compute a metric \(m_i(t)\) and allocate to \(\arg\max_i m_i(t)\). The three classic schedulers are the same rule with different metrics:
\[ m_i^{\text{RR}}=\text{time since last served},\quad m_i^{\text{MaxCI}}=R_i(t),\quad m_i^{\text{PF}}=\frac{R_i(t)}{\bar{R}_i(t)} \]where \(R_i(t)\) is the achievable rate this slot (from CQI) and \(\bar R_i(t)\) is user \(i\)'s exponentially averaged delivered rate.
Proportional fair — the running average
PF maintains each user's average throughput with an exponential filter, updated every slot:
\[ \bar R_i(t+1)=\Big(1-\tfrac{1}{t_c}\Big)\bar R_i(t)+\tfrac{1}{t_c}\,R_i(t)\,\mathbb{1}[i\ \text{served}] \]\(t_c\) is the fairness time window. Small \(t_c\) (short memory) → aggressive, throughput-leaning, less fair; large \(t_c\) → smoother, fairer, slower to react. This one knob slides PF between max-C/I and round-robin behavior.
Why PF maximizes sum-log-throughput (derivation)
Claim: greedily choosing \(\arg\max_i R_i(t)/\bar R_i(t)\) each slot asymptotically maximizes \(\sum_i \log \bar R_i\). Sketch: the marginal gain of serving user \(i\) to the utility \(U=\sum_j\log\bar R_j\) is \(\frac{\partial U}{\partial \bar R_i}\cdot\Delta\bar R_i \approx \frac{1}{\bar R_i}\cdot\frac{R_i(t)}{t_c}\propto \frac{R_i(t)}{\bar R_i}\). So picking the largest \(R_i/\bar R_i\) is gradient ascent on \(\sum_i\log\bar R_i\) — exactly the proportional-fairness objective (Kelly, 1997). The \(1/\bar R_i\) factor is the derivative of the log; it is why the metric is a ratio.
Complexity & the multi-user diversity gain
Complexity: \(O(U)\) per RB for \(U\) users (evaluate each metric, take the max), \(O(U\cdot N_{RB})\) per slot — must complete within \(2^{-\mu}\) ms, which caps practical \(U\) and drives fast approximations. Diversity gain: with \(U\) users experiencing independent fading, \(\mathbb{E}[\max_i R_i]\) grows like \(\log U\) — serving whoever peaks harvests this, and PF captures nearly all of it while max-C/I captures it unfairly and round-robin forfeits it.
Invariants & limiting cases
Invariants: PF never permanently starves a user (a user's \(\bar R_i\) decays when unserved, raising its metric until it wins); work-conserving (an RB is never idle if any user has data). Limiting cases: \(t_c\to 1\) → PF ≈ max C/I (no memory, pure greedy); \(t_c\to\infty\) → PF ≈ round robin (equal long-run shares); identical static channels → all three coincide; one user with permanently zero rate → excluded, others share (unlike naive fairness which would waste slots on it).
Round 3 — Where It Breaks & Expert Debates
PF is throughput-fair, not latency-fair. Its objective is long-run rate, so it says nothing about delay. A URLLC packet with a hard deadline can lose repeatedly to a user who merely has a better channel. Delay-aware variants (M-LWDF, EXP/PF) bolt a deadline term onto the metric, but combining throughput-fairness and latency guarantees in one scheduler has no clean optimum — it's an active design tension, especially with mixed slices.
The CQI it trusts is stale and quantized. Channel reports arrive with delay and in a few bits; by the time the scheduler acts, the channel has moved. Fast fading makes reported \(R_i(t)\) an unreliable predictor, so schedulers over- or under-shoot. Link adaptation and outer-loop rate control patch this, but the scheduler is fundamentally deciding on out-of-date information.
Multi-antenna makes it combinatorial. With MU-MIMO, the scheduler must pick a set of users to co-schedule on the same RBs whose beams don't interfere — a combinatorial user-pairing problem, not a simple max. Optimal MU-MIMO scheduling is NP-hard; production uses greedy heuristics whose gap to optimal is unknown and workload-dependent.
Fairness metric is a value choice, not a fact. PF (sum-log) is one point on a family of \(\alpha\)-fair utilities; \(\alpha{=}0\) is max-throughput, \(\alpha{=}1\) is PF, \(\alpha\to\infty\) is max-min fairness. Which \(\alpha\) an operator should use is a policy/business decision that the math can't settle — a genuine debate dressed as an equation.
Round 4 — AI × Networks Connection
The scheduler is the cleanest reinforcement-learning target in the RAN: a sequential decision (which users each slot), a state (CQIs, buffers, \(\bar R_i\)), and a reward (throughput under fairness/latency constraints). PF is a hand-designed policy with a fixed utility; an RL policy can learn a state-dependent metric that adapts to traffic mix and channel statistics — precisely attacking the "fairness metric is a value choice" and "delay-vs-throughput" tensions from Round 3 by learning the trade instead of fixing it.
But the slot deadline is the hard constraint that shapes where the learning can live. The scheduler runs every \(2^{-\mu}\) ms, far below the near-RT RIC's inference floor — so an RL scheduler cannot run inference in the RIC per slot. The realistic pattern is: the non-RT RIC learns the scheduler's parameters or utility weights offline, and the DU executes a cheap distilled policy at slot rate. This is the same offline-train / online-serve split as everywhere in the KB, but here the "serve" side must be almost free.
Cross-links
AI · RL policy gradients → the scheduler as a learned policy; PF is the hand-designed baseline it must beat.
Networks · 5G NR numerology → sets the per-slot deadline the scheduler — and any learned variant — must hit.
Networks · O-RAN architecture → the RIC learns/adjusts scheduler policy; the DU executes it in real time.
Pending intersection nodes this unblocks: Deep RL for RAN optimization, RL for load balancing, RL for network slicing (per-slice scheduling weights).
Open questions this raises
- Can a learned scheduler beat PF enough to justify its complexity and verification burden, or is PF already near-optimal for most traffic mixes?
- How do you distill an RL-learned scheduling policy into something cheap enough to run every 125 µs in the DU without losing the gains?
- What is the right multi-objective formulation when a cell mixes eMBB, URLLC, and mMTC slices — a single \(\alpha\)-fair utility, per-slice schedulers, or a learned arbitration?
- With stale, quantized CQI, is there value in a learned channel predictor feeding the scheduler, and how does its error propagate into allocation decisions?