GATE CSE 2015 | Set 2 | Question: 34

Question

Assume that the bandwidth for a $\text{TCP}$ connection  is $1048560$ bits/sec. Let $\alpha$ be the value of RTT in milliseconds (rounded off to the nearest integer) after which the $\text{TCP}$ window scale option is needed. Let $\beta$ be the maximum possible window size with window scale option. Then the values of $\alpha$ and $\beta$ are 

• A. $63$ milliseconds, $65535$ $\times $2$^{14}$
• B. $63$ milliseconds, $65535$ $\times $2$^{16}$
• C. $500$ milliseconds, $65535$ $\times $2$^{14}$
• D. $500$ milliseconds, $65535$ $\times $2$^{16}$

Comments

Reference : https://en.wikipedia.org/wiki/Bandwidth-delay_product#:~:text=In%20data%20communications,detection%20(RED).

Bandwidth delay Product ==> Maximum amount of unacknowledged data that can exist in the transmission path between a sender and receiver at any single moment...

==> From this can we infer Bandwidth-delay Product <= maximum buffer size

==> MAximum buffer size can be receiver window size that can be  (window size in header x 2^ scaling factor )

==> Bandwidth -delay product <= window size in header x 2^ scaling factor ( used when window scale needed)

Important Line of this Question 

α be the value of RTT in milliseconds (rounded off to the nearest integer) after which the TCP window scale option is needed.

Means ,

A standard TCP header has only 16 bits for the Window Size field. Without any window scale option, the maximum unacknowledged data TCP can advertise is $2^{16} - 1 = 65,535 \text{ bytes}$.

• If $\text{BDP} \le 65,535 \text{ bytes}$, normal TCP is sufficient.

• The moment $\text{BDP} > 65,535 \text{ bytes}$, standard TCP becomes the bottleneck. This is the exact point after which the Window Scale Option is needed.

Solution of Part a) :

Given Bandwidth R

$R = 1,048,560 \text{ bits/sec} = \frac{1,048,560}{8} \text{ bytes/sec} = 131,070 \text{ bytes/sec}$

Maximum unscaled TCP window size ( W_unscaled) = $ 2^{16} - 1 = 65,535 \text{ bytes}$

$\text{BDP} = \text{Bandwidth (bytes/sec)} \times \text{RTT}$

$131,070 \times \alpha = 65,535$

$\alpha = \frac{65,535}{131,070} = 0.5 \text{ seconds} = \mathbf{500 \text{ ms}}$

what does it means α = 500 ms 

==> If $\text{RTT} \le 500 \text{ ms}$, $\text{BDP} \le 65,535 \text{ bytes}$ $\rightarrow$ Standard TCP works fine.

==> If $\text{RTT} > 500 \text{ ms}$, $\text{BDP} > 65,535 \text{ bytes}$ $\rightarrow$ Window Scale Option is needed.

Solution of Part b) :

The question asks for $\beta$, which is the maximum possible window size with the window scale option enabled.

The 16-bit window field allows a base value of up to $65,535$.

The maximum allowed bit-shift scale factor is  = 14.

$$\beta = 65,535 \times 2^{14}$$

---

Some extra Note

References : you can refer Forozoun ,Kurose & Ross, W. Richard Stevens' TCP/IP Illustrated, and RFC 7323

Receiver Buffer ($\text{RcvBuffer}$): The physical memory allocated in kernel space to store incoming data before the application reads it.

Receiver Window ($rwnd$): The currently available free space inside that buffer, advertised back to the sender in the TCP header.

$$rwnd = \text{RcvBuffer} - (\text{LastByteRcvd} - \text{LastByteRead})$$

$$\text{Max Advertised } rwnd \le \text{Total Allocated } \text{RcvBuffer}$$

==> Buffer size sets the upper bound for the receiver window size. The window size can be smaller than or equal to the buffer size, but never larger.

$$\text{BDP} \le \text{Effective } rwnd \le \text{Max Allocated } \text{RcvBuffer}$$

$$\text{Bandwidth} \times \text{RTT} \le (\text{Window Field in Header}) \times 2^{\text{Scale Factor}} \le \text{RcvBuffer}$$

