GATE IT 2004 | Question: 88

Question

Suppose that the maximum transmit window size for a TCP connection is $12000$ $\text{bytes}$. Each packet consists of $2000$ $\text{bytes}$. At some point in time, the connection is in slow-start phase with a current transmit window of $4000$ $\text{bytes}$. Subsequently, the transmitter receives two acknowledgments. Assume that no packets are lost and there are no time-outs. What is the maximum possible value of the current transmit window?

• A. $4000$ $\text{bytes}$
• B. $8000$ $\text{bytes}$
• C. $10000$ $\text{bytes}$
• D. $12000$ $\text{bytes}$

Comments

Maximum window size=12000B

Threshold =12000/2=6000B

MSS= 2000B

Current window size= 4000B

In slow start phase next window size=4000*2=8000B > 6000B(threshold)

So increment should of MSS only.

After 2 ACKs, current window size= 4000+ 2000+2000= 8000B

---

Jo window size smjh gya

Use congestion control smjh me pakka ayega

---

@arpit_18  Yes. We increase window size exponentially in the slow-start phase. Consider initial window size as 1. You sent 1 MSS to the receiver. Once you receive the acknowledgement from the receiver, you will increase window size by 1 MSS. Now the sender window size has become 2. So the sender will send 2 MSS. Now remember one thing, the sender will increase its window size by 1 MSS FOR EVERY ACKNOWLEDGEMENT it receives. So here, it will receive 2 acknowledgements and it will increase window size by 2. It will become 4 now. 

I hope your doubt is cleared!

Answer 1

In slow-start phase, for each ACK, the sender increases the current transmit window by Maximum Segment Size (MSS). In the question it is given a packet consists of $2000$ bytes and that can be taken as MSS. So, after two ACKs, current transmit window
$= 4000 + 2000 + 2000$
$= 8000$

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

Correct Answer: $B$

Comments

is this  correct solution

---

@Arjun: Question says "maximum transmit window size for a TCP connection is 12000 bytes."

What is it ??

What is the difference b/w this so called "maximum transmit window" and what we call a "MSS".

please explain . its a bit puzzling.

Also, can we  take a packet size  to be ab  MSS or is it some standard !!

---

maximum transmit window is the receiver window and sender can never transfer more than this. MSS is something that is fixed during the connection set up between sender and receiver and the packet size is the MSS.

---

After receiving 2 ack the current window size will also be decreased  by 2 segments right ??

---

why not doubled? why adding?

---

Since recvWind = 12000B and Packet Size = 2000B which is MSS here.

So MSS = 2000B then recvWind = 6MSS and currentSenderWindow = 2MSS

Threshold = recvWind/2 = 3MSS which implies transmission is in Slow Start Phase.

After receiving first ACK: currentSenderWindow should increase exponentially to 4 MSS but since threshold = 3MSS, currentSenderWindow Size goes to threshold which is 3MSS

After receiving second ACK: Since now it is in Congestion avoidance phase sender window size increases lineraly which makes currentSenderWindow = 4MSS = 4 * 1MSS = 4 * 2000B  = 8000B

---

What abt the threshold limitation on the slow start phase @Arjun sir ?

---

@Arjun Can you please clarify why we are considering individual acknowledgements, instead of cumulative acknowledgments? It is given in the question that it is TCP protocol and TCP uses cumulative acknowledgemets or selective acknowledgement.

https://en.wikipedia.org/wiki/Transmission_Control_Protocol#Selective_acknowledgments 

Using cummulative ack the answer comes out to be 12000

---

@Nilesh
In slow start phase why did you assume the threshold to be equal to half of reciever window?
In the first slow start phase the only restriction is threshold<=rwnd
Your assumption will be the case only after the first time out where the cwnd = rwnd and  cwnd becomes 1 MSS and threshold becomes half of the reciever window...

Reference:https://www.utdallas.edu/~venky/acn/CongestionControl.pdf

Any one please confirm asap

---

So, a total of 4 ACKS are received  by the receiver ?

---

@Arjun:in slow start phase conjunction window size increase exponentially. Current window size is 4000 byte. Mean it has two packet. It become 4 packet on getting 1st ack and 8 on getting 2nd ack. Therefore size of conjuction window is 8*2000=16000 byte. But maximum transmit window size is 12000 byte.hence conjunction can't grow beyond transmit window. Therefore answer is 12000 byte. Is my approach correct?

---

"After receiving first ACK: currentSenderWindow should increase exponentially to 4 MSS"

