GATE CSE 2015 Set 1 | Question: 53

Question

Suppose that the stop-and-wait protocol is used on a link with a bit rate of $64$ $\text{kilobits}$ per second and $20$ $\text{milliseconds}$ propagation delay. Assume that the transmission time for the acknowledgment and the processing time at nodes are negligible. Then the minimum frame size in bytes to achieve a link utilization of at least $50$ $\text{%}$ is_________________.

Comments

That is not right. @Raj

Efficiency = etta(n)

Link utilization = etta * Bandwidth

 

---

Was the guy who made the question was high on weed, or is there some concept behind the 160 in the official answer. Anyone know?

---

haha

Answer 1

Link Utilization $=\dfrac{\text{Amount of data sent}}{\text{Max. amount of data that could be sent}}$

Let $x$ be the frame size in bits.

In stop-and-wait protocol, once a frame is sent, next frame won't be sent until ACK is received.

Time for this,

RTT $=\text{Propagation delay for frame + Transmission time for frame}$
$\qquad\text{+ Propagation delay for ACK + Transmission time for ACK}$

$= 20\ \text{ms} +\dfrac{ x }{64\ \text{ms}}+20\ \text{ms} + 0$ (as given in question)

$=\left(40 +\dfrac{x}{64}\right)\ \text{ms}$.

Amount of data sent during RTT $= x$

Max. amount of data that could be sent $ = \left(40 +\dfrac{x}{64}\right)\times 64=2560+x\ \text{bits}$.

So, link utilization,$0.5 = \dfrac{x}{(2560 + x)}$

$x= 2560\ \text{bits} = 320\ \text{bytes}$.

Alternative Approach ,

Link utilization or efficiency of stop and wait protocol is , 

efficiency $=\dfrac{T_x}{(T_x + 2T_p)}=\dfrac{1}{\left(1+2\left(\dfrac{T_p}{T_x}\right)\right)}=\dfrac{1}{(1 +2a)},$ 

where , Transmission time $=T_x=\dfrac{\text{packet size}}{\text{bandwidth}}=\dfrac{L}{B}$

Propagation time$=T_p=\dfrac{\text{distance}}{\text{speed}}=\dfrac{d}{v},$ and
$a=\dfrac{\text{Propagation time}}{\text{Transmission time}}=\dfrac{T_p}{T_x},$

Now for $50\%$ efficiency ,

efficiency $=\dfrac{1}{(1+2a)}$

$50\%=\dfrac{1}{(1+2a)}$

$\dfrac{1}{2}=\dfrac{1}{(1 +2a)}$

$2=(1+2a)$ 

$2-1=2a$

$1=2\left(\dfrac{T_p}{T_x}\right)$

$T_x =2\times T_p$

$\dfrac{L}{B}=2\times 20\ \text{ms}$ 

$L=2\times 20\ \text{ms} \times B=2\times 20\times 10^{-3}\times 64\text{ k bits}$

$  =2\times 20\times 10^{-3}\times 64\times 10^3\ \text{bits}$

$L=40\times 64\ \text{bits} = 40\times \dfrac{64}{8}\ \text{bytes} = 40\times 8\ \text{bytes} = 320\text{ bytes (answer)}$

Comments

gate answer keys are out and the ans to this question theyh have given is 160 :-/ how come ppl?

---

but this ans seems to be correct.also my  marks reduced to 2.66.why it is wrong ?

---

@Arjun Sir if the transmission time for the acknowledgement was not negligible in the question then how many frames should we have taken for the acknowledgement ?

---

An ACK is too small than a frame. In the worst case it would be a frame -happens during piggybacking also.

---

thanks :)

---

bit rate of 64 kilobits per second should mean it 64*1024 bits per seconds since we are talking in terms of digital data transfer speed. rather than 34kbps bandwidth which is in terms of analog so K converts to 1000 in this case.

i had learnt about this long back in nptel video so maybe i might be wrong.please tell me diffrence between bandwidth and bitrate?

---

@ arjun sir, sometimes in RTT they just consider 2*Tp time and if we solve by that approach we get answer as 160. which one should be followed in gate?

---

@Arjun  Sir, If I calculate Frame size by formula: Transmission time >= 2*Propagation Time.

The answer still comes out to be 320bytes. And this is for 100% utilization rt ?

So what Gate must have considered is for 50%, the frame size should be 320/2 = 160 bytes.

Was this the approach for the answer?

---

I have seen Examples in Fourozan. Only 2*Tp used there. Sir, @Arjun what should be the choice? -_-

---

nothing is given about transmission time of sender, then we can not assume it to be $0$, correct answer should be $320B$

---

Thank you, great answer . Good to know the first approach

---

thanks

---

As per GATE 2015 official key answer is $160$.

If above link doesn’t work use it’s archive

https://web.archive.org/web/20201105191513if_/http://www.gate.iitg.ac.in/2015answers/CS_S05.pdf#page=13

---

Just a request @Arjun sir @GateOverflow team, make sure when you are selecting an answer as best, add the GATE official key answer, if the answer comes out to be different.

People are moving ahead with the thought of the best answer was the same as the original key.

---

was answer changed or given bonus or
60 was the final answer?

---

@JAINchiNMay Don’t think answer debate option was there during GATE 2015. May be this question was a motivation for adding that :)

 

---

That’s a relief :)

Answer 2

for a stop and wait ARQ we send only a single packet at once.

$$\begin{align*} \eta &= \frac{TT}{TT+2\times PT} \\ \frac{50}{100}&= \frac{f/64k}{f/64k+2\times 20ms}\\ \frac{f}{64}&=40\\ f &= 2560bits\\ &= 2560/8\\ &= 320Bytes \end{align*}$$

Comments

160 was in key and I guess ACE had given some formula like that. But AFAIK that is wrong..

---

Why they have given wrong answer?  @arjun sir

Answer 3

let x be Bandwidth delay product = $2*T_{propagation}*BW$

$\Rightarrow$ Bandwidth delay product = $2*20*10^{-3}*64*10^{3}$ = $2560 bits$

Now,Let y be the length of packet.

$\frac{y}{x} >= \frac{1}{2}$

$\Rightarrow$ $y >= \frac{2560}{8*2}$Bytes

Therefore length of packet should be atleast $160 bytes$.

We end up with a wrong answer if include Transmission delay in RTT! But Forouzan has not included Transmission delay in his examples. Moreover if you don't include Transmission delay in RTT you will come up with 16 as an answer for the question in the following link which is wrong.  (Same year question). This is ambiguity.

https://gateoverflow.in/8056/gate2015-2_8

Comments

@ Aghori as per your given definition and the way  @reena_kandari has derived LU=1/(1+2a), we can say that it is link efficiency too. As both giving same result. Than how are they different? plz clear

@reena_kandari  so for this question, if we follow Arjun Sir approach than correct ans is 320 B since Tt for sending frame isn't negligible and we have to include this in RTT? please correct me.

---

This is the right way to get the answer of this question..:)

---

What is the difference between link utilization and throughput?

Answer 4

Link Utilization (efficiency) = {Throughput/Bandwidth} or {usefull time/ total time}

here link utilization is 50% i.e   ½  given in question

usefull time is tf(transmission delay) and total time is (tf(transmission delay )+2tp(round trip time)).

½ = tf/(tf + 2tp)

on evaluation above we get 

tf +2tp = 2tf

tf = 2tp   , and we know that tf = length / bandwidth,

length/bandwidth = 2tp

length = 2tp * Bandwidth

length = 2 * 20 ms * 64kilobits persec

length = 2560 bits

length = 2560/8 = 320 bytes.