---

• This question mentions: Let alpha be the value of RTT in ms, this is a confusing sentence, since it can be thought that it is taking alpha to be the actual RTT.

 

• But the actual RTT is larger than this alpha, that is the entire reason why we are even considering increasing the window size using options.

 

• So this alpha is nothing but the time after which we will feel the need to increase the window size, since we have a lot of waiting time left in the RTT.

Answer 1

In TCP when the bandwidth-delay product increases beyond $64\;\textsf{K}$ receiver window scaling is needed. 

The bandwidth-delay product is the maximum amount of data on the network circuit at any time and is measured as RTT * Bandwidth. This is not the time for sending data rather just the time for sending data without acknowledgement. 

So, here, we have bandwidth delay product $= (1048560 / 8) B \ast \alpha  = 64\;\textsf{K}$

$\alpha = (64\;\textsf{K} \ast 8 ) / 1048560 = 0.5\;\text{s} = 500$ milliseconds. 

---

When window scaling happens, a $14$ bit shift count is used in $\text{TCP}$ header. So, the maximum possible window size gets increased from $2^{16}-1$ to $(2^{16}-1) \ast 2^{14}$ or from $65535$ to $65535 \ast 2^{14}$

http://en.wikipedia.org/wiki/TCP_window_scale_option

Comments

@Vgone  if you look in TCP header fomat  ...window size field has  16 bits hence maximum number represented  by it is 2^16-1=65535 …..maximum buffer size(maximum amount of data on network i.e. bandwidth delay product) = 2^16 bytes=64KB

---

@Digvijay Pandey  Section 2.3 in https://tools.ietf.org/html/rfc1323#page-10 clearly explains why 14 bits shift count is used in TCP header.

TCP determines if a data segment is "old" or "new" by testing whether its sequence number is within 2**31 bytes of the left edge of the window, and if it is not, discarding the data as "old". To insure that new data is never mistakenly considered old and vice- versa, the left edge of the sender's window has to be at most 2**31 away from the right edge of the receiver's window. Similarly with the sender's right edge and receiver's left edge. Since the right and left edges of either the sender's or receiver's window differ by the window size, and since the sender and receiver windows can be out of phase by at most the window size, the above constraints imply that 2 * the max window size must be less than 2**31, or max window. 

 

Since the max window is 2**S (where S is the scaling shift count) times at most 2**16 - 1 (the maximum unscaled window), the maximum window is guaranteed to be < 2*30 if S <= 14. Thus, the shift count must be limited to 14 (which allows windows of 2**30 = 1 Gbyte). If a Window Scale option is received with a shift.cnt value exceeding 14, the TCP should log the error but use 14 instead of the specified value.

---

Please see my answer on this question, I am sure it will clear all your doubts:

https://gateoverflow.in/8154/gate-cse-2015-set-2-question-34?show=540181#a540181

Answer 2

The TCP window scale option is an option to increase the receiver window size allowed in Transmission Control Protocol above its former maximum value of 65,535 bytes.

65,535 bytes = 64KB = $2^{16}$ B

The scaling option allows us to increase the window size from 64KB to 1 GB!

 

• When is scaling used?

When the bandwidth-delay product exceeds the value of 64K or $2^{16}$, we use scaling.
Bandwidth must be in bytes/sec and delay (RTT) must be in ms.

 

• What happens when we scale?

Window size increases from 64KB to 1GB, ie, from $2^{16}$B to $2^{30}$B

---

---

 

Now, coming to the question:

Calculating α

131070 * RTT = $2^{16}$

=> 131070 * RTT = 65536

=> RTT = 500 ms

 

Calculating β

Window size would be increased from  $2^{16}$B to $2^{30}$B

i.e. from 65536 to 65536 * $2^{14}$B

 

Option C

Comments

@JashanArora

How did you get 64K as Bandwidth delay? If it is Standard value, then I think Bandwidth is a concern. 

---

