Rate Limiting and Throttling Mechanisms

Introduction:

Rate limiting and throttling are essential techniques used in distributed systems, especially in blockchain networks, to prevent any single participant or group of participants from overwhelming the system. They ensure that the network remains fair, resilient, and performs optimally by preventing spam or DDoS attacks.

---

Theoretical Background:

1. Fixed Window: A straightforward approach where users are given a fixed number of requests they can make in a given time window. For example, 100 requests per hour.

2. Sliding Window Log: This uses a timestamp to log each request from a user. Users are allowed a maximum number of requests in a given time window. If they exceed it, they must wait until some of the earlier logged requests "age out."

3. Token Bucket: Users accrue tokens at a specific rate. Making a request costs a token. If a user is out of tokens, they must wait to accrue more.

4. Leaky Bucket: Similar to token bucket but reverses the metaphor. Requests fill the bucket, and it leaks at a constant rate. If the bucket overflows, additional requests are discarded or penalized.

---

Math Formulas:

1. Fixed Window: $Requests Left=Max Requests−Requests Made in Current Window$

2. Sliding Window Log: $Requests Allowed=Max Requests−Requests Made in Previous Time Window$

3. Token Bucket: $Tokens Generated=Rate×Time Since Last Request$ $Tokens After Request=Tokens Generated−Cost of Request$

4. Leaky Bucket: $Bucket Fill Level=Current Fill Level+Request Size−Leak Rate×Time Since Last Request$

---

Code Example (C++): Token Bucket Rate Limiter:

#include <iostream>
#include <chrono>

class TokenBucket {
private:
    double rate;
    double capacity;
    double tokens;
    std::chrono::steady_clock::time_point lastCheck;

public:
    TokenBucket(double r, double cap) : rate(r), capacity(cap), tokens(0.0), lastCheck(std::chrono::steady_clock::now()) {}

    bool allowRequest(double requestSize) {
        refillTokens();
        if (tokens >= requestSize) {
            tokens -= requestSize;
            return true;
        }
        return false;
    }

private:
    void refillTokens() {
        auto now = std::chrono::steady_clock::now();
        std::chrono::duration<double> elapsed_seconds = now - lastCheck;
        
        tokens += rate * elapsed_seconds.count();
        if (tokens > capacity) tokens = capacity;

        lastCheck = now;
    }
};

int main() {
    TokenBucket limiter(2.0, 10.0); // 2 tokens/sec with max capacity of 10 tokens

    for (int i = 0; i < 20; ++i) {
        std::this_thread::sleep_for(std::chrono::seconds(1));
        if (limiter.allowRequest(3.0)) {
            std::cout << "Request allowed!" << std::endl;
        } else {
            std::cout << "Request denied." << std::endl;
        }
    }

    return 0;
}

---

Parameters:

• Rate: The number of requests/tokens per time unit.

• Window Size: The duration of time over which the rate is measured.

• Bucket Size/Capacity: Maximum size or number of tokens the bucket can hold.

• Leak Rate: The rate at which the leaky bucket drains.

• Request Size: The size or cost of a request in tokens.

---

Graph:

Imagine a graph representing the token bucket mechanism:

Token Level vs Time
|              
|             
|    /\
|   /  \         /\
|  /    \       /  \
| /      \     /    \       /\
|/        \   /      \     /  \
|----------|----------|----------|-----> Time (sec)
0          5         10         15

In this graph, token level (y-axis) increases over time (x-axis) at a constant rate until it hits the maximum capacity, after which it remains constant. Whenever a request is made, there's a sudden drop, representing the token cost of the request.