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,⇒2MSS

t=2,⇒4MSS

t=3,⇒8MSS

t=4,⇒9MSS

(after threshold additive increase)

t=5,⇒10MSS

(fails)

Threshold will be reduced by n2

i.e. 10/2=5.

, 

(The window size is NOT always =1MSS. Here it is mentioned  2MSS)

t=6⇒2MSS

t=7,⇒4MSS

t=8,⇒5MSS

t=9,⇒6MSS

t=9,⇒7MSS

the the congestion window size will be =7MSS.

Answer 2

"Additive Increase, Multiplicative  Decrease Out of the  three versions of  TCP,  the  Reno  version is most  common  today.  It  has been observed that, in  this version,  most of  the  time  the congestion is  detected  and  taken care of  by  observing the three  duplicate ACKs. Even if  there are  some  time-out events, TCP recovers from them  by  aggressive  exponential  growth."

 

This is taken from Data Communications and Networking by Forouzan. 5th edition. Page 784.

 

So in my understanding:

By the end of 

1st transmission: 2+2=4

2nd transmission: 8 (slow start threshold)

3rd transmission: 9

4th transmission: 10 

During 5th a time-out occurs. In AIMD in time-out we go back to the initial MSS. Therefore:

5th transmission: 2

Then we do fast recovery in case of timeouts. 

6th transmission: 4

7th transmission: 8 (ss threshold)

8th transmission: 9

9th transmission: 10

10th transmission: 11

Which we don't have in the options. So I am assuming the recovery is not FR and Addictive increase instead. 

In that case, by the end of:

 

6th transmission: 3

7th transmission: 4

8th transmission: 5

9th transmission: 6

10th transmission: 7

 

Also according to Wikipedia, "In TCP, after slow start, the additive increase parameter a is typically one MSS (maximum segment size) per round-trip time, and the multiplicative decrease factor b is typically 1/2."

But on time out we don't do multiplicative decrease. Multiplicative decrease is in case of 3 duplicate acknowledgements. 

 

 

Answer 3

2 I 4 I 8 I 9 I 10 I 1 I 2 I 4 I 5 I 6 I 7 

                          ^( TIME OUT OCCURS AFTER 5TH RTT) THUS SSTHRESHOLD BECOMES= CWND/2=10/2=5

                                                     ^(10TH RTT CWND=7 MSS)

   Ans=C       If the question said after the 10th RTT then it would have been 8 MSS.                   

Answer 4

Ans

Answer 5

.....

 

Answer 6

Answer: C

$$\text{Given Threshold Th= 8 MSS}$$

$$\text{Therefore, Receiving window size } W_R= 2 \times Th \text{ = 16 MSS}$$

 

the window size at the start of the slow start phase is 2 MSS

 

$$\text{Start AIMD with 2 MSS:}$$

$$\text{2 | 4 | 8 (Th) | 9 | 10 (TO)}$$

$$\text{In case of timeout, the slow start phase starts again with new threshold = 10/2 = 5 }$$

$$\text{2 | 4 | 8 (Th) | 9 | 10 (TO) | 2 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |12 | 13 | 14 | 15 | 16 (W(R)) | 16 | 16............}$$

 

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

$$\text{The size of congestion window after the 10th transmission is the 10th term of this sequence i.e. 7 MSS}$$

 

$$\text{NOTE: Don't get confused with vertical lines, those are round trip time including the transmission AND acknowledgment.}$$

$$\text{NOTE: End of transmission means as soon as the packet leaves the sender (No acknowledgment needed)}$$