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

For these types of questions or in any CN question, even if we assume 1K as 2¹⁰ or 10³(if nothing is mentioned), there wouldn't be any problem I think because because the range of answers will not be too big. And in official answer key they ll provide the range.

---

There is some confusion going over ceil or floor ...
So lets calculate it ..
1KB frame and 2^7.10^3 Bw
so Tt comes out 64 ms  ((2^10.2^3/2^7)*10^-3 sec)

Now for max utilisation we dont want sender to be empty at all if there is bandwidth available then itll trasmit ..
time available after sending first frame .. 2Tp ie 300 ms
so in that time it can transmit 4.68 frame

we're adding 1 cause it have to keep track of the first transmitted frame too cause it's ack isnt received yet .
therefore 5.68 frame are transmitted ..
now think of it  should we waste time by sitting idle and not transmit .68 part of the frame ???

Its waste we can recieve the ack also and by then we'll transmit .68 part of the frame and continue .32 part ie left afterwards.

so that is why we are taking ciel .. therefore 6 seq no at reciever side and 6 at sender side so total 12 .. ie it would require 4 bits  
 

---

this will help 

Answer 1

Answer is 4 bits.

As  we want $100 \%$ efficiency$(\mu),\ \large {w_s}\geq 1+2a$

 $a = \dfrac{\text{propagation time}}{\text{transmission time}}$

$\quad=\dfrac{150  }{1024 \times \dfrac{8}{128}} = \dfrac{150}{64} =  2.34,$

 $\Rightarrow \large {w_s} \geq 1+2a = \lceil  5.6875 \rceil =  6$

Available $\text{seq numbers} \geq \large w_s+w_r$

In Selective Repeat,

$\large w_s=w_r$ (let it be n)

$2\times n=2\times 6=12$

avail $\text{seq numbers}\geq 12$

So, minimum $\text{seq numbers}$ are $12$.

Number of bits for that is $\lceil \log_2 {12} \rceil =4.$

Comments

I’m not sure why people are arguing over 5 here. @Abhrajyoti00 has rightly explained it – we have to use ceil here to guarantee 100% efficiency. If you know how the formula is derived there won’t be this confusion. Meanwhile I should change the $=$ in the answer to $\geq$.

---

@Abhrajyoti00  why we have not taken max window size = 1+4a?

cause RTT will be here = Td + Tp(s->satellite) + Tp(satellite → receiver) +Tp(receiver→ satellite) + Tp(satellite->sender).

---

@Rusty_01 This q is different from the other pyq that you are thinking about. There $2$ ground stations (one sender & one receiver) were connected to the satellite. That’s why we needed $4Tp$.  Here only one station is collected. So sender, itself is the receiver and it’s just two way propagation Tp(s->satellite)+ Tp(satellite->s). So $2Tp$ will suffice. 

Answer 2

Transmission time of a frame = (10^3 * 8 * 10^3)/ (128 * 10^3) = 62.5 ms.

RTT = 150* 2 ms = 300 ms

(One frame transmission time + RTT) is the maximum time that sender can transmit without waitng for acknowledgement.

Here utilization is 100% i.e. efficiency is 1

So in (62.5 +300) ms sender can send atmost 362.5/ 62.5 frame = 5.8 i.e approx 6 frames.

In selective repet, sender window size = receiver window size. So window size = 6 * 2 = 12.

So, 4 bits to represent window.

Comments

Thank you sir for such a simple concept.

---

why the  6*2? explain please. even the sender window size equal to receiver, why a multiplication of 2 needed

---

@PRANAV M Yes,
Sender window Size = 6 frames and also Reciver Window Size = 6 frames too as the technique used is Selective Repeat.
Total Number of frames = 12 
Bit's needed to represent 12 frames = \(\lceil (\log_{2}(12)) \rceil\) = 4.

Answer 3

For selective repeat: size of window( W )  = 2^k-1

(Utilization or Efficiency)_{selective repeat} = $W \div ( 1 + RTT / TD)$

Since utilization is given 100%,

TD = 8 * 10³ / 128 * 10³ 

      = 8 / 128 sec

     = 0.0625 sec

RTT = 2 * PD 

        = 2 * 150 ms = 300 * 10^-3 = 0.3 sec

1 = W / (1 + 0.3 / 0.0625)

W = 5.8 or,

2^k-1 = 5.8

k = 4 only this value satisfies.

Thus the min no. of sequence bits required for 100% utilization is 4.

Answer 4

for 100% utilization sender can keep sending data till it receives an +ve or -ve acknowldegement.

So it can send for 150*2 ms

so total data that can be transmitted = 300*128 = 38400/8 = 4800bytes

4800/1024 = 4.6875 =  5 frames = 3 bits

This is because receiver can demand retransmission of first frame itself.

Comments

$3$ bits for GBN.

For  SR,  $2^{n-1} = 5 frames \implies n = \left \lceil {log(5)} \right \rceil +1 = 4 bits$

---

why it is 128 instead of 128*10^3

Answer 5

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 6

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