Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Algorithm
2.2.
Example
2.3.
Dry Run
2.4.
Implementation of Leaky Bucket
2.5.
C++
2.6.
Java
2.7.
Time Complexity
2.8.
Space Complexity
3.
Difference Between Leaky and Token Buckets
4.
Advantages of Leaky Bucket Algorithm
5.
Disadvantages of Leaky Bucket Algorithm
6.
Frequently Asked Questions
6.1.
What is the purpose of the leaky bucket algorithm?
6.2.
How does the leaky bucket algorithm work?
6.3.
What is the leaky bucket rate limiting algorithm?
6.4.
What are leaky bucket applications?
7.
Conclusion
Last Updated: Apr 23, 2024
Medium

Leaky Bucket Algorithm

Author Aditya Gupta
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

Have you ever tried to pour water into a glass or bottle, but it pours out because you poured it too quickly? What if you could manage the water's flow so it never leaks out of the bottle? Similar to what the "Leaky Bucket" algorithm does. 

Leaky bucket algorithm

In a Computer Network, the Leaky Bucket algorithm is a method of managing data flow. Data can flow too quickly and lead to issues, just like water in a container. The algorithm ensures that data constantly flows to prevent the network from overloading.

Problem Statement

In computer networking, the Leaky Bucket Algorithm regulates the speed at which data is transferred. It is a method that ensures that data transmission rates are kept to the maximum allowed level to check the flow of information through a network.

The algorithm visualises a "bucket" with a specific data capacity. A predetermined amount of data is added to the bucket at any time, and any extra data overflows the container. This can be compared to a "leak" that permits controlled data to flow out of the bucket. The rate at which the bucket is emptied is called the leak rate

The "fill rate" and "bucket size" refer to the pace at which data is added to the bucket and the size of the bucket, respectively. The algorithm operates by keeping track of the bucket's volume and restricting data flow when the bucket is full. Excess data is removed if the bucket overflows.

problem statement

Algorithm

The leaky bucket algorithm is commonly implemented using the following steps:

  • Initialise the bucket's capacity and leak rate to be fixed and constant, respectively.
     
  • Add packets to the bucket as they come in. If the bucket is already full, put away the packages or put them off till there is room.
     
  • Remove packets from the bucket at a fixed pace as they are transmitted. No packets can be broadcast if the bucket is empty until other packets arrive and fill it back up.
     
  • As additional packets are received and broadcast, repeat the above steps.

Example

Let the buffer size = 10000 Mb, leak rate = 1000 Mb. At any time interval, we have the bucket as [300, 400, 500, 400, 100].

Dry Run

Now, let’s see the dry of the leaky bucket algorithm that we have discussed above.

Iteration 1

Bucket:[300, 400, 500, 400, 100]

The first and second packets will be sent into the network. The sum of (300 + 400 + 500) is more significant than the leak rate. Hence we are unable to transmit the third.

Iteration 2

  • Bucket = [500, 400, 100] The next three packets will be transferred since their combined size is less than the leak rate. We have a data packet with a size of 500 at the head of the queue. We will send this packet and update the value of the leak rate as (1000 - 500)=500.
     
  • Bucket =[400, 100] Since 400 <= leak rate, we will send the packet at the front of the queue. Value of leak rate = (500 − 400) = 100.
     
  • Bucket = [100]. Since 100 <= leak rate, we will send the packet at the front of the queue. leak rate will become 0 and the bucket will be empty.

Implementation of Leaky Bucket

  • C++
  • Java

C++

#include <iostream>
#include <queue>
#include <chrono>
#include <thread>

// Represents a network packet with an ID and size
class Packet {
int m_id, m_size;
public:
Packet(int id, int size) : m_id{id}, m_size{size} {}
int get_id() const { return m_id; }
int get_size() const { return m_size; }
};

// Implements the Leaky bucket algorithm for traffic shaping
class TrafficManager {
// Maximum rate at which packets can be transmitted
const int m_leak_rate;

// Maximum size of the packet buffer
const int m_buffer_size_limit;

// size of the packet buffer
int m_curr_buffer_size;

// Queue to store packets
std::queue<Packet> m_buffer;
public:
TrafficManager(int leak_rate, int buffer_size_limit): m_leak_rate{leak_rate},
m_buffer_size_limit{buffer_size_limit},
m_curr_buffer_size{0} {}

/*
Adds a new packet to the buffer
Returns true if the packet was successfully added, false otherwise
*/

bool add_packet(Packet new_packet) {
if (m_curr_buffer_size + new_packet.get_size() > m_buffer_size_limit) {
std::cout << "Bucket is full." << std::endl;
return false;
}

m_buffer.push(new_packet);
m_curr_buffer_size += new_packet.get_size();
std::cout << "Packet with id = " << new_packet.get_id() << " added." << std::endl;
return true;
}

/*
Transmits packets from the buffer
Sets the is_transmission_complete flag to true if all packets have been transmitted
*/

void transmit(bool &is_transmission_complete) {
int available_bandwidth = m_leak_rate;
while (!m_buffer.empty()) {
Packet& top_packet = m_buffer.front();
int top_packet_size = top_packet.get_size();
if (top_packet_size > available_bandwidth) break;
available_bandwidth -= top_packet_size;
m_curr_buffer_size -= top_packet_size;
m_buffer.pop();
std::cout << "Packet with id = " << top_packet.get_id() << " transmitted." << std::endl;
}

is_transmission_complete = m_buffer.empty();
}
};

