GATE CSE 2014 | Set 1 | Question: 28

Question

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

Comments

I didn't calculate further and just wrote 12 as answer... it was asking sequence bits....😭

---

I made a really silly mistake.
I calculated N = 11.84 and rounded it down to 11, which gave me min ASN = 22.
Even though the final answer might look the same, this is conceptually wrong.
If N = 11.84, then to maintain at least 60% efficiency, we should round it up to 12. (see this)

 

---

this will help

Answer 1

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

Comments

Why latency = propagation time?

---

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

---

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.

Answer 2

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$ 

Comments

then why in this question we are taking 1KB = 8 * 10^3 bits

I know this doesn’t affect answer in this question but still…..

---

Sometimes people assume that to make the calculation simpler but best practice is to use

Data size 1KB = 1024 B

Bandwidth 1MBPS=10^6 byte/sec .

In gate paper this are given mostly. If not given then using this standard will not give wrong answer.

---

Okay Thanks :)

Answer 3

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 = log₂(23.712)
Answer is 4.56

Ceil(4.56) = 5 

Comments

Why we have not calculated window size  using

Window size = (Bandwith* RTT)/frame size

---

hsd9116

acc. to this  formula ans. is 6.

---

Nice one

Answer 4

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

Comments

floor (log 24 )

Answer 5

For 100% efficiency we--------- sent (1+2a) Frames
For 60% efficiency we----------- sent ? Frames
= 60/100(1+2a) , where a = Propogation delay(Tp)/Transmission delay(Tt)
= 11.85
We are using the Selective repeat sliding window protocol. Therefore, Sender window size(Ws) = Reciever window size(Wr).
We know, Available sequences number >= Ws+Wr.
Available sequences number = 11.85 +11.85 = 23.70
Therefore, sequence number bits required = ceil(Log 23.70) = 4 bits.

Comments

ceil(Log 23.70) is 5 bits.

Answer 6

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