The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+24 votes
3.3k views

The distance between two stations $M$ and $N$ is $L$ kilometers. All frames are $K$ bits long. The propagation delay per kilometer is $t$ seconds. Let $R$ bits/second be the channel capacity. Assuming that the processing delay is negligible, the $\text{minimum}$ number of bits for the sequence number field in a frame for maximum utilization, when the $\text{sliding window protocol}$ is used, is:

  1. $\lceil \log_2 \frac{2LtR +2K}{K} \rceil$

  2. $\lceil \log_2 \frac{2LtR}{K} \rceil$

  3. $\lceil \log_2 \frac{2LtR +K}{K} \rceil$

  4. $\lceil \log_2 \frac{2LtR +2K}{2K} \rceil$

asked in Computer Networks by Veteran (69k points) | 3.3k views

6 Answers

+32 votes
Best answer

Answer: C

We can send $\dfrac{\text{RTT}}{\text{Transmission Time}}$ number of packets

for maximum utilization of the channel, as in this time, we get the first $\text{ACK}$
back and till that time, we can continue sending packets.

So, $\dfrac{\text{Transmission Time + 2$\times $Propagation Time}}{\text{Transmission Time}}$

number of packets should be sent.

Therefore, bits required for the sequence number field:

$\left \lceil \log_2 \left(\frac{\dfrac{K}{R}+\large 2L_t}{\dfrac{K}{R}}\right) \right\rceil = \left\lceil \log_2\left(\dfrac{K+2L_tR}{{K}}\right) \right\rceil$

Edit : here it is asked for general sliding window protocol not GBN nor SR .

In general sliding window protocol:

Sequence number bit $=\log \text{(sender window size)}$

answered by Veteran (36.4k points)
edited by

#...

@Arjun sir

while finding no. of bits shouldn't we consider  ws+wr<=sequence no.And take wr as 1(atleast and not 0).

With this
(K+2LtRK) /K  +1 = (2K+2LtRK)/K

Answer is A

and not C

Please clear this doubt
I have to revisit this. Will surely do it.
When we are talking about only sliding window protocol, we only care about sender's window.
If it is explicitely mentioned about GBN or SR then only focus on reciever's window.
(Sliding window protocol is a theoretical concept, implemented using either GBN or SR protocol)

So C is the ans.

One of the Previous Comment by @Arjun Sir
"Not really, unless asked we should always do the genral sliding window protocol and not GBN or SR."

I guess this statement is correct. Sliding window protocol is a theoretical concept, practically implemented using GBN or SR.   

But while we talk only about sliding window protocol, we are only talking about the activity of sender's window.

If it is specified about GBN or SR protocol, then only we will focus on receiver's window. 

@Ahwan again can you explain the General sliding window protocol..

I mean to say in this you are considering only senders window and not the receivers window..something like that.
@Arjun Sir,answer should a here,Please re check once?

rahul sharma 5 answer should be here is c only as in the question it is given that 

the minimum number of bits for the sequence number field in a frame for maximum utilization, when the sliding window protocol is used

 comparing GBN and SR, GBN require less no of bits as compared to SR and give more window size, so here we should use GBN, and acc to GBN 

Reciever window = 1

Sender windows = 2LtR/k

and no of bits required is = log(recievier window + sender window)

so it is log(1+2LtR/k) = log{(K + 2LtR)/K}.

No this is not correct.

Sender window size = 2LtR/k+1.On that you should apply your formulae.See answer below by amar
I think the word "Channel Capacity" shouldn't be used here. Since R bits/sec is given the correct term should be Bandwidth instead of Channel Capacity.
As we know      channel capacity = 2 * Tp * BW for full duplex
&                         channel capacity =  Tp * BW for half duplex
+52 votes

for maximum utilization $\eta = 1$,

$\begin{align*} \eta &= SWS \times \frac{\text{Transmission Time}}{\text{Transmission Time + 2$\times$Propagation Time}} \\ \\ 1 &= SWS \times \frac{\text{Transmission Time}}{\text{Transmission Time + 2$\times$Propagation Time}} \\ \end{align*}$

so, $\dfrac{\text{Transmission Time + 2$\times$Propagation Time}}{\text{Transmission Time}} =\text{SWS}$

gives the number of packets that are sent. It means that it is the Sender's Window Size.

But we also know that,

$\text{sequence numbers} \ \geq \text{ SWS } + \text{ RWS}$
$\qquad\text{available}$                                                           

so, to get the minimum number of bits needed to represent the sequence numbers
we should consider what protocols are in use.

if GBN ARQ: 

