The Leaky Bucket

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.

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.

<!-- {{c_html_root}} -->
<div class="controls">
  <label for="burstSize">{{lbl_burst_size}} <span id="burstVal">8</span></label>
  <input id="burstSize" type="range" min="1" max="20" value="8">
  <button id="btnBurst" type="button">{{btn_burst}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="viz">
  <div class="bucket-wrap">
    <div class="bucket-label">{{lbl_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>{{lbl_queued}} <b id="queued">0</b></span>
      <span>{{lbl_capacity}} <b id="capDisp">16</b></span>
    </div>
  </div>
  <div class="stream-wrap">
    <div class="stream-label">{{lbl_output}}</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">{{lbl_sent}}</span></div>
  <div class="metric"><span class="mval" id="mFwd">0</span><span class="mlbl">{{lbl_forwarded}}</span></div>
  <div class="metric drop"><span class="mval" id="mDrop">0</span><span class="mlbl">{{lbl_dropped}}</span></div>
</div>
<div class="status" id="status">{{status_idle}}</div>

/* {{c_css_root}} */
* { 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; }
/* {{c_css_bucket}} */
.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; }
/* {{c_css_stream}} */
.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; }

// Code not found

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 leaky bucket is deceptively simple to describe but precise in what it guarantees.

The model. The bucket has a finite capacity $b$ (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 $r$ (packets per unit time), regardless of how full it is. The output is always exactly $r$ packets per time unit, as long as the bucket is not empty.

The output guarantee. For any time interval of length $T$, the number of packets forwarded is at most $r \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 $r$ packets per unit time.

Contrast with the token bucket. The token bucket also uses a capacity $b$ and a rate $r$, but it accumulates tokens during idle periods and allows bursting up to $b$ 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 $\text{last} + 1/r$. This $O(1)$ per-packet cost makes the algorithm practical at hardware line rates.

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 $r$, 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 $r$ 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.

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.