Introduction

Every time you stream a video, load a web page, or send a message, your data travels as a shower of small packets. Networks are shared resources: if everyone sends at full speed at once, routers overflow and packets are dropped. Rate limiting is the discipline of shaping that chaos into something manageable.

The token bucket algorithm is the most widely deployed solution. Picture a bucket that slowly fills with tokens — one token arriving every fixed interval, up to some maximum capacity. To send a packet, you must first claim a token from the bucket. If the bucket is empty, you wait (or the packet is dropped). The result is elegant: bursts are allowed as long as saved-up tokens cover them, but the long-term average rate is strictly capped by how fast tokens refill.

Invented in the early 1980s and standardized in networking RFCs throughout the 1990s, the token bucket is not a theoretical curiosity. It lives inside every home router, cloud load balancer, API gateway, and quality-of-service policy engine on the planet. Understanding it means understanding how the internet stays usable even when everyone is on it at the same time.

Try It

The bucket starts full. Each packet you send costs one token; tokens refill automatically at the configured rate. Try sending a burst — the bucket drains fast. Then wait and watch it recover.

<div class="controls">
  <label>Bucket capacity: <strong id="capVal">10</strong> tokens
    <input type="range" id="capSlider" min="4" max="20" value="10">
  </label>
  <label>Refill rate: <strong id="rateVal">2</strong> tokens/s
    <input type="range" id="rateSlider" min="1" max="8" value="2">
  </label>
</div>
<div class="bucket-wrap">
  <div class="bucket-outer">
    <div class="bucket-fill" id="fill"></div>
    <div class="bucket-label" id="bucketLabel">10 / 10</div>
  </div>
  <div class="legend">
    <div class="legend-row"><span class="dot green"></span> Token available</div>
    <div class="legend-row"><span class="dot red"></span> Packet dropped</div>
  </div>
</div>
<div class="log" id="log"></div>
<div class="btns">
  <button id="sendOne">Send 1 packet</button>
  <button id="sendBurst">Send burst (5 packets)</button>
  <button id="resetBtn" class="ghost">Reset</button>
