Rate Limiting Algorithms at CDN Edge: Token Bucket, Sliding Window, and Leaky Bucket

Rate limiting at the CDN edge is the first line of defense against API abuse, DDoS attacks, and runaway client behavior. By enforcing request limits before traffic reaches origin infrastructure, edge rate limiting protects backend capacity while delivering rejection responses at network-edge latency. The choice of rate limiting algorithm determines the trade-off between burst tolerance, memory efficiency, accuracy, and fairness—each algorithm suits different traffic patterns and protection requirements.

This guide covers the five major rate limiting algorithms as implemented in CDN edge environments: fixed window, sliding window log, sliding window counter, token bucket, and leaky bucket. Each section explains the algorithm's mechanics, its CDN edge implementation characteristics, and the specific scenarios where it outperforms the alternatives.

Fixed Window Counter

The fixed window algorithm divides time into fixed intervals (typically 1 minute or 1 second) and counts requests per client within each interval. When the count exceeds the limit, subsequent requests are rejected until the next window begins. The implementation requires a single counter per client per window, making it the most memory-efficient option for CDN edge nodes that track millions of concurrent clients.

// Fixed Window Counter — pseudocode
function fixedWindow(clientId, limit, windowSize) {
  key = clientId + ":" + floor(now() / windowSize)
  count = increment(key)
  if (count == 1) setExpiry(key, windowSize)

  if (count > limit) {
    return REJECT  // 429 Too Many Requests
  }
  return ALLOW
}

// Example: 100 requests per 60-second window
// Window 1 (00:00-01:00): requests 1-100 → ALLOW
//                          request 101    → REJECT
// Window 2 (01:00-02:00): counter resets → requests ALLOW again

The fixed window's weakness is the "boundary burst" problem. A client can send 100 requests at the end of window 1 and 100 requests at the start of window 2, achieving 200 requests in a 1-second span around the window boundary while never exceeding the 100 requests/window limit. This 2x burst at window boundaries can overwhelm backends that are sized for the steady-state rate. Despite this limitation, fixed window counters are used extensively in CDN rate limiting because the implementation is trivial and the memory footprint is minimal—DDoS protection often prioritizes low overhead over perfect accuracy.

Sliding Window Log

The sliding window log eliminates the boundary burst problem by tracking every individual request timestamp. To check the rate limit, the algorithm counts all timestamps within the last N seconds. If the count exceeds the limit, the request is rejected. As time advances, old timestamps fall out of the window naturally.

// Sliding Window Log — pseudocode
function slidingWindowLog(clientId, limit, windowSize) {
  now = currentTimestamp()
  cutoff = now - windowSize

  // Remove expired entries
  removeRange(clientId, 0, cutoff)

  // Count remaining entries (within window)
  count = countEntries(clientId)

  if (count >= limit) {
    return REJECT
  }

  // Add current request
  addEntry(clientId, now)
  return ALLOW
}

// Memory: O(limit) per client — stores every timestamp
// For 1000 req/min limit with 1M clients = 1 billion entries
// Not practical for CDN edge nodes with memory constraints

The accuracy is perfect: no boundary bursts, no approximation. However, the memory cost is proportional to the rate limit multiplied by the number of clients. At CDN edge scale (millions of clients, thousands of requests per second each), storing individual timestamps is impractical. Sliding window logs are appropriate for low-volume, high-accuracy scenarios like API key-based billing enforcement, but not for general-purpose CDN WAF-level rate limiting.

Sliding Window Counter

The sliding window counter provides a practical approximation of the sliding window log using only two counters per client. It combines the current window's count with a weighted portion of the previous window's count, where the weight corresponds to the overlap between the sliding window and the previous fixed window.

// Sliding Window Counter — pseudocode
function slidingWindowCounter(clientId, limit, windowSize) {
  now = currentTimestamp()
  currentWindow = floor(now / windowSize)
  previousWindow = currentWindow - 1
  windowProgress = (now % windowSize) / windowSize

  currentCount = getCounter(clientId, currentWindow)
  previousCount = getCounter(clientId, previousWindow)

  // Weighted estimate of requests in the sliding window
  estimate = currentCount + previousCount * (1 - windowProgress)

  if (estimate >= limit) {
    return REJECT
  }

  incrementCounter(clientId, currentWindow)
  return ALLOW
}

// Example: limit = 100, windowSize = 60s
// Current window: 30 requests (40% elapsed)
// Previous window: 50 requests
// Estimate: 30 + 50 * 0.6 = 60 → ALLOW (under 100)

// Memory: 2 counters per client (current + previous window)
// Accuracy: within ~1% of true sliding window for uniform traffic

This algorithm is the sweet spot for CDN edge rate limiting. The memory footprint is constant per client (two counters, regardless of the rate limit value), the accuracy is within 1-2% of a true sliding window for uniform traffic, and the implementation avoids the boundary burst problem. Cloudflare's rate limiting and AWS WAF both use variants of this algorithm for their edge rate limiting features.

Token Bucket

The token bucket algorithm models rate limiting as a bucket that holds tokens, refilled at a constant rate. Each request consumes one token. If the bucket is empty, the request is rejected. The bucket has a maximum capacity, so unused tokens accumulate up to that limit but not beyond. This creates a natural burst allowance: a client that has been idle accumulates tokens and can send a burst of requests up to the bucket capacity.

