Thursday, 8 June 2017

TCP congestion control


This post is more of problem oriented. This topic include less of theory and more of problem solving. Before I explain about TCP congestion control algorithm let's see why people came up with this algorithm.

History of congestion control:

Back in late 1980's when ARPANET was getting adopted to TCP/IP and when researchers started developing networks of networks (which was later called as internet), a severe problem occurred. Whenever any node in a network wanted to send some data, it used to transmit it without any restrictions. Because of which the entire internet used to come down. To understand it more clearly, let's take an example.
Assume there is node named S who wants to send a 1 GB of file to a node named D. Assume the packet size is 1 MB. This means the node S cannot send the entire 1 GB of file in a single piece. It needs to be divided into smaller chunks (packets) of size 1 MB. If we divide 1 GB by 1 MB we get 1024 packets.

Now since there is no congestion control algorithm back then, so all the nodes had full freedom of sending as many packets as they want. So nodes like S would start sending all the packets at once. In this case node S will transmit all the 1024 packets at once. 

1024 is a small number now, but back then when bandwidth was very less and we had limited resources, this number was of some significance. Here we are talking of just one node. Imagine if even quarter of the total nodes transmit 1024 packets what would be the amount of traffic generated at every router.

It was because this situation the internet would come down very often. This problem was called as Congestion meltdown. To overcome this problem we came up with TCP congestion control algorithm. TCP congestion control algorithm acts as a protective layer over the internet. 
Before we discuss TCP congestion control algorithm there are few things you should know.
  • MSS: It's called as maximum segment size. A packet at transport layer is called as a segment. So MSS means the maximum size segment that the sender can send onto internet.
  • Ws: It is called as the sender window size. It is the maximum amount of data that sender can have at any instance of time. You can call it as the buffer present at the sender side.
  • Wᵣ: It is called as the receiver window size. It is the maximum amount of data that receiver can store at its end, at any given instance of time. It is the buffer present at the receiver's end.
  • Wc: It is called as the congestion window. It is the maximum amount of data that the internet can have at any given instance of time.

Congestion control algorithm:

The algorithm is divided into 3 phases - 
  • Slow start phase. 
  • Congestion avoidance phase. 
  • Congestion detection phase.
As I said the algorithm is used to put restrictions onto unrestricted traffic. So if a host has some data to send we don't allow him/her to send all the data once.
During the slow start phase we grow exponentially till a point called threshold (we will see how to calculate it). This means the rate at which we start sending the packets starts growing exponentially in this phase. 

Initially we send 1 segment, then we send 2 segments then we double it and send 4 segments, next time we send double of 4 segments and this goes on till we reach threshold value.
You might get the doubt that, why do we call it as slow start phase? It is so because we start with very small value example 1 or 2.

After this we grow linearly till we reach Ws. This phase is called as congestion avoidance phase. In this phase we grow linearly because we have crossed the threshold and if now we try to send packets at exponential rate there might be chances of congestions and network breakdown.

We increase the number of packets linearly. If threshold is 10 then next time we send 11 segments, then 12, and then 13 and so on.... till we reach Ws.

Once we reach Ws we keep sending the packets at the same rate. It is so because now we don't have the capability to send more packets than Ws.  This is the most packets that we can generate at our end. 
Now coming to congestion detection phase. It is that phase which is active all the time. You can detect congestion at any instance of time and in any phase. So it's not represented in graph shown above. There are 3 different ways of detecting congestion:
To solve the problems we should keep the following things in mind:
  • Whenever timeout occurs, new threshold becomes half of current window size and we start from slow start phase.
  • Whenever 3-duplicate acknowledgement occurs, new threshold is equal to half of current window size and we start with congestion avoidance phase. That means we start from threshold value.Now let's take an example and understand it more clearly.
Example: We are given the following data - 
Wᵣ: 64KB.
Start with 1 MSS initially.
Find out after how many transmissions Ws reaches its maximum value? if the sender gets timeout timer after 8th transmission and 3 duplicate acknowledgement after 17th transmission.
↦ To answer this question we need to find out certain values. First is Wᵣ in terms of the segments and threshold.
Wᵣ = (Wᵣ size in packets)/(MSS size) = 64 KB/1 KB = 64 MSSs.
Threshold = Wᵣ/2 = 64 / 2 = 32.
Now according to the algorithm we start with 1 MSS.
124816323334⨯(timeout)12481617181920⨯(3-duplicate acknowledgements)1011121314 . . . . . . .64 MSSs. So after 71 transmissions we will reach maximum value MSSs i.e Ws.

So this was about TCP congestion control. If I missed out something or you want to suggest something, mention in the comments section below. Tell me how did you like the post. Don't forget to follow the blog. You can also follow me on Facebook and google+.

Thank you!