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

why we have done 10/2 the threshold is 8 na so it should be 8/2 ?

why 10/2? please explain...

---

So answer could be both 7mss and 8mss that’s why it was given bonus?

---

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

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

i think you are right !

---

The question asks the window size at the end of 10th transmission. The window size increases by 1 after the acknowledgment are recived, not at the end of the transmission. 

---

Ditto!!!! This should be the way.It is not mentioned that when we start again then MSS should be 2MSS,so we should follow normal algorithm and set it to 1 MSS.

---

nice explanation....

---

This is the right explanation! After strong possibility of congestion, it always rebegins with 1 MSS. Thank you.

---

In this question https://gateoverflow.in/2156/gate2012_45 marks is given to all by IIT D ..so you understand now you can take any one among 1 or 2  .

And this question https://gateoverflow.in/1794/gate2014-1-27  correct answer comes in a range between 1100-1300 , where 1100 comes from taking window size 2 and 1200 comes by taking window size 1

In congestion avoidance, we increase window size either by 1 or 2..

This is correct statement .

---

@Bikram Sir

t=7 =>2mss

t=8, =>4mss

t=9, =>8mss( Slow start threshold =5MSS)

t=10, =>9mss.(Now,Congestion avoidance starts)

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

Why is it wrong?

---

@  VS 

t=7 =>2mss

t=8, =>4mss

t=9, =>5mss  (  rebegins with 1 MSS )

t=10, =>6mss.

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

see the above answer carefully .

---

@Bikram sir

The question says AIMD in one place and slow start in other place. According to this video:

AIMD increases one congestion window one packet at a time whereas slow start goes exponential. How should one know whether the question is asking for AiMD  or slow start?

---

Why is every one taking t 7=2 And t 8 = 4   why not taking t8 as 3

---

After time out window size drops to 1MSS(t6) and then starts increasing exponentially till the threshold (which is half of the time-out in the previous round, which is 4 in the given case). Hence, t7 = 2, t8 = 4.

---

The transition to Congestion avoidance phase from slow start phase happens when window size>=threshold. So, why are we doing the transition at 4MSS when the threshold is 5MSS ??

---

Here also it is given that the congestion window is ALWAYS 1 MSS after timeout.

http://www.ece.virginia.edu/~mv/edu/ee136/Lectures/congestion-control/tcp-congestion-control.pdf

---

After the fifth transmission failed, how we know there is strong possibility of congestion, weak possibility also may be? And in the problem additive increase is mentioned, so we should go for congestion avoidance instead of slow start. Plz clear my doubt.

---

Why are you taking

t=1,⇒2MSS

t=2,⇒4MSS

t=3,⇒8MSS

It should be instead,

r=1 => 2MSS ( 2 segments are transmitted)

r=2 => 4MSS ( 3rd and 4th segment is transmitted then at 5th segment TO occurs)

It is supposed to be rounds instead of transmissions. Each round will have number of transmissions equal to the congestion window of that particular round. For each round the transmission has to start from count 1 until all the MSS in that congestion window is filled.

---

There is an ambiguity present in the question...here nothing is mention about the segment size....if we consider segment size=1mss then ans is 7mss ...if we consider segment size=2mss then the ans is12mss....

---

Why 6+1?

---

Question asks : Find the congestion window size at the end of the tenth transmission.
I Its given in the question that a timeout occurs during the fifth transmission, so timeout will occur on the 10th transmission , so why now window size became 6/2 =3 at the end of 10th transmission?

---

@ Sandy SharmaTO  occurs at the end of fifth transmission not every 5th transmission

---

Thanks, can you have a looks over a similar yet different question https://gateoverflow.in/272917/me-topicwise-computer-networks-2-gate-2019-q12

---

Look at the wordings - 

 at the start of the slow start phase is $2$ MSS

so it should be like this according to me -  (the value of $t$ represents the cwnd at the end of $t_{th}$ $RTT$.)

At $t=0$ : $2$