$\begin{align*} \substack{\large\text{# bits required to rep.} \\ \large\text{ sequence numbers}}
&= \lceil \log_2{(SWS + RWS)} \rceil \\ &= \left \lceil \log_2{\left(\frac{\frac{K}{R} + 2L_t}
{\dfrac{K}{R}}+1 \right)} \right \rceil \\ &= \left \lceil \log_2{\left(\frac{2K + 2L_tR}{K}\right)}
 \right \rceil \end{align*}$

if Selective Repeat ARQ :

$\begin{align*} \substack{\large\text{# bits required to rep.} \\ \large\text{ sequence numbers}}
&= \lceil \log_2{(2\times SWS)} \rceil \\ &= \left \lceil \log_2{\left(2\times \frac{\frac{K}{R} + 2L_t}{\frac{K}{R}}\right)}
\right \rceil \\ &= \left \lceil \log_2{\left(\frac{2K + 4L_tR}{K}\right)} \right \rceil \end{align*}$

answered by Veteran (31k points)
edited by
What should be the answer... I am getting A.
I am also getting this answer because we must consider the window size of the receiver too(1 in this case). But everywhere it is given C.

What is the correct answer?
I am also getting this but i dont know why is C.)
When we are talking about only sliding window protocol, we only care about sender's window.
If it is explicitely mentioned about GBN or SR then only focus on reciever's window.
(Sliding window protocol is a theoretical concept, implemented using either GBN or SR protocol)

So C is the ans.
Maximum Sender window is = Number of frames in 2*BD+1.

Now using above if you find maximum sender window.You will get the same answer as given.C should not be correct option.Because if question is saying maximum utilization then there is always 1 frame we need to add to 2*BD
+3 votes
Answer : (C)

Ws(window size of sender)=1+2a  where a=Tp/Tt

 minimum sequence number possible= 1+2a

min. num of bit for sequence number = ⌈log(1+2a)⌉ ************************** Equation 1

Tp/Tt=Lt/(K/R)

1+2a=(K+2LtR)/K

put value of 1+2a in eq 1

answer is C.
answered by Active (1.5k points)
@bikram sir, this method is correct, isn't it?
+1 vote
Check this...

Utilization = amount of data send / amount of data can be send

Utilization = (window size *frame size) / ((transmission time+RTT)*channel capacity)

Utilization = 1 when maximum

 window size *frame size = (transmission time+RTT)*channel capacity

W * K =  ( K/R + 2Lt ) * R

W = (K + 2LtR) / K

let  sequence number  field in frame contains n bits

Then  2^n = w

n = log w

n= log ( (K + 2LtR) / K)
answered by (85 points)
Here W is the sender window size, so you're not accounting for receiver window size, which can be 1 for GBN and W for SR. You should account for receiver window size as well for getting minimum number of bits for sequence number.
0 votes
Bandwidth R bps , Frame size = K bits , PT = t sec,/ kilometer, distance L kilometer. So total PT ( not RTT) = L*t sec .Processing delay =0.Assuming W is window size

Now, it says that We need to maximize utilization for sliding window protocol.

Maximum utilization if=> useful time/ total time =1 .

it is possible when ,useful time = Total time.

Useful time= W * {K/R } sec

Total time = K/R + 2* L*t sec

Now  =>  (W * {K/R } ) / ( K/R + 2* L*t ) = 1

W * {K/R } = K/R + 2* L*t

W = K + 2LTR / K

Suppose W= 2n, where n = number of bits in sequence number

2n​ ​= K + 2LTR / K

n= log((K+2LTR)/K)
answered by Junior (935 points)
i am nt getting ur total time calculation ... how hav u done it ??
–1 vote
Total time required for  K bit delivery = K/ R + 2* RTT = K/R+ 2* ( L* t)

                                                     = K/R+ 2Lt

optimal window size = 1+(2 * BW* prop delay)/Frame size = 1+ (2*R*Lt /K)

                              = (K+2RLt)/K

 For maximum utilization window size should be 2^n-1 = (K + 2RLt)/K

                                                                         2^n = (2K +2RLt)/K

                                                                            n = log (2K+2RLt)/K

                                                                        Answer option A
answered by (9 points)
optimal window size = 1+(2 * BW* prop delay)/Frame size

Why 2*BW?
(2L KM) * (t sec / KM) * (R bits / sec) = 2LtR bits.. => 2LtR bits / K bit per frame = (2LtR / K) frame => log2(2LtR / K) bits for sequence number...

therefore option (B)
That 2  came from considering propogation delay two times ...

Ie. Rtt = transimission time + 2*propogation dealy..


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,687 questions
40,231 answers
114,269 comments
38,800 users