CONGESTION CONTROL

Congestion is an important issue that can arise in packet switched

network. Congestion is a situation in Communication Networks in

which too many packets are present in a part of the subnet,

performance degrades. Congestion in a network may occur when

the load on the network (i.e. the number of packets sent to the

network) is greater than the capacity of the network (i.e. the number

of packets a network can handle.)

In other words, when too much traffic is offered, congestion sets in

and performance degrades sharply.

Fig. When too much traffic, congestion sets in and performance degrades.

1
When the number of packets dumped into the network by the hosts

is within it carrying capacity, they are all delivered and the number

delivered is proportional to the number sent. If the traffic suddenly

goes up, there will be congestion in the network and, as a result,

some packets may be discarded by the routers. At very high traffic,

performance collapses completely and almost no packets are

delivered. Figure above depicts the situation.

Congestion can be brought by several factors

 The input traffic rate exceeds the capacity of the output

lines. If suddenly, a stream of packet start arriving on three or

four input lines and all need the same output line. In this case,

a queue will be built up. All these packets will be forwarded to

the next router, increasing the load all the way to destination.

2
  Insufficient memory to hold all the packets.

 Slow processors can also cause congestion. If routers CPUs are

slow at performing their task, queues can build up, even

though there is excess line capacity.

 Low-bandwidth lines can also cause congestion.

What is Congestion Control?

 the efforts made by network nodes to prevent or respond to

overload condition.

 Monitor the system to detect when and where congestion

occurs and pass this information so that action can be taken.

 Adjust the system operation to correct the problem.

3
Difference between Congestion Control and Flow Control

1. Congestion control has to do with making sure the network is

able to carry the offered traffic. In contrast, Flow control keeps

fast sender from overrunning a slow receiver.

2. Example: Fiber optic network with a capacity of 1000Gbps on

which a supercomputer is trying to transfer a file to a personal

computer at 1Gbps. Although there is no congestion, flow

control is needed to force the supercomputer so that personal

computer can able to accept the data.

3. Example: A network with 1Mbps lines and 1000 computers,

half of which are trying to transfer files at 100Kbps to the

other half. Here the problem is not that of fast senders

overpowering slow receivers, but the total offered traffic

exceeds what the network can handle.

Classification of Congestion Control

4
 Router-Centric

- The internal network routers take responsibility for:

 Which packets to forward

 Which packets to drop

 The nature of congestion notification to the hosts.

- This includes the Queuing Algorithm to manage the buffers

at the routers.

 Host-Centric

- The end hosts adjust their behavior based on observations of

network conditions

- TCP Congestion Control Mechanisms

 Feedback-Based

5
 - The transmission rate is adjusted according to feedback

received from the network.

 Explicit feedback

 Sender needs to be notified of congestion

received from network and from receiver

 Implicit feedback

 Congestion indicators? – Packet loss

 Reaction to congestion – No congestion: increase

rate, Congestion: decrease rate

 How rate is controlled? – Congestion window

size

TCP CONGESTION CONTROL

6
TCP reacts to congestion by reducing the sender window size. The

size of the sender window is determined by the following two

factors-

 Receiver window size: Receiver window size is an advertisement

of- “How much data (in bytes) the receiver can receive without

acknowledgement?”

 Sender should not send data greater than receiver

window size.

 Otherwise, it leads to dropping the TCP segments which

causes TCP Retransmission.

 So, sender should always send data less than or equal to

receiver window size.

 Receiver dictates its window size to the sender

through TCP Header.

 Congestion window size: Sender should not send data greater

than congestion window size.

7
 Otherwise,

 it leads to dropping the TCP segments which causes TCP

Retransmission.

 sender should always send data less than or equal to

congestion window size.

 Different variants of TCP use different approaches to

calculate the size of congestion window.

So always

Sender window size = Minimum (Receiver window size, Congestion

window size)

Three mechanisms

AIMD (Additive Increase/Multiplicative Decrease)

Slow Start (SS)

Congestion Avoidance (CA)

AIMD
8
In TCP, congestion control is done through a mechanism called

additive increase/multiplicative decrease. A congestion window size

is fixed at the beginning of the transmission, such as 16 packets. If

there is suddenly congestion, and a packet loss is detected, the TCP

reduces the congestion window size to 8. Even then, if a packet loss

is detected, the window size is reduced to 4, and then to 2.

Fig.2 AIMD

The decrease is multiplicative:

Cut Congestion Window (cwnd) in half after congestion occurs.

