GCRA generic cell rate algorithm in Python
Mock implementation of the Generic Cell Rate Algorithm (GCRA) for traffic shaping and rate limiting.
Python code
43 linesfrom 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
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
- Implement with token bucket approach using timestamps from time.time() for real-time rate limiting
- 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
More from Reliability & rate limiting
- At Least Once with Idempotent Consumer in Python medium
- Build a Rate Limiter Decorator in Python easy
- Build a queue-based admission control system in Python easy
- Chaos Inject Random Failures in Python easy
- Circuit breaker failure threshold count in Python medium
- Exactly Once Processing Dedupe Mock in Python easy
Keep learning
Related tutorials and quizzes for this topic.