Congestion Control Techniques

In past few years, the congestion and its control has been an area of interest where lots of developments are there, due to three reasons:

1. The worldwide spread of internet has make it unmanageable.
2. The transmission technology is  developing exponentially. As inventions in optical field  has made the hypothetical bitrates like Gbps and Tbps manageable in real life.
3. In recent years, as the data communication field, the telecommunication field has grownup very much, and each service provider tries to give best facilities to its clients in terms of voice quality, connectivity, and lesser number of drop and blocked calls.

What is Congestion?

Old definition of congestion says that:

Ø  “A network is said to be congested if network is under high load”

Now assume a case where short term packet arrival rate increases the service rate, thus three things can happen

Ø  Queuing delay of packets increases

Ø  There may be packet loss

Ø  Due to congestion traffic is dominated by retransmissions

So due to these 3 conditions a new definition of congestion comes forward:

“A network is congested if due to overload condition X is reached”, where X is queue delay, packet loss and decreased throughput .”

New definition of Congestion

The recent researches in the field of congestion has given us a new definition of congestion based on three points which are:

1. A network can be congested from the perspective of one user, and uncongested from the perspective of another.
2. A network can be said to be strictly uncongested if no user perceives it to be congested.
3. A user’s utility may decrease due to something other than network load, but the user may not be able to tell the difference. The onus on the user is to determine the cause of the loss of utility, and to take appropriate corrective action.

“A network is said to be congested from the perspective of user i if the utility of i decreases due to an increase in network load.”

Causes of Congestion

1. Insufficient queue(buffer) space in processing unit.
2. Processing speed not in accordance to data arrival speed
3. Inefficient transmission media and techniques
4. Insufficient resources for bursty traffic

All the above reasons of congestion are interdependent on each other. If we change statistics of one point and don’t change other we will again stuck on congestion. For e.g. if we change the buffer but not the processing speed, or vice-versa we will again suffer congestion.

The congestion affects mainly two vital performance parameters of a network namely ‘Delay’ and ‘Throughput’

Simply throughput is percentage utilization of network capacity.

As the offered load increases nearly 60 %, the throughput goes on decreasing. And in delay case, if load increases, the delay reaches infinity before the limit.

Congestion control refers to the mechanisms and techniques used to control congestion and keep the traffic below the capacity of the network.

Ø  Open loop: Protocols to prevent or avoid congestion, ensuring that the system (or network under consideration) never enters a Congested State.

Ø  Close loop: Protocols that allow system to enter congested state, detect it, and remove it. It involves feedback to the central control unit or sometimes to source or destination node of packet

Fundamental requirements of a congestion control scheme

Ø  Efficiency

Ø  Ability to deal with heterogeneity

Ø  Ability to deal with ill-behaved sources

Ø  Stability

Ø  Scalability

Ø  Simplicity

Ø  Fairness

Efficiency: Two aspects are

1. Congestion control technique doesn’t impose too much overheads in network which result in more congestion
2. It doesn’t let the network underutilized i.e. inefficient control may throttle down the traffic even in no congestion.

Heterogeneity: Congestion control scheme will be able to

Ø  Control large network

Ø  Allow different packet sizes

Ø  Support different protocols and services

Ø  Deal with misbehaving source: Scheme must be able deal with misbehaving sources which do not obey to control scheme. Otherwise network has to suffer for it.

Ø  Stability: Delay in control signaling create instability in the network. The congestion control scheme should be able to stabilize this instability

Ø  Scalability: As the network grows with time, the control scheme should mould itself to that situation

Ø  Simplicity: Simplicity is always an asset. The control scheme should be simple to implement and use.

Ø  Fairness: There should be fair resource allocation among the demands to the control scheme.

Open loop Congestion Control

Slow Start

Ø  Simplest pro-active technique to avoid congestion

Ø  Initialization of connection is with small data packets

Ø  As the acknowledgement of previous message is received packet size go on increase

Ø  This goes upto point when either full window size is reached or congestion is detected

