COMPUTER NETWORKS MINOR PROJECT REPORT ON

“Leaky Bucket Algorithm”

Submitted

In the partial fulfilment of the requirements for

The award of the degree of
BACHELOR OF TECHNOLOGY

In

COMPUTER SCIENCE & ENGINEERING

By

S.Manasa 171FA04177

B.V Sai Chandana 171FA04191

E. Raja Rajeswari 171FA04199

Under the esteemed guidance of

Mrs.G Parimala, Assistant Professor

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

VIGNAN'S FOUNDATION FOR SCIENCE, TECHNOLOGY AND RESEARCH
DEEMED TO BE UNIVERSITY
(Accredited by NAAC “A” grade)
Vadlamudi, Guntur.

1
VIGNAN’S FOUNDATION FOR SCIENCE TECHNOLOGY AND
RESEARCH DEEMED TO BE UNIVERSITY
(Accredited by NAAC “A” grade)

CERTIFICATE

This is to certify that the Minor project Report entitled “Leaky Bucket
Algorithm”is being submitted by S.Manasa(171FA04177), B.V Sai
Chandana(171FA04191) and E.Raja Rajeshwari(171FA04199) in partial
fulfilment for the award of B.Tech degree in Computer Science and Engineering
to the Vignan’s Foundation for Science, Technology and Research, Deemed to
be University, is a record of bonafide work carried out by them under my
supervision.

Guide Name External Examiner Dr.D.Venkateshwarlu

Mrs. G.Parimala HOD, CSE

2
 ACKNOWLEDGEMENT

We are very grateful to our beloved Chairman Dr. Lavu. Rathaiah, and Vice Chairman Mr. Lavu.
Krishna Devarayalu , for their love and care.

It is our pleasure to extend our sincere thanks to Vice-Chancellor Dr. M.Y.S. Prasad and Dean
Engineering & Management, Dr. V.MADHUSUDAN RAO, for providing an opportunity to do my
academics in VFSTR.

It is a great pleasure for me to express my sincere thanks to Dr. D.Venkatesulu HOD, CSE of VFSTR,
for providing me an opportunity to do my Minor Project.

We feel it our responsibility to thank Mrs.U.Sri Lakshmi under whose valuable guidance that the
project came out successfully after each stage.

We extend our whole hearted gratitude to all our faculty members of Department of Computer
Science and Engineering who helped us in our academics throughout course.

Finally we wish to express thanks to our family members for the love and affection overseas and
forbearance and cheerful depositions, which are vital for sustaining effort, required for
completing this work.

With Sincere regards,

S.Manasa (171FA04177)
B.V Sai Chandana(171FA04191)
E.Raja Rajeshwari(171FA04199)

3
 TABLE OF CONTENTS

Contents Page.
No.
1. Congestion 5
2. Traffic Shaping 5
3. Introduction 5
4. Algorithm Example 6-7
5. Leaky Bucket Model 7-8
6. Parameters 8
7. Uses 8
8.Advantages 9
9.Disadvantages 9
10.Source code 9-10
11.Result Screenshots 11-12
12.Conclusion 12
13.References 12

CONGESTION:
 Internet can be considered as a Queue of packets, where transmitting nodes are
constantly adding packets and some of them (receiving nodes) are removing packets
from the queue.

 Consider a situation where too many packets are present in this queue , such that
constantly transmitting nodes are pouring packet at a higher rate than receiving nodes
are removing them.

 This degrades the performance , and such a situation is termed as Congestion.

4
TRAFFIC SHAPING:
 It is about regulating average rate of data flow.
 It is a method of congestion control by providing shape to data flow before entering
the packet into the network.
 At connection set-up time , the sender and carrier negotiate a traffic pattern(shape)
 There are two types of Traffic shaping algorithm
1.Leaky Bucket Algorithm.
2.Token Bucket Algorithm.

INTRODUCTION:
 Conceptually , each host connected to the network has an interface containing a
“Leaky Bucket”(a queue)
 To send a packet into a network , it must be possible to put more water into the
bucket.
 If a packet arrives when the bucket is full , the packet must either be queued until
enough water leaks out to hold it or be discarded.
 This technique was proposed by Turner(1986) and is called the leaky bucket
algorithm.
 Allow one packet per clock tick.
 It is implemented as a single-server queue with constant service time.
 If the bucket(buffer) overflows then packets are discarded.
 In this algorithm the input rate can vary but the output rate remains constant.

5
  This algorithm converts bursty traffic into fixed rate traffic by averaging the data rate.
Leaky Bucket Algorithm:

ALGORITHM:
 Step-1:Initialize the counter to ‘n’ at every tick of clock.
 Step-2:If n is greater than the size of packet in 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 the packet.
 Step-3:Reset the counter and go to step-1.
EXAMPLE:
Let n=1000
 Packet=
6
 200 700 500 540 400 200
