COMPUTER NETWORK | CONGESTION CONTROL ALGORITHMS

📌Highlights: Hi friends ! In this post we will discuss about Congestion Control Algorithms such as, Pre-allocation of buffer, Scheme of packet discarding, Flow control, Congestion control by token bucket / Isarithm control, Congestion control by choke packet, Congestion control by leaky bucket, Token bucket.

Let we discuss about Congestion Control Algorithms which is used to control the congestion.

1. Pre-Allocation of buffer :

It is a prevention scheme. It is for virtual circuit subnet.

We know that this scheme is based on virtual circuit that mean a logical path is establish for delivering a packet in subnet.

Suppose in the case of stop and wait protocol one buffer is reserved in each IMP before establishing the connection.

In this way congestion problem is removed because no any IMP/HOST will not send any packet until next IMP have empty buffer. In other words if buffer is not empty than no connection will establish.

In the case of selective repeat protocol we can reserve more than one buffer before connection establishment.

2. Scheme of packet discarding:

This scheme is congestion avoidance from the above diagram , If P send data to q and buffer of q is full than q will discard the data/packet.

Here we send data/packet from one IMP to another IMP and if buffer of another IMP are not empty then we discard packet/data.

If any packet is come from HOST and receiving IMP have no empty buffer than the packet is discard from where it is coming (like HOST).In this way packet will not come for some time, may be in this duration buffer of receiving IMP become empty and now that IMP become ready to receive new packet.

Some time may happen if buffer of receiving  IMP are not empty and we discard packet at HOST as we discuss above and receiving IMP also send packet to HOST (such as A) and waiting for acknowledgement but here we are using piggybacking concept where acknowledgement is send with packet than the IMP continuously waiting because we discard packet at HOST side. Than how the acknowledgement will come. So for overcome this problem we will send a temporary packet.

3. Flow Congestion Control :

 

                                             

It is an avoidance technique. It is in between two point whether HOST / router. If we deliver more than capacity of over all network.In congestion control we talk about overall network.

In flow control scheme all IMP's are connected to their corresponding host.When the speed of host (mean delivery rate) is more than the receiving rate of IMP at that time flow control is needed and for this IMP send some message to HOST that our buffer down the  are full so slow delivery.

4. Isarithmic Congestion Control  (Congestion control by token packet):

It is prevention scheme. In this scheme concept of token is implemented.If capacity of subnet is 100 packet than 100 token packet is send  to subnet. If all IMP's are connected to HOST.

If any IMP has token than only it is able to receive the packet from subnet. Here checking is not done between IMP to IMP but checking between HOST and IMP.

Through this scheme it is guarantee that network has only 100 packets because it has 100 tokens.

It remove congestion problem and never occur.

Problem during this scheme:

a. How we distribute the token.

b. Suppose if we send 100 token in any time and if 20 token packet are lost and there is no record about these packet and still we have 100 packet in subnet than congestion will occur.

Solution for above problem:

Reset over all network in any particular time and release / pump new tokens.

5. Congestion control by Choke Packets:

It is an avoidance scheme. In this scheme each and every IMP suppose to calculate percentage line utilisation of their incident line.

Unew = alpha . Uold + (1-alpha) f

alpha is constant (it is between 0-1)

F = If there is no pending packet between two line in buffer and if buffer is empty f=0 otherwise f=1

Suppose W has one threshold  value example 0.9. If percentage utilisation become more than threshold value , than W send chock packet to A and A will slow the flow of packet.

From this congestion is resolve.

6. Congestion Control by leaky bucket algorithm:

It is admission control method.

Here packet delivery from bucket to network is in consistent state so congestion will not occur.In bucket there is a buffer which store packet which is send by HOST.

But for some application where intently data rate become fast then this method is not applicable.

In this scheme network is under utilised.

7. Token Bucket algorithm:

Token bucket is implemented for overcoming the problem of leaky bucket.

Here leaky rate is adaptive we can change the leaky rate when it is needed.But in leaky bucket method leaky rate is constant / fixed.

In this scheme one counter is added with buffer after one regular interval  of time one token is generate. Bucket contain number of buffers, if any buffer have token than it receive packet from HOST. 

Example: If 10 token is generate to buffer than 10 packet are received.

In this scheme we can also send bulk amount of data because leaky rate is adaptive.

If bucket is properly created than we get flexible data rate.

So friends this is all over about Congestion Control Algorithms, I am try to explain the working and behaviour of each algorithms. I hope this post is useful for you Continue reading we will meet in next post with new topic.