# GATE2014-1-28

11.5k 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 ________.

edited
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

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!!

$\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.$

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
8
@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.

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$

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.

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

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}$ ?

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)

Ceil(4.56) = 5

edited
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$.
Sender window size is  e*[1+2a] where e is the efficiency

Divided by 2 as window size of sender + window size of receiver is less then available sequence number

after putting all the values of a = Tp/Tt and e=0.6

we got answer to be log[2e(1+2a)] = 5 as our bits for sequence number

## Related questions

1
15.9k views
Let the size of congestion window of a TCP connection be $32$ KB when a timeout occurs. The round trip time of the connection is $100$ msec and the maximum segment size used is $2$ KB. The time taken (in msec) by the TCP connection to get back to $32$ KB congestion window is _________.
Consider a token ring network with a length of 2 km having 10 stations including a monitoring station. The propagation speed of the signal is $2 \times10^8m/s$ and the token transmission time is ignored. If each station is allowed to hold the token for $2 µsec$, the minimum time for which the monitoring station should wait (in $µsec$) before assuming that the token is lost is _______.
Consider a network connecting two systems located $8000$ $\text{Km}$ apart. The bandwidth of the network is $500 \times 10^6$ $\text{bits}$ per second. The propagation speed of the media is $4 \times 10^6$ $\text{meters}$ per second. It needs to ... full capacity. Assume that processing delays at nodes are negligible. Then, the minimum size in bits of the sequence number field has to be ______.
Consider two processors $P_1$ and $P_2$ executing the same instruction set. Assume that under identical conditions, for the same input, a program running on $P_2$ takes $\text{25%}$ less time but incurs $\text{20%}$ more CPI (clock cycles per instruction) as compared to the program ... $P_1$. If the clock frequency of $P_1$ is $\text{1GHZ}$, then the clock frequency of $P_2$ (in GHz) is ______.