MAC and the Scheduler

The scheduler is the only part of the stack that makes real decisions. Everything below it executes instructions. Everything above it produces work. In between, one function decides who transmits, on which resources, with which modulation, twice every millisecond. It is small in code and it determines almost everything a user experiences.

• Executive Summary
• What decision does the scheduler actually make?
• What information does it have, and how old is it?
• How do the classic algorithms work?
• How does link adaptation actually converge?
• What does HARQ require of the implementation?
• Why is the scheduler usually one thread?
• What makes a scheduler bad in practice?
• Reference

Executive Summary

The table is a lookup. Every input arrives late, and the staleness column is the reason scheduling is hard rather than merely fiddly.

What decision does the scheduler actually make?

The output is more specific than the word scheduling suggests. Once per slot, for both directions, the scheduler fills a grid. Every decision it makes is a placement in that grid plus a set of parameters.

For each device it chooses whether to schedule it at all. If it does, it picks which resource blocks that device gets. It picks the modulation and coding scheme, which sets how many bits fit in those blocks. It picks which HARQ process the transmission belongs to.

Those choices are not independent. The resource blocks and the modulation together determine the transport block size, which has to match what the data actually needs. Allocating generously and then finding too little data to send wastes the slot.

The uplink decision has an extra property that makes it harder. The scheduler is deciding what a device will send before that device has told it what it has. So an uplink grant is a prediction, and a wrong prediction produces a transmission carrying padding.

All of this has to be expressed as control messages. Each scheduled device needs downlink control information addressed to it, and that control channel occupies resources too. Scheduling many devices in one slot therefore costs resources before any data moves.

One constraint runs through everything and is easy to overlook. The grid is shared. Two devices cannot be given the same resource block, so every allocation reduces what remains for the rest of that slot.

That shared resource is what makes the scheduler an optimisation rather than a queue. A queue decides an order. A scheduler decides an order and a division. One constraint couples every decision to every other one in the same slot.

• The output is a filled grid : Placements plus parameters, decided once per slot for both directions.
• Four choices per scheduled device : Whether to schedule, which resource blocks, which modulation and coding, and which HARQ process.
• The choices are coupled : Blocks and modulation together fix the transport block size, which has to match the data actually waiting.
• An uplink grant is a prediction : The scheduler decides what a device will send before the device has said what it has.
• Control messages cost resources too : Every scheduled device needs its own grant, so scheduling many costs capacity before data moves.
• The grid is shared : Every allocation reduces what remains, which is what makes this an optimisation rather than a queue.

What information does it have, and how old is it?

A scheduler is only as good as its inputs. Every one of those inputs describes the past, and some describe it from quite a long time ago. Designing as though they were current is the most common source of poor performance.

Channel quality is the worst case. The device measures reference signals, forms an index, and reports it on a schedule. By the time the scheduler acts on it, the channel it described may be tens of milliseconds old.

For a stationary device that hardly matters. For a moving one it matters enormously, because the channel can change completely in that time. This is why mobility degrades throughput even when signal strength stays constant.

Buffer status has a different problem. A device reports how much data it has waiting. It can only send that report once it has been granted room to do so. So a device with nothing scheduled cannot easily tell the network that it suddenly has data.

The scheduling request mechanism exists to break that deadlock. It is a single bit, so it says that data exists without saying how much. The scheduler responds with a small grant, and the real report arrives inside it.

HARQ acknowledgements are the freshest input and the most useful. They arrive k1 slots after the transmission they describe, and they are unambiguous. Whether a transport block decoded is a fact rather than an estimate.

That freshness is why the outer loop of the next section is built on them rather than on channel reports. A slow, reliable signal beats a fast, indirect one when the fast one is describing a moment that has passed.

Uplink information is a special case worth noting. The base station measures the uplink itself, so it does not have to wait for a report. Uplink link adaptation can therefore react much faster than downlink link adaptation.

• Every input describes the past : Designing as though the reports were current is the usual cause of disappointing throughput.
• Channel reports can be tens of milliseconds old : That is harmless for a stationary device and severe for a moving one.
• Mobility costs throughput even at constant signal strength : The channel changes faster than the report describing it can arrive.
• Buffer status needs a grant to be reported : A device with nothing scheduled cannot easily announce that it now has data.
• The scheduling request breaks that deadlock : One bit says data exists. The real report arrives in the small grant that follows.
• Acknowledgements are facts, not estimates : They are the freshest input, which is why link adaptation is built on them.
• The uplink is measured, not reported : The base station sees it directly, so uplink adaptation can react much faster.

