Token Bucket Rate Limiting

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.

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>{{lbl_capacity}} <strong id="capVal">10</strong> {{unit_tokens}}
    <input type="range" id="capSlider" min="4" max="20" value="10">
  </label>
  <label>{{lbl_rate}} <strong id="rateVal">2</strong> {{unit_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> {{legend_ok}}</div>
    <div class="legend-row"><span class="dot red"></span> {{legend_drop}}</div>
  </div>
</div>
<div class="log" id="log"></div>
<div class="btns">
  <button id="sendOne">{{btn_send_one}}</button>
  <button id="sendBurst">{{btn_send_burst}}</button>
  <button id="resetBtn" class="ghost">{{btn_reset}}</button>
</div>
<div class="stats" id="stats">{{stat_sent}}: 0 &nbsp;|&nbsp; {{stat_dropped}}: 0 &nbsp;|&nbsp; {{stat_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; }

// Code not found

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 \times T$. That bound is provably tight — it is why network engineers can give latency guarantees even on shared links.

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.

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.

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.