At $t=1$ : $4$

At $t=2$ : $8$ ($cwnd$ at threshold)

At $t=3$ : $9$

At $t=4$ : $10$

At $t=5$ : $11$, here at the end of $RTT$ timeout has been realized. so $CWND_{threshold}=\lfloor{11/2}\rfloor = 5$ and $CWND=1$

At $t=6$ : $2$ (Assuming it restarts with $2$ as it started with that)

At $t=7$ : $4$ (Receiver will advertize $CWND = 5$ for next RTT)

At $t=8$ : $5$

At $t=9$ : $6$

At $t=10$ : $7$ 

But I am not sure about this solution. Can anyone point out mistakes in this?

---

@2019_Aspirant your solution seems more accurate.

At t=0 they (TCP/IP 4th Edition forouzan ) started from 1MSS, here in question they have give to start from 2MSS

So, in the above answer by @Harsh181996 it should have been started from t=0 and no need for 6+1 (bcz its clearly mention at the end of transmission).

---

Why cwnd size is 1 more than the last segment transmitted?

---

Yes @2019_Aspirant

answer makes more sense. The transmission starts from 0th.

In the above answer at T=6, its written as 1MSS. I think its not possible, because it should be 2MSS.

---

@Shamim Ahmed 'During' means when $10MSS$ was being transmitted. I was wrong there, I took 'after transmission'. These are possible solutions -

• 2 -> 4-> 8 -> 9 -> 10 (time out. make threshold 5) -> 1-> 2 -> 4 -> 5 -> 6 -> 7
• 2 -> 4-> 8 -> 9 -> 10 (time out. make threshold 5) -> 2-> 4 -> 5 -> 6 -> 7 -> 8

@Ashish Patel 

---

So in that case 8 would be the answer right as its mentioning "During", i.e.., at T=4.

But how can it be 7 then? It clearly mentioned that MSS = 2.

---

I think there should be no confusion..bcz it mentioned in textbooks when time out happens set thrrshold to half and congestion window size to one....

---

@Arjun

2 questions : <please answer>

1) selected answer has time t1 to t10 ,but at start (t1) cwnd was 2 but this is before any transmission right..so last time should be t11 isn't it? cause at t2 1st transmission happened and ackn received so cwnd is 4 now .

t1...2

t2...4(1st transmission)

t3...8(2nd transmission)....so on and so forth

 

 

2) when cwnd turned to 8 we went in congestion avoidance phase incrementing cwnd by 1 MSS,but when ssthresh brcame 10/2=5  and cwnd became 4 at t8 it hasn't yet reached 5 so..cwnd should be 8 in next step ... isn't it...???

wht start congestion avoidance at cwnd=4 when ssthresh is 5????

 

---

https://gateoverflow.in/2156/gate2012-45?show=137392#c137392

---

https://gateoverflow.in/2156/gate2012-45?show=141129#c141129

---

https://gateoverflow.in/2156/gate2012-45?show=273763#c273763

---

@Bikram

please reply with your own words..please do

if my picture is wrong then why?

if it's correct then mention it too in your reply.

---

https://gateoverflow.in/2156/gate2012-45?show=89218#a89218

---

@Bikram sir, at 10th transmission we dont know if congestion occurs or not. If time out occurs @ 10th transmission then after 10th transmission should be 1MSS right?

---

The question has asked “at the end of transmission” and not “at the end of a successful transmission”. So I think we can assume that the acknowledgement for the tenth transmission has not been received. So if we take 2 MSS for t=6 then we will get 7 MSS as the answer as it will not get incremented by 1 as the acknowledgement has not been received yet. So, 7 MSS should be the right answer using 2MSS for t = 6.

---

@nvs16 There’s either during transmission, or end of transmission. Now what you are suggesting is during transmission, in question they clearly asked end of the transmission. Also if you are just considering the transmission period for all the segments as transmission which i think is the case then the problem definition of having timeout during 5^th transmission doesn’t make any sense.   

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

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.