How do the classic algorithms work?

Three algorithms cover almost every real scheduler, and the third is what nearly everyone actually uses. Understanding the first two is still worth the effort, because they define the two extremes the third sits between.

Round robin gives each device a turn regardless of its channel. It is trivially fair and it wastes a great deal of capacity. A device in a deep fade gets the same share as one beside the antenna. It converts that share into very few bits.

Maximum rate scheduling is the opposite. It always picks the device with the best channel, so cell throughput is as high as it can be. It also starves everyone at the cell edge completely, which is unacceptable in any real deployment.

Proportional fair sits between them, and the idea behind it is elegant. Each device is ranked by the rate it could achieve now, divided by the average rate it has been receiving. A device with a good instantaneous channel scores highly, and so does a device that has been getting nothing.

The behaviour that emerges is the useful part. Every device gets scheduled when its own channel is relatively good rather than when the cell's channel is good. So the scheduler rides each device's fading independently, which extracts most of the throughput benefit without the starvation.

The averaging window is the parameter that tunes it. A short window makes the scheduler responsive and less fair, and a long window does the reverse. It is one number, and it moves the behaviour between the two extremes described above.

Real schedulers add constraints on top of this ranking rather than replacing it. Delay-sensitive bearers get priority. Devices with pending retransmissions are handled first, because a retransmission is cheaper than a new transmission. Guaranteed bit rate bearers get a floor.

Figure 1 shows how the three behave when one device has a consistently worse channel than the others.

Figure 1. Proportional fair is not a compromise between the other two so much as a different question. It asks when each device is at its own best, which recovers most of the throughput without abandoning anybody.

• Round robin is fair and wasteful : Equal turns regardless of channel. A device in a fade converts its share into very few bits.
• Maximum rate is efficient and unusable : It maximises cell throughput by starving everyone at the cell edge completely.
• Proportional fair ranks by a ratio : Achievable rate now, divided by the average rate already delivered to that device.
• It rides each device's own fading : Everyone gets scheduled when their personal channel peaks rather than when the cell's best channel does.
• The averaging window is the tuning knob : Short is responsive and less fair, and long is the reverse, on one parameter.
• Real schedulers add constraints on top : Retransmissions first, delay-sensitive bearers prioritised, and guaranteed rates given a floor.

How does link adaptation actually converge?

Choosing a modulation and coding scheme is a bet. Too aggressive and the transmission fails. Too conservative and capacity is wasted on redundancy nobody needed. The mechanism that settles this bet is two nested loops.

The inner loop is the obvious one. The device reports a channel quality index, and a table maps that index to a modulation and coding scheme. If the reports were accurate and current, that would be the whole story.

They are neither. The report is stale. The device's own receiver differs from the model behind the table, and interference changes in between. So the inner loop is systematically wrong by an amount nobody can predict.

The outer loop corrects for that using the acknowledgements. It maintains an offset, applied to the inner loop's answer before the scheme is chosen. When a transmission fails the offset moves down, and when one succeeds it moves up slightly.

The asymmetry between those two steps is what sets the operating point. Make the failure step nine times the success step and the loop settles at roughly ten percent failures. The ratio of the steps chooses the target, directly and simply.

Ten percent sounds high until the retransmission cost is considered. A failed first transmission is not lost, since HARQ combines it with the retransmission that follows. Aiming for near-certain success on the first attempt means using a scheme so conservative that the average throughput falls.

So a healthy cell shows a first-transmission failure rate around ten percent. That is a sign of correct tuning rather than a problem. A cell showing one percent is being scheduled too conservatively and is leaving capacity unused.

One implementation detail causes real bugs. The offset is per device. It has to be reset when the device's situation changes fundamentally, such as after a handover. Carrying an old offset into a new radio environment produces a burst of failures that the loop then has to unwind.

Figure 2 shows the outer loop settling, and what happens when the step ratio is wrong.

Figure 2. The step ratio chooses the target failure rate directly. A cell showing one percent first-transmission failures is conservative rather than healthy. It gives away capacity to buy reliability HARQ would have supplied for free.