9
If the congestion is reduced on the network, and acknowledgements

for the packets are being received by the source, for each

acknowledgement received, the TCP increases the window size by 1.

If 4 was the earlier window size, it becomes 5, then 6 and so on.

The increase is additive:

Increase Congestion Window (cwnd) by one every RTT in the

absence of congestion.

10
Fig.3 Packets during additive increase with one packet being added each RTT

Slow Start

 The Source starts with Congestion Window (cwnd) = 1

 Every time ACK arrives, cwnd is incremented. cwnd is

effectively doubled per RTT.

 Summary: initial rate is slow but ramps up

exponentially fast until congestion finally does occur.

11
 Fig.4 Slow start (exponential increase)

A slow start cannot continue indefinitely. There must be a threshold

to stop these phases. The sender keeps track of a variable ssthresh

(slow start threshold). When the size of the window reaches this

threshold, slow start stops and the next phase begins.

In slow-start algorithm, the size of the congestion window increases

exponentially until it reaches a threshold.

12
Congestion Avoidance: Additive Increase

During the initial data transfer the Slow Start algorithm is used.

However, there may be a point during Slow Start that the network is

forced to drop one or more packets due to overload or congestion. If

this happens, Congestion Avoidance is used to slow the transmission

rate. It increases the congestion window additively instead of

exponentially. When the size of the congestion window reaches the

slow start threshold (ssthresh), the slow start phase stops and the

additive phase begins. In this algorithm, each time the whole

“window” of segments is acknowledged, the size of the congestion

window is increased by one.

In Congestion Avoidance algorithm, the size of the congestion

window increases additively until congestion is detected.

13
 Fig. 5. Illustration of Slow Start and Congestion Avoidance

Congestion Detection

The TCP sender uses the occurrence of two events as signs of

congestion in the network:

time-out or no acknowledgement received: the sign of a strong

congestion

and

14
receiving three duplicate ACKs: the sign of a weak congestion in the

network.

The first is the time-out. If a TCP sender does not receive an ACK

for a segment or group of segments before the time-out occurs, it

assumes that the corresponding segment or segments are lost and

the loss due to congestion.

Another event is the receiving of three duplicate ACKs (four ACKs

with the same acknowledgement number). When a TCP receiver

sends a duplicate ACK, it is the sign that a segment has been

delayed, but sending the three duplicate ACKs is the sign of a

missing segment, which can be due to congestion in the network.

When a receiver sends three duplicate ACKs, it means that one

segment is missing, but three segments have been received.

Time Out

 When CongWin (cwnd) is below Threshold, sender is in slow-

start phase, window grows exponentially.

15
  When timeout occurs, Threshold set to Cong Win ((cwnd)/2)

and CongWin(cwnd) is set to 1.

 When CongWin (cwnd) is above Threshold, sender is in

congestion avoidance phase, window grows linearly.

Fig.6

Three Duplicate Packets received

Duplicate ACKs

16
 • When a duplicate ACK is seen by the sender, it infers that the

other side must have received a packet out of order.

– Delays on different paths could be different -- thus, the

missing packets may be delivered.

– So, wait for “some” number of duplicate ACKs before

resending data.

This number is usually 3.

Two algorithms: Fast retransmit and Fast Recovery.

Fast Retransmit

Retransmit missing packet immediately if 3 duplicate ACKs

received.

17
 Fig. 7. Fast Retransmit based on three duplicate ACKs

Fast Recovery

After the sender detects missing TCP segment as indicated by the

receipt of 3 duplicate acknowledgements, fast recovery mechanism

is initiated. Fast recovery with congestion avoidance works as

follows:

18
  After three duplicate acknowledgements are received, the

sender takes it as indication of missing TCP segment. It

retransmits the missing segment and sets ssthresh to half the

current cwnd.

 The new value of cwnd is set equal to the revised ssthresh

plus 3 since the receiver has already received three

subsequent TCP segments.

 For every subsequent duplicate ACK

 Increase cwnd linearly by one segment

 Once receive a new ACK

 Reset cwnd to sstresh and resume Congestion

Avoidance.

This process is called fast recovery because after the receiver gets

missing segment, it sends an acknowledgement that acknowledges

missing segment and all the received succeeding TCP segments as

19
well. Thus the sender and receiver recover quickly. If time-out

occurs or if there is no acknowledgment, TCP assumes that there is

congestion in the network and moves to slow-start procedure.

Fig. 8

20