Symptom

You put a rate limiter in front of a service. It allows 1,000 requests per second, and the service can handle 1,000 requests per second, so the limiter should keep the service safe.

It does not. The service still times out, and the traces show why: the limiter admitted 1,000 requests in the first 40 milliseconds of the second and then nothing for 960 milliseconds. Averaged over the second, the limit held. Inside the second, the queue reached 900 and the tail latency reached two seconds.

So you make the limiter stricter — one request every millisecond, no bursts at all — and now a client that batches its writes gets rejected constantly while the service sits idle. You are picking between “bursts allowed and latency unbounded” and “no bursts allowed and capacity wasted”, as if those were the only two options.

They are not. There is a theory here. It says exactly how much burst you can allow and exactly what delay that costs you, and the answer is a formula rather than a tuning session.

Statement

The idea is to stop describing traffic by a rate and start describing it by a curve: a bound on the cumulative arrivals over every window length at once.

Arrival curve. Let $R(t)$ be the cumulative number of bits (or requests) that have arrived by time $t$. A function $\alpha$ is an arrival curve for $R$ if for all $s \le t$,

$$R(t) - R(s) \le \alpha(t - s)$$

That is: over any window of length $d$, no more than $\alpha(d)$ arrives.

Service curve. A server offers service curve $\beta$ if its cumulative output $R^*$ satisfies

$$R^*(t) \ge \inf_{s \le t}\, \{\, R(s) + \beta(t-s) \,\}$$

The common case is the rate-latency curve $\beta_{R,T}(d) = R,[d - T]^+$: after a startup delay $T$, the server drains at rate $R$.

The token bucket is the arrival curve everyone has already implemented without knowing that is what it was.

Token bucket $(r, b)$. Tokens accumulate at rate $r$ into a bucket of depth $b$; a request needs a token to pass. The traffic it admits obeys the affine arrival curve

$$\alpha(d) = b + r\,d$$

And then the result that makes the whole apparatus worth learning:

Delay and backlog bounds. For arrival curve $\alpha$ and service curve $\beta$:

$$\text{backlog} \le \sup_{d \ge 0}\,\{\alpha(d) - \beta(d)\} \qquad > \text{delay} \le \sup_{d \ge 0}\,\{\inf\{\tau \ge 0 : \alpha(d) \le \beta(d + \tau)\}\}$$

Both are the vertical and horizontal distance between the two curves. For a token bucket $(r,b)$ into a rate-latency server $\beta_{R,T}$ with $r \le R$:

$$\text{backlog} \le b + rT, \qquad \text{delay} \le T + \frac{b}{R}$$

That last line is the payoff. Burst size divided by service rate is your worst-case queueing delay, and it is a bound, not an average.

Argument

Why the bounds are the distance between two curves. Plot cumulative arrivals and cumulative departures against time on the same axes. Arrivals lie below $\alpha$ shifted to start at any point; departures lie above $\beta$ similarly. The backlog at time $t$ is $R(t) - R^*(t)$, the vertical gap between the two curves. The delay of the item arriving at $t$, under FIFO, is how long until the departure curve reaches the same height, which is the horizontal gap. Taking suprema over all windows gives the worst case over all admissible traffic, and that is the whole proof modulo the algebra.

Do the affine case concretely, because it is the one you will use. Arrivals are bounded by $b + rd$. The server, after its latency $T$, drains at $R \ge r$. The vertical gap $,b + rd - R[d-T]^+$ increases while $d < T$, peaks at $d = T$ with value $b + rT$, and then decreases because $R \ge r$ makes the service line steeper than the arrival line. So the backlog never exceeds $b + rT$. The horizontal gap is largest for the burst that arrives instantaneously — $b$ units at once — which takes $b/R$ to drain, on top of the server’s own latency $T$.

Where the intuition lives. The condition $r \le R$ is stability, which is the same precondition Little’s law needs: over the long run, arrival rate must not exceed service rate, or nothing is bounded. What network calculus adds on top of Little is the burst term. Little’s law relates the three long-run averages and says nothing about the shape of arrivals inside the window. Network calculus keeps the same stability condition and then charges you exactly $b/R$ seconds for the burstiness you chose to permit.

Running the numbers on the symptom. The service drains at $R = 1000$/s. The naive limiter was effectively $(r=1000, b=1000)$: a full second’s worth of tokens could accumulate and be spent at once. So

$$\text{delay} \le \frac{b}{R} = \frac{1000}{1000} = 1\text{ second}$$

A one-second worst-case queueing delay was not a bug in the limiter; it was the configuration, stated precisely. Choose the delay you can tolerate and solve for the bucket instead. If the latency budget for queueing is 50 ms:

$$b \le R \cdot d = 1000 \times 0.05 = 50$$

A bucket depth of 50 with the same 1,000/s refill rate gives a 50 ms bound. The same limiter, one number changed, and now the tail is a design parameter rather than an emergent property. This is the actual content of the theory: burst depth and worst-case delay are the same knob viewed from two ends.

Composition, which is what makes it a calculus. The reason this is a theory and not a formula is that the pieces compose, in two directions.

Servers in series. If a flow crosses two servers with curves $\beta_1$ and $\beta_2$, the pair behaves as a single server with curve $\beta_1 \otimes \beta_2$, the min-plus convolution $(f \otimes g)(t) = \inf_{0\le s\le t}{f(s) + g(t-s)}$. For rate-latency curves this comes out beautifully:

