# GATE2007-69

7.1k 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$

3

Can anybody answer, when to use capacity mentioned as capacity and not as bandwidth??

Ps: Knowing that would we have easily solved this question!

0
See according to option dude. If none matches with capacity then it's definitely bandwidth. I don't think they would put both options with ambiguous terminologies

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 2Lt}{\dfrac{K}{R}}\right) \right\rceil = \left\lceil \log_2\left(\dfrac{K+2LtR}{{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)}$

edited
0
a is RTT rt?
1
Here, a = Propagation Time/Transmission Time.
(Transmission Time + 2*Propagation Time) is the RTT.
Basically we can send (RTT/Transmission Time) number of packets for maximum utilisation of the channel.
Modified the answer for more clarity.
0
here propogation time is = d/v = L/t only right or is it only t secs  ?. If propogation time is only t secs then now is 2 * L * t. how ?. please help.
0
propagation time is given per kilometer. So, for 2L kilometers (to and fro) total delay will be 2Lt.
0

cc

1
hi you have taken "Basically we can send (RTT/Transmission Time) number of packets for maximum utilisation of the channel." how ?... needs more clarification ? :/
2
RTT is the time interval after which the ACK arrives. When ACK comes back, new packets can be sent (window slides). So, for maximum utilization we just need to ensure the channel is full until ACK arrives.
6

@arjun sir , Is this (above)  solution correct ? I get more clarity in the solution given by @ . If this(above) soloution is correct why didn't he take ASN > SWS +RWS   and calculate the number of bits ?

1
written things seem correct except the ASN part

in answer log is taken for the packets send by the sender what about the sequence number used by the receiver.
1
Why have you not considered reciever window size of 1 then the answer becomes A
0
This is wrong at som many levels, don't know who selected this as the answer. Clearly, depending on the protocol used, the answer must have 2K+2Ltr in numerator for GBN and 2K+4Ltr for SR. This makes A the correct choice
0
@Arjun sir, the analysis given by Amar Vasisth is more clear and to the point.. please reconsider the answer selection
3
Not really, unless asked we should always do the genral sliding window protocol and not GBN or SR.
1
What is this "general" sliding window protocol. Justify yourself. Lets say (K+2Ltr)/K evaluates to 4. By your logic we will use 2 sequence numbers(xx) and have a sliding window of size 4(00,01,10,11). Can you show one protocol in which there will be no ambiguity. In other words, define general sliding window protocol. In GBN, I will use 3 sequence nos. (xxx) selectively to include only 5 of the 8 combinations and have sliding window of size 4 with 1 sequence number to resolve any ambiguity.
0

### #...

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

and not C

0
I have to revisit this. Will surely do it.
14
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.
5

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.

0
@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.
0
1

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

0
No this is not correct.

Sender window size = 2LtR/k+1.On that you should apply your formulae.See answer below by amar
3
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
0
This is what I hate about out question papers. They use ambiguous terminologies.
0
I am not getting sender window size. How the sender window size is calculated?
Ws= 1+2Tp/Tt
Tp=t (given)
Tt=L/Bandwidth
Tt=L * 2t /R
0
Thanks @subhanshu even I interpreted it same way as you mentioned your comment made me sure that I was thinking in right way!!
1

Let there be m bits in sequence number.

We have 2$^{m}$ $\geq$ W$_{s}$ + W$_{r}$

Case 1) Sliding window protocol:

Here, W$_{s}$ = 1+2a; W$_{r}$=0

(we do not have any buffer at the receiver end. The receiver simply sends a cumulative acknowledgement.)

2$^{m}$ $\geq$ W$_{s}$ + W$_{r}$

2$^{m}$ $\geq$ 1+2a

m $\geq$ $\left \lceil log (1+2a) \right \rceil$

Case 2) Go back n protocol:

Here, W$_{s}$ = 1+2a; W$_{r}$=1

2$^{m}$ $\geq$ W$_{s}$ + W$_{r}$

2$^{m}$ $\geq$ 1+2a + 1

m $\geq$ $\left \lceil log (2+2a) \right \rceil$

Case 3) Selective repeat:

Here, W$_{s}$ = W$_{r}$ = 1+2a;

2$^{m}$ $\geq$ W$_{s}$ + W$_{r}$

2$^{m}$ $\geq$ 1+2a + 1 + 2a

m $\geq$ $\left \lceil log (2+4a) \right \rceil$

Someone please let me know if this is right. :)

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$\timesPropagation 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{available sequence numbers} \ \geq \text{ SWS + RWS}$

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} + 2Lt} {\dfrac{K}{R}}+1 \right)} \right \rceil \\ &= \left \lceil \log_2{\left(\frac{2K + 2LtR}{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} + 2Lt}{\frac{K}{R}}\right)} \right \rceil \\ &= \left \lceil \log_2{\left(\frac{2K + 4LtR}{K}\right)} \right \rceil \end{align*}

edited
0
What should be the answer... I am getting A.
1
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.

0
I am also getting this but i dont know why is C.)
4
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.
0
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
0
Sequence number bit =log(sender window size)

because Question mention minimum number of bits for the sequence number but we can take only SWS not RWS WHY ?

Because of we can only transmit in GBN So, take only SWS not include RWS.

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

0
@bikram sir, this method is correct, isn't it?
0
Is Tp not L/t.....i mean Tp=distance/velocity......!!
0

Given t is not velocity.

Delay per km is given as t sec. So total delay in L km is L * t sec.

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)
0
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.
1 vote

Ans: C

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)
0
i am nt getting ur total time calculation ... how hav u done it ??

• Here, "capacity" means "bandwidth". Look at the given units.
• "minimum number of bits for the sequence number field" using sliding windows, would be for GBN and not SR, obviously.
• 100% utilisation means The size of the sender window = 1 + 2a.

Hence, Option C

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

0
optimal window size = 1+(2 * BW* prop delay)/Frame size

Why 2*BW?
–1
(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)
0
That 2  came from considering propogation delay two times ...

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

## Related questions

1
9.5k views
The message $11001001$ is to be transmitted using the CRC polynomial $x^3 +1$ to protect it from errors. The message that should be transmitted is: $11001001000$ $11001001011$ $11001010$ $110010010011$
There are $n$ stations in slotted LAN. Each station attempts to transmit with a probability $p$ in each time slot. What is the probability that ONLY one station transmits in a given time slot? $np(1-p)^{n-1}$ $(1-p)^{n-1}$ $p(1-p)^{n-1}$ $1-(1-p)^{n-1}$
Match the following: ... $\text{P - 1, Q - 4, R - 2, S - 5}$ $\text{P - 2, Q - 4, R - 1, S - 3}$