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.
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.
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:
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.
518+ registered 