$$\beta_{R_1,T_1} \otimes \beta_{R_2,T_2} = \beta_{\min(R_1,R_2),\, T_1+T_2}$$

The rates take a minimum and the latencies add. So the end-to-end bound across a chain of five services is not five times the single-hop delay bound; the burst is paid for once, at the slowest hop, and only the fixed latencies accumulate. This “pay bursts only once” phenomenon is the result that makes end-to-end guarantees across a service mesh tractable at all.

Traffic through a server. A flow with arrival curve $\alpha$ leaving a server with service curve $\beta$ has a new arrival curve $\alpha \oslash \beta = \sup_{s\ge0}{\alpha(t+s) - \beta(s)}$ — the output is burstier than the input by exactly the amount the server was allowed to hold back. For the affine case the output of $(r,b)$ through $\beta_{R,T}$ is $(r, b + rT)$: same rate, burst grown by $rT$. Rate limiting at the edge does not stay rate-limited three hops in, and this term is how much re-shaping the interior needs.

Shaping versus policing, which the theory keeps distinct. A policer drops or rejects traffic that exceeds the curve. A shaper delays it into conformance. Both produce output obeying $\alpha$; they differ in what happens to the excess, and the theorem that matters is that a shaper with the same curve as the flow’s own arrival curve adds no delay at all. Putting a correctly-sized shaper in front of a downstream service is therefore free with respect to conforming traffic, which is the argument for shaping at every boundary rather than policing at one.

The dual bucket, because one bucket is usually the wrong model. Real policies use two token buckets in series: $(r_{\text{sustained}}, b)$ and $(r_{\text{peak}}, 1)$, giving the concave curve $\alpha(d) = \min(b + rd,; Md)$ where $M$ is the peak rate. This is exactly the $T_{spec}$ in RFC 2212 and the committed/peak pair in every cloud provider’s throttling documentation. The bound is unchanged in form: you take the vertical and horizontal distance to $\beta$, and the concavity means the tightest constraint switches from the peak term to the sustained term at $d = b/(M - r)$.

Forbids

A rate limit alone bounding latency. A limiter with rate $r$ and depth $b$ permits a queueing delay of $b/R$, and no amount of correctness in the limiter changes that. If you did not choose $b$, you did not choose your tail.

Deterministic delay guarantees for unshaped traffic. With no arrival curve, the supremum in the bound is infinite. There is no bound to compute. Traffic must be constrained at ingress or there is nothing to prove downstream.

Averaging away a burst. “1,000 requests per second” is not an arrival curve. It is one point on one, and the entire behaviour that hurts you lives in the window lengths shorter than a second.

Sizing a queue independently of the burst. The backlog bound $b + rT$ says buffer depth is determined by the admission policy. A queue shorter than that drops conforming traffic; a queue longer than that only adds latency, because anything above $b + rT$ can never be occupied by conforming traffic anyway. Bufferbloat is exactly this mistake made in hardware.

Does not forbid

It does not require reserved capacity or QoS hardware, which is the most common reason people dismiss it. Network calculus grew up alongside IntServ and RSVP, both of which failed to deploy on the public internet, and the theory is widely written off with them. But the delay bound needs only an arrival curve and a service curve, and a plain thread pool draining at a known rate is a rate-latency server. The theory applies unchanged to an HTTP service behind a token-bucket limiter, with no network support of any kind.

It does not make bursts bad. A large $b$ is a deliberate trade: it absorbs client-side batching and improves goodput for clients that write in chunks. The theory does not say to set $b$ small, it says to know what $b$ costs. The common advice to allow a burst equal to a few seconds of steady rate is fine for a batch ingestion endpoint and only wrong when the same endpoint carries interactive traffic.

It does not compete with statistical multiplexing. Deterministic bounds are worst-case and will be pessimistic for aggregates of many independent flows, where the effective bandwidth is far below the sum of the peak rates. Stochastic network calculus exists for precisely that regime, and using the deterministic version per-flow while sizing the aggregate statistically is standard, not contradictory.

It does not need the traffic to actually be smooth. The arrival curve is an upper bound, not a description. Traffic well below its curve simply gets bounds that are loose, and loose bounds are still bounds.

Boundary

  • Worst case, not typical case. Every number here is an envelope. If you want the distribution, this is the wrong tool and queueing theory is the right one; the two answer different questions about the same system.
  • The bound needs a real service curve. Assuming $\beta_{R,T}$ when the server’s rate collapses under load — garbage collection, cache misses, contention — invalidates the guarantee. The service curve must be the pessimistic one, which is why the $R$ you plug in is a p99 drain rate and not a mean.
  • FIFO assumed for the delay bound. Priority and fair-queueing servers get their own service curves, one per class, and computing the residual curve left to the low-priority class is where most of the real work in an analysis goes.
  • Aggregate flows need care. Bounding each flow individually and adding the results is valid but can be very loose; tight multiplexed bounds are an active area and the source of most of the subtlety in the field.
  • Long-run stability is still required. If $r > R$ nothing is bounded, and the theory degenerates to the same warning Little’s law already gave you.

The sentence to carry out of this: you do not configure a rate limiter, you configure a delay bound, and $b/R$ is the exchange rate between them.