We will do time travel now!!! It has something to do with our discussion and we can relate. Remember the “baby bottle” which everyone used during their childhood? Why a simple bottle or glass is not used to feed milk? The flow of milk is the cause! When a large (comparatively) sized mouth is used, the milk flow will be a discomfort or inconvenience to the child. Whatever the amount of milk is in the bottle, the outflow will be through a tiny hole. This regulates the flow of milk to the child’s mouth instead of overflow.

What if the child drinks milk in a glass? When he lifts the glass to a height at sip 1, the flow will be high and he might not be able to consume complete milk. Also, at sip 2, he might not get the milk from the glass as it doesn’t have any. He should wait for it to get filled. What happened here? Loss of milk. Now, let’s apply this simple thing to our “Leaky Bucket Algorithm”. Apologies if the time travel was not smooth😁.

Traffic Shaping:

It is a mechanism that controls the amount of traffic that is being sent to the network. It reduces congestion and regulates the rate of data transmission. It may delay some or all data packets to sync them with the desired traffic profile. The two algorithms in traffic shaping are:

1. Leaky Bucket
2. Token Bucket

We shall discuss Leaky Bucket here.

Leaky Bucket:

Let’s say we need data of 20 MB. I have a network with a specific bandwidth of 2 Mbps. Now, the incoming network traffic has a speed of 5 Mbps. This speed continued for two seconds and I have received 10 MB data. Then the network stopped sending data for 3 s and again transmitted with a speed of 10 Mbps for a second and I received the complete data.

Due to this, the incoming traffic will damage the network by utilizing more bandwidth than the allocated. Here is where the algorithm comes into the picture.

The leaky bucket is similar to the baby bottle we have discussed earlier. The analogy is, bottle filters the milk, and the leaky bucket filters the network speed. When the algorithm is applied, this is how it works.

The incoming speeds are 5Mbps for 2s and 10 Mbps for 1s with a time gap of 3s. This implies, a total of 15 Mbps speed is consumed in 6s for 20 MB data. On average, a speed of 3.3 Mbps speed is sufficient to deliver a constant speed and data.

The traffic with interruptions at intervals or the transmission is uneven, it is called bursty traffic. This algorithm controls the bursty traffic of packets.

Algorithm

1. Initialize the bucket_size and output_size.
2. Input the values of bucket_size and output_size along with the
   simulation time (here) to keep track of the Algorithm working.
3. Take any random packets as incoming packets as the incoming packets
   have different sizes.
4. When packet size is greater than the bucket_size; discard or drop the
   extra packets and send the remaining to the bucket or buffer.
5. The output_size of packets will be sent out and the other will remain in
   the bucket.
6. The next incoming packet will be received according to the size of the packet
   left in the bucket.
7. Repeat the steps 4 and 5 untill the packets left is less than the size of the
   bucket.
8. Send all the remaining packets as output.
9. Exit

Simulation in Java

//File Name: LeakyBucket.java
import java.util.*;
class LeakyBucket{
    static Scanner s=new Scanner(System.in);
    static int i=0,buf_size=0,output_size=0,no_of_sec=0,bucket_size=0;
    static int[] packet_array=new int[100];
    public static void main(String [] args) {
        System.out.println("Enter the size of the bucket: ");
        bucket_size=s.nextInt();
        System.out.println("Enter the output size of the bucket: ");
        output_size=s.nextInt();
        System.out.println("Enter the simulation time (in sec): ");
        no_of_sec=s.nextInt();
        int packet_remaining=0,drop=0,min=0;
        Random r=new Random();
        for(i=0;i<no_of_sec;i++)
            packet_array[i]=((r.nextInt(9)+1)*10);
        for(i=0;i<no_of_sec;i++){
            packet_remaining+=packet_array[i];
            if(packet_remaining>bucket_size){
                drop=packet_remaining-bucket_size;
                packet_remaining=bucket_size;
                System.out.println("Number of seconds: "+ (i+1));
                System.out.println("Packets received: " + packet_array[i]);
                min=Math.min(packet_remaining, output_size);
                System.out.println("Packets sent to the buffer: " + min);
                packet_remaining-=min;
                System.out.println("Packets left: " + packet_remaining);
                System.out.println("Packets dropped: " + drop + "\n");
                drop=0;
            }
        }
        System.out.println("Simulating beyond the time: ");
        while(packet_remaining!=0){
            if(packet_remaining>bucket_size){
                drop=packet_remaining-bucket_size;
                packet_remaining=bucket_size;
            }
            min=Math.min(packet_remaining,output_size);
            System.out.println("Packets received: " + packet_remaining);
            System.out.println("Packets left: "+ min + "\n");
            packet_remaining-=min;
            System.out.println("Packets left: " + packet_remaining);
            System.out.println("Packets dropped: " + drop + "\n");
            drop=0;
        }
    }
}

Description

s → object for Scanner class
bucket_size → stores the size of the bucket
output_size → stores the output rate of data from bucket
no_of_sec → stores the number of seconds the simulation has to be done
packet_array → stores the packets received to the bucket
drop → stores the value of the dropped packets
min → stores the minimum value of the two values sent for comparision

Random → Function generates random values in the given bounds
r → object of "Random" class
r.nextInt(9)+1)*10 → (generates random numbers within the range (0-9))*10
Math → class for mathematical operations
min(a,b) → gives the minimum of a and b; method of Math class
More clarity with the below sample data!

Sample Data

Assumptions: Bucket size=10 and Time of simulation=10s

For the first second: 

Received packets are 60. Since the bucket size is 10, the remaining 50 packets are discarded or dropped. The remaining 10 packets are divided in such a way that the output or sent packets are 4 (constant output_size) and 6 left in the bucket.

For the second (2^nd) second:

Received packets are 30. Since there are already 6 packets left in the bucket or buffer, only 4 packets can be taken as the output_size is 10. The remaining 30-4 = 26 packets are dropped.

This is the case for all the remaining seconds, till 10.

At →1:

There isn’t any incoming traffic. The size of packets left in the bucket at 10^th second is 6. Now, all the packets left can be sent to the bucket. Hence the left packets are the received ones. Since the output_size is 4, 4 out of 6 are sent leaving behind 2 packets and 0 dropped.

At →2:

The size of packets left in the bucket at →1is 2. The left packets are the received ones. Since the output_size is 4, all the packets can be sent as output. The transmission is hence completed.

Disadvantages:

1. The packets are simply discarded if the bucket size is full.
2. No matter what the size of bursts, the output will be constant which is not in the case of Token Algorithm.

References and Recommendations:

1. Transmission Control Protocol
2. Token Bucket Algorithm
3. Network Performance
4. Internet Backbone
5. Bandwidth and Speed