12. Quality of Service and Traffic Engineering
Every mechanism so far has assumed the network's default contract: it will try to deliver your packet, and it owes you nothing about when or whether it arrives. That contract is adequate for a file transfer and useless for a surgeon's video feed, because the moment a link is congested the network's arbitrary choices about who waits become the application's user experience. This chapter covers how to state service requirements numerically, the per-hop mechanisms that enforce them (classification, policing, shaping, scheduling, active queue management, admission control), and the two architectures — IntServ and DiffServ — that assemble those mechanisms into an end-to-end service, ending with MPLS and segment routing traffic engineering, which choose paths rather than queue positions.
<a id="121-qos-fundamentals"></a>
12.1 QoS Fundamentals
Quality of service begins as an exercise in specification rather than configuration: this subchapter covers how to describe what an application needs, how to divide an end-to-end requirement into a per-hop budget, what kinds of promises a network can actually make, and how those promises become contracts.
Traffic Classes and Service Requirements
Theory
A router with an empty queue gives every packet identical, excellent service, so QoS is invisible until the instant demand exceeds capacity. At that instant the router must decide which packet goes first and which packet is discarded, and the only question that matters is whether that decision is deliberate or accidental. Best-effort forwarding makes it accidental: with a single FIFO queue, a 2 GB backup pushes 40 ms of extra delay in front of every voice packet behind it, purely because the backup's packets arrived first. Traffic classes exist so that the decision can instead be made according to what each application can survive.
The fundamental split is between elastic and inelastic traffic. Elastic applications adapt: a file transfer finishes in 10 seconds or 30 seconds, and the only cost is impatience. Their throughput is what matters, and loss is not a catastrophe — it is TCP's congestion signal (Section 7.5), the mechanism by which the application discovers its fair share. Inelastic applications have a threshold: a voice call needs its packet within roughly 150 ms or the packet may as well not exist, because the conversation has already moved on. Sending it faster does not help, and sending it late is equivalent to losing it.
A useful analogy is a city street shared by ambulances, commuter cars, and gravel trucks. The ambulance is inelastic: arriving 20 minutes late is a total failure, and arriving 20 seconds early is worth nothing. The gravel truck is elastic: it cares only about tonnes delivered per day, and a detour costs nothing as long as the total holds. A single first-come-first-served rule serves the trucks well and kills the patient, which is exactly what one FIFO queue does to a mixed network.
Four requirement dimensions are enough to describe almost any class:
| Dimension | Question | Who is sensitive |
|---|---|---|
| Bandwidth | How many bits per second, and how bursty? | Video, bulk transfer |
| Delay | How long from sender to receiver, one way? | Voice, gaming, trading, control loops |
| Jitter | How much does delay vary packet to packet? | Voice, live video, industrial control |
| Loss | What fraction can be discarded without harm? | Voice tolerates some; bulk data tolerates none visibly |
The loss dimension is the most misunderstood. Voice appears loss-sensitive and is actually loss-tolerant but retransmission-intolerant: a G.711 codec with packet loss concealment interpolates a lost 20 ms sample well enough that 1% random loss is barely audible, but a retransmission arriving 90 ms later is worthless. Bulk TCP is the reverse — it never loses data visibly, because it retransmits everything, so loss shows up purely as reduced throughput. "Can this class lose packets?" therefore has two answers depending on whether the application or the transport is asked.
RFC 4594 gives the standard industry class model, which is a good default because it is what vendor templates and service-provider offerings assume. The essential rows:
| Class | Example application | Bandwidth | One-way delay | Jitter | Loss tolerance |
|---|---|---|---|---|---|
| Network control | routing protocols (BGP, OSPF), BFD | very low | low | low | very low |
| Telephony | VoIP bearer (RTP) | low, constant (~87 kb/s) | < 150 ms | < 30 ms | < 1% |
| Signalling | SIP, H.323 | very low, bursty | < 200 ms | loose | < 1% |
| Interactive video | video conferencing | 1-6 Mb/s, bursty | < 150 ms | < 30 ms | < 0.1% |
| Streaming video | on-demand video, IPTV | 3-25 Mb/s | < 4-5 s (buffered) | absorbed by buffer | < 0.1% |
| Low-latency data | transactional apps, RPC, SSH | low-medium, bursty | < 100-400 ms | loose | 0 (TCP) |
| OAM | SNMP, syslog, telemetry | low | loose | loose | low |
| High-throughput data | backups, replication, CI artefacts | high, sustained | irrelevant | irrelevant | 0 (TCP) |
| Scavenger | peer-to-peer, OS updates, opportunistic sync | whatever is left | irrelevant | irrelevant | high |
Two design rules follow. First, the number of classes should be small — typically four to eight. Each class needs a scheduler entry, a marking policy, thresholds, counters, and a documented meaning on every device in the path; twelve classes are twelve things to misconfigure, and operators cannot keep more than a handful straight. Second, the scavenger class is as valuable as the priority class. Giving backups a class that is explicitly allowed to starve is often the single most effective change in an enterprise network, because it removes the largest source of queue occupancy without needing to guarantee anything at all.
Examples
Requirement space: where classes sit on the two axes that matter
loss
tolerance
^
1% | [ telephony ] <- drop it, do not delay it
|
|
0.1% | [ interactive video ]
| [ streaming video ]
|
0 | [ network control ] [ low-latency data ] [ bulk data ] [ scavenger ]
+--------------------------------------------------------------------> delay
10 ms 150 ms 1 s 10 s unbounded
tolerance
Reading the diagram:
top-left = inelastic real time -> needs a scheduler guarantee, small queue
bottom-left = control plane -> needs protection, tiny volume
bottom-right= elastic bulk -> needs a big queue, nothing else
Two classes in the same region of this plane should be merged.
# One FIFO queue vs one deliberate decision, on the same arrival pattern.
# A 12 ms burst of bulk packets arrives, then a voice packet.
LINK_MBPS = 10
MTU_BITS = 1500 * 8
serialize_ms = MTU_BITS / (LINK_MBPS * 1000) # 1.2 ms per full-size packet
backlog_packets = 10 # bulk burst already queued
voice_bits = 200 * 8 # G.711, 20 ms of audio + headers
# FIFO: the voice packet waits behind every byte that arrived before it.
fifo_wait = backlog_packets * serialize_ms
# Priority: it waits only for the packet currently on the wire (non-preemptive).
pq_wait = serialize_ms
print(f"FIFO voice queueing delay: {fifo_wait:5.2f} ms")
print(f"Priority voice queueing delay: {pq_wait:5.2f} ms")
# FIFO voice queueing delay: 12.00 ms
# Priority voice queueing delay: 1.20 ms
# The bulk transfer lost 10.8 ms of completion time out of several seconds;
# the voice call gained 10.8 ms out of a 150 ms end-to-end budget.
# Why the trade is asymmetric: express each cost as a fraction of its own budget.
bulk_transfer_ms = 8_000
print(f"cost to bulk: {100*(fifo_wait-pq_wait)/bulk_transfer_ms:.3f}% of its budget")
print(f"gain to voice: {100*(fifo_wait-pq_wait)/150:.2f}% of its budget")
# cost to bulk: 0.135% of its budget
# gain to voice: 7.20% of its budget
# Sizing a class plan against a real link: does the mix fit, and what starves?
link_mbps = 100
classes = [
# name, offered Mb/s, class, may_starve
("network control", 0.5, "control", False),
("telephony", 8.7, "realtime", False), # 100 G.711 calls
("interactive video", 20.0, "realtime", False),
("low-latency data", 25.0, "elastic", False),
("high-throughput", 60.0, "elastic", False),
("scavenger", 30.0, "elastic", True),
]
offered = sum(c[1] for c in classes)
realtime = sum(c[1] for c in classes if c[2] == "realtime")
protected = sum(c[1] for c in classes if not c[3]) # everything but scavenger
print(f"offered {offered:6.1f} Mb/s on a {link_mbps} Mb/s link "
f"-> {offered/link_mbps:.0%} of capacity")
print(f"realtime {realtime:6.1f} Mb/s -> {realtime/link_mbps:.0%} "
f"(keep under 33%: see Section 12.2 on priority policing)")
print(f"protected {protected:6.1f} Mb/s -> fits: {protected <= link_mbps}")
# offered 144.2 Mb/s on a 100 Mb/s link -> 144% of capacity
# realtime 28.7 Mb/s -> 29% (keep under 33%: see Section 12.2 ...)
# protected 114.2 Mb/s -> fits: False
#
# Conclusion: scavenger absorbs 30 Mb/s of the overload, but 14.2 Mb/s of real
# demand still has nowhere to go. QoS cannot fix this link; only capacity can.
Key takeaways
- QoS has no effect on an uncongested link; it only makes the choice at the moment of congestion deliberate instead of accidental.
- Elastic traffic cares about throughput and treats loss as a signal; inelastic traffic has a delay threshold past which a packet is worthless.
- Voice is loss-tolerant but retransmission-intolerant — the right response to congestion for real-time traffic is to drop, not delay.
- Describe every class with four numbers: bandwidth, one-way delay, jitter, loss tolerance. Merge classes that land in the same region.
- Keep the class count between four and eight, and always define a scavenger class that is allowed to starve.
- If the sum of all non-starvable demand exceeds the link rate, no scheduler can help — that is a capacity problem.
🧪 Practice
- Place these on the delay/loss-tolerance plane and name the class each belongs to: an SSH session, a 4K on-demand stream, a BGP keepalive, an hourly database replication job, a cloud-gaming stream.
- A 10 Mb/s link carries 40 G.711 calls at 87 kb/s each plus one TCP backup. Compute the worst-case FIFO queueing delay if the backup keeps 50 full-size packets buffered, and say whether the calls meet a 150 ms end-to-end budget when propagation alone is 60 ms.
- Write a four-class plan for a branch office running VoIP, a video-conferencing room, business web apps, and nightly backups. For each class give the four requirement numbers and say whether it may starve.
- Interview-style: An engineer proposes marking all of a company's traffic as high priority so nothing is ever delayed. (Hint: ask what the scheduler is actually being told to do when every queue has the same priority, and compare the result with the original FIFO.)
Delay, Jitter, and Loss Budgets
Theory
A requirement like "one-way delay under 150 ms" is a statement about the whole path, but no single device controls the whole path. A budget turns the end-to-end requirement into a set of per-component allowances that can be designed and measured independently, exactly as a mechanical engineer divides a tolerance across a stack of parts. If the parts sum to less than the budget, the system works; if not, the budget says which part to attack.
The canonical figure comes from ITU-T G.114 for interactive voice, measured mouth to ear in one direction:
| One-way delay | Experience |
|---|---|
| < 150 ms | Users notice nothing; normal conversation |
| 150-400 ms | Usable but people begin talking over each other |
| > 400 ms | Unacceptable; speakers fall into walkie-talkie turn-taking |
That budget is consumed by five categories, only some of which a network engineer can change:
end-to-end one-way delay =
codec + packetization (fixed by codec choice)
+ serialization per hop (packet size / link rate)
+ propagation (distance / speed in medium, ~5 us/km in fiber)
+ queueing per hop (the only term QoS controls)
+ dejitter buffer (chosen to absorb the queueing variation)
Propagation is the hard floor and the most commonly forgotten term. Light in fiber travels at roughly 200,000 km/s, which is 5 µs per kilometre, or 1 ms per 200 km of fiber — and real fiber routes are typically 1.3 to 1.5 times the great-circle distance. London to New York is about 5,600 km straight, so roughly 8,000 km of fiber, so about 40 ms one way. No amount of bandwidth, queueing policy, or hardware upgrade changes that number; only moving the endpoints closer does, which is the entire justification for content delivery networks (Section 8.6).
Serialization is the time to clock a packet onto a link, bits / rate. It is negligible on modern core links (1500 bytes on 10 Gb/s is 1.2 µs) and dominant on slow access links (the same packet on a 1 Mb/s uplink is 12 ms). This is why fragmentation and interleaving mattered so much on narrowband WAN circuits and why they are irrelevant in a data centre.
Queueing is the variable term, and it is variable in two senses: it depends on load, and it differs packet to packet. That variation is jitter. Jitter matters because a real-time receiver must play out samples at a constant rate; if packets arrive unevenly, the playout buffer either runs dry (a gap in the audio) or overflows (a discarded sample). The fix is a dejitter buffer that deliberately delays playout by some amount D, converting variable arrival into constant playout. The cost is exact and unavoidable: a dejitter buffer that absorbs D milliseconds of jitter adds D milliseconds of delay. Jitter is therefore not a separate problem from delay; it is a tax paid in delay.
The loss budget works differently because loss is not additive in a useful way for real time. What matters for voice is the loss pattern: 1% of packets lost uniformly at random is concealed almost perfectly by a modern codec, while the same 1% arriving as a single 200 ms burst is an audible dropout. Consecutive losses defeat concealment because the interpolator has nothing recent to interpolate from. This is why tail-drop during a burst (Section 12.2) is worse for voice than the same average loss spread thinly, and why real-time classes want small queues with early, probabilistic discard rather than large queues that overflow all at once.
For elastic traffic, the loss budget is expressed differently again: as throughput. A classic approximation for a loss-based TCP flow gives throughput proportional to MSS / (RTT * sqrt(p)), so loss and RTT together cap a single flow's rate regardless of link capacity. On a 100 ms path, 0.1% loss caps one standard TCP flow at a few tens of Mb/s — which is why a fast link across an ocean often underperforms without either many parallel flows or a loss-insensitive congestion control such as BBR (Section 7.6).
Examples
A voice budget, drawn as a ladder that must fit under 150 ms
(branch office in Milan to a data centre in Frankfurt, ~650 km, ~950 km of fiber)
component ms cumulative
-------------------------------- ----- ----------
codec look-ahead + packetization 20.0 20.0 <- G.711, 20 ms frames
serialization, 2 Mb/s access link 0.8 20.8 <- 200 B at 2 Mb/s
queueing, access link (priority) 1.5 22.3 <- one MTU ahead of us
propagation, Milan -> Frankfurt 4.8 27.1 <- 950 km x 5 us/km
queueing, 5 provider core hops 2.5 29.6 <- 0.5 ms each
serialization, core hops 0.1 29.7
queueing, DC access 0.5 30.2
dejitter buffer 40.0 70.2 <- the largest term!
-------------------------------- ----- ----------
TOTAL one way 70.2 ms budget 150 ms: PASS
headroom 79.8 ms
Where the budget actually goes wrong in practice:
- propagation underestimated (fiber route, not map distance)
- dejitter buffer grown to hide jitter that QoS should have removed
- one uncontrolled hop with a deep FIFO contributing 80+ ms by itself
# Budget arithmetic: propagation floors, serialization, and the jitter tax.
FIBER_US_PER_KM = 5.0 # ~200,000 km/s in glass
ROUTE_FACTOR = 1.45 # real fiber path vs great-circle distance
def propagation_ms(great_circle_km, route_factor=ROUTE_FACTOR):
return great_circle_km * route_factor * FIBER_US_PER_KM / 1000
for name, km in [("Milan-Frankfurt", 640), ("London-New York", 5_570),
("London-Sydney", 16_990)]:
ow = propagation_ms(km)
print(f"{name:16s} one-way {ow:6.1f} ms RTT {2*ow:6.1f} ms "
f"fits 150 ms one-way: {ow < 150}")
# Milan-Frankfurt one-way 4.6 ms RTT 9.3 ms fits 150 ms one-way: True
# London-New York one-way 40.4 ms RTT 80.8 ms fits 150 ms one-way: True
# London-Sydney one-way 123.2 ms RTT 246.4 ms fits 150 ms one-way: True
# London-Sydney leaves only 26.8 ms for EVERYTHING else -> interactive voice
# on that path is inherently marginal, whatever the QoS policy says.
def serialization_ms(packet_bytes, link_mbps):
return packet_bytes * 8 / (link_mbps * 1_000)
for rate in (1, 2, 10, 100, 10_000):
print(f"1500 B at {rate:>6} Mb/s -> {serialization_ms(1500, rate):8.4f} ms")
# 1500 B at 1 Mb/s -> 12.0000 ms <- dominant: one packet blocks a frame
# 1500 B at 2 Mb/s -> 6.0000 ms
# 1500 B at 10 Mb/s -> 1.2000 ms
# 1500 B at 100 Mb/s -> 0.1200 ms
# 1500 B at 10000 Mb/s -> 0.0012 ms <- irrelevant
# Sizing a dejitter buffer from measured arrival times, and paying its cost.
import statistics
# Sender emits every 20 ms; these are measured one-way delays in ms.
one_way = [31, 34, 30, 52, 33, 31, 47, 32, 30, 61, 33, 35, 30, 44, 32]
def buffer_sizing(delays, percentile=0.99):
lo = min(delays)
ordered = sorted(delays)
idx = min(len(ordered) - 1, int(percentile * len(ordered)))
hi = ordered[idx] # ignore the extreme tail on purpose
return lo, hi, hi - lo
lo, hi, jitter = buffer_sizing(one_way)
print(f"min delay {lo} ms, p99 delay {hi} ms, jitter to absorb {jitter} ms")
# The buffer must hold at least `jitter`; playout delay = min delay + buffer.
buffer_ms = jitter
playout = lo + buffer_ms
late = [d for d in one_way if d > playout] # these arrive after their slot
print(f"buffer {buffer_ms} ms -> playout delay {playout} ms, "
f"packets discarded as late: {len(late)}/{len(one_way)} "
f"({100*len(late)/len(one_way):.1f}%)")
# min delay 30 ms, p99 delay 61 ms, jitter to absorb 31 ms
# buffer 31 ms -> playout delay 61 ms, packets discarded as late: 0/15 (0.0%)
# The trade-off, made explicit: a smaller buffer saves delay and costs loss.
for b in (5, 10, 20, 31):
p = lo + b
late_n = sum(1 for d in one_way if d > p)
print(f"buffer {b:2d} ms -> playout {p:2d} ms, late loss {100*late_n/len(one_way):5.1f}%")
# buffer 5 ms -> playout 35 ms, late loss 26.7%
# buffer 10 ms -> playout 40 ms, late loss 26.7%
# buffer 20 ms -> playout 50 ms, late loss 13.3%
# buffer 31 ms -> playout 61 ms, late loss 0.0%
# Reducing jitter in the network is what lets the buffer shrink; that is the
# real reason a real-time class wants a short, well-scheduled queue.
# Why loss PATTERN matters more than loss RATE for concealed audio.
def audible_gaps(pattern, conceal_run=1):
"""A codec conceals runs up to conceal_run packets; longer runs are audible."""
gaps, run = [], 0
for lost in pattern:
if lost:
run += 1
else:
if run > conceal_run:
gaps.append(run)
run = 0
if run > conceal_run:
gaps.append(run)
return gaps
n = 1000
uniform = [i % 100 == 0 for i in range(n)] # 1% spread evenly
bursty = [400 <= i < 410 for i in range(n)] # 1% as one 200 ms burst
print(f"uniform 1%: loss={sum(uniform)/n:.1%} audible gaps={audible_gaps(uniform)}")
print(f"bursty 1%: loss={sum(bursty)/n:.1%} audible gaps={audible_gaps(bursty)}")
# uniform 1%: loss=1.0% audible gaps=[] <- concealed, sounds fine
# bursty 1%: loss=1.0% audible gaps=[10] <- a 200 ms hole: clearly heard
# Identical loss rate on a monitoring dashboard, opposite user experience.
Key takeaways
- Turn every end-to-end requirement into a per-component budget; the budget tells you which component to fix.
- G.114: under 150 ms one way is transparent for voice, 150-400 ms degrades, over 400 ms is unusable.
- Propagation is a floor at roughly 1 ms per 200 km of fiber, and real routes are about 1.4x map distance. Only moving endpoints changes it.
- Serialization dominates on slow access links and is negligible above ~1 Gb/s.
- Queueing is the only term QoS controls, and its variation is jitter.
- A dejitter buffer converts jitter into delay one-for-one: absorbing 40 ms of jitter costs 40 ms of delay.
- For real-time traffic the loss pattern matters more than the loss rate; bursty loss defeats concealment that handles the same rate spread thinly.
🧪 Practice
- Build a one-way delay budget for a voice call from a home DSL user (5 Mb/s up) to a cloud PBX 900 km away, using G.711 with 20 ms frames, three provider hops at 0.5 ms queueing each, and a 30 ms dejitter buffer. State the total and the headroom against 150 ms.
- A monitoring system reports 0.8% loss on a voice class and users complain of "chopping". Explain what measurement you would add to distinguish a design problem from a reporting artefact.
- On a 250 ms RTT satellite path with 0.5% loss, estimate whether a single classic TCP flow can fill a 100 Mb/s link, then name two changes that would help.
- Interview-style: A team reduces average latency on a voice path from 90 ms to 70 ms, but user-reported quality gets worse. (Hint: the average is not what a playout buffer reacts to — ask what happened to the spread, and what the receiver does with a packet that misses its slot.)
Best-Effort vs Guaranteed Service
Theory
"Quality of service" covers a spectrum of promises, and the useful way to organise it is by what the network must know and remember in order to keep each promise. The stronger the guarantee, the more state and the more refusals it requires.
| Service model | Promise | State needed | Refuses traffic? | Where it lives |
|---|---|---|---|---|
| Best effort | none | none | never | the default Internet |
| Overprovisioned best effort | statistical, from headroom | none | never | most enterprise LANs, backbones |
| Relative / differentiated | class A beats class B | per-class (a handful) | no (but re-marks) | DiffServ, enterprise WAN |
| Statistically guaranteed | bound holds for ~99.x% of packets | per-class + admission | yes, at the edge | carrier voice, DS-TE |
| Deterministically guaranteed | bound holds for every packet | per-flow reservation | yes, per flow | IntServ, TSN, AVB |
The crucial insight is that QoS never creates bandwidth. A scheduler is a zero-sum allocator: every millisecond of delay it saves for one class is a millisecond it adds somewhere else. This sounds like a limitation and is actually the source of its value, because application sensitivities are wildly asymmetric — as the earlier arithmetic showed, moving 11 ms from a voice call to a backup costs the backup 0.1% of its budget and buys the call 7% of its own. QoS is profitable precisely because it trades a resource that one class values highly for a resource another class barely notices.
The second insight is that guarantees require the right to say no. If any number of flows may enter, then no per-flow guarantee can survive, because the guarantee's arithmetic depends on the total. This is why deterministic service always comes bundled with admission control, and why the Internet, which by design accepts traffic from anyone, cannot offer end-to-end deterministic service. A restaurant can promise you a table at 8 pm only if it can turn other people away at 8 pm.
The third insight is the statistical multiplexing trade-off, first met in Section 1.4. Reserving peak rate for every flow gives a hard guarantee and wastes most of the link, because flows peak at different times. Reserving less than peak and relying on aggregation gives far higher utilisation and a guarantee that holds "almost always". As the number of independent flows grows, the aggregate becomes smoother relative to its mean, so a fixed safety margin protects a larger and larger multiplex — which is why statistical guarantees work well in a carrier core with thousands of flows and badly on a branch link with three.
This leads to the most important practical judgement in the chapter: overprovisioning versus mechanism. If a link runs at 30% average utilisation with brief bursts, adding a sophisticated QoS policy buys almost nothing, because the queue is nearly always empty; adding a modest amount of capacity, or simply fixing an oversized buffer with an AQM (Section 12.2), buys much more. Conversely, on a link that is genuinely saturated for hours a day, no reasonable amount of extra capacity will protect real-time traffic as cheaply as a priority queue. The honest rule: use capacity where it is cheap, use mechanism where capacity is expensive or where the requirement is absolute. WAN circuits, mobile backhaul, satellite links, and industrial control networks are where mechanism earns its complexity.
Examples
The same 100 Mb/s link under three models, during a 40 Mb/s voice + 200 Mb/s bulk offer
BEST EFFORT (one FIFO)
queue: [B B B V B B B B V B B] voice interleaved with bulk
voice delay = full queue depth -> 30-80 ms, highly variable
bulk throughput = ~60 Mb/s -> both classes degraded, neither protected
DIFFERENTIATED (priority queue for voice, policed at 33 Mb/s)
voice queue: [V V] served first, almost always short
bulk queue: [B B B B B B B B ...] served with what remains
voice delay = 1-2 ms -> protected
bulk throughput = ~67 Mb/s -> unchanged in practice
BUT: offered voice above 33 Mb/s is dropped by the policer, not queued
GUARANTEED (per-flow reservation, admission control)
admitted: 380 calls x 87 kb/s = 33 Mb/s reserved
call 381 -> REJECTED with "network busy" before it starts
voice delay = bounded for every admitted call
the cost of the guarantee is a refusal the user can hear
# QoS reallocates; it does not create. One link, three policies, same demand.
LINK = 100.0 # Mb/s
voice_offer, bulk_offer = 40.0, 200.0
def best_effort(link, v, b):
total = v + b
share = link / total
return v * share, b * share # proportional degradation
def strict_priority(link, v, b, cap=None):
served_v = min(v, cap if cap else link)
return served_v, max(0.0, link - served_v)
def guaranteed(link, v, b, reserved):
admitted_v = min(v, reserved) # excess calls are REJECTED, not degraded
return admitted_v, link - reserved # reservation is held even when idle
for name, (v, b) in {
"best effort": best_effort(LINK, voice_offer, bulk_offer),
"priority (policed 33)": strict_priority(LINK, voice_offer, bulk_offer, 33.0),
"guaranteed (reserve 33)": guaranteed(LINK, voice_offer, bulk_offer, 33.0),
}.items():
print(f"{name:24s} voice {v:6.1f} Mb/s bulk {b:6.1f} Mb/s total {v+b:6.1f}")
# best effort voice 16.7 Mb/s bulk 83.3 Mb/s total 100.0
# priority (policed 33) voice 33.0 Mb/s bulk 67.0 Mb/s total 100.0
# guaranteed (reserve 33) voice 33.0 Mb/s bulk 67.0 Mb/s total 100.0
# Every row sums to 100. The difference is WHO gets the shortfall and HOW they
# learn about it: silent degradation, a policer drop, or an explicit rejection.
# Statistical multiplexing: why guarantees get cheaper as the multiplex grows.
import math
def required_capacity(n_flows, mean_mbps, peak_mbps, sigmas=3.0):
"""Gaussian approximation: mean + safety margin covering n independent flows."""
p = mean_mbps / peak_mbps # activity probability
var = n_flows * peak_mbps**2 * p * (1 - p)
return n_flows * mean_mbps + sigmas * math.sqrt(var)
MEAN, PEAK = 0.2, 2.0 # a bursty 2 Mb/s video source
for n in (1, 10, 100, 1000):
peak_alloc = n * PEAK
stat_alloc = required_capacity(n, MEAN, PEAK)
print(f"{n:5d} flows: peak-reserve {peak_alloc:8.1f} Mb/s "
f"statistical {stat_alloc:8.1f} Mb/s gain {peak_alloc/stat_alloc:5.2f}x")
# 1 flows: peak-reserve 2.0 Mb/s statistical 2.0 Mb/s gain 1.00x
# 10 flows: peak-reserve 20.0 Mb/s statistical 7.7 Mb/s gain 2.60x
# 100 flows: peak-reserve 200.0 Mb/s statistical 38.0 Mb/s gain 5.26x
# 1000 flows: peak-reserve 2000.0 Mb/s statistical 256.9 Mb/s gain 7.78x
# A branch link with 1 flow gains nothing from statistical sharing, so it needs
# either peak reservation or real mechanism. A core with 1000 gains ~8x for free.
Key takeaways
- Service models form a ladder from best effort to deterministic guarantees, ordered by how much state the network keeps and whether it may refuse traffic.
- A scheduler is zero-sum: it moves delay and loss between classes. It is worth doing because application sensitivities are asymmetric, not because it adds capacity.
- No guarantee without admission control. Unbounded admission invalidates any per-flow bound.
- Statistical multiplexing gain grows with the size of the multiplex, so statistical guarantees are cheap in a core and expensive on a small link.
- Prefer capacity where it is cheap and mechanism where it is not; a link at 30% utilisation rarely benefits from an elaborate policy.
- The guarantee's visible cost is a refusal — a busy signal is a feature of a network that keeps its promises.
🧪 Practice
- For each, pick the weakest service model that suffices and justify it: a factory robot control loop, a call centre's VoIP, a university residence network, a stock exchange feed handler.
- A 1 Gb/s campus uplink averages 220 Mb/s with 700 Mb/s peaks. Argue for or against deploying an eight-class QoS policy, and name the cheaper intervention.
- Using the statistical multiplexing model above, compute how much capacity 250 flows of mean 0.5 Mb/s and peak 4 Mb/s need at three sigma, and compare it with peak reservation.
- Interview-style: Management asks you to guarantee that video conferencing "always works" without ever blocking a user from starting a call. (Hint: these two requirements are in direct conflict — identify which of the three insights above applies, and what you can offer instead.)
Service Level Agreements
Theory
An SLA is where QoS stops being an engineering preference and becomes a number someone can be held to. The reason to study its structure is not legal but technical: almost every SLA dispute is a disagreement about definitions, not about the network. A provider reporting 99.99% availability and a customer reporting three outages last month can both be correct if they measure different things.
Three terms are routinely conflated and should not be:
| Term | What it is | Example |
|---|---|---|
| SLI (indicator) | the measurement itself | p95 round-trip time between two PE routers, sampled every 5 minutes |
| SLO (objective) | the internal target for that indicator | p95 RTT < 40 ms in 99.9% of 5-minute windows per month |
| SLA (agreement) | the contract, including consequences | if the SLO is missed, 10% of the monthly fee is credited |
An SLO is a target you choose; an SLA is a promise with teeth. Good practice is to set internal SLOs stricter than the contracted SLA, so that the alarm fires before the penalty does.
Every SLI needs five properties specified, and each is a place where honest parties can diverge:
- Metric and statistic. "Latency under 50 ms" is meaningless without a statistic. A mean hides the tail that users feel; a maximum is hostage to one bad sample. Percentiles (p95, p99) are the workable compromise, and the percentile must be stated.
- Measurement interval and aggregation. Is the objective evaluated per 5-minute window, per hour, or as one monthly average? A monthly average of loss can hide a complete 30-minute outage. Shorter windows are stricter.
- Scope. Provider SLAs almost always cover edge to edge (their own ingress PE to their own egress PE), not end to end. The customer's own LAN, the access circuit, and any third-party network are excluded — which is often exactly where the problem is.
- Direction and path. Delay is one-way for real time but usually measured as RTT. Asymmetric routing means the two directions can have different loss.
- Exclusions. Scheduled maintenance windows, force majeure, customer-caused faults, and traffic exceeding the contracted rate are typically excluded; traffic above the committed rate has no SLA at all.
Availability deserves its own arithmetic because the "number of nines" is unintuitive:
| Availability | Downtime per month | Downtime per year |
|---|---|---|
| 99% | 7 h 18 m | 3 d 15 h |
| 99.9% | 43 m 28 s | 8 h 46 m |
| 99.95% | 21 m 44 s | 4 h 23 m |
| 99.99% | 4 m 21 s | 52 m 36 s |
| 99.999% | 26 s | 5 m 15 s |
Availability relates to failure statistics as MTBF / (MTBF + MTTR). The practical consequence is that reducing repair time is usually cheaper than increasing time between failures: halving MTTR from 4 hours to 2 hours improves availability exactly as much as doubling MTBF, and is generally achieved with monitoring, spares, and runbooks rather than hardware.
Two rate constructs appear in nearly every network contract and are worth knowing precisely. CIR and PIR (committed and peak information rate) split traffic into a guaranteed portion and a best-effort excess: traffic within CIR carries the SLA, traffic between CIR and PIR is forwarded if capacity allows and may be re-marked for earlier discard, and traffic above PIR is dropped. 95th-percentile billing charges on the 95th percentile of 5-minute average throughput samples over the month, which effectively gives the customer the busiest ~36 hours of the month for free — a strong incentive to schedule bulk transfers into short, intense windows rather than spreading them.
Examples
A service definition, written so both sides measure the same thing
SERVICE : Managed IP VPN, 200 Mb/s port, 4 classes
SCOPE : PE-to-PE between sites MIL01 and FRA02 (customer LAN excluded)
MEASUREMENT : synthetic probes, 100 B, 1 per second, both directions
WINDOW : 5-minute aggregation; monthly compliance = 99.9% of windows
class rate delay (p95, RTT) loss (p95) jitter (p95)
---------- ---------- ---------------- ------------ ------------
realtime CIR 30 Mb/s <= 20 ms <= 0.05% <= 5 ms
business CIR 80 Mb/s <= 40 ms <= 0.10% n/a
default CIR 60 Mb/s <= 60 ms <= 0.50% n/a
scavenger PIR 200 Mb/s no SLA no SLA n/a
AVAILABILITY: 99.95% monthly, per site pair
EXCLUSIONS : notified maintenance (<= 8 h/month, 01:00-05:00 local),
traffic above CIR in its class, customer equipment, access loop
REMEDY : 5% monthly fee credit per 0.1% availability below target,
capped at 50%; credits require a ticket within 30 days
# Availability arithmetic and the MTTR lever.
SEC_PER_MONTH = 30 * 24 * 3600
def downtime(avail_pct, period=SEC_PER_MONTH):
s = period * (1 - avail_pct / 100)
return f"{int(s//3600)}h {int(s%3600//60)}m {int(s%60)}s"
for a in (99, 99.9, 99.95, 99.99, 99.999):
print(f"{a:7.3f}% -> {downtime(a):>12s} per 30-day month")
# 99.000% -> 7h 12m 0s per 30-day month
# 99.900% -> 0h 43m 11s per 30-day month
# 99.950% -> 0h 21m 35s per 30-day month
# 99.990% -> 0h 4m 19s per 30-day month
# 99.999% -> 0h 0m 25s per 30-day month
def availability(mtbf_h, mttr_h):
return 100 * mtbf_h / (mtbf_h + mttr_h)
base = availability(2000, 4)
print(f"baseline MTBF 2000 h, MTTR 4 h -> {base:.4f}% ({downtime(base)})")
print(f"halve MTTR MTBF 2000 h, MTTR 2 h -> {availability(2000,2):.4f}%")
print(f"double MTBF MTBF 4000 h, MTTR 4 h -> {availability(4000,4):.4f}%")
# baseline MTBF 2000 h, MTTR 4 h -> 99.8004% (1h 26m 13s)
# halve MTTR MTBF 2000 h, MTTR 2 h -> 99.9001%
# double MTBF MTBF 4000 h, MTTR 4 h -> 99.9001%
# Identical gain. Faster repair is usually far cheaper than better hardware.
# Why the statistic and the window decide compliance, not the network.
import random
random.seed(7)
# 8,640 five-minute windows in a 30-day month; one 35-minute total outage.
windows = [random.gauss(18, 3) for _ in range(8_640)] # RTT in ms, healthy
for i in range(4_000, 4_007): # 7 windows = 35 min
windows[i] = 400.0 # degraded / down
def pct(values, p):
s = sorted(values)
return s[min(len(s) - 1, int(p * len(s)))]
target = 40.0
monthly_mean = sum(windows) / len(windows)
bad_windows = sum(1 for w in windows if w > target)
compliant_pct = 100 * (1 - bad_windows / len(windows))
print(f"monthly MEAN RTT : {monthly_mean:6.2f} ms -> "
f"meets 40 ms: {monthly_mean <= target}")
print(f"monthly p95 RTT : {pct(windows, 0.95):6.2f} ms")
print(f"monthly p99.9 RTT : {pct(windows, 0.999):6.2f} ms")
print(f"monthly p99.95 RTT : {pct(windows, 0.9995):6.2f} ms")
print(f"windows over 40 ms : {bad_windows} of {len(windows)}")
print(f"window compliance : {compliant_pct:.4f}% -> "
f"meets 99.9%: {compliant_pct >= 99.9}")
# monthly MEAN RTT : 18.34 ms -> meets 40 ms: True
# monthly p95 RTT : 23.00 ms
# monthly p99.9 RTT : 27.87 ms
# monthly p99.95 RTT : 400.00 ms
# windows over 40 ms : 7 of 8640
# window compliance : 99.9190% -> meets 99.9%: True
#
# The 35-minute outage is 0.081% of the month, so it hides below p99.9 and
# appears only at p99.95. The monthly mean hides it completely. The provider's
# report says "fine"; the customer who was cut off disagrees. Neither is lying:
# the chosen statistic, not the network, decided the answer.
# 95th-percentile billing: the free allowance is monthly, not daily.
def bill_mbps(samples_5min):
s = sorted(samples_5min)
return s[int(0.95 * len(s)) - 1] # discard the top 5% of samples
n = 8_640 # 5-minute samples in a 30-day month
baseline = [60.0] * n # steady business traffic
free_samples = int(0.05 * n)
print(f"discarded samples: {free_samples} = {free_samples * 5 / 60:.0f} hours/month")
spread = [x + 50.0 for x in baseline] # +50 Mb/s continuously
nightly = list(baseline) # +600 Mb/s for 2 h every night
for day in range(30):
for k in range(24): # 24 samples = 2 hours
nightly[day * 288 + k] += 600.0
monthly = list(baseline) # +600 Mb/s for one 30 h window
for k in range(360): # 360 samples = 30 hours
monthly[5_000 + k] += 600.0
for label, series in (("steady +50 Mb/s", spread),
("nightly 2 h burst", nightly),
("one 30 h window", monthly)):
above = sum(1 for x in series if x > 60.0)
print(f"{label:20s} peaks in {above:4d} samples "
f"({above/n:5.1%} of month) -> billed at {bill_mbps(series):6.1f} Mb/s")
# discarded samples: 432 = 36 hours/month
# steady +50 Mb/s peaks in 8640 samples (100.0% of month) -> billed at 110.0 Mb/s
# nightly 2 h burst peaks in 720 samples ( 8.3% of month) -> billed at 660.0 Mb/s
# one 30 h window peaks in 360 samples ( 4.2% of month) -> billed at 60.0 Mb/s
#
# The nightly job is billed at its PEAK, because 2 h x 30 days = 60 h exceeds the
# 36 h allowance. The same traffic in a single 30 h window is free. The lesson is
# not "burst harder" but "fit inside 36 hours per month, counted across the month".
Key takeaways
- Separate SLI (the measurement), SLO (your target), and SLA (the contract with consequences); set the SLO stricter than the SLA.
- Most SLA disputes are definitional. Always pin down statistic, window, scope, direction, and exclusions.
- A mean can hide a total outage; percentiles plus a short evaluation window are what make an objective meaningful.
- Provider SLAs are typically edge to edge, excluding the customer LAN and access loop — the segments where faults are most common.
- Availability is
MTBF / (MTBF + MTTR), so halving repair time equals doubling reliability and usually costs far less. - CIR carries the SLA; traffic above it does not. Above PIR, traffic is dropped.
- 95th-percentile billing discards the busiest ~36 hours of the month, so one long bulk window can be free while a nightly job of the same total volume is billed at its peak.
🧪 Practice
- Rewrite the requirement "latency must stay below 50 ms" as a complete SLI with statistic, window, scope, and direction.
- A provider offers 99.99% availability but excludes up to 12 hours of monthly maintenance. Compute the worst-case real monthly downtime and compare it with an unqualified 99.9% offer.
- Describe the computation for a 95th-percentile bill from 5-minute samples, then decide which is cheaper for the same 90 TB per month: a 3-hour nightly replication job, or a single 36-hour window once a month. Show the sample counts.
- Interview-style: Your dashboard shows the voice class met its 0.05% loss SLO every month last year, yet the support queue is full of complaints about dropped audio. (Hint: two of the five SLI properties are the usual culprits here — think about what an average over a long window conceals, and about which part of the path the probes actually traverse.)
<a id="122-traffic-management-mechanisms"></a>
12.2 Traffic Management Mechanisms
A QoS policy is assembled from a small set of primitives that appear in every vendor's implementation under slightly different names: this subchapter covers how packets are sorted into classes, how rates are enforced by discarding or by delaying, the token bucket formalism that underlies both, the schedulers that decide transmission order, the queue managers that decide what to discard before the buffer fills, and the admission logic that keeps guarantees honest by refusing work.
Classification and Marking
Theory
Every QoS action needs to know which class a packet belongs to, and there are only two ways to find out: inspect the packet's contents, or read a label someone already attached. Inspecting is expensive and fragile — a core router forwarding 400 Gb/s cannot afford to parse application payloads, and increasingly cannot read them at all because they are encrypted. Labelling is cheap: one field lookup per packet.
This produces the central architectural pattern of practical QoS: classify once at the edge, act everywhere. The first device that touches the traffic does the expensive work — matching on ports, addresses, application signatures, or interface — and writes the result into the packet as a marking. Every device thereafter reads only the marking. It is the same principle as a warehouse putting a coloured sticker on a parcel at intake so that no one downstream has to open the box.
A marking is a small integer carried in a header field. The fields available differ by layer:
| Layer | Field | Bits | Values | Notes |
|---|---|---|---|---|
| Ethernet (802.1Q) | PCP (priority code point) | 3 | 0-7 | Requires a VLAN tag; lost on untagged links |
| MPLS | Traffic Class (formerly EXP) | 3 | 0-7 | What an MPLS core actually schedules on |
| IPv4 | DSCP, in the former ToS byte | 6 | 0-63 | The primary marking (RFC 2474) |
| IPv6 | DSCP, in the Traffic Class byte | 6 | 0-63 | Identical semantics to IPv4 |
| IPv4/IPv6 | ECN | 2 | 0-3 | Shares the same byte as DSCP; see RFC 3168 |
The DSCP is the one that matters. It replaced the original IPv4 "Type of Service" bits, occupies the top six bits of that byte, and leaves the bottom two for ECN. Standard codepoint names exist so that an operator writing a policy and a vendor shipping a default template mean the same thing:
| Name | DSCP | Typical use |
|---|---|---|
| CS0 / DF (default) | 0 | best effort |
| CS1 | 8 | scavenger, lower than best effort |
| AF11-AF43 | 10-38 | four classes x three drop precedences |
| CS3 | 24 | signalling (SIP) |
| CS6 | 48 | network control (routing protocols) |
| EF | 46 | expedited forwarding: telephony bearer |
| VOICE-ADMIT | 44 | EF-equivalent, admitted by CAC (RFC 5865) |
Note the information-loss problem in the table of fields: DSCP has 6 bits, but 802.1p and MPLS have only 3. A 64-value marking cannot survive intact across an Ethernet or MPLS segment, so operators define an explicit mapping, conventionally the top three bits (dscp >> 3), and accept that AF11 and AF13 become indistinguishable inside the MPLS core. Any design that relies on drop-precedence distinctions must check whether they survive every segment.
The second essential concept is the trust boundary. A marking is only meaningful if you know who wrote it, and an end host can write any DSCP it likes — a user's game client marking itself EF would otherwise be promoted into the priority queue ahead of the company's telephony. The rule is therefore: do not trust markings from outside your administrative control. At the boundary you either re-mark unconditionally (overwrite with a value you determine by inspection) or conditionally trust a narrow set of values from known devices, such as accepting EF only from IP phones identified by their voice VLAN. Service providers commonly go further and bleach customer markings — reset everything to 0 — at ingress, then re-mark according to the contracted class. This is why a DSCP set by an application on one side of the Internet almost never arrives intact on the other.
Classification itself comes in three flavours, in increasing cost:
- Interface or VLAN based: everything from the voice VLAN is telephony. Cheap and robust.
- Multi-field (MF): match on the 5-tuple — source and destination address, protocol, ports. The workhorse, though ports are unreliable identifiers for modern applications.
- Deep inspection / application recognition: examine payload patterns or behaviour. Powerful, expensive, and defeated by TLS; usable only for traffic you terminate or for heuristic classification of flow shape.
Examples
The ToS / Traffic Class byte, and where the trust boundary sits
IPv4 header, byte 1:
bit 7 6 5 4 3 2 1 0
+---+---+---+---+---+---+ +---+---+
| DSCP (6 bits) | | ECN |
+---+---+---+---+---+---+ +---+---+
\___ 0..63, RFC 2474 __/ \_ RFC 3168
EF = 101110 = 46 -> whole byte 0xB8 with ECN=00
Where classification and marking happen:
[ PC ]--+ UNTRUSTED
[phone]-+--[ access switch ]===============||=====[ router ]---[ WAN ]
^ trust boundary ^
| |
classify by VLAN/port, WRITE DSCP, READ DSCP only,
overwrite whatever the PC claimed apply queueing policy
Provider edge behaviour:
[ customer ]--->| PE ingress |---> bleach to 0, re-mark per contract
(this is why end-to-end DSCP rarely
survives the public Internet)
# The DSCP field lives in the top 6 bits of the IPv4 ToS / IPv6 Traffic Class byte.
def tos_byte(dscp, ecn=0):
return (dscp << 2) | ecn # DSCP occupies bits 7..2, ECN bits 1..0
def decode(tos):
return tos >> 2, tos & 0b11 # -> (dscp, ecn)
NAMES = {0: "CS0/default", 8: "CS1/scavenger", 18: "AF21",
34: "AF41", 46: "EF/telephony", 48: "CS6/network-control"}
for dscp in (0, 8, 18, 34, 46, 48):
tos = tos_byte(dscp)
print(f"DSCP {dscp:2d} ({dscp:06b}) {NAMES[dscp]:20s} "
f"ToS byte 0x{tos:02x} L2 CoS (dscp>>3) = {dscp >> 3}")
# DSCP 0 (000000) CS0/default ToS byte 0x00 L2 CoS (dscp>>3) = 0
# DSCP 8 (001000) CS1/scavenger ToS byte 0x20 L2 CoS (dscp>>3) = 1
# DSCP 18 (010010) AF21 ToS byte 0x48 L2 CoS (dscp>>3) = 2
# DSCP 34 (100010) AF41 ToS byte 0x88 L2 CoS (dscp>>3) = 4
# DSCP 46 (101110) EF/telephony ToS byte 0xb8 L2 CoS (dscp>>3) = 5
# DSCP 48 (110000) CS6/network-control ToS byte 0xc0 L2 CoS (dscp>>3) = 6
# ^ note: AF11(10) and AF13(14) both map to CoS 1 -> drop precedence
# is LOST on an 802.1p or MPLS segment.
# AF codepoints follow a formula: AFxy = 8x + 2y (x = class 1..4, y = drop pref 1..3)
for x in range(1, 5):
print(f"class {x}: " + " ".join(f"AF{x}{y}={8*x + 2*y:2d}" for y in range(1, 4)))
# class 1: AF11=10 AF12=12 AF13=14
# class 2: AF21=18 AF22=20 AF23=22
# class 3: AF31=26 AF32=28 AF33=30
# class 4: AF41=34 AF42=36 AF43=38
# ECN shares the byte, so a re-marking policy must preserve the low two bits.
for name, ecn in (("Not-ECT", 0b00), ("ECT(0)", 0b10), ("CE", 0b11)):
tos = tos_byte(46, ecn)
print(f"EF + {name:8s} -> ToS 0x{tos:02x} decodes to {decode(tos)}")
# EF + Not-ECT -> ToS 0xb8 decodes to (46, 0)
# EF + ECT(0) -> ToS 0xba decodes to (46, 2)
# EF + CE -> ToS 0xbb decodes to (46, 3)
# --- Linux: classify and mark at the edge (nftables / iptables mangle) ---
# Mark by destination port: SIP signalling -> CS3, RTP media range -> EF.
iptables -t mangle -A POSTROUTING -p udp --dport 5060 -j DSCP --set-dscp-class cs3
iptables -t mangle -A POSTROUTING -p udp --dport 16384:32767 -j DSCP --set-dscp-class ef
# Mark by source (a known device), not by what the packet claims.
iptables -t mangle -A PREROUTING -s 10.20.30.0/24 -j DSCP --set-dscp-class af41
# TRUST BOUNDARY: bleach everything arriving from an untrusted segment FIRST,
# so that later rules cannot be pre-empted by a client marking itself EF.
iptables -t mangle -I PREROUTING -i eth1 -j DSCP --set-dscp 0
# --- Verify on the wire: DSCP 46 -> ToS 0xb8 ---
tcpdump -ni eth0 -v 'ip[1] & 0xfc == 0xb8' -c 5 # match DSCP bits only, ignore ECN
# IP (tos 0xb8,ECT(0)... ) <- tcpdump prints the whole byte; mask before comparing
# Match DSCP in a tc filter (dsfield is the full byte, so mask off ECN with 0xfc)
tc filter add dev eth0 parent 1: protocol ip prio 1 \
u32 match ip dsfield 0xb8 0xfc flowid 1:10
Key takeaways
- Classify once at the edge, act everywhere: expensive inspection happens at the first hop, and every later hop reads a cheap label.
- DSCP (6 bits, top of the old ToS byte) is the primary marking; ECN occupies the low 2 bits of the same byte, so never overwrite the whole byte carelessly.
- Memorise the anchors: EF = 46 (telephony), CS6 = 48 (network control), CS3 = 24 (signalling), CS1 = 8 (scavenger), AFxy = 8x + 2y.
- 802.1p and MPLS carry only 3 bits, so mapping down from DSCP loses drop precedence. Verify that any distinction you rely on survives every segment.
- Define a trust boundary: re-mark or bleach anything from outside your control, because hosts can mark themselves anything.
- Provider edges routinely bleach DSCP, which is why markings rarely survive the public Internet.
🧪 Practice
- Give the full ToS byte in hexadecimal for AF31 with ECT(0) set, and for EF with no ECN support.
- An access switch maps DSCP to 802.1p using
dscp >> 3. List which of AF21, AF22, AF23, and CS2 become indistinguishable, and state one design consequence.- Write the ordered rule set for a branch router that trusts EF only from the voice VLAN, marks the ERP server's traffic AF31, marks a backup subnet CS1, and bleaches everything else from the user VLAN. Explain why rule order matters.
- Interview-style: A customer insists their application marks packets EF and the provider must honour it end to end. (Hint: think about who is able to write that field, what the provider's edge typically does to it, and what contract would have to exist for the request to be meaningful.)
Policing vs Shaping
Theory
Both policing and shaping answer the question "this traffic must not exceed R bits per second", and they differ in exactly one respect: what they do with the excess. A policer has no buffer, so non-conforming packets are dropped or re-marked immediately. A shaper has a buffer, so non-conforming packets are delayed until they conform. That single difference determines everything else about where each belongs.
The analogy is a busy restaurant. A policer is a doorman who turns away anyone arriving when the restaurant is full: the arrival rate is enforced exactly, nobody waits, and some customers simply do not get in. A shaper is a queue rope outside: everyone eventually gets in, the rate through the door is smooth, and the cost is waiting. Neither creates tables.
| Policer | Shaper | |
|---|---|---|
| Excess traffic | dropped or re-marked | buffered and delayed |
| Adds delay | no | yes, potentially a lot |
| Needs memory | no | yes, a queue per shaped class |
| Output pattern | bursty (passes bursts up to the burst size) | smooth |
| Typical direction | ingress (and egress) | egress only |
| Effect on TCP | loss -> window halving, retransmission | growing RTT, no retransmission |
| Cost of misconfiguration | unnecessary loss, throughput collapse | bufferbloat, latency for everyone in the class |
The TCP interaction is the practical heart of the matter. A policer set to 10 Mb/s on a link carrying TCP does not produce a smooth 10 Mb/s; it produces a sawtooth that averages well below 10 Mb/s, because every burst that exceeds the token budget causes loss, every loss halves a sender's window, and the sender then spends a round trip or more recovering. Measured throughput under a policer is routinely 20-30% below the configured rate for long-RTT flows. A shaper set to the same rate delivers close to 10 Mb/s, because TCP's window naturally grows to fill the pipe and the queue absorbs the bursts. This is the single most common reason a customer reports "we pay for 100 Mb/s and only get 70".
That leads to the standard deployment rule. Police at ingress from a party you do not control, because you want to enforce a limit without dedicating buffer to someone else's excess, and because delaying traffic you are about to reject is pointless. Shape at egress toward a bottleneck, especially in the classic case where a downstream device (a provider's edge) will police your traffic. Shaping to just below the policed rate converts what would have been provider-side drops into your own buffering, where you control which class waits — this is called shaping to a policed rate and is the reason nearly every branch router egress policy starts with a parent shaper.
A second, subtler use of shaping is the sub-rate physical link: a router with a Gigabit Ethernet port connected to a service that delivers 200 Mb/s has no way to know about the limit from the physical layer. Its queues will never fill, because the interface believes it can send at 1 Gb/s, so no queueing policy inside the router ever takes effect. A parent shaper at 200 Mb/s recreates the congestion point inside the router, where the scheduler can manage it. Without it, the entire class-based policy underneath is inert — a genuinely common and confusing failure.
Finally, policers can re-mark instead of drop, which is much gentler. Traffic within the committed rate keeps its marking; excess traffic is re-marked to a higher drop precedence (AF21 becomes AF23) and forwarded. It is discarded later only if a downstream queue is actually congested. This is the mechanism behind CIR/PIR contracts and the colour-marking schemes in the next topic.
Examples
Same 25 Mb/s burst offered to a 10 Mb/s limit, output over time
POLICER (burst 16 kB)
offered |#########################| 25 Mb/s for 50 ms
output |####| |####| |####| passes bursts, then drops
verdict pass pass DROP DROP pass DROP ...
delay added: 0 ms discarded: ~50%
SHAPER (queue 200 kB)
offered |#########################|
output |##########################################| smooth 10 Mb/s,
runs past the burst
delay added: up to 76 ms discarded: 0%
Where each belongs:
[ customer ]--->| PE ingress: POLICE to contract |--->[ provider core ]
drop/re-mark what exceeds CIR
[ branch LAN ]--->| CE egress: SHAPE to 0.95 x CIR |--->[ 200 Mb/s service ]
queue locally, choose who waits,
so the PE policer never has to drop
# Policer vs shaper on the SAME offered burst: one drops, the other delays.
CONFIG_MBPS = 10.0 # the rate both mechanisms enforce
POLICER_BURST = 16_000 # bytes of credit the policer tolerates
SHAPER_QUEUE = 200_000 # bytes of buffer the shaper may use
def policer(packets, rate_mbps, burst_bytes):
"""No buffer: a packet either fits in the token budget or is discarded."""
byte_rate = rate_mbps * 1e6 / 8
tokens = float(burst_bytes)
passed = dropped = 0
prev = packets[0][0]
for t, size in packets:
tokens = min(burst_bytes, tokens + byte_rate * (t - prev)) # refill
prev = t
if tokens >= size:
tokens -= size
passed += size
else:
dropped += size # no queue: drop
return passed, dropped, 0.0
def shaper(packets, rate_mbps, queue_limit_bytes):
"""Buffer: packets wait for a transmission slot; only overflow is discarded."""
byte_rate = rate_mbps * 1e6 / 8
queue, passed, dropped, max_delay = 0.0, 0, 0, 0.0
prev = packets[0][0]
for t, size in packets:
queue = max(0.0, queue - byte_rate * (t - prev)) # drain
prev = t
if queue + size <= queue_limit_bytes:
queue += size
passed += size
max_delay = max(max_delay, queue / byte_rate) # head-of-line wait
else:
dropped += size # tail drop
return passed, dropped, max_delay * 1000
# Offer 50 ms of traffic at 25 Mb/s: 2.5x the configured rate.
pkts, t, gap = [], 0.0, 1500 * 8 / 25e6
while t < 0.050:
pkts.append((t, 1500))
t += gap
offered = sum(s for _, s in pkts)
print(f"offered: {offered*8/1e6:.2f} Mb in 50 ms = {offered*8/1e6/0.050:.1f} Mb/s "
f"against a {CONFIG_MBPS:.0f} Mb/s limit")
for name, (p, d, delay) in (
("policer", policer(pkts, CONFIG_MBPS, POLICER_BURST)),
("shaper", shaper(pkts, CONFIG_MBPS, SHAPER_QUEUE))):
print(f"{name:8s} delivered {p*8/1e6:5.2f} Mb discarded {100*d/(p+d):5.1f}% "
f"worst added delay {delay:6.2f} ms")
# offered: 1.26 Mb in 50 ms = 25.2 Mb/s against a 10 Mb/s limit
# policer delivered 0.62 Mb discarded 50.5% worst added delay 0.00 ms
# shaper delivered 1.26 Mb discarded 0.0% worst added delay 76.08 ms
#
# Identical long-run rate, opposite cost:
# policer -> TCP sees loss, halves its window, retransmits
# shaper -> TCP sees delay, its RTT estimate grows, nothing is retransmitted
# --- Policing on Linux: a hard ingress limit, excess is dropped ---
tc qdisc add dev eth0 handle ffff: ingress
tc filter add dev eth0 parent ffff: protocol ip prio 1 u32 match u32 0 0 \
police rate 10mbit burst 16k drop
# --- Shaping on Linux: TBF delays instead of dropping ---
# rate = enforced rate, burst = token bucket depth, latency = max queueing delay
tc qdisc add dev eth0 root tbf rate 10mbit burst 16k latency 70ms
# --- The important real-world pattern: a parent shaper on a sub-rate link ---
# GigE port, but the service only delivers 200 Mb/s. Without this shaper the
# interface queue never fills and every class policy below it is inert.
tc qdisc add dev eth0 root handle 1: htb default 30
tc class add dev eth0 parent 1: classid 1:1 htb rate 190mbit ceil 190mbit
# ^ 95% of 200: leave headroom
# so the PE policer never drops
tc class add dev eth0 parent 1:1 classid 1:10 htb rate 60mbit ceil 190mbit prio 0
tc class add dev eth0 parent 1:1 classid 1:20 htb rate 100mbit ceil 190mbit prio 1
tc class add dev eth0 parent 1:1 classid 1:30 htb rate 30mbit ceil 190mbit prio 2
tc qdisc add dev eth0 parent 1:10 fq_codel # keep per-class queues short
# Verify: rising "dropped" on the policer, rising "backlog" on the shaper.
tc -s qdisc show dev eth0
tc -s class show dev eth0
Key takeaways
- Policing and shaping enforce the same rate; the difference is that a policer drops or re-marks while a shaper buffers and delays.
- A policer adds no delay and needs no memory; a shaper needs a queue and adds latency proportional to its depth.
- A policer applied to TCP produces throughput well below the configured rate, because each burst causes loss and window halving. This is the classic "we pay for 100 and get 70" complaint.
- Police at ingress from parties you do not control; shape at egress toward a bottleneck, especially one that will police you.
- On a sub-rate link (GigE port, 200 Mb/s service), a parent shaper is mandatory — without it, the congestion point is outside the router and the whole class policy does nothing.
- Re-marking instead of dropping makes a policer far gentler: excess is forwarded and discarded only if a later queue is genuinely congested.
🧪 Practice
- A branch has a 50 Mb/s circuit that the provider polices. Choose policing or shaping for the branch router's egress, give the rate you would configure, and justify both choices.
- Explain, step by step, why a 100 Mb/s ingress policer yields about 70 Mb/s of TCP goodput on a 100 ms path but nearly 100 Mb/s on a 1 ms path.
- Compute the maximum delay a shaper adds when configured at 5 Mb/s with a 100 kB queue, then state the queue size that would cap added delay at 50 ms.
- Interview-style: An engineer configures a full eight-class priority policy on a router's Gigabit interface facing a 300 Mb/s metro Ethernet service. Traffic tests show the policy has no effect whatsoever. (Hint: ask where the packets are actually queueing, and whether the router believes the link is congested.)
Token Bucket and Leaky Bucket
Theory
Policers and shapers both need a precise definition of "conforming", and two formalisms supply it. They are frequently confused, and the distinction is worth getting right because it is about whether bursts are permitted.
The leaky bucket is a bucket with a hole in the bottom. Packets pour in and drain out at a constant rate; if the bucket overflows, the excess is lost. Its output is perfectly smooth — one packet every 1/r seconds, no exceptions. It is a shaper by nature, and its defining property is that no burst ever leaves it, however long the input was idle.
The token bucket inverts the picture: the bucket holds permits, not packets. Tokens arrive at a constant rate r and accumulate up to a maximum depth b. To send a packet of size L, a sender must remove L tokens; if there are not enough, the packet is non-conforming. Its defining property is that idleness earns credit: a source silent long enough to fill the bucket may then transmit a burst of up to b bytes at full line rate. The formal guarantee is an upper bound on cumulative arrivals:
A(t) <= r*t + b for every interval of length t
which reads: over any window, a conforming source sends no more than the long-run rate times the window, plus one bucket's worth of burst. This inequality is the contract that the IntServ delay bound in Section 12.3 is built on.
A useful analogy: the leaky bucket is a metronome, and the token bucket is a prepaid phone plan. The metronome permits exactly one note per beat no matter how long you rested. The phone plan lets unused minutes accumulate to a cap, so a quiet month funds a long call.
Which you want depends on the traffic. Real applications are bursty — a web page is a flight of objects, a database query returns a batch — and a leaky bucket would delay every burst even on a link that was idle a moment earlier. That is why the token bucket, with its explicit burst allowance, is what essentially all real implementations use. b is the tuning knob: too small and normal bursts are penalised (and TCP throughput collapses); too large and the burst can momentarily swamp downstream buffers. A common sizing rule sets the burst to the traffic sent in one scheduling interval, Bc = CIR * Tc, with Tc typically a few milliseconds, and a widely used practical floor is the bandwidth-delay product of the path, or at minimum a few MTUs.
Two buckets together give a three-way verdict instead of pass/fail, which is how CIR/PIR contracts are implemented. The two standard schemes:
| Scheme | RFC | Parameters | Colour semantics |
|---|---|---|---|
| srTCM (single rate, three colour) | 2697 | CIR, CBS, EBS | green within CBS, yellow within EBS, red beyond. Measures burst size excess |
| trTCM (two rate, three colour) | 2698 | CIR, CBS, PIR, PBS | green within CIR, yellow up to PIR, red above PIR. Measures rate excess |
The colours then drive action: green is forwarded with the contracted marking, yellow is forwarded but re-marked to a higher drop precedence (so it is the first casualty if a downstream queue congests), and red is discarded at the edge. This is the mechanism that makes a "50 Mb/s committed, 200 Mb/s peak" product implementable. Both schemes also have a colour-aware mode, in which an upstream device's verdict is taken as input, so a packet already marked yellow can never be promoted back to green.
Examples
The two buckets, side by side
LEAKY BUCKET (a queue that drains at r) TOKEN BUCKET (a store of permits)
packets in tokens in at rate r
| | | | | |
v v v v v v
+---------+ +---------+
| ##### | <- overflow is dropped | ooooo | <- depth b; tokens
| ##### | | ooooo | beyond b are lost
+----o----+ +---------+
| drains at exactly r |
v packet needs L tokens
perfectly smooth output -> conforming if available
NO burst ever permitted -> BURST of up to b permitted
The arrival constraint a token bucket enforces:
cumulative
bytes ^ ,-' slope = r
| ,-'
| ,-'
| ,-'
b ---|-------,-' <- intercept b = burst allowance
| ,-'
| ,'
+-----------------------> time
A conforming source stays on or below this line: A(t) <= r*t + b
class TokenBucket:
"""Rate r bytes/s, depth b bytes. Enforces A(t) <= r*t + b."""
def __init__(self, rate_bps, burst_bytes):
self.r = rate_bps / 8.0
self.b = float(burst_bytes)
self.tokens = float(burst_bytes) # start full: an initial burst is allowed
self.last = 0.0
def consume(self, now, size):
# No timer thread needed: compute the refill lazily from elapsed time.
self.tokens = min(self.b, self.tokens + self.r * (now - self.last))
self.last = now
if self.tokens >= size:
self.tokens -= size
return True
return False
tb = TokenBucket(rate_bps=8_000_000, burst_bytes=10_000) # 1 MB/s, 10 kB burst
print(" t(ms) size verdict tokens_left")
for ms, size in [(0, 4000), (0, 4000), (0, 4000), (5, 4000), (20, 10000), (20, 1)]:
ok = tb.consume(ms / 1000, size)
print(f"{ms:5d} {size:6d} {'PASS' if ok else 'DROP'} {tb.tokens:9.0f}")
# t(ms) size verdict tokens_left
# 0 4000 PASS 6000 <- burst allowance spends down
# 0 4000 PASS 2000
# 0 4000 DROP 2000 <- burst exhausted at t=0
# 5 4000 PASS 3000 <- 5 ms refilled 5000 bytes of credit
# 20 10000 PASS 0 <- 15 ms idle refilled the bucket to b
# 20 1 DROP 0 <- even 1 byte fails with no tokens left
def srtcm(packets, cir_bps, cbs, ebs):
"""RFC 2697 single-rate three-colour marker: one rate, two buckets."""
tc, te, last = float(cbs), float(ebs), 0.0
rate = cir_bps / 8.0
out = []
for t, size in packets:
fill = rate * (t - last)
last = t
new_tc = tc + fill
tc = min(cbs, new_tc)
te = min(ebs, te + max(0.0, new_tc - cbs)) # C bucket's overflow feeds E
if tc >= size:
tc -= size
out.append("green") # conforming: forward with contracted marking
elif te >= size:
te -= size
out.append("yellow") # excess: forward, re-mark for earlier discard
else:
out.append("red") # violating: discard at the edge
return out
from collections import Counter
stream = [(i * 0.001, 1500) for i in range(30)] # 1500 B every 1 ms = 12 Mb/s
colours = srtcm(stream, cir_bps=4_000_000, cbs=6_000, ebs=6_000)
print("offered 12 Mb/s against CIR 4 Mb/s, CBS = EBS = 6000 B")
print(" sequence:", "".join(c[0].upper() for c in colours))
print(" counts :", dict(Counter(colours)))
green_bytes = colours.count("green") * 1500
allowed = 4_000_000 / 8 * 0.030 + 6_000 # r*t + b over the 30 ms window
print(f" green bytes {green_bytes} <= r*t + b = {allowed:.0f}: "
f"{green_bytes <= allowed}")
# offered 12 Mb/s against CIR 4 Mb/s, CBS = EBS = 6000 B
# sequence: GGGGGYGYYGYRGRRRGRGRRGRRGRRRGR
# counts : {'green': 13, 'yellow': 4, 'red': 13}
# green bytes 19500 <= r*t + b = 21000: True
#
# The green count (13) exceeds a naive "4 Mb/s for 30 ms = 10 packets" estimate
# precisely because the bucket started full. Conformance is defined by the
# INEQUALITY, not by the rate alone -- which is why burst size must be stated.
# Token bucket parameters in three dialects of the same idea.
# Linux tc: rate = r, burst = b, latency bounds the queue (shaper form)
tc qdisc add dev eth0 root tbf rate 4mbit burst 6k latency 50ms
# Linux tc policer: same bucket, but excess is dropped rather than delayed
tc filter add dev eth0 parent ffff: u32 match u32 0 0 \
police rate 4mbit burst 6k conform-exceed drop
# Sizing the burst: Bc = CIR * Tc, with Tc a few milliseconds.
# CIR = 4 Mb/s, Tc = 10 ms -> Bc = 4e6 * 0.010 / 8 = 5000 bytes
# Practical floor: several MTUs, or the path's bandwidth-delay product.
# 4 Mb/s x 80 ms RTT / 8 = 40 kB <- a 6 kB burst would throttle TCP badly here
Key takeaways
- Leaky bucket holds packets and drains at a constant rate: output is perfectly smooth and no burst is ever allowed.
- Token bucket holds permits that accumulate to depth
b: idleness earns credit, so a burst of up tobbytes is allowed at line rate. - The token bucket's contract is
A(t) <= r*t + bover every interval — conformance depends on the burst size, not the rate alone. - Real implementations use token buckets, because real traffic is bursty and a leaky bucket would penalise every normal burst.
- Size the burst with
Bc = CIR * Tc, and never below a few MTUs or the path's bandwidth-delay product, or TCP throughput will suffer. - Two buckets give three colours: srTCM (RFC 2697) limits burst excess, trTCM (RFC 2698) limits rate excess. Yellow means "forward but re-mark", not "drop".
🧪 Practice
- A token bucket has r = 1 Mb/s and b = 10 kB and has been idle for 2 seconds. State the largest instantaneous burst it admits, and the sustained rate it permits afterwards.
- Compute
Bcfor a 20 Mb/s CIR at Tc = 8 ms, then compare it with the bandwidth-delay product for a 60 ms RTT and say which value you would configure.- Trace srTCM with CIR = 1 Mb/s, CBS = 2 kB, EBS = 2 kB over packets of 1500 B arriving at t = 0, 2, 4, and 20 ms, giving the colour of each.
- Interview-style: A provider polices a customer to exactly 100 Mb/s with a 1500-byte burst. The customer reports 12 Mb/s of throughput on a transatlantic transfer. (Hint: relate the burst size to the bandwidth-delay product of that path, and think about what happens to a TCP window that can never exceed one packet's worth of credit.)
Queuing Disciplines: FIFO, PQ, WFQ, CBWFQ
Theory
Once packets are classified, something must decide the order in which they leave. That is the scheduler, and it is separate from the question of which packets to discard, which is queue management (the next topic). Keeping the two apart is the clearest way to understand any QoS implementation: the scheduler allocates time, the queue manager allocates space.
FIFO is one queue served in arrival order. It has a single virtue — it is free — and one fatal property: no isolation. Any flow can fill the queue and impose its buffering delay on every other flow. Because there is exactly one queue, there is no such thing as a per-class guarantee, and the only tuning available is the buffer size, which trades loss against delay for everyone simultaneously. A deep FIFO buffer is the direct cause of bufferbloat: the link stays 100% utilised while every packet crossing it acquires hundreds of milliseconds of standing delay.
Priority queueing (PQ) maintains several queues and always serves the highest-priority non-empty one. It gives the best possible delay to the top class: a packet waits only for the packet currently on the wire, since transmission is non-preemptive. It also has an obvious failure mode — starvation. If the priority class is offered more than the link rate, lower classes get nothing at all, including routing protocol traffic. The mandatory companion to a priority queue is therefore a policer on the priority class, which is why the common recommendation is to cap the real-time class at roughly one third of link capacity: enough for the intended traffic, structurally unable to starve the rest.
Fair queueing (FQ) takes the opposite approach: give every flow its own queue and serve them so that each receives an equal share. The reference model is bit-by-bit round robin, which is not implementable (packets are indivisible), so real schedulers approximate it. Weighted fair queueing (WFQ) computes for each packet a virtual finish time — the moment it would finish under the idealised bit-by-bit model — and transmits packets in increasing order of that value:
F(i) = max( F(i-1 for this flow), V(arrival) ) + size / weight
The weight sets the share. WFQ's important property is that a flow sending less than its share experiences almost no queueing delay regardless of what other flows do, which is exactly what a thin real-time stream needs, and it achieves this without any classification at all. The cost is state and computation proportional to the number of active flows.
Deficit round robin (DRR) achieves near-identical fairness with O(1) work per packet: each queue gets a byte quantum per round and carries forward unused credit as a "deficit", which handles variable packet sizes without computing finish times. Most hardware implementations of "fair queueing" are really DRR.
CBWFQ (class-based WFQ) is the practical enterprise form: instead of per-flow queues, there is one queue per class, each with a configured bandwidth share; unused share is redistributed to whoever needs it. Adding a strict-priority queue on top, with a built-in policer, gives LLQ (low-latency queueing), which is the near-universal template for enterprise WAN policies: one policed priority queue for voice, weighted queues for everything else.
| Discipline | Isolation | Delay for a thin flow | State | Starvation risk | Where used |
|---|---|---|---|---|---|
| FIFO | none | equals full queue depth | none | n/a | default, core links with headroom |
| PQ | strong, top-down | one packet time | per class | high without a policer | real-time class |
| WFQ | per flow | very low | per active flow | none | edge links, routers |
| DRR | per flow/class | low | per queue, O(1) | none | hardware schedulers |
| CBWFQ + LLQ | per class | one packet time (LLQ) | per class | controlled by policer | enterprise WAN standard |
| FQ-CoDel / CAKE | per flow + AQM | very low | per flow | none | modern hosts, CPE, bufferbloat fix |
Examples
The scheduler decides ORDER; the queue manager decides WHO IS DISCARDED
classify schedule link
----> +----------+ voice +===============+
| match |---------->| PQ (policed) |--\
----> | DSCP | video +===============+ \
| / 5-tuple|--------->| queue w=4 |----+--> [ serializer ] ---->
----> | | data +---------------+ /
| |---------->| queue w=2 |--/
----> +----------+ bulk +---------------+
| queue w=1 |
+---------------+
^ AQM (RED/CoDel) lives INSIDE each queue
Strict priority starvation, and its fix:
priority offered 120 Mb/s on a 100 Mb/s link
without policer: bulk gets 0 Mb/s, routing adjacencies drop, network fails
with policer at 33 Mb/s: priority capped, 67 Mb/s remains for everyone else
from collections import deque, OrderedDict
LINK_BPS = 2_000_000 # 2 Mb/s, deliberately congested
def make_traffic():
"""voice: small and steady (80 kb/s). bulkA/bulkB: greedy, ~4 Mb/s each."""
pkts = [(i * 0.020, "voice", 200) for i in range(10)]
for i in range(60):
pkts.append((i * 0.003, "bulkA", 1500))
pkts.append((i * 0.003, "bulkB", 1500))
return sorted(pkts)
def simulate(scheduler, traffic, weights=None):
queues, now, served, i = OrderedDict(), 0.0, [], 0
while i < len(traffic) or any(queues.values()):
while i < len(traffic) and traffic[i][0] <= now: # admit arrivals
t, flow, size = traffic[i]
queues.setdefault(flow, deque()).append((t, size))
i += 1
if not any(queues.values()):
now = traffic[i][0]
continue
flow = scheduler(queues, weights) # THE decision
arrival, size = queues[flow].popleft()
now += size * 8 / LINK_BPS # serialize it
served.append((flow, now - arrival)) # sojourn time
return served
def fifo(queues, _w):
"""One logical queue: strict arrival order, no isolation at all."""
return min((q[0][0], f) for f, q in queues.items() if q)[1]
def strict_priority(queues, _w):
"""voice outranks everything; the rest share by arrival order."""
if queues.get("voice"):
return "voice"
return min((q[0][0], f) for f, q in queues.items() if q)[1]
def drr_factory():
"""Deficit round robin: O(1) per packet, byte-fair via a carried-forward credit."""
deficit, order = {}, []
def drr(queues, weights):
nonlocal order
active = [f for f, q in queues.items() if q]
for f in active:
deficit.setdefault(f, 0)
order = [f for f in order if f in queues] or list(active)
for f in active:
if f not in order:
order.append(f)
while True:
f = order[0]
order = order[1:] + [f] # rotate
if not queues.get(f):
continue
deficit[f] += (weights or {}).get(f, 1) * 1500 # quantum
if deficit[f] >= queues[f][0][1]:
deficit[f] -= queues[f][0][1] # carry the rest
return f
return drr
def wfq_factory():
"""WFQ: serve the smallest virtual finish time
F = max(F_last_of_flow, virtual_now) + size / weight."""
finish, vnow, seq = {}, [0.0], {}
def wfq(queues, weights):
best = None
for f, q in queues.items():
if not q:
continue
w = (weights or {}).get(f, 1)
ft = max(finish.get(f, vnow[0]), vnow[0]) + q[0][1] / w
key = (ft, seq.get(f, 0)) # tie-break to the least-recently served
if best is None or key < best[0]:
best = (key, f, ft)
_, f, ft = best
finish[f], vnow[0] = ft, ft
seq[f] = seq.get(f, 0) + 1
return f
return wfq
traffic = make_traffic()
weights = {"voice": 1, "bulkA": 4, "bulkB": 4}
print(f"link {LINK_BPS/1e6:.0f} Mb/s, offered ~8.1 Mb/s (voice 0.08 + bulk 8.0)\n")
for name, sched in (("FIFO", fifo), ("Strict PQ", strict_priority),
("DRR", drr_factory()), ("WFQ", wfq_factory())):
by = {}
for f, d in simulate(sched, traffic, weights):
by.setdefault(f, []).append(d)
parts = [f"{f} avg {1000*sum(by[f])/len(by[f]):6.1f} max {1000*max(by[f]):6.1f}"
for f in ("voice", "bulkA", "bulkB")]
print(f"{name:10s} " + " | ".join(parts))
# link 2 Mb/s, offered ~8.1 Mb/s (voice 0.08 + bulk 8.0)
#
# FIFO voice avg 281.6 max 548.0 | bulkA avg 275.4 max 544.2 | bulkB avg 281.4 max 550.2
# Strict PQ voice avg 3.2 max 5.6 | bulkA avg 278.5 max 545.0 | bulkB avg 284.5 max 551.0
# DRR voice avg 6.8 max 12.8 | bulkA avg 278.5 max 545.0 | bulkB avg 284.5 max 551.0
# WFQ voice avg 3.2 max 5.6 | bulkA avg 278.5 max 545.0 | bulkB avg 284.5 max 551.0
#
# Read the numbers as a trade: voice drops from 281.6 ms to 3.2 ms, while bulk
# rises from 275.4 ms to 278.5 ms. The bulk flows paid 3 ms; voice gained 278 ms.
# Note also that WFQ achieves the priority queue's delay WITHOUT a priority
# queue's starvation risk, because voice is under its fair share.
# --- Enterprise template: LLQ = policed priority queue + CBWFQ (Cisco-style) ---
class-map match-all VOICE
match dscp ef
class-map match-all VIDEO
match dscp af41 af42 af43
class-map match-all CRITICAL
match dscp af31 af32 af33
class-map match-all SCAVENGER
match dscp cs1
policy-map WAN-EGRESS
class VOICE
priority percent 10 ! strict priority WITH an implicit policer
class VIDEO
bandwidth percent 25 ! CBWFQ weighted share
random-detect dscp-based ! AQM inside the queue
class CRITICAL
bandwidth percent 25
class SCAVENGER
bandwidth percent 1 ! allowed to starve
class class-default
bandwidth percent 25
fair-queue ! per-flow fairness within best effort
# --- Linux equivalents ---
# Per-flow fairness plus AQM, one line, no classification needed:
tc qdisc replace dev eth0 root fq_codel
# Class-based shares with a priority band, under a parent shaper:
tc qdisc add dev eth0 root handle 1: htb default 40
tc class add dev eth0 parent 1: classid 1:1 htb rate 95mbit ceil 95mbit
tc class add dev eth0 parent 1:1 classid 1:10 htb rate 10mbit ceil 10mbit prio 0
tc class add dev eth0 parent 1:1 classid 1:20 htb rate 25mbit ceil 95mbit prio 1
tc class add dev eth0 parent 1:1 classid 1:40 htb rate 25mbit ceil 95mbit prio 2
tc qdisc add dev eth0 parent 1:10 handle 10: pfifo limit 20 # small: keep EF shallow
tc qdisc add dev eth0 parent 1:20 handle 20: fq_codel
tc qdisc add dev eth0 parent 1:40 handle 40: fq_codel
Key takeaways
- The scheduler allocates time, the queue manager allocates space. Analyse them separately.
- FIFO provides no isolation and, with a deep buffer, is the direct cause of bufferbloat.
- Priority queueing gives the best delay to the top class and will starve everything else unless that class is policed — cap the real-time class near one third of capacity.
- WFQ gives a below-share flow near-zero queueing delay without classification, at the cost of per-flow state; DRR achieves the same fairness in O(1).
- CBWFQ + LLQ is the standard enterprise pattern: one policed priority queue plus weighted class queues.
- FQ-CoDel and CAKE combine per-flow fairness with active queue management and are the practical default on hosts and customer premises equipment.
- A scheduler's benefit is asymmetric: in the worked example, bulk traffic gave up 3 ms so that voice could gain 278 ms.
🧪 Practice
- On a 100 Mb/s link with a 1500-byte MTU, compute the worst-case queueing delay for a packet in a strict-priority queue, assuming non-preemptive transmission and one packet already on the wire.
- Explain why a priority queue without a policer can break OSPF adjacencies, and give the two configuration changes that prevent it.
- Given three classes with weights 1, 3, and 6 on a 200 Mb/s link, compute each class's guaranteed rate when all are backlogged, and state what class 1 receives when classes 2 and 3 are idle.
- Interview-style: Users on a 50 Mb/s office link complain that video calls stutter whenever anyone uploads to cloud storage, even though the link never reaches 50 Mb/s. (Hint: look at the buffer, not the utilisation graph, and consider what a single-queue device does to a thin stream sharing space with a greedy one.)
Congestion Avoidance with RED and WRED
Theory
A scheduler decides who transmits; something still has to decide what happens when the buffer runs out of room. The default is tail drop: accept packets until the queue is full, then discard new arrivals. It is simple and it has three serious faults.
First, it produces full queues by design. Tail drop only signals congestion at the moment the buffer is completely full, so a TCP sender keeps increasing its window until that point, and the steady state of a tail-drop queue under greedy TCP is full. A full buffer means maximum standing delay for every packet crossing the link, even though the link is perfectly utilised. That is bufferbloat: the pathology is not lost throughput but hundreds of milliseconds of latency added to traffic that never asked for a big buffer.
Second, it causes global synchronisation. When the buffer overflows, it drops from every flow at nearly the same instant, so all senders back off together, the link goes briefly idle, all senders grow together, and the buffer overflows again. Throughput oscillates instead of settling, and the aggregate utilisation suffers.
Third, it is burst-hostile in the wrong way. A short burst arriving at a queue that happens to be full is destroyed wholesale, producing exactly the consecutive-loss pattern that defeats real-time concealment (Section 12.1).
RED (random early detection) fixes all three with one idea: drop a few packets early, at random, before the buffer is full. It maintains an exponentially weighted moving average of the queue length and compares it against two thresholds:
avg < min_th -> accept everything
min_th <= avg < max_th -> drop with probability rising linearly to max_p
avg >= max_th -> drop everything
Three design choices make this work. Using the average rather than the instantaneous length lets genuine short bursts through, since a burst barely moves the average. Dropping randomly breaks synchronisation, because different flows are hit at different times. Dropping in proportion to a flow's share of the traffic happens automatically — a flow sending more packets is selected more often — which provides a crude fairness without per-flow state. Real implementations add a count-based adjustment so that drops are spread out in time rather than clustered.
WRED (weighted RED) applies different thresholds per drop precedence within the same queue. AF11, AF12, and AF13 share one queue and one scheduler share, but AF13 gets the lowest min_th and so is discarded first. This is precisely what makes the AF group and the yellow/green colour marking from the previous topic useful: the metering at the edge decides which packets are expendable, and WRED in the core acts on that decision.
ECN (explicit congestion notification, RFC 3168) is the strictly better version of the same signal: instead of dropping the packet, set the CE codepoint in the two ECN bits and let the receiver echo it back to the sender, which reduces its rate exactly as if it had seen a loss. The congestion signal arrives without destroying data or costing a retransmission. It requires both endpoints to negotiate it and the queue to be configured for marking.
RED's weakness is that its thresholds are in queue length, which is the wrong unit: the right target is delay, and the same 50-packet queue means 6 ms on a 100 Mb/s link and 600 ms on a 1 Mb/s link, so thresholds must be retuned for every link speed. CoDel (controlled delay) replaces them with a single target sojourn time, typically 5 ms measured over a 100 ms interval, and needs essentially no tuning. FQ-CoDel combines it with per-flow queueing and is the modern default; PIE is a similar delay-targeting design used in cable modems.
| Tail drop | RED / WRED | CoDel / FQ-CoDel | |
|---|---|---|---|
| Signals congestion | when buffer is full | early, probabilistically | when sojourn delay exceeds target |
| Tuning parameter | buffer size | min_th, max_th, max_p, w_q | target delay (5 ms), interval |
| Needs retuning per link rate | yes | yes | no |
| Global synchronisation | yes | no | no |
| Steady-state queue | full | between thresholds | near target delay |
Examples
RED's drop probability as a function of the AVERAGE queue length
drop
prob
1.0 | ,------------------
| |
| | <- avg >= max_th:
| | drop everything
max_p | ,-----+
0.10 | ,-'
| ,-' <- linear region: random,
| ,-' proportional early drop
| ,-'
0.0 +------+--'--------------+----------------------------->
0 min_th max_th queue limit
(40) (120) (240)
WRED: the same queue, three curves, one per drop precedence
drop 1.0 | AF13 AF12 AF11
prob | /| /| /|
| / | / | / | <- yellow-marked (AF13) traffic is
0.0 +---+--+-----+--+------+--+----> discarded well before green (AF11)
20 60 40 100 60 140
import random, statistics
random.seed(7)
class RED:
"""Floyd/Jacobson RED: probabilistic drop based on the AVERAGE queue length."""
def __init__(self, min_th, max_th, max_p, w_q=0.02, limit=240):
self.min_th, self.max_th, self.max_p = min_th, max_th, max_p
self.w_q, self.limit, self.avg, self.count = w_q, limit, 0.0, 0
def verdict(self, qlen):
self.avg = (1 - self.w_q) * self.avg + self.w_q * qlen # EWMA
if qlen >= self.limit:
return "drop" # hard ceiling
if self.avg < self.min_th:
self.count = 0
return "accept"
if self.avg >= self.max_th:
self.count = 0
return "drop"
pb = self.max_p * (self.avg - self.min_th) / (self.max_th - self.min_th)
self.count += 1
pa = min(1.0, pb / max(1e-9, 1 - self.count * pb)) # spread drops over time
if random.random() < pa:
self.count = 0
return "drop"
return "accept"
class TailDrop:
def __init__(self, limit=240):
self.limit = limit
def verdict(self, qlen):
return "drop" if qlen >= self.limit else "accept"
def simulate(aqm, ticks=4000, flows=8, capacity=10.0):
"""capacity = packets served per tick. Each flow is AIMD: grows, halves on loss."""
rate = [capacity / flows] * flows
q, depths, tput, drops, sent = 0.0, [], [], 0, 0
for _ in range(ticks):
for f in range(flows):
whole = int(rate[f]) + (1 if random.random() < rate[f] % 1 else 0)
lost = False
for _ in range(whole):
sent += 1
if aqm.verdict(q) == "accept":
q += 1
else:
drops += 1
lost = True # THE FEEDBACK LOOP: a drop is a signal
rate[f] = max(0.05, rate[f] * 0.5) if lost else rate[f] + 0.02
served = min(q, capacity)
q -= served
depths.append(q)
tput.append(served)
return depths, tput, drops, sent
for name, aqm in (("tail drop (240)", TailDrop(240)),
("RED 40/120/0.10", RED(40, 120, 0.10))):
depths, tput, drops, sent = simulate(aqm)
warm = slice(500, None) # discard the startup transient
d = depths[warm]
print(f"{name:17s} avg queue {statistics.mean(d):6.1f} pkts "
f"p99 {sorted(d)[int(0.99*len(d))]:5.1f} "
f"loss {100*drops/sent:5.2f}% "
f"utilisation {100*statistics.mean(tput[warm])/10.0:5.1f}% "
f"tput stdev {statistics.stdev(tput[warm]):4.2f}")
# tail drop (240) avg queue 223.6 pkts p99 230.0 loss 7.01% utilisation 100.0% tput stdev 0.00
# RED 40/120/0.10 avg queue 33.7 pkts p99 77.0 loss 2.11% utilisation 98.9% tput stdev 0.49
#
# RED gave up 1.1% of utilisation and bought:
# - a 6.6x shorter queue (223.6 -> 33.7 packets)
# - 3.3x LESS loss (7.01% -> 2.11%), because senders back off before overflow
# Translate the queue into what a user feels, on a 10 Mb/s egress link:
for depth, label in ((224, "tail drop: buffer kept full"), (34, "RED: average queue")):
print(f"{label:28s} {depth:3d} pkts x 1500 B at 10 Mb/s = "
f"{depth*1500*8/10e6*1000:6.1f} ms of standing delay")
# tail drop: buffer kept full 224 pkts x 1500 B at 10 Mb/s = 268.8 ms of standing delay
# RED: average queue 34 pkts x 1500 B at 10 Mb/s = 40.8 ms of standing delay
# --- RED on Linux: note that every threshold is in BYTES, tied to link rate ---
tc qdisc add dev eth0 parent 1:20 handle 20: red \
limit 360000 min 60000 max 180000 avpkt 1000 \
burst 61 bandwidth 100mbit probability 0.02 ecn
# min/max = the two thresholds (bytes) -> 60 kB / 180 kB
# burst = roughly (2*min + max)/(3*avpkt) -> tolerance for real bursts
# bandwidth= the link rate, used to age the average when the queue is idle
# ecn = MARK instead of dropping where the sender supports it
# Changing the link from 100mbit to 10mbit requires retuning ALL of these.
# --- CoDel: one meaningful knob, expressed as DELAY, no rate dependence ---
tc qdisc replace dev eth0 root fq_codel target 5ms interval 100ms ecn
# target = the sojourn delay CoDel tries to hold -> valid at ANY link rate
# fq_ = per-flow hashing, so a greedy flow cannot delay a thin one
# --- Verify ---
tc -s qdisc show dev eth0
# fq_codel ... maxpacket 1514 drop_overlimit 0 new_flow_count 812
# ecn_mark 1043 <- senders were signalled WITHOUT losing data
Key takeaways
- Tail drop signals congestion only when the buffer is full, so its steady state is a full buffer. That is bufferbloat: full utilisation plus hundreds of milliseconds of added delay.
- Tail drop also causes global synchronisation (all senders back off together) and destroys bursts wholesale.
- RED drops early, randomly, and in proportion to a flow's share, using the average queue length so real bursts pass. That shortens the queue and reduces total loss.
- WRED applies per-drop-precedence thresholds inside one queue, which is what makes AF classes and yellow re-marking actionable.
- ECN delivers the same signal by marking instead of discarding, so no data is lost and no retransmission is needed.
- RED's thresholds are in queue length and must be retuned for every link rate; CoDel targets sojourn delay instead and needs no tuning.
- FQ-CoDel is the sensible modern default: per-flow fairness plus delay-targeted AQM.
🧪 Practice
- A queue holds 300 packets of 1500 bytes on a 20 Mb/s link. Compute the standing delay when tail drop keeps it full, then the
min_thin packets that would cap the average delay at 30 ms.- Explain why RED uses the average rather than the instantaneous queue length, and what breaks if
w_qis set far too large.- Given a queue carrying AF21, AF22, and AF23, propose
min_th/max_th/max_ptriples for each and justify the ordering.- Interview-style: A team increases a router's interface buffer from 64 MB to 256 MB to "stop the packet loss". Loss does fall, and every application gets slower. (Hint: relate buffer size to standing delay under a greedy TCP sender, and ask what the sender uses as its congestion signal.)
Admission Control
Theory
Every mechanism so far reallocates a fixed resource. None of them can create capacity, so when the offered real-time load exceeds what the link can carry, they can only choose how the failure is distributed. A scheduler facing 44 voice calls on a link that fits 37 will deliver 44 unusable calls. Admission control is the mechanism that instead delivers 37 good calls and 7 honest rejections.
This is the least popular and most necessary idea in QoS, because its output is visible refusal. It is also the only way a guarantee can mean anything: the arithmetic of "every admitted flow gets its bound" depends on knowing how many flows there are, so the network must have the right to stop counting.
The analogy is a restaurant with 40 seats. Turning away the 41st party is not a service failure; seating them on the floor and serving everyone cold food is.
There are two families of admission control.
Parameter-based admission control asks each flow to declare what it needs — typically as a token bucket (r, b) plus a peak rate — and admits it only if the sum of declarations still fits a budget. It is deterministic and gives hard bounds, and it is what IntServ and RSVP implement (Section 12.3). Its weakness is that declarations must be conservative, so the link runs well below capacity when sources are bursty and rarely simultaneous.
Measurement-based admission control ignores declarations and watches actual load: admit the new flow if recent measured utilisation plus an estimate of the new flow leaves enough margin. It achieves much higher utilisation, at the cost of an occasional wrong decision when traffic shifts after admission. Most real voice deployments are effectively measurement-based with a safety margin.
The engineering question underneath is the effective bandwidth of a flow: how much capacity must be set aside so that a bound holds with the required probability. For a constant-rate source such as G.711 voice, it is simply the peak rate and the arithmetic is trivial. For bursty sources it lies between the mean and the peak, closer to the mean the more flows are multiplexed — which is the statistical multiplexing result from Section 12.1 restated as a budgeting rule.
For call-oriented traffic, sizing is a classical problem solved long before packet networks. Erlang B answers "how many simultaneous channels do I need so that the probability of a new call finding them all busy is below P?" given the offered load in Erlangs (mean number of simultaneous calls, equal to calls per hour times mean duration in hours). Its practical lesson is economies of scale: a small trunk group needs far more channels per Erlang than a large one, which is why centralising voice trunks across sites saves capacity and why a small branch needs disproportionate headroom.
Where admission control actually appears:
| Context | Mechanism | Refusal looks like |
|---|---|---|
| Enterprise voice | call admission control at the call manager, or RSVP | fast busy tone, "network busy" |
| Cellular | radio admission control per cell | call setup failure, downgraded bearer |
| MPLS TE | RSVP-TE reservation against per-link bandwidth pools | LSP setup fails, tunnel stays down |
| Video conferencing | bandwidth budget per site in the call control platform | join rejected, or joined audio-only |
| DiffServ domains | aggregate policing at the edge plus offline planning | excess re-marked or dropped, no explicit refusal |
Note the last row: a pure DiffServ network has no signalling and therefore no true admission control. It substitutes capacity planning — provision the EF class so that expected load never exceeds it — plus an edge policer as a backstop. This is the standard compromise, and RFC 5865's Voice-Admit codepoint exists precisely to distinguish traffic that has passed an admission check from ordinary EF that has not.
Examples
A call that is refused rather than degraded
phone A call manager WAN link
| | (EF budget 3.3 Mb/s)
|-- INVITE ------------->| reserved: 3.23 Mb/s
| |-- check budget -----------> 3.23 + 0.087 > 3.30
| |<-- DENY -------------------
|<- 503 / fast busy -----|
|
The user hears a busy tone in 200 ms and redials in a moment.
WITHOUT this check: the call connects, and all 44 calls on the link
become unintelligible at once, including the 37 that were already fine.
The shape of the decision:
admitted load
^
budget--|---------------------##### <- flows beyond this point are REFUSED,
| #### not degraded
| ####
| ####
| ####
+-----------------------------> offered load
def erlang_b(servers, offered_erlangs):
"""Blocking probability for `servers` channels under `offered` Erlangs.
Iterative form: B(0)=1, B(n) = A*B(n-1) / (n + A*B(n-1))."""
b = 1.0
for n in range(1, servers + 1):
b = (offered_erlangs * b) / (n + offered_erlangs * b)
return b
CALL_KBPS = 87.2 # G.711 + RTP/UDP/IP/Ethernet headers, 20 ms frames
print("Trunk sizing for 20 Erlangs of voice (e.g. 240 calls/hour x 5 minutes):")
for trunks in (20, 24, 27, 30, 35):
print(f" {trunks:3d} concurrent calls -> blocking {erlang_b(trunks, 20.0):7.3%} "
f"bandwidth {trunks*CALL_KBPS/1000:5.2f} Mb/s")
# 20 concurrent calls -> blocking 15.889% bandwidth 1.74 Mb/s
# 24 concurrent calls -> blocking 6.610% bandwidth 2.09 Mb/s
# 27 concurrent calls -> blocking 2.681% bandwidth 2.35 Mb/s
# 30 concurrent calls -> blocking 0.846% bandwidth 2.62 Mb/s
# 35 concurrent calls -> blocking 0.069% bandwidth 3.05 Mb/s
print("\nEconomies of scale: what a 1% grade of service costs at each size")
for load in (5, 10, 20, 50, 100):
n = 1
while erlang_b(n, load) > 0.01:
n += 1
print(f" {load:3d} Erlangs -> {n:3d} channels "
f"({n/load:4.2f} channels per Erlang, {n*CALL_KBPS/1000:6.2f} Mb/s)")
# 5 Erlangs -> 11 channels (2.20 channels per Erlang, 0.96 Mb/s)
# 10 Erlangs -> 18 channels (1.80 channels per Erlang, 1.57 Mb/s)
# 20 Erlangs -> 30 channels (1.50 channels per Erlang, 2.62 Mb/s)
# 50 Erlangs -> 64 channels (1.28 channels per Erlang, 5.58 Mb/s)
# 100 Erlangs -> 117 channels (1.17 channels per Erlang, 10.20 Mb/s)
# A small site needs 2.2 channels per Erlang; a large one needs 1.17. This is
# why trunks are centralised, and why small branches need extra headroom.
class AdmissionControl:
"""Parameter-based CAC: admit only while the reservation still fits the budget."""
def __init__(self, link_mbps, realtime_fraction=0.33):
self.budget = link_mbps * realtime_fraction # never let EF starve the link
self.reserved = 0.0
def request(self, mbps):
if self.reserved + mbps <= self.budget:
self.reserved += mbps
return True
return False # explicit refusal
CALL_MBPS = 0.0872
cac = AdmissionControl(link_mbps=10.0)
print(f"CAC on a 10 Mb/s link, realtime budget {cac.budget:.2f} Mb/s:")
admitted = rejected = 0
for call in range(1, 45):
if cac.request(CALL_MBPS):
admitted += 1
else:
rejected += 1
if rejected == 1:
print(f" call {call} is the first REJECTED "
f"(reserved {cac.reserved:.2f} Mb/s of {cac.budget:.2f})")
print(f" admitted {admitted}, rejected {rejected}")
print(f" without CAC: all 44 admitted, each receives "
f"{cac.budget/44*1000:.1f} kb/s where {CALL_MBPS*1000:.1f} kb/s is needed "
f"-> every call fails, including the 37 that would have worked")
# CAC on a 10 Mb/s link, realtime budget 3.30 Mb/s:
# call 38 is the first REJECTED (reserved 3.23 Mb/s of 3.30)
# admitted 37, rejected 7
# without CAC: all 44 admitted, each receives 75.0 kb/s where 87.2 kb/s is
# needed -> every call fails, including the 37 that would have worked
Key takeaways
- Admission control is the only mechanism that converts overload into refusal instead of universal degradation.
- Without it, a guarantee is arithmetic with an unknown term: no bound survives unbounded admission.
- Parameter-based control admits against declared token buckets and gives hard bounds at low utilisation; measurement-based control watches real load and achieves higher utilisation with some risk.
- A flow's effective bandwidth sits between its mean and peak rate, approaching the mean as more flows are multiplexed.
- Erlang B sizes call capacity from offered Erlangs and a target blocking probability, and shows strong economies of scale: 2.2 channels per Erlang at 5 Erlangs, 1.17 at 100.
- Pure DiffServ has no admission control — it relies on capacity planning plus an edge policer, which is why RFC 5865 adds a codepoint for traffic that has been admitted.
- Cap the real-time budget at a fraction of link capacity (commonly about one third) so that admitted traffic can never starve the rest.
🧪 Practice
- A site offers 12 Erlangs of voice. Using Erlang B, find the channel count needed for 1% blocking and convert it to Mb/s at 87.2 kb/s per call.
- Explain why merging two branches' voice trunks into one shared pool reduces the total channel requirement, and quantify it for two sites of 10 Erlangs each versus one of 20.
- Design an admission rule for video conferencing on a 100 Mb/s site link where each call needs 2 Mb/s, the real-time budget is 30%, and voice already reserves 3 Mb/s. State how many calls are admitted and what the 16th caller experiences.
- Interview-style: A DiffServ network marks all voice EF and polices it at the edge. Management asks for a guarantee that no call will ever degrade. (Hint: identify what DiffServ structurally lacks, and describe the two things you would have to add to turn a policing backstop into a real guarantee.)
<a id="123-qos-architectures"></a>
12.3 QoS Architectures
The mechanisms of the previous subchapter are per-hop; turning them into a service that holds along an entire path requires an architecture that says how hops coordinate: this subchapter covers the two canonical answers (per-flow reservation and aggregate marking), the traffic engineering that chooses paths rather than queue positions, and how to assemble a design that survives crossing administrative boundaries.
Integrated Services and RSVP
Theory
IntServ (RFC 1633) was the first complete answer to "how do we offer a real guarantee across a packet network?", and its answer was the most direct one possible: let each flow ask, and let each router along the path agree. A flow describes its traffic, every router on the path runs admission control and installs state for it, and the resulting reservation is a chain of per-hop commitments that composes into an end-to-end bound.
IntServ defines two services beyond best effort:
| Service | RFC | Promise | Needs |
|---|---|---|---|
| Guaranteed Service | 2212 | a mathematically provable delay bound and no queueing loss | TSpec + RSpec, WFQ-class scheduler |
| Controlled-Load | 2211 | behaves like an unloaded network ("very high percentage" delivered, delay near minimum) | TSpec only |
The flow describes itself with a TSpec, which is exactly the token bucket of the previous subchapter plus limits: (r, b, p, m, M) — token rate, bucket depth, peak rate, minimum policed unit, maximum packet size. For Guaranteed Service the receiver adds an RSpec (R, S): the rate it wants reserved, which may be greater than r, plus a slack term. Reserving R > r is the knob that buys a tighter delay bound, because the bound is:
D <= b/R + Ctot/R + Dtot (RFC 2212, valid when R >= r)
\____/ \______/ \___/
burst rate-dep. rate-indep.
drain error latency
Ctot and Dtot are accumulated along the path by the signalling itself: each router adds its own error terms as the message passes, so the receiver learns the real characteristics of the actual path rather than guessing. This is an elegant property — the bound is computed from measured path data, not assumptions.
RSVP (RFC 2205) is the signalling protocol that carries all this, and three of its design decisions are worth understanding because they recur throughout networking.
First, it is receiver-initiated. The sender emits a PATH message downstream, which does not reserve anything; it records the route hop by hop (each router stores the previous hop) and accumulates the Ctot/Dtot terms. The receiver then sends RESV back along exactly that recorded path, and reservations are installed hop by hop as it travels. Receiver initiation exists because only the receiver knows its own capabilities, and because it generalises naturally to multicast, where different receivers of the same stream may want different quality.
Second, it uses soft state. A reservation is not permanent; it expires unless refreshed, conventionally every 30 seconds with a timeout of about 3.5 refresh intervals. This makes the protocol robust without any explicit teardown: if a router fails, if the route changes, or if an endpoint crashes, the stale reservation simply ages out, and a new PATH/RESV exchange follows the new route. The cost is continuous refresh traffic proportional to the number of reservations.
Third, it is not a routing protocol. RSVP reserves along whatever path the routing protocol chose. If routing reconverges, the reservation follows on the next refresh, with a gap in the guarantee in the meantime.
RSVP also defines reservation styles for multicast, which determine how reservations from multiple receivers merge:
| Style | Meaning |
|---|---|
| FF (fixed filter) | a distinct reservation per sender |
| WF (wildcard filter) | one shared reservation for all senders, any sender may use it |
| SE (shared explicit) | one shared reservation, with an explicit list of permitted senders |
Why IntServ failed as an Internet-wide architecture is the standard scalability argument, and it is worth stating precisely: per-flow state in the core. A backbone router carrying a million concurrent flows would need a million reservation records, a million refresh timers, and a classifier that matches on the full 5-tuple at line rate. State grows with the number of conversations rather than with the size of the network, which is the opposite of what a core device can tolerate. Every router on the path must also implement RSVP, so a single non-participating hop breaks the chain.
What survived is substantial, though, and in each case the scaling problem is absent because the number of reservations is small:
- RSVP-TE for MPLS tunnels: reservations are per tunnel, not per flow, and there are thousands at most. This is the dominant use today (next topic but one).
- Enterprise voice: a few hundred calls per WAN link, with RSVP acting as call admission control.
- DetNet and TSN: modern deterministic networking for industrial and automotive use, where the flow count is small, fixed, and engineered in advance.
Examples
RSVP: PATH goes with the data, RESV comes back against it
sender R1 R2 R3 receiver
| | | | |
|=== PATH ==========>| | | |
| SENDER_TSPEC |=== PATH =======>| | |
| ADSPEC (C,D) | +R1's C,D |=== PATH =======>| |
| | prev_hop=send | +R2's C,D |=== PATH ==>|
| | | prev_hop=R1 | +R3's C,D |
| | | | |
| | | receiver now knows Ctot, Dtot
| | | and computes the R it needs
| | | | |
| | |<=== RESV =======|<=== RESV ==|
| |<=== RESV =======| admission ctl | FLOWSPEC |
|<=== RESV ==========| admission ctl | install state | (TSpec+RSpec)
| reservation is now installed on every hop |
| | | | |
|=== data ==========>|== data ========>|== data ========>|== data ===>|
| | | | |
|--- PATH refresh -->| every ~30 s; state expires after ~3.5 intervals
(SOFT STATE: no teardown needed after a failure)
If admission control FAILS at R2, it returns ResvErr and no reservation exists
anywhere -- the flow learns it cannot have a guarantee BEFORE it sends data.
def guaranteed_delay_ms(b_bytes, r_bps, R_bps, Ctot_bytes, Dtot_ms):
"""RFC 2212 Guaranteed Service bound: b/R + Ctot/R + Dtot, valid for R >= r."""
assert R_bps >= r_bps, "the reserved rate must be at least the token rate"
return (b_bytes * 8 / R_bps + Ctot_bytes * 8 / R_bps) * 1000 + Dtot_ms
TSPEC = dict(b_bytes=8_000, r_bps=1_000_000) # bucket depth 8 kB, token rate 1 Mb/s
HOPS = 5
Ctot = HOPS * 1500 # rate-dependent error, accumulated by ADSPEC along PATH
Dtot = HOPS * 0.5 # rate-independent per-hop latency, likewise accumulated
print("Reserving MORE rate R than the token rate r buys a tighter delay bound:")
for R in (1_000_000, 2_000_000, 4_000_000, 10_000_000):
d = guaranteed_delay_ms(TSPEC["b_bytes"], TSPEC["r_bps"], R, Ctot, Dtot)
print(f" r=1 Mb/s, R={R/1e6:5.1f} Mb/s -> bound {d:7.2f} ms "
f"(overbooking {R/TSPEC['r_bps']:4.1f}x)")
# r=1 Mb/s, R= 1.0 Mb/s -> bound 126.50 ms (overbooking 1.0x)
# r=1 Mb/s, R= 2.0 Mb/s -> bound 64.50 ms (overbooking 2.0x)
# r=1 Mb/s, R= 4.0 Mb/s -> bound 33.50 ms (overbooking 4.0x)
# r=1 Mb/s, R= 10.0 Mb/s -> bound 14.90 ms (overbooking 10.0x)
# This is the fundamental IntServ trade: a 150 ms voice budget forces you to
# reserve several times the average rate, so the link runs far below capacity.
print("\nSensitivity to the declared burst size b, at a fixed R = 4 Mb/s:")
for b in (1_500, 4_000, 8_000, 32_000):
print(f" b={b:6d} B -> bound "
f"{guaranteed_delay_ms(b, TSPEC['r_bps'], 4_000_000, Ctot, Dtot):7.2f} ms")
# b= 1500 B -> bound 20.50 ms
# b= 4000 B -> bound 25.50 ms
# b= 8000 B -> bound 33.50 ms
# b= 32000 B -> bound 81.50 ms
# A source that declares a large burst is granted a weaker bound: honesty about
# smoothness is rewarded, which is why shaping BEFORE reserving pays off.
# Why per-flow state does not scale: the cost of IntServ at each network tier.
BYTES_PER_RESERVATION = 500 # classifier + scheduler + timer state
REFRESH_SEC = 30
for tier, flows in (("home router", 200), ("enterprise WAN edge", 5_000),
("ISP aggregation", 500_000), ("backbone core", 20_000_000)):
state_mb = flows * BYTES_PER_RESERVATION / 1e6
refresh_pps = flows / REFRESH_SEC
print(f"{tier:22s} {flows:>10,} flows -> {state_mb:9.1f} MB of state, "
f"{refresh_pps:>11,.0f} refresh msg/s")
# home router 200 flows -> 0.1 MB of state, 7 refresh msg/s
# enterprise WAN edge 5,000 flows -> 2.5 MB of state, 167 refresh msg/s
# ISP aggregation 500,000 flows -> 250.0 MB of state, 16,667 refresh msg/s
# backbone core 20,000,000 flows -> 10000.0 MB of state, 666,667 refresh msg/s
#
# 10 GB of reservation state and 667k control messages per second is why IntServ
# was never deployed in cores -- and why RSVP-TE, which reserves per TUNNEL
# (thousands, not millions), is perfectly viable on the same hardware.
Key takeaways
- IntServ gives per-flow guarantees by having every router on the path admit and remember each flow.
- Guaranteed Service provides a provable delay bound; Controlled-Load provides "as if unloaded" behaviour with less machinery.
- A flow's TSpec is a token bucket
(r, b, p, m, M); the RSpec(R, S)lets the receiver reserve more rate than the average to tighten the bound. - The bound
D <= b/R + Ctot/R + Dtotis computed from terms accumulated along the real path by the signalling itself. - RSVP is receiver-initiated (PATH downstream records the route, RESV upstream installs state), uses soft state refreshed about every 30 seconds, and is not a routing protocol.
- It failed in the Internet core because state grows with the number of flows, and every hop must participate.
- It thrives where reservations are few: RSVP-TE tunnels, enterprise voice admission control, and deterministic networking (TSN, DetNet).
🧪 Practice
- Compute the Guaranteed Service delay bound for
b= 4 kB,r= 2 Mb/s,R= 8 Mb/s over 6 hops with 1500 bytes and 0.4 ms of error per hop.- Explain why RSVP is receiver-initiated rather than sender-initiated, giving one unicast reason and one multicast reason.
- Describe what happens to an established reservation when the IGP reroutes the path, and name the property of RSVP that makes recovery automatic.
- Interview-style: Someone proposes using RSVP to guarantee latency for every video call across a national ISP backbone. (Hint: estimate the reservation count at an aggregation router and what must be stored and refreshed per reservation, then contrast with reserving per tunnel.)
Differentiated Services and PHBs
Theory
DiffServ (RFC 2474, RFC 2475) is the architecture that won, and it won by giving up exactly the thing that made IntServ unscalable: it keeps no per-flow state anywhere. The design move is a strict division of labour between the edge and the core, and it is one of the most instructive examples of a scalability pattern in all of networking.
The edge does the complicated, stateful, per-customer work: classify traffic by whatever means necessary, meter it against a contract, mark the DSCP accordingly, re-mark or drop excess, and shape. This is affordable because an edge device handles few interfaces at modest rates, and because the work is proportional to the number of customers, not flows.
The core does one thing per packet: read the DSCP, apply the corresponding per-hop behaviour. It keeps state per class — a handful of queues and threshold sets — regardless of whether one flow or ten million are passing through. State is therefore O(classes), and classes are a small constant.
A PHB is precisely the right abstraction for this: it specifies the externally observable forwarding behaviour a codepoint must receive, and deliberately does not specify the mechanism. "EF must be forwarded with a departure rate at least equal to its configured rate, independent of other traffic" can be implemented with a priority queue, with WFQ at a high weight, or with a rate-controlled scheduler. This is what lets a policy be written once and honoured by routers from different vendors with different internals.
The standardised PHB groups:
| PHB group | RFC | Codepoints | Behaviour |
|---|---|---|---|
| Default (DF) | 2474 | 0 | best effort; must not be starved entirely |
| Class Selector (CSn) | 2474 | 8, 16, ..., 56 | backwards compatibility with IP Precedence; higher is not worse |
| AF (assured forwarding) | 2597 | 4 classes x 3 drop precedences | each class gets a bandwidth share; within a class, higher precedence is dropped first |
| EF (expedited forwarding) | 3246 | 46 | low loss, low delay, low jitter; departure rate independent of other classes |
| Voice-Admit | 5865 | 44 | EF behaviour, but reserved for traffic that has passed admission control |
The AF group is where the marking work of Section 12.2 pays off. Four classes give four scheduler shares. Within each class, the three drop precedences give WRED three threshold sets. So a metering policer at the edge that marks conforming traffic AF21 and excess AF23 has expressed a complete statement — "this traffic belongs to class 2, and the excess portion is what you should discard first" — that the core can act on with no knowledge of the flow. Crucially, all three precedences of a class must share one queue, because reordering within a flow would otherwise occur when a flow's packets carry different precedences.
DiffServ's scope is a DS domain: a contiguous set of nodes under one administration with a consistent PHB mapping. Guarantees are therefore per domain, and crossing a boundary requires a bilateral agreement about which codepoints mean what plus a TCA (traffic conditioning agreement) describing the metering applied at the boundary. In practice, because such agreements exist only between parties with a contract, most boundaries simply bleach the DSCP to 0. This is the honest answer to "does my DSCP survive the Internet?" — no, and it was never designed to.
The corresponding weakness is the one from the last topic: DiffServ has no signalling, so it has no admission control. It cannot know whether the EF class is about to be oversubscribed; it can only police EF at the edge and rely on capacity planning. When EF traffic exceeds the provisioned rate, the excess is dropped by the policer, which for voice means degrading all calls rather than refusing a new one. RFC 5865 exists to plug exactly this gap by distinguishing admitted from unadmitted real-time traffic.
RFC 4594 supplies the recommended mapping from application classes to codepoints and PHBs, which is worth using as a default because vendor templates and provider offerings already assume it.
Examples
The DiffServ division of labour: complexity at the edge, simplicity in the core
CUSTOMER DS EDGE (per-customer state) DS CORE (per-class only)
+------------------------------+
---------> | classify | meter | mark | +---------+ +---------+
many flows | (5-tuple)| (CIR)| (DSCP) |---->| PHB |-->| PHB |--->
unknown marks | shape / police / re-mark | | EF/AF/DF| | EF/AF/DF|
+------------------------------+ +---------+ +---------+
state: O(customers) state: O(classes) = ~6
work : expensive, per packet work : one lookup per packet
Crossing a DS boundary:
[ DS domain A ]--- TCA: "your AF31 = our AF21, metered at 50 Mb/s" ---[ B ]
[ DS domain A ]--- no agreement: DSCP bleached to 0 -------------------[ B ]
^ the normal case on the public Internet
AF within one class: ONE queue, THREE drop thresholds
class 2 queue (scheduler share 25%)
+--------------------------------------+
| AF21 AF21 AF23 AF21 AF22 AF21 ... | <- one queue: no reordering
+--------------------------------------+
WRED thresholds: AF23 drops first, then AF22, then AF21
(so edge metering decides who is expendable, core enforces it)
# RFC 4594-style class plan turned into a per-hop policy, mechanically.
PLAN = [
# name, dscp, phb, share%, priority, aqm
("network-control", 48, "CS6", 3, False, None),
("telephony", 46, "EF", 10, True, None), # policed priority
("signalling", 24, "CS3", 2, False, None),
("interactive-video", 34, "AF41", 23, False, "wred-af4"),
("low-latency-data", 26, "AF31", 20, False, "wred-af3"),
("high-throughput", 10, "AF11", 25, False, "wred-af1"),
("best-effort", 0, "DF", 16, False, "fq_codel"),
("scavenger", 8, "CS1", 1, False, "fq_codel"),
]
total = sum(p[3] for p in PLAN)
rt = sum(p[3] for p in PLAN if p[4])
print(f"shares total {total}% (must be <= 100: {total <= 100}), "
f"strict-priority {rt}% (keep <= ~33: {rt <= 33})\n")
print(f"{'class':20s} {'DSCP':>5s} {'PHB':>5s} {'L2 CoS':>7s} {'share':>6s} aqm")
for name, dscp, phb, share, prio, aqm in PLAN:
print(f"{name:20s} {dscp:5d} {phb:>5s} {dscp >> 3:7d} {share:5d}% "
f"{'PRIORITY (policed)' if prio else (aqm or 'tail-drop')}")
# shares total 100% (must be <= 100: True), strict-priority 10% (keep <= ~33: True)
#
# class DSCP PHB L2 CoS share aqm
# network-control 48 CS6 6 3% tail-drop
# telephony 46 EF 5 10% PRIORITY (policed)
# signalling 24 CS3 3 2% tail-drop
# interactive-video 34 AF41 4 23% wred-af4
# low-latency-data 26 AF31 3 20% wred-af3
# high-throughput 10 AF11 1 25% wred-af1
# best-effort 0 DF 0 16% fq_codel
# scavenger 8 CS1 1 1% fq_codel
#
# Note the collision: signalling (CS3) and low-latency-data (AF31) both map to
# L2 CoS 3, and scavenger (CS1) collides with high-throughput (AF11). On an
# 802.1p or MPLS segment those pairs are INDISTINGUISHABLE. Either accept it or
# renumber the plan -- this check belongs in every design review.
def phb_of(dscp):
"""Decode a codepoint into its PHB group without a lookup table."""
if dscp == 0: return "DF (best effort)"
if dscp == 46: return "EF (expedited forwarding)"
if dscp == 44: return "VOICE-ADMIT (EF, admission-controlled)"
if dscp % 8 == 0: return f"CS{dscp // 8} (class selector)"
cls, rem = divmod(dscp, 8)
if 1 <= cls <= 4 and rem in (2, 4, 6):
return f"AF{cls}{rem // 2} (assured forwarding, drop precedence {rem // 2})"
return "unrecognised -> must be treated as DF"
for d in (0, 8, 10, 14, 24, 34, 44, 46, 48, 45):
print(f"DSCP {d:2d} -> {phb_of(d)}")
# DSCP 0 -> DF (best effort)
# DSCP 8 -> CS1 (class selector)
# DSCP 10 -> AF11 (assured forwarding, drop precedence 1)
# DSCP 14 -> AF13 (assured forwarding, drop precedence 3)
# DSCP 24 -> CS3 (class selector)
# DSCP 34 -> AF41 (assured forwarding, drop precedence 1)
# DSCP 44 -> VOICE-ADMIT (EF, admission-controlled)
# DSCP 46 -> EF (expedited forwarding)
# DSCP 48 -> CS6 (class selector)
# DSCP 45 -> unrecognised -> must be treated as DF
Key takeaways
- DiffServ scales by keeping no per-flow state: complexity and per-customer state live at the edge, while the core keeps only O(classes) state and does one DSCP lookup per packet.
- A PHB specifies observable forwarding behaviour, not mechanism, which is what makes multi-vendor policies possible.
- EF (46) means low delay, loss, and jitter with a departure rate independent of other classes. AF gives four scheduler shares with three drop precedences each.
- All drop precedences of one AF class must share one queue, or a flow's packets will be reordered.
- Guarantees hold per DS domain; crossing a boundary needs a bilateral agreement, and without one the DSCP is usually bleached to 0.
- DiffServ has no signalling and hence no admission control — it substitutes edge policing plus capacity planning, which RFC 5865's Voice-Admit codepoint partially addresses.
- Always check whether two classes in your plan collide after mapping to 3-bit 802.1p or MPLS traffic class values.
🧪 Practice
- State the PHB and drop precedence for DSCP 20, 28, and 38, and give the scheduler share each class would plausibly receive in an eight-class plan.
- Explain why AF11, AF12, and AF13 must be placed in the same queue, and what symptom appears if they are split across queues.
- Design a four-class DiffServ plan whose codepoints remain distinguishable after mapping to 802.1p with
dscp >> 3. Show the mapping.- Interview-style: A SaaS vendor asks you to mark their traffic EF so their application performs well for customers worldwide. (Hint: identify the scope within which a PHB is meaningful, and what a provider edge typically does to arriving codepoints.)
MPLS Traffic Engineering
Theory
Everything so far decides a packet's position in a queue. Traffic engineering decides its path. The two are complementary, and the reason path selection matters is a structural flaw in how interior gateway protocols route.
An IGP computes shortest paths by an additive metric (Section 6.3). Every flow toward a given destination follows the same shortest path, so when several sources share part of that path, the shared links saturate while longer alternatives sit empty. The classic illustration is the fish topology: two paths between the same pair of routers, one of IGP cost 30 and one of cost 60, and identical capacity. The IGP puts all traffic on the cost-30 path, and it makes no difference that the cost-60 path is completely idle, because a shortest-path algorithm has no notion of load. Metric tuning cannot fix this in general — lowering the long path's cost merely moves the hotspot rather than splitting the load, and one metric must serve every destination simultaneously.
Traffic engineering replaces "shortest" with "shortest subject to constraints". The mechanism has three parts:
- A forwarding plane that can follow an arbitrary path. Plain IP cannot: each router independently chooses the next hop toward the destination, so a packet cannot be told to take the long way. MPLS solves this by forwarding on a label rather than a destination: the head-end router imposes a label, each hop swaps it for the next, and the path is whatever the label-switched path was built to be. Section 13.2 covers the label mechanics.
- A topology database that includes constraints. The IGP is extended (OSPF-TE, IS-IS-TE) to advertise per-link maximum bandwidth, unreserved bandwidth per priority level, and administrative groups (also called link colours or affinities) so that a tunnel can be told "avoid the satellite link" or "use only encrypted links".
- A path computation and a signalling protocol. CSPF prunes every link that fails the constraints and then runs Dijkstra on what remains. RSVP-TE (RFC 3209) signals the resulting explicit route and reserves bandwidth hop by hop, exactly as in the IntServ topic but per tunnel rather than per flow — which is why the same protocol that failed to scale for flows is entirely practical here.
Note carefully what the reservation means. RSVP-TE bandwidth is an accounting construct: a number decremented in the routers' TE databases so that the next path computation knows what is left. It does not by itself police or queue anything. Whether the tunnel's traffic actually receives the bandwidth depends on the DiffServ policy configured on each interface. TE controls placement; DiffServ controls treatment. Conflating the two is a very common misunderstanding. DS-TE (RFC 4124) bridges them by maintaining separate bandwidth pools per class type, so that a voice tunnel is admitted against a voice-specific pool.
Several LSP attributes make the system practical:
- Setup and hold priority (8 levels): a higher-priority tunnel may preempt an established lower-priority one, which is how a network reconverges toward a good allocation after failures instead of leaving important tunnels unplaced.
- Auto-bandwidth: the head-end measures actual usage and periodically resignals the tunnel at an adjusted size, removing the need to predict demand.
- Fast reroute (RFC 4090): precomputed backup paths installed before a failure, so recovery is a local switchover in tens of milliseconds rather than a reconvergence in seconds. Facility backup uses one bypass tunnel to protect all LSPs crossing a link or node; one-to-one (detour) protects each LSP individually.
The modern successor is segment routing (SR-TE). Instead of signalling a tunnel and installing state at every hop, the head-end encodes the path as a list of segment identifiers in the packet itself, and transit routers simply act on the topmost segment. The path is carried in the packet rather than stored in the network, which eliminates per-tunnel state in the core and the RSVP refresh load entirely.
| RSVP-TE | SR-TE | |
|---|---|---|
| Path encoding | signalled, state at every hop | SID list in the packet header |
| Core state | per LSP | none beyond the IGP's SIDs |
| Control protocol | RSVP-TE, with refreshes | none needed; IGP distributes SIDs |
| Bandwidth admission | distributed, in the routers | usually centralised in a controller (PCE) |
| Protection | FRR with bypass tunnels | TI-LFA, computed from the topology |
| Header overhead | one label | one label per segment in the list |
Examples
The fish: why shortest-path routing creates hotspots
B ---------- C
/ \ cost 10 | \
cost 10 / \ | \ cost 10
A \ cost 30 | D upper path A-B-C-D = cost 30
cost 20 \ \ | / lower path A-E-F-D = cost 60
\ E ------F /
------ cost 20
IGP only, three 400 Mb/s demands A->D on 1000 Mb/s links:
all three take A-B-C-D -> 1200 Mb/s offered on a 1000 Mb/s link
A-E-F-D carries 0 -> congestion with 60% of the network idle
CSPF with a bandwidth constraint:
demand 1 -> A-B-C-D (800 free after)
demand 2 -> A-B-C-D (400 free after)
demand 3 -> A-B has only 200 free, so it is PRUNED
-> A-E-F-D, the longer path, is chosen deliberately
Fast reroute around the protected link B-C:
bypass tunnel B-E-F-C is precomputed and installed BEFORE any failure,
so B switches traffic locally in ~50 ms without waiting for the IGP.
import heapq
# The fish: two disjoint A->D paths of unequal IGP cost and equal capacity.
BASE = {
("A","B"): dict(cost=10, cap=1000),
("B","C"): dict(cost=10, cap=1000),
("C","D"): dict(cost=10, cap=1000), # upper path A-B-C-D, IGP cost 30
("A","E"): dict(cost=20, cap=1000),
("E","F"): dict(cost=20, cap=1000),
("F","D"): dict(cost=20, cap=1000), # lower path A-E-F-D, IGP cost 60
("B","E"): dict(cost=30, cap=1000), # cross links, used by FRR bypasses
("C","F"): dict(cost=30, cap=1000),
}
def fresh():
links = {}
for (u, v), a in BASE.items():
links[(u, v)] = dict(a, resv=0)
links[(v, u)] = dict(a, resv=0) # bidirectional, independent reservations
return links
def cspf(links, src, dst, need_mbps=0.0, exclude=()):
"""Constrained SPF: prune links that fail the constraints, THEN run Dijkstra."""
adj = {}
for (u, v), a in links.items():
if (u, v) in exclude or (v, u) in exclude:
continue # affinity / exclusion constraint
if a["cap"] - a["resv"] < need_mbps:
continue # bandwidth constraint: PRUNE
adj.setdefault(u, []).append((v, a["cost"]))
dist, prev, pq = {src: 0}, {}, [(0, src)]
while pq:
d, u = heapq.heappop(pq)
if u == dst:
break
if d > dist.get(u, 1e18):
continue
for v, c in adj.get(u, []):
if d + c < dist.get(v, 1e18):
dist[v] = d + c
prev[v] = u
heapq.heappush(pq, (d + c, v))
if dst not in dist:
return None, None # no feasible path: REJECT
path, node = [dst], dst
while node != src:
node = prev[node]
path.append(node)
return list(reversed(path)), dist[dst]
def reserve(links, path, mbps):
for u, v in zip(path, path[1:]):
links[(u, v)]["resv"] += mbps # decrement the TE database, not a queue
def loads(links):
return " ".join(f"{u}{v}={a['resv']:.0f}" for (u, v), a in sorted(links.items())
if u < v and a["resv"] > 0)
print("(1) IGP shortest path only -- three 400 Mb/s demands, no constraint:")
plain = fresh()
for i in range(3):
p, c = cspf(plain, "A", "D")
reserve(plain, p, 400)
print(f" demand {i+1}: {'-'.join(p)} IGP cost {c}")
print(f" loads: {loads(plain)}")
# (1) IGP shortest path only -- three 400 Mb/s demands, no constraint:
# demand 1: A-B-C-D IGP cost 30
# demand 2: A-B-C-D IGP cost 30
# demand 3: A-B-C-D IGP cost 30
# loads: AB=1200 BC=1200 CD=1200
# -> 1200 Mb/s offered to 1000 Mb/s links while A-E-F-D carries nothing
print("\n(2) CSPF with a 400 Mb/s bandwidth constraint:")
te = fresh()
for i in range(3):
p, c = cspf(te, "A", "D", need_mbps=400.0)
reserve(te, p, 400)
print(f" demand {i+1}: {'-'.join(p)} IGP cost {c}")
print(f" loads: {loads(te)}")
# (2) CSPF with a 400 Mb/s bandwidth constraint:
# demand 1: A-B-C-D IGP cost 30
# demand 2: A-B-C-D IGP cost 30
# demand 3: A-E-F-D IGP cost 60
# loads: AB=800 AE=400 BC=800 CD=800 EF=400
# -> demand 3 took the LONGER path on purpose, because the short one was full
print("\n(3) A 700 Mb/s demand on the same network:")
p, _ = cspf(te, "A", "D", need_mbps=700.0)
print(f" {'REJECTED -- no path has 700 Mb/s free' if p is None else p}")
# REJECTED -- no path has 700 Mb/s free
# Admission control at the path level: the tunnel simply does not come up.
print("\n(4) Fast reroute: a bypass around the protected link B-C")
p, c = cspf(te, "B", "C", exclude=[("B", "C")])
print(f" bypass B->C avoiding B-C: {'-'.join(p)} cost {c}")
# bypass B->C avoiding B-C: B-E-F-C cost 80
# Precomputed and installed BEFORE the failure -> ~50 ms local repair.
Reading a TE tunnel definition (vendor-neutral summary of the usual attributes)
tunnel MIL-to-FRA-VOICE
head-end A tail-end D
bandwidth 400 Mb/s class-type 1 (voice pool, DS-TE)
setup priority 2 hold priority 2 <- may preempt 3..7
affinity include-any 0x02 (encrypted links only)
exclude-any 0x10 (no satellite)
path option 1 dynamic (CSPF)
path option 2 explicit A-E-F-D <- fallback if CSPF fails
fast-reroute node-protection, bypass preferred
auto-bandwidth adjust every 24 h, 5 min samples, +/- 10% deadband
What each attribute controls:
bandwidth -> the number decremented in the TE database (ACCOUNTING only)
class-type -> which DS-TE pool it is admitted against
priority -> who may preempt whom when the network reconverges
affinity -> which links CSPF is even allowed to consider
fast-reroute-> whether a backup is installed before a failure occurs
IMPORTANT: none of this queues a single packet. The tunnel's traffic gets its
bandwidth only if the interfaces also carry a DiffServ policy that schedules
the corresponding class. TE = placement, DiffServ = treatment.
Key takeaways
- IGP shortest-path routing creates hotspots because one additive metric cannot express load; the fish topology congests one path while an equal-capacity alternative is idle.
- Traffic engineering needs three things: a forwarding plane that follows arbitrary paths (MPLS labels), a topology database carrying constraints (OSPF-TE / IS-IS-TE), and CSPF plus RSVP-TE to compute and signal the path.
- CSPF prunes then runs Dijkstra, so a longer path is chosen deliberately when the shorter one lacks capacity, and a tunnel is simply rejected when no path fits.
- RSVP-TE bandwidth is accounting, not queueing. TE controls placement; DiffServ controls treatment. DS-TE links them with per-class-type bandwidth pools.
- Setup and hold priorities allow preemption so the network can converge to a good allocation; auto-bandwidth removes the need to forecast demand.
- Fast reroute installs backups before failures, giving roughly 50 ms local repair instead of seconds of IGP reconvergence.
- SR-TE carries the path as a SID list in the packet, removing per-tunnel state and refresh load from the core.
🧪 Practice
- In the fish topology, compute the link loads when four 300 Mb/s demands are placed by CSPF with a bandwidth constraint, and state which demand is rejected if any.
- Explain why lowering the lower path's IGP cost to 30 does not solve the hotspot in general, using a second destination to make the point.
- A tunnel is signalled with 500 Mb/s of RSVP-TE bandwidth on a link with no DiffServ policy. Explain what the tunnel's traffic actually receives during congestion, and what configuration would make the reservation meaningful.
- Interview-style: An operator running RSVP-TE with 40,000 tunnels wants to move to segment routing. (Hint: compare what each approach stores in transit routers and what it puts in the packet, then consider where path computation and bandwidth accounting would have to move.)
End-to-End QoS Design Considerations
Theory
A QoS design fails in practice for reasons that have little to do with the mechanisms and much to do with composition. The governing principle is blunt: the path's quality is the quality of its worst-managed hop. A budget is a sum, and one unmanaged device with a deep FIFO buffer contributes more delay than every well-configured hop saves. Designing end to end is therefore mostly about inventorying hops and boundaries rather than tuning thresholds.
Five composition problems recur.
The domain problem. DiffServ guarantees hold within a DS domain. A path from a branch office to a cloud region may cross the enterprise LAN, an SD-WAN overlay, a provider MPLS core, an Internet exchange, and a cloud provider's network. Only the first is under your control; the provider core is contractual; the Internet segment has no QoS at all and will bleach your markings. The realistic design consequence is that end-to-end QoS exists only on paths built from segments that each honour it, which is precisely why enterprises buy MPLS or SD-WAN services for real-time traffic instead of sending it over the open Internet.
The tunnel problem. Encapsulation hides the inner header. An IPsec, GRE, VXLAN, or WireGuard tunnel presents the outer header to intermediate routers, so unless the DSCP is copied from inner to outer at encapsulation, every packet in the tunnel receives identical treatment — usually best effort. Every tunnel configuration therefore needs an explicit DSCP-copy or DSCP-set directive, and this is one of the most common real defects in enterprise QoS. A related trap: a tunnel's overhead reduces the effective MTU and therefore changes serialization arithmetic and shaper accounting, which must be computed on the outer size.
The bottleneck-location problem. A queueing policy only acts where packets queue. If the congestion point is outside the device holding the policy — a sub-rate circuit, a wireless link, a provider policer — the policy is inert. The remedy from Section 12.2 is a parent shaper that recreates the bottleneck inside the device you control. This is the single most common reason a correct-looking policy has no measurable effect.
The asymmetry problem. Most designs configure egress only, because that is where queueing happens. But a branch's download direction queues at the provider's edge, which the customer does not control. The only levers are the provider honouring markings in that direction, or host-side and proxy-side pacing. Any design claiming to protect a download path must say which of those it relies on.
The link-layer problem. The path's markings must survive every layer transition. DSCP maps down to 3 bits on 802.1p and MPLS, and on Wi-Fi it maps into the four WMM access categories (AC_VO, AC_VI, AC_BE, AC_BK), which is a further reduction to two bits of meaning. The mapping must be explicit and verified, because a default that sends EF into the wrong access category silently removes real-time protection on the wireless segment where it matters most.
Given all this, the honest hierarchy of interventions, most to least valuable per unit of effort:
- Fix the buffers. Deploy FQ-CoDel or CAKE at every edge and customer-premises device. This addresses bufferbloat, needs no classification, no marking, and no cross-domain agreement, and on typical access links it improves interactive performance more than any class-based policy.
- Add capacity where it is cheap. A link at 30% utilisation needs no policy.
- Define a small class plan and a trust boundary, and apply it where capacity is expensive: WAN circuits, mobile backhaul, satellite, wireless.
- Add admission control for real-time services whose failure mode is universal degradation.
- Add traffic engineering only when the topology has capacity that shortest-path routing will not use.
Two special environments deserve a note. In data centres, the constraint is different — latency is microseconds, links are fast, and the problem is incast and lossless transport for RDMA. The toolkit is ECN-based congestion control (DCQCN), priority flow control (802.1Qbb) applied to a single lossless class, and enhanced transmission selection (802.1Qaz), with the strong caveat that PFC creates head-of-line blocking and can propagate congestion backwards through the fabric. In SD-WAN, the notable capability is per-application steering across multiple underlays with continuous path measurement, which converts a QoS problem into a path-selection problem — closer in spirit to traffic engineering than to queueing.
Finally, a design that is not measured per class is not a design. Every policy needs per-class counters on packets, bytes, and drops, plus synthetic probes per class along each segment, so that a complaint can be attributed to a hop and a class rather than argued about.
Examples
An end-to-end path, segment by segment, with who controls what
[ phone ]--Wi-Fi--[ AP ]--[ switch ]--[ CE ]===[ PE ]--[ core ]--[ cloud edge ]
| | | | | | | | |
mark EF WMM map 802.1p SHAPE to policed DiffServ PHBs cloud QoS:
AC_VO 3 bits sub-rate here (contract) usually none
+ LLQ
control: you you you you |<--- provider ---->| them
marking: DSCP AC CoS(3b) DSCP DSCP (per TCA) often bleached
Failure points, in the order they actually occur in practice:
1. no parent shaper on CE -> whole LLQ policy inert
2. tunnel does not copy DSCP to the outer header -> everything best effort
3. DSCP->WMM mapping wrong -> voice unprotected on the wireless hop
4. download direction never addressed -> queueing at the PE, invisible to you
5. no per-class counters -> no way to attribute a complaint to a hop
# An end-to-end budget verifier: sum the segments, then find the offender.
SEGMENTS = [
# name, km, rate_mbps, policy, mtu
("branch LAN", 0.1, 1000, "fq_codel", 1500),
("branch WAN egress", 0.0, 20, "llq-priority", 1500),
("provider access", 40.0, 20, "ef-queue", 1500),
("provider core", 900.0, 10000, "ef-queue", 1500),
("DC edge", 1.0, 1000, "ef-queue", 1500),
("DC fabric", 0.2, 25000, "ecn-fq", 9000),
]
QUEUEING_MS = {"fq_codel": 5.0, "llq-priority": 1.5, "ef-queue": 0.5,
"ecn-fq": 0.1, "fifo-deep": 120.0} # an unmanaged deep buffer
FIBER_MS_PER_KM = 0.005
def audit(segments, codec_ms=20.0, dejitter_ms=30.0, budget_ms=150.0):
rows, total = [("codec + packetization", codec_ms)], codec_ms
for name, km, rate, policy, mtu in segments:
ser = mtu * 8 / (rate * 1e6) * 1000 # serialization
prop = km * FIBER_MS_PER_KM # propagation
contribution = ser + prop + QUEUEING_MS[policy]
rows.append((f"{name} ({policy})", contribution))
total += contribution
rows.append(("dejitter buffer", dejitter_ms))
total += dejitter_ms
return rows, total, total <= budget_ms
for label, segs in (
("every segment managed", SEGMENTS),
("ONE hop left as a deep FIFO",
[s if s[0] != "provider access"
else ("provider access", 40.0, 20, "fifo-deep", 1500) for s in SEGMENTS])):
rows, total, ok = audit(segs)
print(f"--- {label} ---")
for n, ms in rows:
print(f" {n:34s} {ms:7.2f} ms")
print(f" {'TOTAL one way':34s} {total:7.2f} ms "
f"budget 150 ms: {'PASS' if ok else 'FAIL'}\n")
# --- every segment managed ---
# codec + packetization 20.00 ms
# branch LAN (fq_codel) 5.01 ms
# branch WAN egress (llq-priority) 2.10 ms
# provider access (ef-queue) 1.30 ms
# provider core (ef-queue) 5.00 ms
# DC edge (ef-queue) 0.52 ms
# DC fabric (ecn-fq) 0.10 ms
# dejitter buffer 30.00 ms
# TOTAL one way 64.03 ms budget 150 ms: PASS
#
# --- ONE hop left as a deep FIFO --- (rows above unchanged, then:)
# provider access (fifo-deep) 120.80 ms <- the single offender
# TOTAL one way 183.53 ms budget 150 ms: FAIL
#
# Seven correctly configured hops cannot compensate for one unmanaged buffer.
# This is why an audit enumerates hops instead of tuning the ones you like.
Class mapping across every layer transition -- verify, do not assume
class DSCP 802.1p MPLS TC WMM (Wi-Fi) notes
----------------- ----- ------- -------- --------------- ----------------
network-control 48 6 6 AC_VO keep off WMM if
possible
telephony (EF) 46 5 5 AC_VO must be AC_VO
signalling (CS3) 24 3 3 AC_VI collides with AF31
interactive-video 34 4 4 AC_VI
low-latency-data 26 3 3 AC_BE collides with CS3
high-throughput 10 1 1 AC_BK collides with CS1
best-effort 0 0 0 AC_BE
scavenger (CS1) 8 1 1 AC_BK collides with AF11
Two collisions appear as soon as 6 bits become 3. Resolve them by either
merging the colliding classes or renumbering so that the pairs differ in the
top three bits. Decide this at design time, not during an incident.
# The five checks that catch most real end-to-end QoS defects.
# 1. Is there a parent shaper on any sub-rate interface?
tc -s class show dev eth0 | grep -A2 'class htb 1:1 ' # ceil must match the service
# 2. Does the tunnel copy DSCP to the outer header?
ip -d link show dev gre1 | grep -o 'tos [^ ]*' # expect "tos inherit"
# tos inherit <- correct: inner DSCP is reflected outward
# tos 0x0 <- WRONG: every tunnelled packet becomes best effort
# 3. Do markings survive each segment? Capture at both ends and compare.
tcpdump -ni eth0 -c 200 -w /tmp/ingress.pcap 'udp portrange 16384-32767'
tshark -r /tmp/ingress.pcap -T fields -e ip.dsfield.dscp | sort | uniq -c
# 196 46 <- EF preserved
# 4 0 <- 4 packets bleached: find the hop that did it
# 4. Are per-class counters actually incrementing, and where are the drops?
tc -s qdisc show dev eth0
tc -s class show dev eth0 | grep -E 'class|dropped'
# 5. Measure per class, not in aggregate: one probe stream per DSCP.
for dscp in 46 34 26 0; do
ping -Q $((dscp << 2)) -c 200 -i 0.05 -q 10.0.0.1 | tail -2
done
# EF (46) must show both a lower max RTT and a much lower mdev than DSCP 0.
# If every class reports the same numbers, the policy is not being applied.
Key takeaways
- The path is only as good as its worst-managed hop. One deep unmanaged FIFO can exceed the entire budget, as the audit above shows (183 ms versus 64 ms).
- QoS is per domain. A path crossing the open Internet has no QoS and its markings will be bleached, which is why real-time traffic is bought as a managed service.
- Tunnels must copy DSCP to the outer header, or all encapsulated traffic is treated identically. Also recompute serialization and shaper rates on the outer packet size.
- A policy acts only where packets actually queue; a parent shaper is required whenever the bottleneck is outside the device.
- Designs are usually egress-only, so the download direction depends on the provider honouring markings. Say which you rely on.
- Verify that class distinctions survive every layer transition: DSCP to 802.1p, to MPLS TC, and to the four WMM categories on Wi-Fi.
- Order of value: fix buffers with FQ-CoDel first, then add capacity, then a small class plan where capacity is expensive, then admission control, then traffic engineering.
- Data centres use ECN-based control plus PFC and ETS, remembering that PFC causes head-of-line blocking and can spread congestion backwards.
- Per-class counters and per-class probes are part of the design, not an afterthought.
🧪 Practice
- Audit this path for a 150 ms voice budget and name the single change with the largest effect: 20 ms codec, a 1 Gb/s LAN with FQ-CoDel, a 10 Mb/s WAN egress with a deep FIFO of 150 ms, 1,200 km of fiber, three managed core hops at 0.5 ms, and a 40 ms dejitter buffer.
- An IPsec tunnel carries voice and backups between two sites and users report that QoS "stopped working" after the VPN was introduced. Give the configuration directive that fixes it, and explain what intermediate routers were seeing before.
- Write the DSCP-to-WMM mapping for a five-class plan and identify which classes become indistinguishable on the wireless segment.
- Interview-style: A company has spent six months deploying an eight-class QoS policy across 200 branches and users report no improvement in video call quality. (Hint: work down the five composition problems in order, and ask first where packets actually queue on a branch link and whether the policy is in that place at all.)
<a id="13-modern-network-infrastructure"></a>