Since n> front of Queue i.e. n>200
Therefore, n=1000-200=800
Packet size of 200 is sent to the network.

Packet =

200 700 500 540 400

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.

EXPLANATION:
 When the packets are all of the same size(e.g.,ATM cells) , this algorithm can be used
as described.
 When variable-sized packets are being used , it is often better to allow a fixed number
of bytes per tick , rather than just one packet.
 If the rule is 1024 bytes per tick , a single 1024-byte packet can be admitted an the
tick , two 512-byte packets , four 256-byte packets , and so on.
Leaky Bucket Model:
 To understand the leaky bucket model , consider a bucket with a small hole at the
bottom. Three parameters define the bucket:
 The capacity(B)
 The rate at which water flows out of the bucket(R)
 The initial fullness of the bucket(F)

7
 If water is poured into the bucket at exactly rate R , the bucket will remain at F ,
because the input rate equals the output rate.
 If the input rate increases while R remains constant , the bucket accumulates water.
 If the input rate is larger than R for a sustained period , eventually the bucket
overflows.
 However , the input rate can vary around R without over floating the bucket , as long
as the average input rate does not exceed the capacity of the bucket.
 The larger the capacity , the more the input rate can vary within a given window of
time.
 Real life applications are – “Digital media”.

PARAMETERS:
 The leaky bucket algorithm uses two parameters to control traffic flow:
 Burst rate: The rate at which cells are allowed to accumulate in the bucket ,
expressed in cells per second.
 Average rate: The average number of cells per second that “leak” from the hole in
the bottom of the bucket and enter the network.
For example, if the average burst rate is 10 cells per second , a burst of 10 seconds
allows 100 cells to accumulates in the bucket.

USES:
 The leaky bucket algorithm is used in packet switched computer networks and
telecommunications networks.

8
  The leaky bucket as a queue can only be used in shaping traffic with no delay in the
output.
 It may be used within the network , as part of bandwidth management , but is more
appropriate to traffic shaping in the network.
 A technique used in ATM networks that applies a sustained cell flow rate to burst
traffic.
 Leaky bucket algorithm is used as the mechanism of the UPC(Usage Parameter
Control)in the network.

ADVANTAGES:
 Token independent.
 Packets are transmitted continuously.
 It send the packet at constant rate .
 Input rate can differ but output rate will be constant.

DISADVANTAGES:
 It does not save token.
 If bucket is full packet or data is discarded.
 LB sends packets at an average rate.

SOURCE CODE:
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>

#define NOF_PACKETS 10

int rand(int a)
{
int rn = (random() % 10) % a;
return rn == 0 ? 1 : rn;
}

int main()
{

9
 int packet_sz[NOF_PACKETS], i, clk, b_size, o_rate, p_sz_rm=0,
p_sz, p_time, op;
for(i = 0; i<NOF_PACKETS; ++i)
packet_sz[i] = rand(6) * 10;
for(i = 0; i<NOF_PACKETS; ++i)
printf("\npacket[%d]:%d bytes\t", i, packet_sz[i]);
printf("\nEnter the Output rate:");
scanf("%d", &o_rate);
printf("Enter the Bucket Size:");
scanf("%d", &b_size);
for(i = 0; i<NOF_PACKETS; ++i)
{
if( (packet_sz[i] + p_sz_rm) > b_size)
if(packet_sz[i] > b_size)
printf("\n\nIncoming packet size (%dbytes) is
Greater than bucket capacity (%dbytes)-PACKET REJECTED",
packet_sz[i], b_size);
else
printf("\n\nBucket capacity exceeded-PACKETS
REJECTED!!");
else
{
p_sz_rm += packet_sz[i];
printf("\n\nIncoming Packet size: %d", packet_sz[i]);
printf("\nBytes remaining to Transmit: %d", p_sz_rm);
p_time = rand(4) * 10;
printf("\nTime left for transmission: %d units",
p_time);
for(clk = 10; clk <= p_time; clk += 10)
{
sleep(1);
if(p_sz_rm)
{
if(p_sz_rm <= o_rate)
op = p_sz_rm, p_sz_rm = 0;
else
op = o_rate, p_sz_rm -= o_rate;
printf("\nPacket of size %d Transmitted", op);
printf("----Bytes Remaining to Transmit: %d",
p_sz_rm);
}
else
{
printf("\nTime left for transmission: %d units",
p_time-clk);
printf("\nNo packets to transmit!!");
}
}
}}}

10
SCREENSHOTS:

11
12
CONCLUSION:
 The Leaky Bucket Algorithm used to control rate in a network. It is implemented as
a single-server queue with constant service time.
 If the bucket (buffer) overflows then packets are discarded. In this algorithm the
input rate can vary but the output rate remains constant

REFERENCES:
 https://www.geeksforgeeks.org/leaky-bucket-algorithm/

13