The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+21 votes
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 (99.8k points)
edited by | 5.8k views
In question " frame size of 1 Kb"  given why everyone assuming it as 1 KB ?

3 Answers

+67 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.5k points)
selected by
@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

In GBN, receiver window size is 1. So the equation will be N+1 <= Available Sequence Numbers
@ Vikrant Singh

Since the sender window Was has to be an integer

Hence to be precise our N should be the floor of 11.58 which will be 11.

In SR-.  Ws=Wr=11

Therefore available sequence number >=Ws+Wr(11+11=22)

Now bits required will be ceil of log 22 .Which will be 5
+26 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. -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 (355k points)

"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

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 

yes that is correct- corresponding to 100% utilization.

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

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

Please clear me.

@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

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

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

@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
+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.3k points)
edited by
Why we have not calculated window size  using

Window size = (Bandwith* RTT)/frame size

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

38,050 questions
45,543 answers
48,879 users