GATE CSE 2012 | Question: 45

Question

Consider an instance of TCP’s Additive Increase Multiplicative Decrease (AIMD) algorithm where the window size at the start of the slow start phase is $2$ MSS and the threshold at the start of the first transmission is $8$ MSS. Assume that a timeout occurs during the fifth transmission. Find the congestion window size at the end of the tenth transmission.

• A. $8$ MSS
• B. $14$ MSS
• C. $7$ MSS
• D. $12$ MSS

Comments

2012 is the test with the most mistakes made by any iit

---

initial ssthres = 8MSS

start from 2 MSS

so at t=1 => 2

at t=2 => 4

at t=3 => 8 (reached ssthres now it will go linear i.e +=1)

at t=4 =>9

at t=5 =>10 (now the timeout occur so the new ssthres will be CWND/2 i.e 5)

at t=6 => 1

at t=7 =>2

at t=8 => 4 (ssthres = 5 so it can't go 8)

at t=9 =>5

at t=10 =>6

at t=11 =>7

CWND AT THE END OF 10TH TRANSMISSION

now CWND is (6+1) = 7 MSS

---

go-classes-dpp-cn-aimd ( follows rfc5681) its correct. 

Answer 1

At:

$t=1,\Rightarrow2$ MSS

$t=2, \Rightarrow4$ MSS

$t=3, \Rightarrow8$ MSS

$t=4, \Rightarrow9$ MSS (after threshold additive increase)

$t=5, \Rightarrow10$ MSS (fails)

Threshold will be reduced to $\dfrac{n}{2}$ i.e. $\dfrac{10}{2} = 5.$

$t=6, \Rightarrow 1$ MSS , 

(There is an ambiguity here if the window size will be 1 MSS or 2 MSS as given in the question and due to this GATE gave marks to all. Assuming window size to be 1 MSS) 

$t=7 \Rightarrow2$ MSS

$t=8, \Rightarrow4$ MSS

$t=9, \Rightarrow5$ MSS

$t=10, \Rightarrow6$ MSS.

So, at the end of $10^{\text{th}}$ successful transmission ,

The the congestion window size will be $(6+1) = 7$ MSS.

Comments

"A picture is worth a thousand words"

---

Find the congestion window size at the end of the tenth transmission.
 

In the question they have asked about the window size at the end of 10th transmission, you are considering at the end of 10th acknowledgement. the sender window size can be increamented only after receiving acknowledgement not after each tranmission. 

---

AFTER THE TIME OUT THE NEW CWND SIZE WILL BE SET TO GIVEN STARTING VALUE WHICH IS 2MSS

Answer 2

At

$t=1,\Rightarrow2MSS$

$t=2, \Rightarrow4MSS$

$t=3, \Rightarrow8MSS$

$t=4, \Rightarrow9MSS$ (after threshold additive increase)

$t=5, \Rightarrow10MSS$ (fails)

Threshold will be reduced by $\dfrac{n}{2}$ i.e. $\dfrac{10}{2}=5$.

$t=6, \Rightarrow2MSS$

$t=7 \Rightarrow4MSS$

$t=8, \Rightarrow5MSS$

$t=9, \Rightarrow6MSS$

$t=10, \Rightarrow7MSS$.

So at the end of $10^{th}$ transmission congestion window size will be $8 MSS$.

Comments

For the linear increase you should consider the additive factor of 2 MSS and not 1 MSS (As it is the smallest window possible in given system). Thus, at t=4 , you will get => 10 MSS. And calculating it upto 10th iteration the answer one should get is 12 MSS (after 10th iteration).  So, option (d).

BUT, as the algo suggest, in slow start mechanism, system should start sending with 1 packet only in entire window. That equates to 1 MSS. But, as they mentioned 2 MSS here, many students must have got  answer as either 7 MSS (by consider +1) or 12 MSS (like approach above). And that is why, they had gone for grace marks for this particular qstn.

---

At the beginning of first transmission congestion window size: 2 MSS
After end of first transmission congestion window size: 4 MSS

At beginning of 10th transmission congestion window size: 7 MSS
After end of 10th transmission congestion window size: 8 MSS

Then answer should be 8 MSS? 
Please check

---

Shouldn't it be 8 MSS? since it is asked AFTER 10th transmission, so after 10th transmission will be done window size would become 8 MSS.

---

since 10 packet is sent and why u wait for ack , and will be 8 if question says 10 packet successfully received by receiver . question ask time when u send 10th packet. 

---

it i asked as "at the end of 10th transmission" -which i guess mean after 10th transmission

-=- must be 8 then

---

https://tools.ietf.org/html/rfc5681#section-3.1

Here is the rfc reference and there is a thing called smss which is 2 mss in this problem

---

Why does the window size increase linearly after t=7?i.e., 4MSS,5MSS,6MSS. But previously after timeout window size increased doubled i.e., 2MSS 4MSS.

Please explain.

---

Because new threshold is set to 5 due to Time Out.

---

While solving I got the same answer as this one...

---

Here the maximum window size is 2MSS so after the congestion threshold till the timeout we have to increase linearly by 2MSS (i.e the given window size) . but why here it is increased by 1MSS only??

pls help in this!! 

EDIT:

I misinterpreted the question , here only the starting window size is given and not the maximum window size :)