// Main function to test the TrafficManager class
int main() {
TrafficManager traffic_manager{1000, 10000};
traffic_manager.add_packet(Packet{1, 300});
traffic_manager.add_packet(Packet{2, 400});
traffic_manager.add_packet(Packet{3, 500});
traffic_manager.add_packet(Packet{4, 400});
traffic_manager.add_packet(Packet{5, 100});

// Loop to transmit packets from the buffer until all packets have been transmitted
while (true) {
bool is_transmission_complete;
traffic_manager.transmit(is_transmission_complete);
if(is_transmission_complete) break;
std::cout << "Waiting for next tick." << std::endl;
// Wait for one second to simulate
std::this_thread::sleep_for(std::chrono::seconds(1));
}
std::cout << "All packets have been transmitted." << std::endl;
}

Java

import java.util.LinkedList;
import java.util.Queue;

// Represents a network packet with an ID and size
class Packet {
private int id, size;

public Packet(int id, int size) {
this.id = id;
this.size = size;
}

public int getId() {
return id;
}

public int getSize() {
return size;
}
}

// Implements the Leaky bucket algorithm for traffic shaping
class TrafficManager {
// Maximum rate at which packets can be transmitted
private final int leakRate;

// Maximum size of the packet buffer
private final int bufferSizeLimit;

// Current size of the packet buffer
private int currBufferSize;

// Queue to store packets
private Queue<Packet> buffer;

public TrafficManager(int leakRate, int bufferSizeLimit) {
this.leakRate = leakRate;
this.bufferSizeLimit = bufferSizeLimit;
this.currBufferSize = 0;
this.buffer = new LinkedList<>();
}

/*
Adds a new packet to the buffer
Returns true if the packet was successfully added, false otherwise
*/
public boolean addPacket(Packet newPacket) {
if (currBufferSize + newPacket.getSize() > bufferSizeLimit) {
System.out.println("Bucket is full.");
return false;
}
buffer.add(newPacket);
currBufferSize += newPacket.getSize();
System.out.println("Packet with id = " + newPacket.getId() + " added.");
return true;
}

/*
Transmits packets from the buffer
Sets the isTransmissionComplete flag to true if all packets have been transmitted
*/
public void transmit(boolean[] isTransmissionComplete) {
int availableBandwidth = leakRate;
while (!buffer.isEmpty()) {
Packet topPacket = buffer.peek();
int topPacketSize = topPacket.getSize();
if (topPacketSize > availableBandwidth) break;
availableBandwidth -= topPacketSize;
currBufferSize -= topPacketSize;
buffer.remove();
System.out.println("Packet with id = " + topPacket.getId() + " transmitted.");
}
isTransmissionComplete[0] = buffer.isEmpty();
}
}

// Main function to test the TrafficManager class
public class Main {
public static void main(String[] args) throws InterruptedException {
TrafficManager trafficManager = new TrafficManager(1000, 10000);
trafficManager.addPacket(new Packet(1, 300));
trafficManager.addPacket(new Packet(2, 400));
trafficManager.addPacket(new Packet(3, 500));
trafficManager.addPacket(new Packet(4, 400));
trafficManager.addPacket(new Packet(5, 100));

// Loop to transmit packets from the buffer until all packets have been transmitted
while (true) {
boolean[] isTransmissionComplete = { false };
trafficManager.transmit(isTransmissionComplete);
if (isTransmissionComplete[0]) break;
System.out.println("Waiting for next tick.");
// Wait for one second to simulate
Thread.sleep(1000);
}
System.out.println("All packets have been transmitted.");
}
}


Output:

output1

Explanation:

We have implemented the Leaky Bucket Algorithm for traffic shaping. The Packet class is used to represent a network packet with an ID and size. TrafficManager class is used to implement the Leaky Bucket algorithm to regulate the flow of packets

Time Complexity

  • The addPacket function has a constant time complexity of O(1).
     
  • The time complexity of the transmit function is O(B), where B is the number of packets in the buffer. This is because, in the worst scenario, it will repeatedly examine each packet in the buffer to determine whether or not it may be forwarded.
     

The code's overall time complexity is O(B), where B is the number of packets in the buffer.

Space Complexity

  • The Packet class has a space complexity of O(1) since it only stores two integers.
  • The LeakyBucket class has a space complexity of O(K), where K is the maximum size of the buffer.
  • The main function has a constant space complexity of O(1).
     