I think this is wrong. In slow start phase after receiving a ACK , window sizes increases by 1 MSS and after each RTT window size doubles( Suppose current window size is X MSS. Total X number of ACK will come for X segments and each ACk will increase window size by 1 MSS , so total increment = X MSS, So, at the end of the RTT window size will be doubled (X+X=2X))

---

@Sourav,

" In slow start phase after receiving a ACK , window sizes increases by 1 MSS and after each RTT window size doubles" No, receiving an ACK refers 1 RTT at sender in which sender will increase the window size exponentially, But since threshold is 3 MSS it will go max up to 3 MSS and stops from there it grows linearly and once it got 2nd ACK it increases up to 4 MSS

---

After Window size of 4000, 2 acknowledgements has been received

So. after 4000 the window size will be 6000 and then 8000 and the acknowledgement is received till 8000, then the window size be 10000...?

---

@Nilesh:-

How did you get : -Threshold = recvWind/2 

I dont think we set threshold to any value in slow start .It is generally given.Now in case it is not given ,so how did you take it half the window?Can you given any reference to this point?

---

@Arjun Sir, @Bikram Sir,

Could you please check if the below explanation satisfies.

Slightly different opinion. The difference b/w slow increase and Additive increase. is such that-

Let's say at sender window(cwnd) is having x segments.(n1,n2,n3...nx). Mark this window as wi.

size of wi is x number of segments=n1+n2+n3.....+nx

In case of Slow increase , when the ack for n1 received by Sender after RTT, then cwnd=x+1. Then when ack received for n2, then cwnd=(x+1 MSS)+1MSS..and so on. So when the last ack such as ni would be received, then cwnd=((((x+1MSS)+1MSS)+1MSS)+1MSS)+1MSS....x times=x+x=2x.

When window wi starts it's transmission of it's frame, then it was x.  And when all the acks are received for window(wi), then cwnd becomes 2x.

However for additive increase(taking the same example) cwnd size doesn't increase after every ack . Instead of that when all the segments of window(wi) are sent and their acks are  received , such that the last ack nx is received , it confirms that all the segments of entire window(wi) are acked. Then cwnd= cwnd+1MSS.

 

In this case, the sshthresh= 12000/2=6000 bytes=3segments

1MSS=2000 bytes=1 segment

Present window size(cwnd)wi=4000 bytes=2 segments (name them as seg-p ,seg-q)

At the moment we are in slow start phase.

seg-p sent and it's ack received by sender. So cwnd= cwnd+1 MSS =2+1 segments= 3 segmemts. Now it has reached sshthresh.

So now additive increase starts and from wi , still seg-q is left. Send the seg-q and receive the ack for seg-q.

So all the segments for window (wi) are received. So cwnd=cwnd+1 MSS=3+1=4 segments=8000 bytes.

---

till the threshold value it increases exponentially.

---

This is most precise answer as in selected answer blindly 1 MSS is increased and in question it is slow start phase which are contradictory.

---

Nicely explained sir.

---

We know that In slow-start phase, for each ACK, the sender increases the current transmit window exponentially.

We are given that maximum transmit window size for a TCP Conn = 12000 B.

Now as per question due to congestion, the TCP Conn would come to slow-start phase which is:

 

TCP THRESHOLD WINDOW SIZE NEW = TCP CURRENT WINDOW SIZE / 2 

 =>   12000/2 = 6000 Bytes.

 

The current window size has been incremented to 4000 B which is <  TCP THRESHOLD WINDOW SIZE ( 6000 B )

 

Now we are given a scenario after these actions have been performed.

 

We send two packets and then we receive ACK of them one by one.

As per question before any ACK came out of these two packets TCP CURRENT WINDOW SIZE = 4000 B.

On

 

RECEIVING 1st ACK = 2 * TCP CURRENT WINDOW SIZE

                                   = 2 * 4000 B

                                   = 8000 B  but it should be <= TCP THRESHOLD WINDOW SIZE acc to congestion algorithm therefore 

                                   TCP CURRENT WINDOW SIZE = 6000 Byte

Now the TCP CURRENT WINDOW SIZE = TCP THRESHOLD WINDOW SIZE, therefore, TCP CURRENT WINDOW SIZE now will increase linearly as the algorithm is in congestion avoidance phase therefore on 

 

RECEIVING 2nd ACK:

                                       TCP CURRENT WINDOW SIZE = TCP CURRENT WINDOW SIZE + 1 MSS

                                                                                            = 6000B + 2000B

                                                                                            = 8000 Bytes                                 

 

