DoS Lab 03 — Rate-Limiter Variants

WARMUP: Chapter 6 (rate-limiting algorithms). Extends: Lab 02 (token bucket).

The idea

Lab 02 built a token bucket. This implements the other classic algorithms and demonstrates the failure mode each one fixes or exhibits: a fixed window is simple but permits a ~2× burst across the window boundary; a leaky bucket smooths output to a constant drain rate (no bursts at all). Knowing the tradeoffs — and that a naive fixed-window counter lets a client send double the nominal rate around the boundary — is the point.

What you build (lab.py)

  • FixedWindowLimiter(limit, window) — per-key count per fixed bucket; resets at the boundary.
  • LeakyBucketLimiter(capacity, leak_rate) — leak-then-admit; smooths to a constant rate.
  • boundary_burst_demo(limit, window) — returns the allowed count (≈ 2*limit) when sending limit at the end of one window and limit at the start of the next — the fixed-window flaw, made visible.

Cases the tests cover

  • Fixed window limits within a window and resets at the next; boundary burst = 2×limit; per-key.
  • Leaky bucket caps at capacity, leaks over time, and smooths to the leak rate (one/sec sustainable, two within an instant not); per-key.

Run

pip install -r requirements.txt
LAB_MODULE=solution pytest -q
pytest -q

Hardening / extensions

  • Add a sliding-window-counter (weighted previous window) that fixes the boundary burst cheaply.
  • Compare all four algorithms (token/leaky/fixed/sliding) on the same request trace and report the effective admitted rate.
  • Make them distributed (shared store) and discuss atomicity (the P02 web-race lesson).

Interview / resume

"Implemented fixed-window and leaky-bucket rate limiters and demonstrated the fixed-window 2× boundary burst — completing the token-bucket picture and explaining when to use each algorithm."

Limitations: in-memory, single-process, supplied-time simulation; sliding-window-counter left as an extension.