Overall, the space complexity of the code is O(K), where K is the maximum size of the buffer.

You can read related articles such as Congestion Control in Computer Networks here.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Difference Between Leaky and Token Buckets

AspectLeaky BucketToken Bucket
PurposeThe Leaky Bucket algorithm controls the output rate of data from a network or systemThe Token Bucket algorithm regulates the input rate of data into a network or system
OperationIt allows a constant data flow rate, similar to water dripping from a leaky bucketTokens are added to the bucket at a fixed rate, and incoming data packets must consume tokens to be transmitted
Burst ToleranceLeaky Bucket is less burst-tolerant due to its constant output rateToken Bucket is more burst-tolerant
Packet treatmentExcess packets are dropped or queuedExcess packets are delayed or marked
Token consumptionPackets consume tokens at a fixed ratePackets consume tokens based on their size

Advantages of Leaky Bucket Algorithm

The advantages of the Leaky Bucket Algorithm include:

  • Traffic Regulation: It helps regulate traffic flow by smoothing out bursts of data, ensuring that network resources are utilized efficiently and fairly.
  • Congestion Control: By limiting the rate at which data is transmitted, the Leaky Bucket Algorithm helps prevent network congestion, maintaining optimal performance and reliability.
  • Quality of Service (QoS) Management: It enables the enforcement of Quality of Service policies by controlling the rate of data transmission, prioritizing critical traffic types, and ensuring that bandwidth is allocated appropriately.
  • Fairness: The algorithm ensures fairness among users or applications sharing network resources by limiting the rate at which each entity can send data, preventing any single user from monopolizing bandwidth.
  • Buffer Management: It helps manage network buffers effectively by preventing them from overflowing during periods of heavy traffic, thus reducing packet loss and improving overall network stability.
  • Security Enhancement: By controlling the rate of incoming data, the Leaky Bucket Algorithm can also serve as a mechanism for preventing certain types of network attacks, such as Denial of Service (DoS) attacks, which rely on overwhelming the network with excessive traffic.

Disadvantages of Leaky Bucket Algorithm

The disadvantages of the Leaky Bucket Algorithm include:

  • Delay Variation: Implementing the Leaky Bucket Algorithm can introduce variable delays in data transmission, particularly when bursts of data are limited. This delay variation may impact real-time applications and sensitive network traffic.
  • Inflexibility: The fixed rate at which the bucket leaks or empties may not always align with the dynamic nature of network traffic patterns. This inflexibility can lead to suboptimal utilization of network resources, especially in environments with fluctuating traffic loads.
  • Overhead: Implementing the Leaky Bucket Algorithm requires additional processing overhead to monitor and regulate data flow. This overhead can consume computational resources and may introduce latency, particularly in high-speed networking environments.
  • Potential for Underutilization: In scenarios where the leak rate is set conservatively to prevent congestion, the Leaky Bucket Algorithm may result in underutilization of available bandwidth. This inefficiency can limit the scalability and cost-effectiveness of network infrastructure.
  • Complexity in Configuration: Configuring the parameters of the Leaky Bucket Algorithm, such as the bucket size and leak rate, may require careful tuning to achieve optimal performance. Managing these parameters across different network devices and environments can introduce complexity and overhead for network administrators.

Frequently Asked Questions

What is the purpose of the leaky bucket algorithm?

The leaky bucket algorithm's primary goal is to control the data flow within a network. The algorithm helps in avoiding congestion and ensuring that the network functions well by managing the data transfer rate.

How does the leaky bucket algorithm work?

The leaky bucket algorithm transmits data packets at a fixed pace while storing them in a buffer (the bucket). When packet arrival rates exceed transmission rates, the extra packets are either deleted or kept in the buffer for later transmission. The algorithm controls the transmission rate using a timer, and the buffer size establishes the maximum quantity of data that may be held at any given time.

What is the leaky bucket rate limiting algorithm?

The leaky bucket rate limiting algorithm regulates data transmission by allowing a fixed amount of data to be sent at a constant rate. If the bucket overflows, excess data is discarded or delayed, preventing network congestion.

What are leaky bucket applications?

Leaky bucket applications include traffic shaping, network congestion control, quality of service (QoS) management, and rate limiting in networking and telecommunications systems.

Conclusion

This article discusses the topic of the Leaky Bucket Algorithm. We have seen the problem statement and algorithm along with the working code of the Leaky Bucket Algorithm. We hope this blog has helped you enhance your knowledge of the Leaky Bucket Algorithm. If you want to learn more, then check out our articles.

And many more on our platform Code360.

Refer to our Guided Path to upskill yourself in DSACompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your coding ability, you may check out the mock test series and participate in the contests hosted on Code 360!

But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundles for placement preparations.

However, you may consider our paid courses to give your career an edge over others!

Happy Learning!

Previous article
Congestion Control in Computer Networks
Next article
Border Gateway Protocol (BGP)
Live masterclass