---

@tusharp

Please check this  and correct if wrong:
1) IN slow start phase Wc increase by 1MSS after every ACK and nearly exponentially AFTER EVERY ROUND [Round ==> whole window sent and acknowledged]

1) IN Congestion avoidance phase Wc increase by 1MSS after every ROUND not after every ACK

---

....

---

@jatin khachane 1 It is not about round, It is about per packet Acknowledgement in both slow start and congestion avoidance phases. Formulae used in both phases are :-

1) In slow-start phase, 

                                           $cwnd = cwnd \;+ \;1\; packet\; per \; acknowledgement$

   Please check here

2) In congestion avoidance phase,

                                           $cwnd = cwnd \;+ \frac{1}{\left \lfloor cwnd \right \rfloor}*\;1\; packet\; per \; acknowledgement$

   Please check here

   Reference              

Edit(06/11/2021): I think, above 2 links for images were not working previously, so updated now.

---

@ankitgupta.1729

For Slow start phase ..we can say that cwnd increases by 1MSS after every acknowledgement and doubles after every round trip time (Round trip time means all segments get acknowledge in current window)

For Congestion avoidance phase ..what can we say then what happens after every acknowledge and every RTT ? in words then

---

@jatin khachane 1 yes, right. We can say this in case of slow-start. In case of congestion avoidance, cwnd is increased by $\frac{1}{cwnd}$ after every successful acknowledgement. For example , suppose, currently I have cwnd size = 3 , now after 1st acknowledgement, it will be $(3 +  \frac{1}{3})$ , after 2nd ack , it will be $(3 +  \frac{1}{3}+ \frac{1}{3})$ and after 3rd ack, it will be $(3 +  \frac{1}{3}+ \frac{1}{3}+\frac{1}{3} )$ which is same as cwnd = 3+1 = 4. So, linear growth in cwnd size . So, we can say that size of cwnd increased by  $\frac{1}{cwnd}$ after every successful acknowledgement and after each RTT , it will be added by 1 MSS i.e. Linear growth in congestion avoidance.

---

Imp point to note here is RTT is not ack for single segment here ..RTT = all segments in current window get acknowledge

Then we can say

In slow start => increases by 1MSS after every ACK and exponentially after every RTT

In congestion avoidance ==> increases by 1/floor(cwnd) after every ack and increases by 1 after every RTT

---

@Denson George where you find this that threshold value <= receiver window size

?

---

Thank you

you have cleared many of my doubts here

---

Consider this scenario: the congestion window is now $8000B$ as given. Continuing slow start, the sender sends out 4 segments/packets.

On 1st ACK, $cwnd$ becomes $8000 + 2000 = 10,000B$.

On 2nd ACK, $cwnd$ becomes $10000 + 2000 = 12,000B$.

Now we've reached the limit ($ssthresh$?), so beyond this, TCP should change into linear increase/congestion avoidance/additive increase phase and continue in this manner until the next timeout (on timeout, the threshold is halved, TCP goes back into slow start and the congestion window becomes $1MSS = 2,000B$).

How does the increase happen on 3rd and 4th ACKs? I am unable to visualize.

---

Here we are asked to give – “maximum possible value of the current transmit window”. Why are we answering the current transmit window after the reception of two acks? The max size of current transmit window is 12000B right?

---

But there is no timeout/ no error how can you attempt this way?

---

@Amit are you asking me?

---

Slow start begins initially with a congestion window size (CWND) of 1, 2, 4 or 10 MSS. The value for the congestion window size will be increased by one with each acknowledgement (ACK) received, effectively doubling the window size each round-trip time.

Source: https://en.wikipedia.org/wiki/TCP_congestion_control#Slow_start

---

Each time an ACK is received, the congestion window is increased by one segment.

The sender starts by transmitting one segment and waiting for its ACK. When that ACK is received, the congestion window is incremented from one to two, and two segments can be sent.  When each of those two segments is acknowledged, the congestion window is increased to four. This provides an exponential growth, although it is not exactly exponential because the receiver may delay its ACKs, typically sending one ACK for every two segments that it receives.

Source: https://tools.ietf.org/html/rfc2001

---

The reference link in ankitgupta.1729 comment is old and wont work.

 https://youtu.be/Cy2cRpwXCvE?t=682 is where that reference is now.

---

