The Gateway to Computer Science Excellence
+22 votes
8.9k views
Consider a selective repeat sliding window protocol that uses a frame size of $1$ $\text{KB}$ to send data on a $1.5$ $\text{Mbps}$ link with a one-way latency of $50$ $\text{msec}$. To achieve a link utilization of $60\%$, the minimum number of bits required to represent the sequence number field is ________.
in Computer Networks by Veteran (105k points)
edited by | 8.9k views
+4
In question " frame size of 1 Kb"  given why everyone assuming it as 1 KB ?
0
Excerpt from 2014-1 Question Paper
Consider a selective repeat sliding window protocol that uses a frame size of 1 KB to send data on a 1.5 Mbps link with a one-way latency of 50 msec. To achieve a link utilization of 60%, the minimum number of bits required to represent the sequence number field is
+1

corrected. Registered user 48

i too wasted some time solving wrong question.

0

My assumption on reading

to send data on a 1.5 Mbps link with a one-way latency of 50 msec. To achieve a link utilization of 60%.

Bandwidth that can be used = 60% of 1.5Mbps

Instead, efficiency is 60%. How did we interpret this?

0

@Mk Utkarsh True. This question checks patience level if solved from GO pdf!!

4 Answers

+96 votes
Best answer
$\eta_{SR} = \dfrac{N}{1+2a}$

$B = 1.5 \text{ Mbps}$

$T_p = 50 \text{ ms}$

$L = 1 \text{ KB} = 1024 \times 8 \text{ bits}$

$\eta_{SR} = 60\%$

$\therefore 0.6 = \dfrac{N}{1+2a}$

$\implies N = 0.6 (1+2a)$

$a =\dfrac{T_p}{T_t} = \dfrac{T_p}{L} . B = \dfrac{50\times 10^{-3} \times 1.5 \times 10^6}{1024 \times 8} = 9.155$

$\therefore N = 0.6 \times (1 + 2 \times 9.155) = 11.58$

 

$w_s + w_R \leq \text{ASN}$

$\implies 2N \leq \text{ASN}$

$\implies 2\times 11.58 \leq \text{ASN}$

$\implies \text{ASN} \geq \lceil 23.172 \rceil$

$\implies \text {ASN} \geq 24$

$\therefore \text{Minimum number of bits required for sequence number field} = \lceil \log_2 24 \rceil = 5.$
by Boss (13.5k points)
selected by
0
@Vikrant suppose this question is asking in GBN then wil we multiply 2? As i also get  value of N = 11.58  

And I took log of 11.58 which is 4

and also what happen in simple stop wait protocol I think in stop wait answer is 4.. plzz help in this
+6
@aman.anand

In GBN, receiver window size is 1. So the equation will be N+1 <= Available Sequence Numbers
0
why isn't one way latency considered as transmission time+ propagation time?
0
Why latency = propagation time?
0
No, Because in Go back n receiver window size is 1 whereas in SR receiver window size is 2^k-1 where k is the sequence bits. but in
0
What is latency? latency is the delay happening after sending your data to receive its ACK. tp is also same just another way of saying. Latency is normally used in token rings.
+34 votes

A frame is $1\text{ KB}$ and takes $\dfrac{8\times 10^3}{1.5\times 10^6}\ s = 5.33\ ms$
to reach the destination. ( $8$ is used to convert byte to bits)

Adding the propagation delay of $50\ ms,$ the total time will be $50 + 5.33 = 55.33\ ms$

Now, we need the $\text{ACK}$ to reach back also, so the time between a packet is sent
and an $\text{ACK}$ is received $= 55.33 + 50\text{(transmission time of ACK neglected)}$
$= 105.33\ ms$

The channel band width is $1.5\text{ Mbps},$ so in $1\ ms,\ 1.5K$ bits can be transferred
and so in $105.33\ ms,\ 157.995 K$ bits can be transferred.

To, ensure $60\%$ utilization, amount of bits to be transferred in

$1\ ms = 157.995\times 0.6 = 94.797\ Kb =\dfrac{ 94.797}{(8\times 1000)}$ frames

$= 11.849\text{ frames}\approx 12\text{ frames}.$
(we bounded up to ensure at least $60\%$ utilization)

So, we need a minimum window size of $12.$ 

Now, in selective repeat protocol, the window size must be less than half the
sequence number space.
http://stackoverflow.com/questions/3999065/why-is-window-size-less-than-or -equal-to-half-the-sequence-number-in-sr-protocol

