GCRA generic cell rate algorithm in Python

Mock implementation of the Generic Cell Rate Algorithm (GCRA) for traffic shaping and rate limiting.

Medium Python 3.9+ Aug 9, 2026 Reliability & rate limiting 14 views 0 copies

Python code

43 lines
Python 3.9+
from collections import deque
import time

class GCRA:
    def __init__(self, rate, burst):
        self.tau = burst
        self.T = rate
        self.t = 0
        self.LCT = 0

    def add_cell(self, arrival_time):
        if arrival_time <= self.t:
            return False
        arrived_early = (arrival_time - self.LCT) < 0
        if arrived_early:
            return False
        if (arrival_time - self.LCT) >= self.tau:
            self.t = self.LCT = arrival_time
            return True
        if self.t <= (arrival_time - self.LCT) < self.tau:
            self.t += self.T
            if self.t > arrival_time:
                return False
            self.t = max(self.t, arrival_time)
            return True
        return False

def mock_gcra(cells, rate=1.0, burst=4.0):
    scheduler = GCRA(rate, burst)
    accepted = []
    rejected = []
    for i, arrival in enumerate(cells):
        if scheduler.add_cell(arrival):
            accepted.append(arrival)
        else:
            rejected.append(arrival)
    return accepted, rejected

if __name__ == "__main__":
    cells = [0.0, 0.5, 1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0, 4.5]
    accepted, rejected = mock_gcra(cells, rate=1.0, burst=2.0)
    print(f"Accepted: {accepted}")
    print(f"Rejected: {rejected}")

Output

stdout
Accepted: [0.0, 1.0, 2.0, 3.0, 4.0]
Rejected: [0.5, 1.5, 2.5, 3.5, 4.5]

How it works

GCRA (Generic Cell Rate Algorithm) is a leaky-bucket variant used in ATM networks to enforce a traffic contract. It tracks the Theoretical Arrival Time (TAT) and the Last Conformance Time (LCT) to decide whether a cell conforms to the rate and burst tolerance. The algorithm accepts cells that arrive no earlier than the theoretical arrival time minus the burst tolerance, and it updates the TAT by the nominal inter-cell time for conforming cells. This mock uses a simple arrival-time-based simulation, returning accepted and rejected timestamps rather than caching or dropping cells.

The add_cell method returns True when the cell conforms, and updates the internal state accordingly. Non-conforming cells are rejected immediately, which is how GCRA provides precise rate and burst enforcement without storing cell data. This pattern is directly applicable to building rate limiters in APIs, network traffic shaping, or any system where bursty input must be smoothed to a sustained rate.

Common mistakes

  • Returning True on empty burst tolerance (tau) when arrival equals LCT, which would allow infinite burst
  • Confusing rate and burst parameters — rate is inter-arrival time, not cells per second
  • Forgetting to handle equal arrival times (same timestamp for multiple cells)
  • Using wall-clock time inside the class instead of passing arrival times explicitly

Variations

  1. Implement with token bucket approach using timestamps from time.time() for real-time rate limiting
  2. Use the algorithm as a decorator to rate-limit API endpoints by IP key

Real-world use cases

  • Rate limiting inbound requests to an API gateway to enforce service-level agreements.
  • Shaping network traffic in a proxy or firewall to smooth out traffic bursts.
  • Control consumer group throughput in message queues to protect downstream services.

Sponsored

Run this sample

Open the browser IDE to tweak the example and see results without installing anything.

Open editor

More from Reliability & rate limiting

Related tutorials and quizzes for this topic.