If we take threshold=12000/2=6000 then for the second ACK TCP enters Congestion avoidance Phase (since first ACK is making it 6000) hence it will be increasing the congestion window by MSS/floor(congestion_window) as is given by  ankitgupta.1729 in his comment above. But then we will get a congestion window size in some fraction and not integer. And we can’t just take ceil of that cause we dont have any std saying that we shd. So i looked in the RFC  https://www.rfc-editor.org/rfc/rfc5681#page-4

In this is clearly mentioned:

“

The initial value of ssthresh SHOULD be set arbitrarily high (e.g.,
   to the size of the largest possible advertised window), but ssthresh
   MUST be reduced in response to congestion

“

Hence we shd take threshold=12000 and NOT 12000/2 (cause in the question it’s clearly given that “No packets are lost and there are no time-outs” till now) and now even for the second ACK TCP will be in Slow start phase and THIS is why we are gonna be incrementing the congestion_window by MSS even for second ACK!

Answer 2

Since recvWind = 12000B and Packet Size = 2000B (or MSS )

 receiverWindow = 6 MSS and currentSenderWindow = 2MSS

Slow Start Threshold = receiverWindow/2 = 3 MSS (2 MSS < 3 MSS which implies transmission is in Slow Start Phase)

After receiving first ACK: currentSenderWindow should increase exponentially to 4 MSS but since threshold = 3 MSS, currentSenderWindow Size goes to threshold which is 3 MSS then 
After receiving second ACK: Since now it is in Congestion avoidance phase sender window size increases linearly which makes currentSenderWindow = 4 MSS = 4 * 1 MSS = 4 * 2000 B  = 8000 B

Thanks to @Nilesh Agrawal ji.

Comments

So is it fact that the threshold is always set to half of the receiver window and not wait for it to timeout?

---

chhotu explanation is not correct and many peope upvote it

image source:KuroseRoss Book

---

@Chhotu But sir  the [congestion threshold = min(recv win, cws)/2]  then why are you taking  [recv win/2]  here??

see this → https://web.archive.org/web/20180619020529/http://www.ece.virginia.edu/~mv/edu/ee136/Lectures/congestion-control/tcp-congestion-control.pdf

This is from Forouzan :

The sender has two pieces of information: the receiver-advertised window size and

the congestion window size. The actual size of the window is the minimum of these two.

Actual window size= minimum (rwnd, cwnd)

It sets the value of the threshold to one-half of the current window size.

please help in this! 

---

@Pranavpurkar i believe this is the initial condition. And as and when the algorithm starts, cwnd size would keep changing dynamically.

Please correct me if I'm wrong! 

Answer 3

Packet size (MSS Maximum segment size)= 2000 B

Advertized window size (RWND)= 12000 B

Sender's Current window size (CWND)= 4000 B

CWND = 2 * MSS --- > This means that the sender can send upto 2 packets at this point and it did.

That is why it now recieves 2 Acks of those two packets sent

So it can now increase the CWND by 1 MSS for each packet acknowledged.

So Current Window Size = 4000 + 2* MSS = 8000 THis is the answer.

 

Now it can send upto 4 packets and if it receives 4 Acks for those packets sent then it will increment its window to 12000

 

This link will be of help !!!

http://packetlife.net/blog/2011/jul/5/tcp-slow-start/

Comments

In slow start phase we double the CNWD with each acknowledgement unless there is a timeout or 3 Ack's and once these events occur the slowstart or AI phase starts respectively . So In the question ,

The it is saying slowstart phase so , we need to double the CNWD with each Ack until we reach a threshold which is 12000 in this case , so

4000*2 for 1st Ack and 8000 * 2 for next Ack  since the maximum threshold is 12000 at the end of slow start phase it will be 12,000 (which is asked in question) and hereafter for the next acknowledgements AI phase will start.

Please let me know If I am wrong .

---

great👍

---

Good

---

@Turning Turing  In slow start phase we double the CNWD with each RTT. and we increase CNWD by 1 with each acknowledgement. 

Answer 4

In slow start phase, window size increases exponentially upon receiving 1 ack till threshold and after that collision avoidance phase start where window size is increased 1 mss after every acknowledgement till max window is reached.

Slow start : 1,2 4 ,8... threshold

Collision avoidance: threshold+1, threshold +2.....Max window size

Threshold = max transit window size/2

In given question Max window size is 12000B and therefore

Threshold = 6000

So the sequence of transit will be

1st 2000

2nd 4000 1 ack received

3rd 6000 1ack received

4th 8000

Hence, Answer is 8000 B

Comments

@Prateek K @Kabir5454

Why 1 ack is not received after the 1^st 2000.