• The inner loop uses the reported index : A table maps channel quality to a modulation and coding scheme. It would be enough if reports were current.
• The inner loop is systematically wrong : Stale reports, receiver differences and changing interference all bias it by an unpredictable amount.
• The outer loop corrects with acknowledgements : An offset moves down on a failure and up slightly on a success. It is applied before the scheme is chosen.
• The step ratio sets the target : A failure step nine times the success step settles the loop at roughly ten percent failures.
• Ten percent failures is correct tuning : HARQ combines the failed attempt with the retransmission. Near-certain success therefore costs more than it saves.
• One percent means capacity is being wasted : The scheduler is being too conservative, and the unused margin does not come back.
• Reset the offset on a fundamental change : Carrying an old offset through a handover produces a burst of failures the loop then unwinds.

What does HARQ require of the implementation?

HARQ is usually described as a protocol feature. From the software side it is mostly a memory management problem, and an awkward one. It is also the feature most often postponed and least often postponable.

The mechanism is simple to state. A transmission that fails is not discarded. The receiver keeps the soft values, and when the retransmission arrives it combines the two before decoding again. Two failed attempts together often decode when neither would alone.

Combining is what makes the ten percent failure target sensible. Without it a failure would mean a full retransmission from nothing. With it a failure means the next attempt starts from a partial result, so the second attempt succeeds with high probability.

The cost is storage, and it is larger than people expect. Soft values for a whole transport block have to be kept until the process completes. Several processes are outstanding at once per device, and NR allows up to sixteen.

So the soft buffer requirement is the number of processes multiplied by the transport block size multiplied by the soft value width. For a high throughput device that is a substantial allocation, and it exists per device rather than per cell.

That multiplication is why soft value quantisation matters so much, as the PHY page notes. Halving the width of a soft value halves the largest memory allocation in the receiver.

The process identifier is what ties it together, and it is carried in the control information. It tells the receiver which stored attempt this transmission should be combined with. Getting that identifier wrong combines unrelated data, which produces decode failures that look like a radio problem.

Asynchronous operation adds one more requirement in NR. A retransmission can be scheduled in any later slot rather than at a fixed offset. So the scheduler tracks which processes are outstanding and chooses freely among them. That flexibility is useful and it makes the bookkeeping the scheduler's job.

One practical consequence is worth stating. Process exhaustion is a real limit, and it appears as a device that stops being scheduled despite having data. All its processes are waiting for acknowledgements that have not arrived, which usually means the uplink carrying them is failing.

• It is a memory problem more than a protocol one : Failed transmissions are kept as soft values, then combined with the retransmission.
• Combining is what makes the failure target work : The second attempt starts from a partial result rather than from nothing.
• Storage is processes times block size times width : NR allows up to sixteen processes per device. The allocation is per device, not per cell.
• Soft value width is the lever : Halving it halves the largest memory allocation in the receiver, at very little performance cost.
• The process identifier must be right : A wrong one combines unrelated data. The decode failures that follow look like a radio fault.
• Asynchronous retransmission is the scheduler's bookkeeping : Any later slot is allowed, so the scheduler tracks which processes are outstanding.
• Process exhaustion looks like starvation : A device with data stops being scheduled because every process is waiting for an acknowledgement.

Why is the scheduler usually one thread?

Every other expensive part of the stack is parallelised. The scheduler generally is not, and that looks like an oversight until the reason is clear. The reason is the shared grid from the first section.

Each allocation changes what is available for the next one. So a decision about the second device depends on the decision already made about the first. That dependency is not incidental, since it is the whole nature of dividing a fixed resource.

Parallelising it therefore means either splitting the grid in advance or locking it. Splitting in advance gives up the flexibility that makes the scheduler good. A device cannot then be given resources from another partition. Locking means the lock is held for nearly the whole computation.

The second thing that makes one thread viable is scale. The scheduler runs once per slot and finishes in tens of microseconds. Coordination between threads costs microseconds too, so the overhead would consume much of what it saved.

There is a third reason, and it is about correctness rather than speed. A scheduler holds the state of every device, and that state is read and written throughout its computation. Single-threaded execution makes that state trivially consistent, which removes an entire class of bug from the most decision-heavy code in the system.

What does get parallelised is the work around it. Preparing the inputs, encoding the control messages, and building the transport blocks all happen elsewhere. The scheduler is left with the decision itself.