So, this means sequence number space must be larger than $2\times 12 = 24.$
To have a sequence number space of $24,$ sequence bits must be at least $\log_{2} 24 = 5$ 

by Veteran (425k points)
0

"The channel band width is 1.5 Mbps, so in 1 ms, 1.5 K bits can be transferred and so in 105.33 ms, 157.995 K bits can be transferred."

sir here 157.995 k bits are the maximum bits which we can transfer right ?? as we have discussed here https://gateoverflow.in/1267/gate2007_69?show=42108#c42108
 

and if i will divide 157.995k by frame size i.e, 157.995k / 8 * k then i will get number of frames when channel utilization is maximum ? right 

0
yes that is correct- corresponding to 100% utilization.
+4

sir why have you taken propogation delay as 50 ms......in forouzan book,it was given latency = propogation time +transmission time.why it is not propogation time + trnasmission time =50 ms

0
There is no "propagation" there rt? Delay is for the packet to reach the sender. I took propagation delay same as propagation time.
0
yes sir...
0
Sir how in 5.33 ms packet can reach at destination. I think this is the transmission time.

Please clear me.
+3

@Arjun Sir,

I could not understand what do u mean by "There is no "propagation" there rt?"

How packets are moving between source and destination without propagation.. Please clarify. What I am missing here

0
@Arjun Sir, plz reply i am also having the same doubt, why u are adding transmission time with one way latency given, as it implicitly include transmission time as given in forouzan book and image is shared above?
+1

Yog If there was no propagation delay then the frame would have taken 5.33ms(because of the bandwidth).
but there is a delay of 50 ms in the propagation hence 5.33+50 = 55.33ms.

In telecommunications a link is a communications channel that connects two or more devices(wiki)
You guys are confusing bandwidth with transmission. 
Transmission time is limited with the transmitting device(node) and not the link connecting them

0
@Arjun Sir .... Is it the correct thinking about this question

TT - Transmission time , PT - Propagation time

Since link utilization is given as 60% then

$\implies$ $\frac{60}{100} = \frac{TT}{TT + 2PT}$

$\implies$$6TT + 12PT = 10TT$

$\implies$$TT = 3PT$  this becomes transmision time according to given data  

Now total time $= TT + 2PT$

                           $= 3PT + 2PT$

                           $= 5PT$

             $\implies$     $5*50 ms = 250 ms$

Bits transmitted in 250 ms = $\frac{250 * 10^{-3} * 1.5 * 10 ^ {6} }{1024 * 8}$

                                                =  45.77

                                                =  46

Number of sequence bits  = log(46)  = 6

Hance 6 bits should be used.

 

Please correct me sir if I am thinking wrong
0
sir i feel this is correct but then how do i find logic to correct answer. please guide if u understood it
0

@Arjun sir

why you 11.849 as 12 but not 11..by considering 12 efficency will be greater than  60 % but we want 60%

0
@Arjun sir, as frame size is of  1KB so why it is  $8 * 10^{3}$ and not $8* 2^{10}$ ?
+5 votes

Transmission delay = Frame Size/bandwidth
                   = (1*8*10^3)/(1.5 * 10^6)=5.33ms
Propagation delay = 50ms
Efficiency = Window Size/(1+2a) = .6

a = Propagation delay/Transmission delay
So, window size = 11.856(approx)
min sequence number = 2*window size = 23.712
bits required in Min sequence number = log2(23.712)
Answer is 4.56

Ceil(4.56) = 5 

by Loyal (9.7k points)
edited by
0
Why we have not calculated window size  using

Window size = (Bandwith* RTT)/frame size
+1 vote
Bandwidth delay product = Bandwidth x RTT
$\rightarrow 1.5\times 10^6 \times 2\times 50\times 10^{-3}=1.5\times 10^5$ bits.

$Utilization=\frac{N\times packet\ size}{Bandwidth\ delay\ product}$

$\rightarrow 0.6=\frac{N\times 8\times 1000}{1.5\times 10^5}\rightarrow6\times 15=N\times 8$
$\rightarrow N=\frac{45}{4}=11.25 \approx12.$

In selective repeat, $N\leq\frac{2^n}{2}\rightarrow12\leq\frac{2^n}{2}\rightarrow2^n\geq24\rightarrow n\geq log_2(24)$ or $n \geq 5$.
by Active (2.5k points)

Related questions

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
50,644 questions
56,523 answers
195,602 comments
101,286 users