</div>
<div class="stats" id="stats">Sent: 0 &nbsp;|&nbsp; Dropped: 0 &nbsp;|&nbsp; Tokens refilled: 0</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.controls { display: flex; flex-direction: column; gap: .4rem; margin-bottom: .8rem; font-size: .88rem; }
.controls label { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; }
.controls input[type=range] { flex: 1; min-width: 100px; max-width: 180px; }
.bucket-wrap { display: flex; align-items: flex-end; gap: 1.4rem; margin-bottom: .7rem; }
.bucket-outer { position: relative; width: 72px; height: 130px; border: 2.5px solid #1d3557;
                border-radius: 0 0 10px 10px; overflow: hidden; background: #f0f4f8; }
.bucket-fill { position: absolute; bottom: 0; left: 0; right: 0; background: #2a9d8f;
               transition: height .35s ease; }
.bucket-label { position: absolute; width: 100%; text-align: center; bottom: 6px;
                font: 700 12px ui-monospace, monospace; color: #fff; text-shadow: 0 1px 2px #0006; pointer-events: none; }
.legend { font-size: .82rem; display: flex; flex-direction: column; gap: .3rem; }
.legend-row { display: flex; align-items: center; gap: .4rem; }
.dot { width: 10px; height: 10px; border-radius: 50%; display: inline-block; }
.dot.green { background: #2a9d8f; }
.dot.red { background: #e63946; }
.log { height: 90px; overflow-y: auto; background: #f8f9fa; border: 1px solid #dde;
       border-radius: 6px; padding: .4rem .6rem; font: 13px ui-monospace, monospace;
       margin-bottom: .6rem; }
.log .ok { color: #0a7d33; }
.log .drop { color: #c92f3c; }
.log .refill { color: #1d6fa5; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.stats { font-size: .83rem; color: #555; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Token Bucket simulation.
// State: tokens (float), capacity (int), rate (tokens/sec).
// Invariant: tokens in [0, capacity].
// Per packet: if tokens >= 1, consume 1 and pass; else drop.
// Refill: tokens = min(capacity, tokens + rate * dt) each animation frame.

let capacity = 10, rate = 2;
let tokens = capacity;
let sent = 0, dropped = 0, totalRefilled = 0;
let lastTick = performance.now();
let rafId = null;

const fillEl   = document.getElementById('fill');
const labelEl  = document.getElementById('bucketLabel');
const logEl    = document.getElementById('log');
const statsEl  = document.getElementById('stats');
const capSlider  = document.getElementById('capSlider');
const rateSlider = document.getElementById('rateSlider');
const capVal     = document.getElementById('capVal');
const rateVal    = document.getElementById('rateVal');

function updateBucket() {
  const pct = tokens / capacity;
  fillEl.style.height = (pct * 100) + '%';
  labelEl.textContent = tokens.toFixed(1) + ' / ' + capacity;
}

function addLog(text, cls) {
  const d = document.createElement('div');
  d.className = cls; d.textContent = text;
  logEl.appendChild(d);
  logEl.scrollTop = logEl.scrollHeight;
  // keep log bounded
  while (logEl.children.length > 60) logEl.removeChild(logEl.firstChild);
}

function updateStats() {
  statsEl.innerHTML = fmt('Sent: %sent% &nbsp;|&nbsp; Dropped: %dropped% &nbsp;|&nbsp; Tokens refilled: %round%', { sent: sent, dropped: dropped, round: Math.round(totalRefilled) });
}

function tick(now) {
  const dt = (now - lastTick) / 1000;
  lastTick = now;
  const add = rate * dt;
  const before = tokens;
  tokens = Math.min(capacity, tokens + add);
  const actual = tokens - before;
  if (actual > 0.001) {
    totalRefilled += actual;
    // log a refill message only roughly once per token
    if (Math.floor(tokens) > Math.floor(before)) {
      addLog(fmt('↑ Refill — tokens now %tokens%', { tokens: tokens.toFixed(1) }), 'refill');
    }
  }
  updateBucket();
  updateStats();
  rafId = requestAnimationFrame(tick);
}

function sendPackets(n) {
  for (let i = 0; i < n; i++) {
    if (tokens >= 1) {
      tokens -= 1;
      sent++;
      addLog(fmt('✓ Packet sent — %tokens% tokens left', { tokens: tokens.toFixed(1) }), 'ok');
    } else {
      dropped++;
      addLog('✗ Packet DROPPED — bucket empty!', 'drop');
    }
  }
  updateBucket();
  updateStats();
}

document.getElementById('sendOne').addEventListener('click', () => sendPackets(1));
document.getElementById('sendBurst').addEventListener('click', () => sendPackets(5));
document.getElementById('resetBtn').addEventListener('click', () => {
  tokens = capacity; sent = 0; dropped = 0; totalRefilled = 0;
  logEl.innerHTML = '';
  updateBucket(); updateStats();
  addLog('— Reset —', 'refill');
});

capSlider.addEventListener('input', () => {
  capacity = parseInt(capSlider.value);
  capVal.textContent = capacity;
  tokens = Math.min(tokens, capacity);
  updateBucket();
});
rateSlider.addEventListener('input', () => {
  rate = parseInt(rateSlider.value);
  rateVal.textContent = rate;
});

// Verify core invariant in console (node-verifiable subset):
// For any sequence of send(n) and wait(t) calls:
//   total_passed <= initial_tokens + rate * total_time
// Test: capacity=10, rate=2, drain all 10, wait 3s => 6 more tokens pass
// => total = 16 <= 10 + 2*3 = 16  ✓
console.log(fmt('Token bucket demo loaded. capacity=%capacity% rate=%rate% tokens/s', { capacity: capacity, rate: rate }));
console.log('Invariant: packets_passed <= capacity + rate * elapsed_seconds');

addLog(fmt('Bucket full (%capacity% tokens). Ready.', { capacity: capacity }), 'refill');
updateBucket(); updateStats();
lastTick = performance.now();
rafId = requestAnimationFrame(tick);
Result
Console

Notice the asymmetry between sending and refilling. You can drain the bucket almost instantly with a burst, but refilling takes real time proportional to the rate. This is the key invariant: no matter how spiky the traffic, the number of packets passing through over any interval T can never exceed capacity+rate×Tcapacity + rate \times T. That bound is provably tight — it is why network engineers can give latency guarantees even on shared links.

The Real Complexity

The token bucket looks deceptively simple, but it encodes a precise mathematical contract.

  • The (σ, ρ) traffic envelope: a flow conforming to a token bucket with capacity σ and rate ρ satisfies: for any interval of length T, at most σ + ρ·T bits (or packets) can arrive. This is the formal (σ, ρ)-constrained or leaky-bucket specification used in network calculus.
  • Worst-case latency: when traffic is shaped to (σ, ρ) and the link has capacity C, a simple bound gives maximum queuing delay of σ/C. This lets engineers guarantee bounded delay across a network path — the foundation of real-time streaming, VoIP, and industrial control networks.
  • Two variants: the token bucket allows bursts up to the bucket capacity; the leaky bucket as a meter smooths output to exactly ρ regardless of input burstiness. Both appear in standards — RFC 2697 (srTCM) and RFC 2698 (trTCM) define them for IP packet marking.
  • Composability: two token buckets in series with parameters (σ₁, ρ₁) and (σ₂, ρ₂) produce a flow bounded by (σ₁ + σ₂, min(ρ₁, ρ₂)) — a key lemma in network calculus that lets you chain service guarantees across routers.
  • Relation to scheduling: token bucket is a policer (it measures conformance) or shaper (it delays non-conforming packets). Deciding how to allocate bucket parameters across thousands of flows to meet aggregate QoS targets is itself an optimization problem related to bin packing.

Where It Matters

The token bucket's combination of burst tolerance and provable long-term bounds makes it indispensable across computing:

  • API gateways: every major cloud API (AWS, Google, Stripe, GitHub) enforces per-user or per-key rate limits with token bucket policies. Your 429 "Too Many Requests" response is the bucket running dry.
  • ISP traffic shaping: internet service providers use token bucket meters (often two-rate, three-color as in RFC 2698) to mark packets as green/yellow/red, then drop or deprioritize red packets during congestion.
  • Streaming media: adaptive bitrate systems (HLS, DASH) model the client's playback buffer as a token bucket to decide when to switch quality levels without rebuffering.
  • Industrial and real-time networks: Time-Sensitive Networking (TSN, IEEE 802.1Q) uses credit-based shapers — a direct implementation of token bucket — to guarantee sub-millisecond latency for factory automation and in-vehicle networks.
  • Cloud resource quotas: compute credits, storage IOPS limits, and database request units in AWS, Azure, and GCP are all governed by token bucket replenishment policies exposed directly to users.
  • Operating system kernel: Linux's tc (traffic control) subsystem implements token bucket filters (tbf) natively; every Linux server can apply per-interface or per-flow rate limits with a single command.

Conclusion

The token bucket is a masterclass in elegant design: a single integer (the current token count) encodes everything a network device needs to decide whether a packet may pass. That count ticks upward at a fixed rate and downward with every transmission — and from those two operations flows a provable, composable guarantee about long-term throughput and worst-case delay.

Next time your API client hits a rate limit or your video stream pauses to buffer, you have met the token bucket in the wild. And if you ever need to build something that must be fast on average yet forgiving of bursts, you now have the right mental model — the same one every router on the internet relies on.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/token-bucket/Content licensed under CC BY-NC 4.0.