The scaling limit is worth knowing. Scheduler cost grows with the number of connected devices rather than with throughput, as the real-time loop page describes. A cell with very many devices is where this design eventually needs revisiting.

At that point the usual answer is not threading but partitioning by cell. Two cells are genuinely independent, so two scheduler threads with no shared state is straightforward. Splitting one cell's grid across threads remains the thing to avoid.

• The grid couples every decision : Each allocation changes what remains, so the second device's decision depends on the first one.
• Both parallel options are bad : Partitioning in advance gives up flexibility, and locking holds the lock for nearly the whole computation.
• Coordination costs as much as the work : The scheduler finishes in tens of microseconds. Thread coordination is measured in microseconds too.
• Single threading removes a bug class : Per-device state is read and written throughout, and consistency comes for free.
• The surrounding work is parallel : Input preparation, control message encoding and transport block construction all happen on other threads.
• Cost grows with device count : Not with throughput, which is a different scaling law from the physical layer.
• Partition by cell, not by grid : Two cells are independent and parallelise cleanly, and one cell's grid does not.

What makes a scheduler bad in practice?

A scheduler that implements proportional fair correctly can still behave badly. The failures are rarely in the ranking formula. They are in the constraints and the edge cases around it, and they show up as complaints rather than as errors.

The first pathology is starvation from a constraint interaction. A device with a guaranteed bit rate is always prioritised, so on a congested cell it can consume everything. The ranking formula is working perfectly and the outcome is still wrong.

The second is oscillation. A scheduler that reacts too quickly to channel reports alternates between devices in a way that helps nobody. Both devices see variable throughput, and the averaging window is usually the parameter that fixes it.

The third is a fairness measure that hides the problem. Average throughput across devices can look excellent while one device receives nothing at all. Reporting the minimum alongside the mean is what makes starvation visible.

The fourth is treating retransmissions as ordinary traffic. A retransmission is cheaper than a new transmission, because HARQ combining means it needs fewer resources for the same result. A scheduler that does not prioritise them wastes capacity on every failure.

The fifth appears only under load and is the hardest to find. Scheduler cost grows with device count, so the computation that fitted comfortably with ten devices may not fit with two hundred. It then overruns its slot, which the real-time loop page describes the consequences of.

One measurement habit finds most of these. Record per-device throughput and per-device scheduling opportunities separately, over minutes rather than seconds. A device receiving grants but achieving little has a link adaptation problem, and a device receiving no grants has a scheduling problem.

That distinction is worth making explicitly, because the two look identical from a throughput graph. Separating them turns an unanswerable complaint about performance into a specific question with a specific answer.

• Constraints cause starvation, not the formula : A guaranteed bit rate bearer on a congested cell can consume everything. The ranking is working correctly throughout.
• Reacting too fast produces oscillation : Devices alternate in a way that helps neither, and the averaging window is usually the fix.
• Average throughput hides starvation : Report the minimum alongside the mean, or a device receiving nothing stays invisible.
• Retransmissions deserve priority : Combining makes them cheaper than new transmissions, so deprioritising them wastes capacity on every failure.
• Cost grows with device count under load : A computation that fits with ten devices may overrun its slot with two hundred.
• Measure grants and throughput separately : Grants without throughput is link adaptation, and throughput without grants is scheduling.

Reference

The list below is where the procedures and tables come from. The specifications are the authority for the reporting formats and the HARQ rules. The ShareTechnote pages carry the layers on either side.

• 3GPP TS 38.321 : NR MAC protocol. HARQ processes, buffer status reporting, scheduling requests and power headroom.
• 3GPP TS 38.214 : NR physical layer procedures for data. Channel quality reporting and the modulation and coding tables.
• 3GPP TS 38.212 : NR multiplexing and channel coding. Downlink control information formats and the redundancy versions HARQ uses.
• 5G FAPI : Small Cell Forum - the P7 messages this layer sends to the physical layer each slot.
• ShareTechnote - The Real-Time Loop : The slot budget this scheduler runs inside, and the k values it chooses.
• ShareTechnote - Physical Layer Software : What executes these decisions, and where soft value width comes from.
• ShareTechnote - RLC, PDCP and RRC : What supplies the data this scheduler allocates room for.
• ShareTechnote - RAN Software Stack : Why this layer is one thread while the rest are not.