Congestion control using Leaky Bucket Algorithm

The leaky bucket algorithm is a simple and effective mechanism for network congestion control. It ensures a smooth flow of packets across a network and prevents data bursts from overwhelming the network's resources. 

Concept Overview

The leaky bucket algorithm can be visualized as a bucket with a small hole at the bottom:

1. Data packets are treated as water poured into the bucket.
2. The bucket leaks water (transmits packets) at a constant rate, ensuring a steady flow.
3. If the incoming packet rate exceeds the leakage rate, the bucket overflows, leading to packet drops.

This mechanism helps to control the data flow rate and smooth out bursts.

---

Steps of the Algorithm

1. Bucket Initialization:

   • The bucket has a fixed capacity.
   • Packets arrive at the bucket (input flow).

2. Constant Leakage:

   • Packets leave the bucket (are transmitted) at a constant rate.
   • This ensures that the output flow remains steady.

3. Overflow Handling:

   • If the bucket overflows (incoming rate > bucket capacity), excess packets are discarded.
   • This mimics real-world network congestion scenarios.

4. Empty Bucket:

   • If no packets arrive, the bucket continues to leak at a constant rate until it's empty.

---

Key Features

• Rate Limiting: Controls the output data rate.
• Burst Management: Smooths out bursts by buffering packets in the bucket (if space is available).
• Simple Implementation: Easy to understand and implement.

---

Advantages

• Smoothens traffic flow by regulating bursts.
• Prevents buffer overflow in routers or switches.
• Improves Quality of Service (QoS) by maintaining a consistent data rate.

---

Disadvantages

• May lead to packet loss during high bursts (if bucket overflows).
• Fixed transmission rate may not adapt well to dynamic network conditions.

C program Implementation

#include <stdio.h>

#include <stdlib.h>

void leaky_bucket(int bucket_capacity, int leak_rate, int num_packets, int packets[]) {

    int bucket = 0; // Current bucket level

    printf("Time\tIncoming\tBucket\tLeaked\tRemaining\n");

    for (int i = 0; i < num_packets; i++) {

        printf("%d%10d", i + 1, packets[i]);

        // Add incoming packets to the bucket

        bucket += packets[i];

        if (bucket > bucket_capacity) {

            printf("%10d(Overflowed, Dropped %d)", bucket_capacity, bucket - bucket_capacity);

            bucket = bucket_capacity; // Discard excess packets

        } else {

            printf("%10d", bucket);

        }

        // Leak out packets at the constant rate

        int leaked = (bucket >= leak_rate) ? leak_rate : bucket;

        bucket -= leaked;

        printf("%10d%10d\n", leaked, bucket);

    }

    // Empty the bucket after all packets are processed

    int time = num_packets + 1;

    while (bucket > 0) {

        int leaked = (bucket >= leak_rate) ? leak_rate : bucket;

        printf("%d%10d%10d%10d%10d\n", time,0,bucket, leaked, bucket - leaked);

        bucket -= leaked;

        time++;

    }

}

int main() {

    int bucket_capacity, leak_rate, num_packets;

    printf("Enter the bucket capacity: ");

    scanf("%d", &bucket_capacity);

    printf("Enter the leak rate: ");

    scanf("%d", &leak_rate);

    printf("Enter the number of packets: ");

    scanf("%d", &num_packets);

    int packets[num_packets];

    printf("Enter the size of each incoming packet:\n");

    for (int i = 0; i < num_packets; i++) {

        scanf("%d", &packets[i]);

    }

    printf("\nLeaky Bucket Simulation:\n");

    leaky_bucket(bucket_capacity, leak_rate, num_packets, packets);

    return 0;

}

Output

Enter the bucket capacity: 10

Enter the leak rate: 4

Enter the number of packets: 5

Enter the size of each incoming packet:

5 8 4 3 6

Leaky Bucket Simulation:

Time Incoming Bucket Leaked Remaining

1         5         5         4         1

2         8         9         4         5

3         4         9         4         5

4         3         8         4         4

5         6        10         4         6

6         0         6         4         2

7         0         2         2         0Explanation

1. Input:

   • bucket_capacity: Maximum capacity of the bucket.
   • leak_rate: Rate at which packets are sent out.
   • num_packets: Number of incoming packets.
   • packets[]: Sizes of the incoming packets.

2. Process:

   • Packets are added to the bucket.
   • If the bucket exceeds its capacity, excess packets are dropped.
   • Packets leak out at the specified rate per time unit.

3. Output:

   • The program prints a table showing the time, incoming packets, current bucket level, packets leaked, and remaining packets in the bucket.