The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+22 votes
6.4k 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 ________.
asked in Computer Networks by Veteran (106k points)
edited by | 6.4k views
+2
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
0

corrected. Registered user 48

i too wasted some time solving wrong question.

4 Answers

+72 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.$
answered by Boss (13.7k 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
+3
@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?
+31 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$ 

answered by Veteran (363k 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.
+2

@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
+4 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 

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

Window size = (Bandwith* RTT)/frame size
0 votes
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$.
answered by Active (2.2k points)
Answer:

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

42,622 questions
48,615 answers
155,895 comments
63,870 users