I think, the maximum window size of receiver is $2^{16}$, so if the bandwidth is maximum $2^{16}$ then receiver will be filled in one go/ one second. If bandwidth is more than $2^{16}$ we can transfer more than the size that a receiver can advertise. So we need to add extra bits so that sender can show more buffer size that it can receive. And the extra bits are available in the option field of the tcp header.

Please correct me if I'm wrong somewhere.

Answer 3

answer is C.
because TCP window scale option is needed when size increases more than 65535 B. it means alpha (RTT) should be the time taken to send 65535 B to the receiver. 

Time to send 65535 B = 65535 * 8/1048560 *1000 = 500 ms. 

so alpha will be 500.

maximum window size with window scale option is possible in TCP is 1073725440 B which is 65535*2^14 .

http://en.wikipedia.org/wiki/TCP_window_scale_option

Comments

PLEASE CHECK CALCULATION ONCE:
because TCP window scale option is needed when size increases more than 65535 B. it means alpha (RTT) should be the time taken to send 65535 B to the receiver. 

Time to send 65535 B = 65535 * 8/1048560 *1000 = 500 ms. 

IT SHOULD BE: // Time to send 65535 B = 65535 * 8*1000/1048560 = 500 ms. 

so alpha will be 500.

maximum window size with window scale option is possible in TCP is 1073725440 B which is 65535*2^14 .

http://en.wikipedia.org/wiki/TCP_window_scale_option

Answer 4

Lets talk about concept first..

Basically We are not utilizing the given bandwidth at its fullest. Sticking to the question, it causes due to the delay caused in sending the data.

(You can consider the example of satellite link , It causes much delay for acknowledgement to arrived after sending data equal to current window size)

One of the solution is we can consider upgrading window size that will pack the data , utilizing maximum of the given bandwidth.

The units we consider for data is in Bytes and delay in "ms"

Lets have a look at our Question.

Given,

B = (1048560/8) B/s

RTT ( alpha ) = X ms ( say)

Current ( default) window size, RWIN = 65535 B

( RWIN = Reciver window )

Using Bandwidth * Delay product ,

B * X = 65535 ,

X = 500 ms.

To use the given Bandwidth  to ita fullest , we can scale our window upto 1GB ( fixed standard)

i.e with scaling factor of 2^14 B

(i.e Shifting 14 bits to left )

So, scaled window size becomes,

65535 * 2^ 14.

(2^16 * 2^ 14 = 2^30 , i.e 1GB )

 

 

https://www.speedguide.net/faq/what-is-the-bandwidth-delay-product-185

 

https://networklessons.com/cisco/ccnp-route/bandwidth-delay-product/

Answer 5

{Given:}

Bandwidth (BW):
    \[
    \text{BW} = 1048560 \, \text{bits/sec} = 2^{20} \, \text{bits/sec} = 2^{17} \, \text{bytes/sec} = 2^{17} \cdot 10^{-3} \, \text{bytes/msec}
    \]
     \( \alpha \): The value of RTT (Round Trip Time) in milliseconds after which the TCP Window Scaling option becomes necessary.
 

The TCP Window Scaling option is required when:
\[
n \cdot \text{Transmission Time} < \text{RTT}
\]
where \( n \cdot L \) represents the window size. Rewriting this condition:
\[
\frac{\text{Window Size}}{\text{BW}} < \text{RTT}
\]

{Without scaling:} The maximum TCP window size is \( 2^{16} - 1 \, \text{bytes} \). Therefore:
\[
\frac{2^{16} - 1}{2^{17} \cdot 10^{-3}} < \text{RTT}
\]

Simplifying:
\[
\text{RTT} > \frac{2^{16} - 1}{2^{17} \cdot 10^{-3}} = 499.99243 \, \text{msec}
\]

Rounding to the nearest decimal:
\[
\text{RTT} > 500 \, \text{msec}
\]

so after 500 msec we need scaling option

 

{With scaling:} The maximum window size after enabling window scaling is:
\[
\text{Max Window Size (with scaling)} ( \beta )= (2^{16} - 1) \cdot 2^{14}
\]
so the answer is option C

 

 

Answer 6

