GATE CSE 2016 Set 2 | Question: 55

Question

Consider a $128 \times 10^3$ bits/second satellite communication link with one way propagation delay of $150$ milliseconds. Selective retransmission (repeat) protocol is used on this link to send data with a frame size of $1$ kilobyte. Neglect the transmission time of acknowledgement. The minimum number of bits required for the sequence number field to achieve $100 \%$ utilization is ________.

Comments

Alternative way to solve these kind of questions:

In transmission time + 2*propagation time max no of packets that can be sended in this question(100% efficiency) from sender to receiver is 5.8. So in case of selective repeat if no of bits in sequence no. is m then max window size can be 2^(m-1). In case of GBN max window size can be 2^(m)-1. So sender is sending 5.8 frames. Means  2^(m-1)=5.8

or         m-1=ceil(log(5.8))  (here log is base 2).

or         m-1=3

or         m=4.

Hence no of bits in seq no is 4.

---

GO to the Root of Concept: Video Explanation with timestamp: Sliding Window PYQs| GATE 2009 Q57, 58| 2006 Q46, 64| 2003, 2014, 2015, 2004, 2016, 2007| With NOTES

---

$BW=128\times10^3 \;bits/sec$
$L=1KB=1\times10^3\times8\;bits$
$T_p=150\;msec$
$\eta=100 \%$

$T_t=\frac{L}{BW}=\frac{1\times10^3\times8}{128\times10^3 }=0.0625\;sec=62.5\;msec$
$a = \frac{T_p}{T_t}=\frac{150}{62.5}=2.4$

$\eta=\frac{N}{1+2a}=1 =>\frac{N}{1+2\times2.4}=1=>N=5.8$

$\therefore W_s=W_r=6$
$Available\;Sequence\;Number \geq12$
Min No. of bits required $4\;bits$

Answer 1

Bandwidth (B) = 128 × 10^3 bits/ second , Tp =  150 milliseconds , L = 1 KB = 1 * 8 * 2^10 bits

Tt = L / B ⇒  64 msec

So, a = 150 msec / 64 msec = 2.343

η = N  /  1 + 2 *a  ( N = window size )

 for 100% η   ,   N = 1 + 2*a = 1 + 2 * Tp / Tt  = 5.686

In SR , Available sequence number = Ws + Wr (where Ws = Wr ) = 5.686 + 5.686 = 11.375

  Sequence bits =  [ log2 (11.375) ] = 4

Answer 2

Let the window size be N, so from the equation Wsender + Wreceiver <= Available Sequence No.

Available Sequence No. = 2N

Given, Utilization=1 

or Efficiency = 1

=> N/(1+2a) = 1

=> N = 1+2a

a = Tp / Tt

Tp = 150 / 1000 = 0.15 sec

Tt = L / B = 1024*8 / 128 * 10^3 = 0.064 sec 

So, a = 0.15 / 0.064 = 2.34375

Thus, N = 1+2a = 5.6875

Therefore, Bits required for Sequence No. = log2(N + N) = log2(11.375) = 4 bits