// Token Bucket — pseudocode
function tokenBucket(clientId, capacity, refillRate) {
  bucket = getBucket(clientId)

  // Calculate tokens accrued since last request
  elapsed = now() - bucket.lastRefill
  bucket.tokens = min(capacity, bucket.tokens + elapsed * refillRate)
  bucket.lastRefill = now()

  if (bucket.tokens < 1) {
    return REJECT  // 429 + Retry-After header
  }

  bucket.tokens -= 1
  saveBucket(clientId, bucket)
  return ALLOW
}

// Example: capacity=10, refillRate=2/sec
// t=0:  10 tokens available (full bucket)
//       Client sends 10 requests → all ALLOW, 0 tokens remain
// t=1:  2 tokens refilled → 2 available
//       Client sends 3 requests → 2 ALLOW, 1 REJECT
// t=5:  8 more tokens refilled → 10 available (capped at capacity)
//       Client can burst 10 requests again

Token bucket is ideal for API rate limiting because it reflects how most APIs are actually used: clients send bursts of requests (page loads, batch operations) followed by idle periods. The burst capacity accommodates legitimate usage patterns while the refill rate enforces the long-term average rate. CDN providers like Akamai use token bucket algorithms for their API security features because the two-parameter model (capacity + rate) maps directly to API plan tiers.

Leaky Bucket

The leaky bucket (also called leaky bucket as a meter) is the strict counterpart to token bucket. Requests enter a queue with a fixed capacity. The queue drains at a constant rate, and requests that arrive when the queue is full are rejected. Unlike token bucket, leaky bucket never allows bursts above the drain rate—it enforces a strictly smooth output pattern regardless of the input's burstiness.

// Leaky Bucket — pseudocode
function leakyBucket(clientId, queueSize, drainRate) {
  bucket = getBucket(clientId)

  // Drain requests that have "leaked" since last check
  elapsed = now() - bucket.lastDrain
  drained = floor(elapsed * drainRate)
  bucket.level = max(0, bucket.level - drained)
  bucket.lastDrain = now()

  if (bucket.level >= queueSize) {
    return REJECT  // Queue full
  }

  bucket.level += 1
  saveBucket(clientId, bucket)
  return ALLOW  // Request queued for processing
}

// The distinction: leaky bucket shapes traffic to a constant rate
// Token bucket allows bursts up to capacity
// Leaky bucket with queue size 0 = strict fixed-rate limiter

Leaky bucket is less common in CDN edge rate limiting because its strict behavior rejects legitimate burst traffic that token bucket would allow. It is appropriate when the backend truly cannot handle bursts—database write endpoints, payment processing APIs, or resource-constrained microservices where even brief traffic spikes cause degradation.

Distributed Rate Limiting Across Edge Nodes

The CDN's distributed architecture creates a fundamental challenge for rate limiting: a client's requests may hit different edge nodes, and each node maintains its own counters. Without coordination, a client can exceed the global rate limit by distributing requests across multiple edge nodes.

Most CDN rate limiters use a hybrid approach. Coarse DDoS protection uses local per-node limits (fast, no coordination needed). API-level rate limiting uses eventually consistent counters synchronized through a distributed data store. Billing-critical limits that must be exact use synchronous checks against a central counter, accepting the additional latency for accuracy.

Response Headers and Client Communication

Well-implemented rate limiting communicates its state to clients through HTTP response headers, enabling clients to self-throttle before hitting the limit. The IETF RateLimit header fields (draft-ietf-httpapi-ratelimit-headers) standardize this communication.

// Successful request with rate limit headers
HTTP/1.1 200 OK
RateLimit-Limit: 100
RateLimit-Remaining: 67
RateLimit-Reset: 43
X-RateLimit-Policy: "100;w=60"

// Rate-limited request
HTTP/1.1 429 Too Many Requests
Retry-After: 12
RateLimit-Limit: 100
RateLimit-Remaining: 0
RateLimit-Reset: 12
Content-Type: application/problem+json

{
  "type": "https://api.example.com/errors/rate-limited",
  "title": "Rate limit exceeded",
  "detail": "You have exceeded the rate limit of 100 requests per minute.",
  "instance": "/users/42",
  "retryAfter": 12
}

The CDN edge function should inject these headers on every response, not just on 429 responses. Clients that monitor RateLimit-Remaining can implement exponential backoff before they exhaust their allowance, reducing both the number of 429 responses and the corresponding retry traffic. This self-regulation effect means that proper header communication actually reduces the total traffic volume that the rate limiter must process.

Choosing an Algorithm: Decision Matrix

Use fixed window when simplicity and memory efficiency are paramount, and the 2× boundary burst is acceptable. Typical use: DDoS mitigation at CDN edge where the goal is to block obvious attacks, not enforce precise limits.

Use sliding window counter as the default for API rate limiting at CDN edge. It provides the best balance of accuracy, memory efficiency, and implementation simplicity. This is the right choice for 90% of API rate limiting requirements.

Use token bucket when burst tolerance is a feature, not a bug. APIs with tier-based rate limits (free: 10 req/s, pro: 100 req/s, enterprise: 1000 req/s) benefit from token bucket's natural burst-then-throttle behavior that matches how applications actually consume APIs.

Use leaky bucket when the backend requires strictly constant input rates. Database write endpoints, queue consumers, and payment gateways where even brief bursts cause cascading failures. This is the least common choice for CDN edge rate limiting but critical when strict smoothing is required.

Use sliding window log only when exact accuracy is required and the client count is manageable (under 10,000 concurrent clients). API billing enforcement and compliance-mandated rate tracking are the primary use cases.