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

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

How did you come up with the value of Ws= 5.6785 ?

I am getting the tranmission delay as t trans = 1024 / 128 * 10^3 = 8 ms

Given in the question t prop = 150 ms

a = t prop / t trans 150 / 8 = 18.75

ws = 1+2a = 38.5

---

I thav the same doubt as  Sharathkumar Anbu

---

"byte"

---

Oh yeah of course byte has to be considered

---

Correct me if im wrong,

N (window size) <= 1 + 2a, i.e. we need to consider only complete packets that can be sent in that duration.

Hence N = ceil(5.6785) = 5. Also sequence numbers should exceed sender + receiver window size, therefore minimum sequence numbers = 5 + 5 + 1 = 11. Hence we need 4 bits.

---

ceil(5.6785) = 5. Wrong. it is 6

---

End to end and one way propagation delay is same. So thefore we should take 2PT as PT

---

@ryan, To get 100% utilization, the sender will keep on sending frames till he gets the first ack i.e. in the time span of 1RTT+ 1st frame transmission time= 8000/128 + 150 = 212.5ms

Now, by simple division with frame transmission time, we obtain the number of frames as 5.8 which only implies, that the sixth frame has been partially sent and the sending is in progress. Thus 6 frames is the sender's window here

---

@ryan: You are right. On further probing, I realized even if one sends 6 frames in the first instance, he will suffer a delay between receiving an ack for the first frame and sending the seventh frame which in turn will bring the average to 5 frames per window. I don't know how is it handled in reality but for 5 frames the utiization is bound at less than 100%, while for 6 frames sender's state(in which he must move his window and send a frame on receipt of an ack) is volatile, which is not allowed in any turing machine

---

@ Debashish Deka sir i would like ask that N=5.8 (Max window size)..and it cannot be greater than this...so window size N should be 5. (and not 6)

hence sequence numbers=N+N=10 

and bits required=3.3 that we can take as 4.

Please tell me if i am wrong???

---

@gari,yes i agree with you. 5.8 should be approximated to 5.Now maximum Sender widnow=5

So Ceil(Log2(2*5)) is the should be the answer.

---

thanks @ rahul sharma 5 :)

---

Can any one explain me question has metion the Bw = 128 * 10^3 bit /sec but in the solution we consider it only 128 why?

---

@Arjun sir is it 10 or 12

---

Since they are saying about 100 % utilization,

efficiency = 100 %

100% >= w/(1+2a)       a = propagation delay / transmission delay

w <= 1+2a

on putting the value of a, we get

w<=5.68

w=5 packets

Available sequence number >= (w_s + w_r)

For SR ; w_s =w_r

So, 5 + 5 = 10 sequence numbers are required, in order to name them in binary , we need minimum 4 bits

---

if you consider rounding of 5.85 to 6 efficiency will be greater than 100% which is not practically possible therefore we write 100 >= (WS of sender*100)/1+2a

therefore WS of sender <= 1+2a

WS<=5.68

window size cant be fraction therefore WS=5

after that no. of bits = ceil(log(5+5))  =4 bits      since its SR protocol therefore  WS sender= WS reciever

---

I think we should take the floor(5.6875). If we consider ceil(5.6875) then efficiency will be greater than 100%.

---

@rajatshukla2910,

$\text{Available Sequence Number} \geq \text{Sender Window Size + Receiver Window Size}$

$\therefore$ here, we're taking the ceil value, that means available sequence number will be greater than the total of sender & receiver window size. And, that will cause no harm.

---

@Subarna Das 

What if we were asked to find the sender window size?

 

---

@rajatshukla2910,

I think Sender window size should be 6, because we're getting 5.68 frames that could be transferred over the channel to get $100\% $ efficiency, so, we should go for ceil value.

---

@Subarna Das

But if u take the size as 6,  efficiency will be greater than 100%. How can that be possible?. I think it should b 5.

---

What's the difference between windows size and frame size? The frame size given is not required for the solution right?

---

Why the bandwidth is not taken as 128*10^3?

---

Why byte has to be considered?

---

In this question transmission time of acknowledgement is neglected that’s why we have to take one times of propagation delay?

---

No, @Nisha Bharti. It is a formula derived like such:-

Let, transmission time = $Tt$ and Propagation time = $Tp$

Now, Total time = Transmission Time + Routed Time = $Tt+2*Tp$

Now, Efficiency = $Transmission Time/Total Time$ (Because we are taking $Tt$ time to transmit in Total time $\implies$ Efficiency = $Tt/(Tt+2*Tp) = 1/1+2a$ where, $a = Tp/Tt$

Now, for $100\%$ efficiency, we need to utilize the whole Time, via pipelining, i.e. send more packets while one packet is being transmitted. To do this the sender window size must be = $1+(2*Tp/Tt)$ or $1+2a$. 

 

---

oh yes @Abhrajyoti00 actualy i am confused about someone ans

thanku

---

@Abhrajyoti00 how can we find the total no. of the frame? 

---

Use the formula $1+2a$. Because that's the number of frames (filling the entire sender window) you need to send to get 100% efficiency. You'll get 6 after ceiling the value. We need to do ceil because 5.68 can't be the no of frames. If we take 5 frames, the efficiency can't be 100%. Hence we need 6 frames.

---

@Abhrajyoti00 Yes for 100% efficiency frame no.=window size, but when efficiency is not 100% in that case what will be the no. of frame?assume total no. of frame =30 and window size is 4 that means sequence no. is 0,1,2,3 but how can we find total no. of frame?

---

@Nisha Bharti $\text{Available Sequence Number} \geq \text{Sender Window Size + Receiver Window Size}$. Now depending on the protocol, Receiver Window Size will be 1 or N. Then accordingly we will get the total number of frames. Remember:  Frames can have sequence number 0 to a maximum of  $2^{n}-1$.

---

@Abhrajyoti00 i think to finding total no. of frame we have to find window size with their 100% efficiency because without 100% efficiency window can’t cover all frame at 1 time and yes it also depends on the protocol with bandwidth and delay. with sequence no. how can we find total frame? actually sequence no. will be maximum or within range it will depends on window size so i think to finding total frame we have to use with 100% efficiency. correct me if i am wrong.

---

Need correction.  

Ws = 5

---

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.