A system's memory controller is shared by a display engine, which must never be starved, and an accelerator, which can use all the bandwidth it is given. The accelerator's bursts keep delaying the display. Adding back-pressure does not help: the controller accepts everything quickly, then falls behind on the display's urgent reads. What is needed is a limit on the accelerator before its traffic reaches the controller.
How can you limit a source's rate and burst size without any feedback from the receiver?
The obvious limit is a fixed gap: "the accelerator may send one request every four cycles". That caps the average, but it also forbids any burst, even when the system is idle and could take one. Real traffic is bursty, and a strict gap either wastes capacity (gap too long) or protects nobody (gap too short). The limit should allow short bursts but bound both the burst and the long-run average.
A token bucket has two parameters: a rate R (tokens added per cycle) and a size S (the most tokens it can hold). Sending one unit costs one token; with no token, the source waits. Tokens arrive steadily, so the long-run average can never exceed R. Unused tokens accumulate up to S, so after a quiet period the source may burst, but never by more than the bucket holds. Two exact bounds follow:
The second bound is slightly more than S because tokens keep arriving during a burst. Nothing here needs any message from the receiver: the bucket is a promise made in advance, enforced at the source. Its close relative, the leaky bucket, smooths traffic to a constant rate with no bursts at all.
The model shapes a source that offers bursts of 12 words every 40 cycles (0.3 words per cycle on average) with a bucket of rate 0.25 and size 4, and checks the output against both bounds.
"""A token bucket shapes bursty traffic to an average rate with a bounded burst.
Tokens arrive at R = 0.25 per cycle into a bucket that holds at most S = 4 tokens.
Sending one word costs one token. The source offers bursts of 12 words every 40 cycles
(an average of 0.3 words per cycle, above R). Count what the shaper lets through.
"""
R, S = 0.25, 4
tokens, queue = float(S), 0
out_per_10 = []
sent_total, offered_total, window = 0, 0, 0
max_burst, run = 0, 0
for t in range(400):
if t % 40 < 12:
queue += 1; offered_total += 1 # bursty source
tokens = min(S, tokens + R)
if queue and tokens >= 1:
tokens -= 1; queue -= 1; sent_total += 1; window += 1; run += 1
max_burst = max(max_burst, run)
else:
run = 0
if t % 10 == 9:
out_per_10.append(window); window = 0
print(f"offered {offered_total} words, sent {sent_total} in 400 cycles "
f"(average {sent_total / 400:.3f} per cycle, rate limit {R})")
print(f"longest back-to-back run: {max_burst} words (bucket size {S})")
print("words sent per 10 cycles:", out_per_10[:12])
# Bounds: in T cycles at most S + R*T words; a burst of n back-to-back words needs
# n <= S + R*n tokens, so n <= S / (1 - R).
assert sent_total <= S + R * 400 and max_burst <= S / (1 - R)
print(f"PASS: at most S + R*T = {S + R * 400:.0f} words in 400 cycles, bursts at most S/(1-R) = {S / (1 - R):.1f}")It prints:
offered 120 words, sent 103 in 400 cycles (average 0.258 per cycle, rate limit 0.25)
longest back-to-back run: 5 words (bucket size 4)
words sent per 10 cycles: [6, 2, 3, 1, 4, 2, 3, 2, 3, 2, 3, 2]
PASS: at most S + R*T = 104 words in 400 cycles, bursts at most S/(1-R) = 5.3The shaper let through 103 of 120 words: the source asked for more than its rate, and the excess waits (or, in some designs, is dropped). The average, 0.258, is just above 0.25 because the bucket started full, exactly as the S + RT bound allows (104 at most). The longest burst was 5 words, within S/(1 − R) = 5.3. The per-window counts show the first burst using the saved tokens (6 in the first 10 cycles), then the output settling to about 2.5 per 10 cycles.
Mechanism | Guarantees | Cost |
|---|---|---|
Token bucket (rate R, size S) | Average ≤ R; bursts bounded by S | A counter and an adder per regulated source |
Leaky bucket (constant rate) | Smooth output at R; no bursts | Higher latency for bursty sources |
Fixed gap between requests | Average ≤ 1/gap; no bursts | Wastes idle capacity |
Back-pressure only | No overflow | No protection for other sources' latency |
Rate limits complement credits rather than replacing them: credits keep a buffer from overflowing; rate limits keep one source from taking more than its share of a shared resource.
Where | Use |
|---|---|
SoC interconnects and memory controllers | Bandwidth regulators on initiator ports cap a requester's average rate and burst, protecting latency-sensitive traffic such as display (lesson 8.7). |
Networks | Traffic shaping and policing at network edges use token buckets to enforce agreed rates. |
A regulator on the accelerator is configured with a generous bucket size so that "short bursts are free" (illustrative): rate 25% of memory bandwidth, bucket 4,096 requests. After a long idle period the accelerator fires 4,096 requests back to back, and the display engine misses its deadline anyway. The rate was right; the burst bound was the real promise, and it was set far beyond what the display's buffering could ride out. Size S from what the protected traffic can tolerate, not from what the regulated source would like.
S + RT = 8 + 0.1 × 100 = 18.
Tokens keep arriving at rate R during the burst, so a burst of n needs only n − Rn tokens from the bucket: n ≤ S/(1 − R).
Not by itself: it limits the source's rate and burst, but the receiver must still be able to absorb the burst and keep up with the rate, or be protected by credits.
A token bucket (rate R, size S) limits a source with no feedback: average at most R, bursts bounded by the bucket.
Exact bounds: at most S + RT units in T cycles, and a burst of at most S/(1 − R).
Rate limits protect shared resources; credits protect buffers. Size S from what the protected traffic can tolerate.