Answer 3

In Case of AIMD , Remember following points to solve the questions : -

1 - Start with Given MSS (Min Seq Size)
2 - Increase the Window size in multiples of MSS till the threshold occurs
3 - Once the threshold reached , increase the window size by 1 MSS till the timeout occurs
4 - Once the timeout occurs , reduce threshold to half and again start from Given Start MSS.

Here , 2-4-8(Threshold reached , increase by 1 MSS till timeout)-9-10(Timeout reached)--(Reduce Threshold and again start from 2)--2-4-5-6-7(Window size at 10th Transaction).

Hence Ans : - 7

Answer 4

Since Slow Start is used, window size is increased by the number of segments successfully sent. This happens until either threshold value is reached or time out occurs.
In both of the above situations AIMD is used to avoid congestion. If threshold is reached, window size will be increased linearly. If there is timeout, window size will be reduced to half.

Window size for 1st transmission = 2 MSS
Window size for 2nd transmission = 4 MSS
Window size for 3rd transmission = 8 MSS
threshold reached, increase linearly (according to AIMD)
Window size for 4th transmission = 9 MSS
Window size for 5th transmission = 10 MSS
time out occurs, resend 5th with window size starts with as slow start.
Window size for 6th transmission = 2 MSS
Window size for 7th transmission = 4 MSS
threshold reached, now increase linearly (according to AIMD)
Additive Increase: 5 MSS (since 8 MSS isn’t permissible anymore)
Window size for 8th transmission = 5 MSS
Window size for 9th transmission = 6 MSS
Window size for 10th transmission = 7 MSS

Comments

Why does the window size increase linearly after 7th transmission???

Also,you mentioned 8MSS isn't permissible anymore.what does this mean?

---

After 7^th transmission it’s not a linear increase, we directly jump to the threshold because we have to start increasing linearly after we’ve reached the threshold.

Answer 5

Answer: 7MSS

if we start with 2MSS as CWND after timeout for next slow start phase the answer will be 8MSS at the end of 10th transmission , as threshold limitation occurs at the end of 7th transmission. 
There is an ambiguity present in the question...here nothing is mention about the segment size after timeout....if we consider segment size=1mss then ans is 7mss ...if we consider segment size=2mss then the ans is 8mss....
So without thinking so much and look gate solution relies on what info they given and if not given then you have to follow standard procedure / algorithm as per the concept . so when it is not mentioned that what is the CWND size after timout in the question directly then try to follow the standard way of solving and it always works. one of the IIT professors told me recently .  

Answer 6

At

t=1, =>2mss

t=2, =>4mss

t=3, =>8mss

t=4, => 10mss (after threshold additive increase  and as the mss is 2 KB we add +2(linear increase) in each step till timeout)

t=5, =>12mss (fails)

Threshold will be reduced by n/2 i.e. 12/2 = 6.

t=6, =>1mss, 

t=7 =>2mss

t=8, =>4mss

t=9, =>5mss

t=10, =>6mss.

So at the end of 10^th successful transmission ,the the congestion window size will be (6+1) = 7 mss.

Comments

At t=1, 2MSS

At t=2,4MSS

At t=3,8MSS

At t=4,9MSS

At t=5,10MSS(Here time out occurs and it enters slow start phase, so new threshold is 5MSS)

At t=6,2MSS (Given in the question, Window size at the start of the slow start phase is 2MSS)

At t=7,4MSS

At t=8,5MSS

At t=9,6MSS

At t=10,7MSS

Now it is asked at the end of the 10th transmission and we are not sure whether it is successful or not untill and unless we get acknowledgment and hence we are not sure about the sender window sizenow.

In the question if it is given as at the end of 10th successful transmission then answer would be 8MSS.

Please refer problem 4 (10) second point in the  below link:

http://web.eecs.utk.edu/~qi/teaching/ece453f06/hw/hw7_sol.htm (reference link from standard book)

Hope it clears..!!

---

I am not getting why after 4 mss at t=7, we increased linearly since threshold was 5 not 4. Please tell.

---

pCS 

 I am not getting why after 4 mss at t=7, we increased linearly since threshold was 5 not 4. Please tell.

because if we again doubled it then it will become 8 mss which is greater than the threshold itself(which is 5 mss) .so that's why we started increasing linearly from 4 mss itself .