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

here they said satellite communication means propagation time will become 4 times .

why dont you consider that?

for solving below question they have considered that feature

A 1Mbps satellite link connects two ground stations. The altitude of the satellite is 36,504 km and speed of the signal is 3 ×
108 m/s. What should be the packet size for a channel utilization of 25% for a satellite link using go-back-127 sliding window
proto col? Assume that the acknowledgment packets are negligible in size and that there are no errors during communication?

 

 

why?

---

In the given question satellite is not used for connecting two ground station.. a single station is communicating with satellite only...

So Rtt=2*Tp

.... but in the example you r asking about the satellite is used for connecting two ground station ..therefore Rtt=4*Tp

---

This might be silly but m not getting answer.

step 1: To get 100% efficiency window size must be equal to Tt + 2*Tp.
2: Tt=64msec 2*Tp=300msec thrfre Tt + 2*Tp=364.
3. Ws+Wr<= total sequence numbers available. Not getting the answer.
:(

---

@ tusharp

ur step 1 is wrong, for 100% efficiency, window size will be = 1 + 2* T_p/T_t

---

Divide my equation in step 1 by Tt you will get what I have written.

---

How can we be certain that that only the sender is communicating with the satellite. Didn't get why 4*tp isn't used here.

---

Here it is different than the other previous year gate question.

it is not given that two servers communicating via satellite .

Here communication between satellite and system is given. Therefore 2* Tp is used as RTT.

---

Please tell me.. From which book i need to study.. So i can solve these type of questions.. Thank you

---

@tusharp, you have to divide this total time, by transmission time then you will get the sender window size,

means for 100% efficiency, 1=N* Tt/364

→ 64*N=364

N=364/64 =5.6 that is 6

Seq. no.=2N=12

now log base 2 ceil 12=4 that is the ans

---

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

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

Answer 3

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 4

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.