CONGESTION

• When excess packets are present in a part of the network the performance degrades. This is called as congestion.

• Congestion occurs when the system load is greater than the system resources. Congestion can be caused when:

  (1) Many packets are routed through the same node (router).

  (2) There is low bandwidth.

  (3) There are slow processors at the routers.

  (4) If a part of the network is upgraded and the remaining network is left as it is, congestion will occur at the non-upgraded section of the network.

  (5) Burstlly traffic.

  Types of Congestion Control Algorithms:

  (1) Open Loop Algorithms: They make sure that congestion does not occur in the first place. They aim at designing the system in such a way that congestion cannot occur.

  (2) Closed Loop Algorithms: They let congestion occur and then take corrective steps. The general steps followed by a closed loop algorithm are:

   (a)    Monitor the system and find out where congestion is occurring.
  
   (b)    Pass this information to the places where action can be taken.
  
   (c)    Take actions to correct the problem.
  

Open loop techniques for congestion control

There are two methods:

(I) Prevention Policies and

(II) Traffic Shaping

(I) Prevention Policies

These systems are designed to minimize congestion in the first place, rather than letting it happen and reacting after the fact. The Prevention policies for the various layers are given below:

(II) Traffic Shaping

• One of the main causes of congestion is the bursty nature of traffic.

• Traffic Shaping forces bursty traffic to be transmitted at a uniform rate.

   

  Techniques for Traffic Shaping:

  (1) Leaky Bucket Algorithm

  (2) Token Bucket Algorithm

  (1) Leaky Bucket Algorithm:

  • Host is connected to the network by an interface. This interface is actually a queue.

  • The host sends an unregulated flow of traffic to the queue (interface). If the queue is not full the packet is appended to the queue. If the queue is full the packet is discarded.

  • Now the queue (interface) puts 1 packet per clock tic into the network.

  • Hence in this way unregulated traffic (bursty traffic) from the host is regulated before putting it on the network.

  • The only problem is that the packets are put on the network at a slow rate (1 per clock tic). Even during large bursts this rate remains the same.

  (2) Token Bucket Algorithm:

  • Host is connected to the network by an interface. This interface is actually a bucket. A token is generated in the bucket every ∆T seconds.

  • The host sends an unregulated flow to the bucket. For a packet to be transmitted to the network, it must capture and destroy a token present in the bucket.

  • If the lost is not sending packets to the bucket the tokens keep getting accumulated in the bucket. Generally there is a maximum amount of tokens that can be accumulated in the bucket.

  • Due to this feature of tokens getting accumulated, bursts can be handled better. Therefore in this case the rate increases if tokens are saved in the bucket, whereas in leaky bucket the rate will always be constant (1 packet per clock tic).

Closed loop techniques for congestion control

(I) Congestion Control in Virtual Circuit Subnets

(1) Admission Control:

 Once congestion has been detected no more virtual circuits are set up until the problem has gone away.

(2) Alternative Approach:

Virtual Circuits are set up but they do not pass through the areas which are facing congestion.

Suppose A wants to set up a connection with B. The shortest path between A and B is through the nodes facing congestion. To avoid this situation we can redraw the virtual circuit ……….

(3) Agreement Negotiation:

• An agreement is made between the host and the subnet when the virtual circuit is set up.

• The agreement decides on parameters such as volume of traffic, shape of traffic, quality of service and other network parameters.

• These resources (bandwidth, table and buffer space) are reserved along the path when the virtual circuit is set up. Due to this reservation of resources congestion cannot occur.

(II) Congestion Control in Datagram Subnets

• These methods can be used in both Datagram and Virtual Circuit Subnets.

• Let u be the utilization of an output line of a router. The value of u is between 0 and 1. The relation between u and f (instantaneous utilization) is given by

Unew =a.uold+(1-a).f where ‘a’ is a constant.

• Whenever a packet arrives at a router, the router first decides on the output line on which the packet will be forwarded on. The router checks the u of its output lines.

  If u is not above a certain threshold value we can say that there is no congestion.
  
  If u is above the threshold value, the output line enters the warning state (congestion state).