The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+40 votes

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.

- $8$ MSS
- $14$ MSS
- $7$ MSS
- $12$ MSS

+4

Is it the default size of MSS(max segment size) i.e 1 ? And in algo it is mentioned that when timeout/error occurs the congestion window is set to MSS size which is 2 here, i think it mean for AIMD also it should be taken as increment factor instead of 1 MSS. What i mean is :

2, 4, 8, 10, 12, 2, 4, 6, 8, 10 (CW size)

1, 2, 3, 4, 5, 6, 7,8, 9, 10 (transmission count)

https://gateoverflow.in/1794/gate2014-1_27 please see this question. Here MSS is mentioned is 2 MSS, means 2 MSS is taken as a additive factor while doing AIMD.

Correct me if wrong.

2, 4, 8, 10, 12, 2, 4, 6, 8, 10 (CW size)

1, 2, 3, 4, 5, 6, 7,8, 9, 10 (transmission count)

https://gateoverflow.in/1794/gate2014-1_27 please see this question. Here MSS is mentioned is 2 MSS, means 2 MSS is taken as a additive factor while doing AIMD.

Correct me if wrong.

+2

In https://gateoverflow.in/1794/gate2014-1_27 , The size is increase by 1 MSS only. There MSS=2KB

+8

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

Both 1 and 2 are correct , you can take any value like either 1 or 2 , both will give correct answer, why i m saying this , see this qstn http://gateoverflow.in/1794/gate2014-1-27 here correct answer given by IIT KGP official key is in the range and range value is 1100-1300 . Now, when you take 1 ans coming 1200 . When you take 2, answer coming 1100 .. so both are correct according to IIT KGP .

And in this question, marks given to all due to this ambiguity :)

+3

Can anyone help me regarding what the congestion window size at the end of transmission means? Does it mean the size of last segment sent or the one to be sent in the next transmission?

+1

Nope. here, answer will be independent of whether it is Tahoe or Reno but in case of three duplicate acknowledgements , TCP reno will give different answer because it avoids the slow-start phase and uses fast recovery after getting 3 duplicate ACKs.

+70 votes

Best answer

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 to $\dfrac{n}{2}$ i.e. $\dfrac{10}{2} = 5.$

$t=6, \Rightarrow1 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 \Rightarrow2MSS$

$t=8, \Rightarrow4MSS$

$t=9, \Rightarrow5MSS$

$t=10, \Rightarrow6MSS$.

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

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

+5

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.

+3

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.

0

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

+5

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 .

0

@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

**Why is it wrong?**

+5

@ 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

see the above answer carefully .

+4

@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?

0

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.

0

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 ??

0

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

0

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.

0

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.

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.

0

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....

+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?

0

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

+2

Look at the wordings -

at the start of the slow start phase is $22$ 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?

+1

@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).

0

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.

0

@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

+36 votes

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$.

$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$.

+4

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.

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.

+5

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

0

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.

0

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.

0

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

-=- must be 8 then

-=- must be 8 then

0

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

+10 votes

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

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

+2 votes

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

+2

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..!!

0 votes

At

*t*=1,⇒2*M**S**S*

*t*=2,⇒4*M**S**S*

*t*=3,⇒8*M**S**S*

*t*=4,⇒9*M**S**S*

(after threshold additive increase)

*t*=5,⇒10*M**S**S*

(fails)

Threshold will be reduced by *n*2

i.e. 10/2=5.

**, **

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

*t*=6⇒2*M**S**S*

*t*=7,⇒4*M**S**S*

*t*=8,⇒5*M**S**S*

*t*=9,⇒6*M**S**S*

*t*=9,⇒7*M**S**S*

the the congestion window size will be =7*M**S**S*.

–3 votes

Should be 6mss..2,4,8,9,10 then timeout occurs and threshold is set to 5mss. Again starts from 1,2,4,5,6mss in the 10th transmission.

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.5k
- Digital Logic 3k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 5.9k
- Compiler Design 2.1k
- Databases 4.2k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 588
- Exam Queries 568
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,071 questions

53,206 answers

184,561 comments

70,424 users