Leaky Bucket Algorithm to Control Transmission Rates

ABSTRACT

Expanding requests on a system with increased connections will greatly drain its capacity. There are diverse congestion control systems which encourages a network system to work in an ideal environment of low latency with high throughput and in this way keeping the system from getting clogged or congested.

In this paper, the Leaky Bucket Algorithm is used to control transmission rate in a system. It tends to be used to monitor data transmissions and packets(data) to define limits on bandwidth.

By setting the bucket size and output rate, congestion can be properly managed to ensure that transmission goes on smoothly in the network. The Leaky Bucket Algorithm ensures bursty and inconsistent packet inputs are moderated and put out as smooth and consistent data.

One of the disadvantages of the Leaky Bucket Algorithm is that packets are destroyed instead of tokens, this often times lead to packet loss.

INTRODUCTION

The leaky bucket algorithm is a method of congestion control where variable number of requests are temporarily stored and organized into a set-rate output of packets in an asynchronous transfer mode. It is used to implement traffic policing and shaping in Ethernet and Cellular data networks. This report will go into details on what this Algorithm is about. This algorithm is one of two algorithms used in congestion control in networking (the other being the Token Bucket Algorithm. For the purpose of this report, I will be focusing on the Leaky Bucket Algorithm.

This report is important as it emphasizes on one of the algorithms over the other in order to ensure a complete understanding on how the algorithm works and how it differs from the Token Bucket Algorithm.

By the time you are done reading, you will be able to;

• clearly identify how this algorithm works,
• its advantages and disadvantages and
• why traffic shaping is important

LEAKY BUCKET ALGORITHM AND ITS RELEVANCE TO NETWORK AND COMMUNICATION

In computer networks and communications, there has always been a tendency of traffic/congestion problems which could be as a result of faster senders and slow receivers, fast receivers and slow senders and or both, as such traffic control has become a necessary part of Networks and Communication to ensure smooth transmission between senders and receivers and vice versa.

There are 2 types of traffic congestion controls as earlier mentioned;

• The Leaky Bucket Algorithm; coined from how an actual leaking bucket works, and
• The Token Bucket Algorithm

Both methods have their pros and cons and different modes of operation but for the purpose of this report, I will be focusing on the Leaky Bucket Algorithm only.

In the leaky bucket algorithm, here are the relevant keys to note;

• The output is not determined by input except the bucket is empty
• The output flows at a constant rate while input may vary

The network monitors traffic flows continuously to ensure they meet their traffic quota (this is called policing). When a packet arrives, it is checked to ensure it agrees with the quota, if in violation, the network either discards or tags the packet giving it lower priority. Whenever there is congestion, tagged packets are discarded first. Leaky Bucket Algorithm can be used to monitor the arrival rates of packets. The illustration below shows how a Leaky Bucket Algorithm operates;

Figure 1.0

Illustration (a) shows how an actual leaky bucket works. The water leaks out of the bucket at a constant rate independent of the water that comes from the faucet.

Illustration (b) shows the transportation of packets using the Leaky Bucket Algorithm. The host computer sends out a packet of data (usually unregulated), it passes through an interface where the Leaky Bucket is situated, this bucket holds the packets in and begins to release them in a regulated manner to the network. It helps to ensure that the network isn’t laden with packets. An overloaded network often leads to packet loss.

Discussion

To understand Leaky Bucket Algorithm, we must first understand a little about traffic and traffic shaping.

Traffic: network traffic, according to techopedia.com, is defined as the amount of data moving across a network at a given point in time.

Data could sometimes be bursty or fixed. Bursty data is data that is transferred or transmitted in a short and uneven manner while fixed data is data that is transferred at a consistent rate. The diagram below illustrates bursty data and fixed data.

Figure 1.1

From the diagram above, it can be observed that bursty data is inconsistent while fixed data takes a consistent pattern.

Traffic Shaping: according to geeksforgeeks.org, traffic shaping is defined as a mechanism used to control the amount and rate of traffic sent to the network. It helps to regulate rate of data transmission and reduces congestion.

The Leaky Bucket Algorithm works by accepting bursty data into a bucket and then transmits it at a smooth and fixed rate. It is usually implemented using the FIFO queue. A FIFO queue holds the packets. If the traffic consists of fixed size packets, the process removes a fixed number of packets from the queue at each tick of the clock, if the traffic consists of variable length packets, the fixed output rate must be based on the number of bytes or bits. It uses two parameters to control traffic flow namely;

• Burst rate: the rate at which packets are allowed to accumulate in the bucket, expressed in cells per second, and
• Average rate: the average number of packets per second that “leaks” from the hole at the bottom of the bucket and enters the network.

The Algorithm works as follows;

• Step 1; Initialize the counter to ‘n’ at every tick of clock
• Step 2; If n is greater than the size of packet at the front of queue, send the packet into the network and decrement the counter by size of packet. Repeat the step until ‘n’ is less than the size of packet.
• Step 3; Reset the counter and go to Step 1.

Example – Let n=1000
Packet=

Since n> front of Queue i.e. n>200
Therefore, n=1000-200=800
Packet size of 200 is sent to the network.
 

Now Again n>front of the queue i.e. n > 400
Therefore, n=800-400=400
Packet size of 400 is sent to the network.
 

Since n< front of queue
Therefore, the procedure is stop.
Initialize n=1000 on another tick of clock.
This procedure is repeated until all the packets are sent to the network.

Some advantages of Leaky Bucket Algorithm are;

• Token independent; tokens are not needed in the Leaky Bucket Algorithm.
• Packets are transmitted continuously.
• Packets are sent out at a constant rate, this is especially helpful with bursty input flows.
• Input rate can differ, but output rate remains constant.

Some disadvantages of the algorithm are;

• Tokens are not saved, mainly because they are not needed in this algorithm
• If the bucket is full, packet or data is discarded.
• It sends packets at an average rate.

SUMMARY

 This report has successfully covered some aspects of the Leaky Bucket Algorithm; how it works, its advantages and disadvantages as well as its effect on traffic shaping. It is a good method of congestion control but keeping in mind that packets can go missing due to a full bucket, other methods of control should be considered.

     REFERENCES

1)   https://www.geeksforgeeks.org/congestion-control-in-computer-networks/

2)   https://www.geeksforgeeks.org/leaky-bucket-algorithm/

3)   https://www.slideshare.net/vimal25792/leaky-bucket-tocken-buckettraffic-shaping

4)   https://pdfs.semanticscholar.org/2f76/919e67b2f0c4a7f57bce3128a27c191b8460.pdf

5)    Figure 1.0 , https://www.slideshare.net/vimal25792/leaky-bucket-tocken-buckettraffic-shaping

6)     Figure 1.1, https://www.geeksforgeeks.org/leaky-bucket-algorithm/