Ø  When congestion start occurring, device decreases the rate and data size.

        Leaky Bucket Algorithm:

Ø  Act as a bucket with small hole

Ø  As much water we put in, it comes out at same rate

Ø  Similarly leaky bucket takes bursty data and sends it at constant rate

Ø  When host has packet to send, it put in the bucket

Ø  Bucket leaks at constant rate i.e. transmits data at constant rate

Ø  In practical case the bucket is finite queue that outputs at finite rate

Token Bucket Algorithm

Ø  Leaky bucket describes the output rate irrespective of the input

Ø  In some applications it is needy to send bursty data at output

Ø  Token bucket is the appropriate algo. for the purpose

Ø  In this algo. the leaky bucket holds the token, generated at regular interval

Few steps regarding its working are:

      •      In regular intervals tokens are thrown into the bucket.

•      The bucket has a maximum capacity.

•      If there is a ready packet, a token is removed from the bucket, and the packet is send.

•      If there is no token in the bucket, the packet cannot be send.

•      Token bucket is less restrictive than leaky bucket in the sense of bursty data

•      The limit of burst is restricted by the number of tokens

•      Just a variable in simple program is used to count tokens

•      The counter is incremented every t second

•      The time counter takes to count down is the time of transmitting packets

•      When counter is zero no further packets are sent

Closed loop techniques:

Ø  A proper feedback technique

 Ø  Feedback contains information about congestion in network, and if necessary slow down transmission

Steps of working:

1. Congestion Detection- Detection of congestion and its proper place after or better, before it occurs.
2. Communication- Communicate to the sources creating congestion and their nearby nodes.
3. Decongestion- Solve the congestion if it has occurred.

Choke Packet Technique:

Ø  Can be applied to virtual circuit and datagram approach

Ø  A threshold level is defined by administrator

Ø  Each router monitors its resources utilization at each output

Ø  Whenever utilization crosses threshold, output line enters ‘warning’ position

Ø  The router which monitors congestion generates ‘choke packets’ to source of congestion

Ø  These packets are tagged, which means that other routers will not have to send choke packets

Ø  When host receives choke packets, it is required to reduce traffic by some percentage

Choke packets(example)

• Q depicts heavy flow and generate choke packets
• P reduces flow by 50%
• If further choke packet is received, P further reduces traffic by 25% and so on

Load Shedding

Ø  One of the simplest closed loop technique

Ø  When router depicts congestion, it simply start dropping packets

Ø  There are different methods to decide which packets to drop

Ø  One of the method is random selection

Ø  Other methods need cooperation of sender and receiver

Ø  Another method is prioritizing the packets

Ø  In priority case a priority policy is made and packets are start dropping from lower priority until congestion less state is reached.

Backward Congestion Notification (BCN): The packet dropping is not the right solution for congestion, because there are very much important packets to be sent and received.

Ø  The ultimate solution is Backward Congestion Notification

Ø  In the place of dropping, it “pauses” the data transmission at sender side for some time

Ø  When uncongested, route is unpaused

Two points are there

Congestion Point (CP): Point where congestion is monitored and BCN packets are generated to source

Reaction Point (RP): A rate limiter that is on source side, it reads BCN and slows down rate of data

Case Study: Cisco Smart Edge Router: For congestion management this router uses three methods

1. Random Early Detection
2. Queue Depth
3. Queue Rates

There are further three queue management systems are used:

1. Priority queue (PQ)
2. Enhanced Deficit Round Robin(EDRR)
3. Asynchronous Transfer Mode Weighted Fair Queue(ATMWFQ)

Random Early Detection:

Ø  Configured through PQ, EDRR, ATMWFQ policies

Ø  It monitors the average queue size at every instant of time

Ø  It drops the packet based on its statistical probability

Ø  If buffer empty, all packets are accepted

Ø  As the queue grows, the probability for dropping packet grows too

Ø  If the buffer is full, packet received has dropping probability 1 and packet is dropped