Sliding Window Counter

Kỹ thuật xấp xỉ kết hợp Fixed Window: lưu số đếm của cửa sổ trước (prev) và cửa sổ hiện tại (cur), độ dài mỗi cửa sổ W. Khi request đến tại t thuộc cửa sổ hiện tại, ước lượng số request gần đây:

estimated = cur + prev * (W - offset) / W

với offset = t mod W. Nếu floor(estimated) < N thì ALLOW (tăng cur), ngược lại DENY. Khi sang cửa sổ liền kề thì prev = cur, cur = 0; nhảy xa hơn thì prev = 0, cur = 0.

Thuật toán

Dùng số học số nguyên: so sánh floor((cur*W + prev*(W-offset)) / W) < N.

Ví dụ

W=10,N=2: nếu cửa sổ trước có 2 và đang ở đầu cửa sổ mới thì ước lượng cao → dễ DENY.