From Token Buckets to Carousel: Solving Rate Limiter Challenges in High‑Performance Networks

Basic Principle of Token Bucket Rate Limiter

Engineers familiar with packet processing know the token bucket model: a bucket holds a limited number of tokens, each packet consumes a token, and packet forwarding depends on token availability. For a PPS‑based limiter, one token represents one packet, and the bucket refills at the configured rate.

Existing Problems

1. Precision Issue – With microsecond timestamps, token generation may be fractional (e.g., 0.3 token per microsecond) and get truncated, causing the limiter to under‑rate traffic.

One workaround is to scale token consumption (e.g., 1000 tokens per packet) to avoid fractions, but this risks 32‑bit overflow.

2. Cascading Compensation Issue – When multiple limiters are chained, a packet dropped by a downstream limiter still consumes tokens upstream, leading to unfair token usage unless upstream tokens are compensated.

3. TCP Sensitivity to Packet Loss – Token buckets drop packets when the rate exceeds the limit; TCP reacts aggressively to loss, reducing effective throughput (e.g., a 100 Mbps limit may only achieve ~80 Mbps).

First Improvement: Port‑Loan Backpressure Limiter

To mitigate TCP loss, a backpressure mechanism delays polling of virtual NIC queues when the token bucket is empty, effectively “borrowing” future tokens and signaling congestion to the guest kernel.

This design relies on the fact that virtual NICs lack a true peek operation, so the limiter estimates a future timestamp and pauses polling until that time.

While effective, the loaned token amount is uncontrolled, potentially causing fairness issues between large and small flows.

Second Improvement: Carousel Limiter

The Carousel algorithm (SIGCOMM 2017) assigns each packet a future transmission timestamp; if the current time is earlier, the packet is placed on a timing wheel (a lightweight cache) instead of being dropped.

This introduces buffering, smoothing TCP traffic, and eliminates the need for cascading compensation because packets are delayed rather than lost.

Experiments on a 10 Gbps link show that the Carousel limiter increases inbound throughput by ~500 Mbps and provides more stable outbound performance compared with the earlier backpressure limiter.

Future Improvements and Summary

Further work includes refining the loan‑based backpressure for low‑rate limits, exploring finer‑granularity backpressure (e.g., using virtio OOO completion as in Google’s PicNIC), and designing lock‑free limiters to handle multi‑core environments.

Overall, rate limiter designs are moving from isolated components toward tightly integrated solutions that consider real‑world traffic patterns, TCP behavior, and system constraints.

References

Traffic policing in eBPF: applying token bucket algorithm

Carousel: Scalable Traffic Shaping at End Hosts, SIGCOMM 2017

PicNIC: Predictable Virtualized NIC, SIGCOMM 2019