The answer is (C). Now lets deconstruct this weirdly looking question........................
Firstly, calculating the value of $\beta$ (the maximum possible window size with window scale option) is straightforward 

---

As defined in the TCP header's Options field, the window scale shift count has a maximum limit of 14.
Therefore, the window size can be scaled up by a maximum factor of $2^{14}$.

We know from the TCP header that the maximum unscaled window size is $(2^{16} - 1) = 65535$ bytes.

Through the TCP Window Scale Option, this can be multiplied by a shift count. Since the maximum allowed shift count in the options field is 14, our maximum scaling factor is $2^{14}$.

Therefore, the absolute maximum window size($\beta$) becomes:

$$\text{Max Window} = 65535 \times 2^{14} \text{ bytes}$$

---

Now, coming to the $\alpha$, it's the value of RTT in milliseconds (rounded off to the nearest integer) after which the TCP window scale option is needed, it simply means that- 

"Which Threshold Value ($\alpha$)  ​​​the RTT should cross, After which we will be scaling up the window to achieve maximum efficiency"

See here we have Bandwidth = $1048560\text{ bps}$.

Before scaling up we need to reach max. window size, which is $(2^{16} - 1)\text{ bytes} = 65535\text{ Bytes}$.

Now, suppose we have this much amount of data inside our window, that we are about to transmitt.

$\therefore$ The $T_d$ (Transmission Time for the whole window)

        $(T_d)_w \Rightarrow \frac{8 \times 65535 \text{ bits}}{1048560 \text{ b/s}} \Rightarrow (0.5) \text{ sec.}$

• $t = 0 \longrightarrow$ transmission started

• $t = 0.5 \longrightarrow$ transmission complete

  

• RTT is the time in which — (we send the packets + we receive ack for all)

Now, if we are completing our sending process by $0.5\text{s}$ and the $RTT \le 0.5\text{ sec.}$, it means till we send our last packet, we already have received some ack and now the window can slide and we can keep sending data

                                                                   [so the host is never idle in this case]

---

But But But - - -

if the [RTT > 0.5s] — here the sender has to wait for some time before receiving all acks -

Suppose, $RTT = 0.8\text{ s}$.

$\therefore$ user is finished sending all packets by $0.5\text{ s}$

but he will receive all acks (pending) by $0.8\text{ s}$.

$\therefore$ He will have to wait for $0.3\text{s}$ without sending any data

This is the idle time we are talking about and to encounter this we actually scale-up and send a larger window.

---

So  if $\alpha$ (the threshold value of this bottleneck RTT) = 0.5 s or 500 ms, this is where we are breakeven and we are not idle.
 

Now if RTT value goes beyond this $\alpha$ 
                      $\Downarrow$
Then after sending the whole window the host will surely become idle
                      $\Downarrow$
Then we will be needing the TCP window scale option 
                      $\Downarrow$
So that we can enlarge the window inorder to not let the host become idle
                      $\Downarrow$
This increases efficiency and maximizes our goal
 

---

Now, let's relate this to Bandwidth delay product [BDP] = $BW \times RTT$
{This is the max. amount of unacknowledged data that can be put on the link at a time$\longrightarrow$ and still have $100\%$ efficiency. (no idle time)

Now if, $RTT = 0.5\text{s}$

Bandwidth = 1048560 bps.

$BDP = \frac{1048560}{8} \text{ bytes/s} \times 0.5\text{s}$

$= \frac{1048560}{16} = 65535\text{ B}$

This means that if and only if the RTT = 0.5s. Then we can put $65535\text{ B}$ on the link

                                    $\downarrow$

So our window size becomes $65535\text{ B}$ and we get no idle time.

---

But, if $(RTT > 0.5)$ Then $(BDP > 65535\text{ B})$ Then,

we need a larger window size to reduce idle time

                       $\downarrow$

This we can achieve only by [scaling up].

---

so the conclusion here comes out to be:

$RTT > \alpha = 0.5\text{s}$ Then, you need to put more bytes on the link, increase the sender window size in order to compensate for that idle time where you would be waiting for ack.

Please put an upvote if you are satisfied by the answer 😀