## 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

**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.