Introduction

Picture a real bucket with a small hole in its base. You can pour water in at any rate — a trickle one second, a torrent the next. But the water drips out at exactly the same steady pace, determined only by the size of the hole. Overflow simply spills away.

That is the leaky bucket algorithm in a sentence. Replace "water" with "network packets" and you have one of the most enduring ideas in traffic engineering. Packets arrive in unpredictable bursts — a user clicks a link, a server replies, a video frame is compressed. The network downstream, however, expects a calm, bounded stream. The leaky bucket sits between the chaos and the calm and acts as a shock absorber.

The algorithm was described by John Turner in 1986 as part of ATM network research, and independently formalized shortly after. Despite being nearly four decades old, it remains the conceptual core of rate limiters in routers, cloud APIs, and operating system schedulers. Its dual, the token bucket, allows controlled bursting; the leaky bucket refuses all bursting and enforces a strict constant output rate.

Try It

Click Send burst to inject a batch of packets into the bucket. The bucket drains at a constant rate — one packet every tick. If packets arrive faster than the drain rate, the excess overflows and is dropped. Adjust the burst size and watch the effect.

<!-- Leaky Bucket demo — burst packets in, constant drain out -->
<div class="controls">
  <label for="burstSize">Burst size: <span id="burstVal">8</span></label>
  <input id="burstSize" type="range" min="1" max="20" value="8">
  <button id="btnBurst" type="button">Send burst</button>
  <button id="btnReset" type="button" class="ghost">Reset</button>
</div>
<div class="viz">
  <div class="bucket-wrap">
    <div class="bucket-label">Bucket</div>
    <div class="bucket" id="bucket">
      <div class="fill" id="fill"></div>
      <div class="drain-arrow" id="drainArrow">&#x25BC;</div>
    </div>
    <div class="bucket-stats">
      <span>Queued: <b id="queued">0</b></span>
      <span>Capacity: <b id="capDisp">16</b></span>
    </div>
  </div>
  <div class="stream-wrap">
    <div class="stream-label">Output stream</div>
    <canvas id="streamCanvas" width="260" height="120"></canvas>
  </div>
</div>
<div class="metrics">
  <div class="metric"><span class="mval" id="mSent">0</span><span class="mlbl">Sent</span></div>
  <div class="metric"><span class="mval" id="mFwd">0</span><span class="mlbl">Forwarded</span></div>
  <div class="metric drop"><span class="mval" id="mDrop">0</span><span class="mlbl">Dropped</span></div>
</div>
<div class="status" id="status">Click "Send burst" to inject packets.</div>

