Page 164 - DCAP406_DCAP_207_Computer Networks

Unit 10: Network Layer in the Internet

In the leaky bucket algorithm, a bucket with a volume of, say, b bytes and with a hole in the Notes
bottom is taken into consideration. If the bucket is empty, it means b bytes are available as
storage. A packet with a size lesser than b bytes arrives at bucket, it will be forwarded. If size of
the packet increases more than b bytes, it will either be discarded or queued. It is also assumed
that the bucket leaks through the hole in its bottom at a constant rate of r bytes per second. The
outflow is considered at a constant rate when there is any packet in the bucket, and zero when
the bucket is empty. This explains that if data flows into the bucket faster than data flows out
through the hole, the bucket overflows. This results further incoming data to be discarded until
enough volume again exists in the bucket to accept new data.
The disadvantages associated with the leaky-bucket algorithm are inefficient use of available
network resources. The leak rate is a fixed parameter. In case of the traffic volume is very low,
the large portions of network resources like bandwidth are not being used efficiently. The
leaky-bucket algorithm does not enable individual flows to burst up to port speed to effectively
consume network resources at times when there would not be resource contention in the network.
The leaky bucket algorithm uses average rate and burst rate parameters to control traffic flow.
Average rate is defined as the average number of packets per second that leak from the hole in
the bottom of the bucket and enter the network. The burst rate is the rate of accumulation of
packets in the bucket and expressed in packets per second. For example, if the average burst rate
is 10 packets per second, a burst of 10 seconds allows 100 packets to accumulate in the bucket.

Notes The leaky bucket algorithm also uses two state variables namely current time and
the virtual time. The current time is current time of the computer’s watch while virtual
time measures how much data has accumulated in the bucket and is expressed in seconds.
For example, if the average rate is 10 packets per second and 100 packets have accumulated in the
bucket, then the virtual time is 10 seconds ahead of the current time.

The Token Bucket Algorithm

The leaky bucket algorithm has rigid output pattern at the average rate independent of the
bursty traffic. In many applications, when large bursts arrive, the output is allowed to speed up.
This calls for more flexible algorithm preferably that never loses data. Hence, a token bucket
algorithm finds its uses in the context of network traffic shaping or rate limiting. The token
bucket is a control algorithm that dictates when traffic should be transmitted. This order comes
based on the presence of tokens in the bucket. The bucket contains tokens. Each of the token
represents a packet of predetermined size. Tokens in the bucket are removed for the ability to
send a packet. When tokens are present, A flow to transmit traffic occurs in the presence of
tokens. No token means no flow transmits its packets. Hence, a flow transmits traffic up to its
peak burst rate in the presence of adequate tokens in the bucket.

Thus, the token bucket algorithm adds token to the bucket every 1 / r seconds. The capacity of
the bucket is b tokens. When a token arrives and the bucket is full, the token is discarded. If a
packet of n bytes arrives and n tokens are removed from the bucket, the packet is forwarded to
the network. When a packet of n bytes arrives but fewer than n tokens are available. In such case
no tokens are removed from the bucket and the packet is considered to be non-conformant. The
non-conformant packets may either be dropped or queued for subsequent transmission when
sufficient tokens have accumulated in the bucket. They may also be transmitted but marked as
being non-conformant. Possibility is that they may be dropped subsequently if the network is
overloaded.

LOVELY PROFESSIONAL UNIVERSITY 157