Leaky Bucket Algorithm

Description

The Leaky Bucket algorithm is a traffic shaping algorithm used in network traffic management. It controls the rate of outgoing packets and smooths bursts of traffic to conform to a predefined rate limit. Incoming packets are stored in a bucket, and packets are released from the bucket at a constant rate. If the bucket overflows, excess packets are either discarded (leaked) or queued.

C++ Code

#include <iostream>
#include <chrono>
#include <thread>
using namespace std;

class LeakyBucket {
private:
    int capacity;
    int rate;
    int currentWaterLevel;

public:
    LeakyBucket(int cap, int r) : capacity(cap), rate(r), currentWaterLevel(0) {}

    void leak() {
        // Simulate packet processing over time
        while (true) {
            if (currentWaterLevel > 0) {
                cout << "Packet sent, current water level: " << currentWaterLevel << endl;
                currentWaterLevel--;
            }
            this_thread::sleep_for(chrono::seconds(1) / rate);
        }
    }

    void receivePacket() {
        if (currentWaterLevel < capacity) {
            currentWaterLevel++;
            cout << "Packet received, current water level: " << currentWaterLevel << endl;
        } else {
            cout << "Bucket overflow, packet discarded" << endl;
        }
    }
};

int main() {
    LeakyBucket lb(10, 2);

    for (int i = 0; i < 15; ++i) {
        lb.receivePacket();
    }

    lb.leak();

    return 0;
}

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Leaky Bucket	O(1)	O(1)

Where:

• 1: Indicates constant time complexity for both operations.

← Back to Homepage