/* Leaky Bucket demo styles */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.controls { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .8rem; }
label { font-size: .88rem; color: #444; }
input[type=range] { width: 110px; cursor: pointer; }
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; }
.viz { display: flex; gap: 1.2rem; align-items: flex-start; flex-wrap: wrap; }
/* Bucket visual — fills from bottom, drains via arrow indicator */
.bucket-wrap { display: flex; flex-direction: column; align-items: center; gap: .3rem; }
.bucket-label, .stream-label { font-size: .8rem; font-weight: 600; color: #555; text-transform: uppercase; letter-spacing: .04em; }
.bucket { position: relative; width: 80px; height: 120px; border: 2.5px solid #1d3557;
          border-top: none; border-radius: 0 0 14px 14px; overflow: hidden; background: #eef2f7; }
.fill { position: absolute; bottom: 0; left: 0; right: 0; background: #457bb7;
        transition: height .22s ease; height: 0%; }
.drain-arrow { position: absolute; bottom: -22px; left: 50%; transform: translateX(-50%);
               font-size: 1.1rem; color: #457bb7; opacity: 0; transition: opacity .15s; }
.drain-arrow.active { opacity: 1; }
.bucket-stats { font-size: .8rem; color: #444; display: flex; flex-direction: column; gap: .1rem; }
/* Output stream canvas and metric counters */
.stream-wrap { flex: 1; min-width: 200px; display: flex; flex-direction: column; gap: .3rem; }
canvas { border: 1px solid #dde4ec; border-radius: 8px; background: #f8fafc; display: block; }
.metrics { display: flex; gap: 1.2rem; margin-top: .6rem; flex-wrap: wrap; }
.metric { display: flex; flex-direction: column; align-items: center; gap: .1rem; }
.mval { font-size: 1.5rem; font-weight: 700; color: #1d3557; }
.metric.drop .mval { color: #c92f3c; }
.mlbl { font-size: .75rem; color: #666; }
.status { margin-top: .5rem; font-size: .9rem; font-weight: 600; min-height: 1.3em; color: #444; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

// Algorithm parameters
const CAPACITY = 16;
const DRAIN_RATE = 1; // packets forwarded per tick
const TICK_MS = 600;

let bucket = 0;   // packets currently queued in the bucket
let totalSent = 0;
let totalFwd = 0;
let totalDrop = 0;
let history = []; // per-tick forwarded counts for the bar chart
let running = false;
let intervalId = null;

const canvas = document.getElementById('streamCanvas');
const ctx = canvas.getContext('2d');

function drawStream() {
  // Draw one bar per tick; bar height = forwarded packets that tick
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  const maxBars = 26;
  const barW = 8;
  const gap = 2;
  const baseY = canvas.height - 10;
  const scaleH = (canvas.height - 20);
  const recent = history.slice(-maxBars);
  recent.forEach((val, i) => {
    const x = canvas.width - (recent.length - i) * (barW + gap) + gap;
    if (val > 0) {
      ctx.fillStyle = '#457bb7';
      ctx.fillRect(x, baseY - scaleH * Math.min(val / DRAIN_RATE, 1), barW, scaleH * Math.min(val / DRAIN_RATE, 1));
    }
  });
  // Red dashed line marks the maximum output rate (DRAIN_RATE)
  ctx.strokeStyle = '#c92f3c';
  ctx.setLineDash([4, 3]);
  ctx.lineWidth = 1.5;
  ctx.beginPath();
  ctx.moveTo(0, baseY - scaleH);
  ctx.lineTo(canvas.width, baseY - scaleH);
  ctx.stroke();
  ctx.setLineDash([]);
}

function updateUI() {
  const pct = (bucket / CAPACITY) * 100;
  document.getElementById('fill').style.height = pct + '%';
  document.getElementById('queued').textContent = bucket;
  document.getElementById('capDisp').textContent = CAPACITY;
  document.getElementById('mSent').textContent = totalSent;
  document.getElementById('mFwd').textContent = totalFwd;
  document.getElementById('mDrop').textContent = totalDrop;
  drawStream();
}

function tick() {
  // Drain up to DRAIN_RATE packets from the bucket each tick
  let forwarded = 0;
  if (bucket > 0) {
    const drained = Math.min(bucket, DRAIN_RATE);
    bucket -= drained;
    forwarded = drained;
    totalFwd += forwarded;
    document.getElementById('drainArrow').classList.add('active');
  } else {
    document.getElementById('drainArrow').classList.remove('active');
  }
  history.push(forwarded);
  if (history.length > 60) history.shift();
  updateUI();
  if (bucket === 0 && !running) {
    document.getElementById('status').textContent = i18nFmt('Bucket empty. Forwarded %fwd%, dropped %drop% total.', { fwd: totalFwd, drop: totalDrop });
  }
}

function sendBurst() {
  const burst = parseInt(document.getElementById('burstSize').value, 10);
  totalSent += burst;
  const accepted = Math.min(burst, CAPACITY - bucket);
  const dropped = burst - accepted;
  bucket += accepted;
  totalDrop += dropped;
  running = true;
  if (!intervalId) {
    intervalId = setInterval(() => {
      tick();
      if (bucket === 0) {
        running = false;
      }
    }, TICK_MS);
  }
  document.getElementById('status').textContent = i18nFmt('Injected %n% packets — %drop% dropped (overflow).', { n: burst, drop: dropped });
  updateUI();
}

function reset() {
  // Clear all state and stop the timer
  clearInterval(intervalId);
  intervalId = null;
  bucket = 0;
  totalSent = 0;
  totalFwd = 0;
  totalDrop = 0;
  history = [];
  running = false;
  document.getElementById('drainArrow').classList.remove('active');
  document.getElementById('status').textContent = 'Click "Send burst" to inject packets.';
  updateUI();
}

document.getElementById('burstSize').addEventListener('input', function () {
  document.getElementById('burstVal').textContent = this.value;
});
document.getElementById('btnBurst').addEventListener('click', sendBurst);
document.getElementById('btnReset').addEventListener('click', reset);

// Initial render with empty bucket
updateUI();
Result
Console

Notice the key property: no matter how large or irregular the incoming bursts are, the output stream is always perfectly smooth — one packet per tick, never more. This is fundamentally different from queuing without rate control, where a downstream receiver would see the same spikes the sender produced. The price is that excess packets are dropped, not delayed.

The Real Complexity

The leaky bucket is deceptively simple to describe but precise in what it guarantees.

The model. The bucket has a finite capacity bb (the queue depth). Packets that arrive when the bucket is full are dropped immediately — they never enter the queue. The bucket drains at a fixed rate rr (packets per unit time), regardless of how full it is. The output is always exactly rr packets per time unit, as long as the bucket is not empty.

The output guarantee. For any time interval of length TT, the number of packets forwarded is at most r⋅Tr \cdot T. This is a hard deterministic bound — not an average, not a "most of the time." Any downstream component can be dimensioned on the assumption that it will never see more than rr packets per unit time.

Contrast with the token bucket. The token bucket also uses a capacity bb and a rate rr, but it accumulates tokens during idle periods and allows bursting up to bb packets at once. A leaky bucket smooths output completely; a token bucket trades smoothness for flexibility. Neither is strictly better — the right choice depends on whether the downstream system can absorb short bursts.

Overflow as a policy decision. Dropping overflow is the simplest policy, but real systems sometimes mark overflowing packets (setting a "discard eligible" bit in ATM or a DSCP marking in IP) so that a downstream network node can drop them under congestion rather than the sender. This is the idea behind the dual-rate leaky bucket used in traffic policing.

Implementation. Because the output rate is constant, a software leaky bucket needs only one integer: the timestamp of the last forwarded packet. The next packet may be forwarded no earlier than last+1/r\text{last} + 1/r. This O(1)O(1) per-packet cost makes the algorithm practical at hardware line rates.

Where It Matters

The constant-output guarantee of the leaky bucket makes it indispensable anywhere a receiver needs protection from traffic spikes:

  • Router line cards: hardware implementations police each traffic flow to a contractual rate rr, dropping or marking excess packets before they reach the core. ATM networks made this mandatory; modern IP routers use the same logic under names like "traffic policing" or "committed access rate."
  • Cloud API rate limiting: every major API gateway (AWS API Gateway, Google Cloud Endpoints, Nginx rate limit module) enforces per-client request rates using a leaky bucket or its close relative. A client that sends 1,000 requests in one second to an API rated at 100 req/s will have 900 requests dropped or queued.
  • Operating system I/O schedulers: disk and network I/O can be shaped with a leaky bucket so that a single greedy process cannot monopolize bandwidth, giving other processes fair access.
  • Video streaming: adaptive bitrate players buffer network jitter; the leaky bucket model describes the decoder buffer — if the network is too slow, the buffer drains to zero and playback stalls.
  • Financial trading systems: order rate limits imposed by exchanges are leaky buckets — a trading firm may submit at most rr orders per second; excess orders are rejected.

Understanding the leaky bucket is understanding how the internet avoids collapse under bursty load. Its companion, the token bucket, is the go-to when controlled bursting is acceptable rather than harmful.

Conclusion

The leaky bucket is one of those ideas that seems almost too simple — pour water in, watch it drip out at a fixed rate, spill the overflow. Yet that simplicity is exactly the source of its power. The output rate is not probabilistic, not amortized, not "on average" — it is an iron-clad bound that every component downstream can rely on.

From 1986 ATM switches to 2024 cloud API gateways, the algorithm has outlasted dozens of competing proposals because it answers a timeless question: how do you give a chaotic sender a well-behaved output without storing infinite state? One bucket, one rate, one drop rule.

If you need a burst occasionally, reach for the token bucket. But if you need a steady stream no matter what, the leaky bucket remains the cleanest answer computer networking has found.

Share this article

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

Comments

Loading comments...

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