The Gateway to Computer Science Excellence

+22 votes

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_________________.

0

@arjun sir

as bandwidth is given and propagation delay is mentioned we can find total capacity of channel by RTT *BANDWIDTH i.e 64 kbps * 40 ms which gives 2560 as total capacity in bits now 2560/8 i.e 320 B for 100 % utilisation so for 50% it should be 160 B!

Why this approach is wrong? What am I missing?

as bandwidth is given and propagation delay is mentioned we can find total capacity of channel by RTT *BANDWIDTH i.e 64 kbps * 40 ms which gives 2560 as total capacity in bits now 2560/8 i.e 320 B for 100 % utilisation so for 50% it should be 160 B!

Why this approach is wrong? What am I missing?

+49 votes

Best answer

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\ ms +\dfrac{ x }{64\ ms}+20\ ms+0$ (as given in question)

$=\left(40 +\dfrac{x}{64}\right)\ 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\ bits$.

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

$x= 2560\ bits=320\ 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\ ms$

$L=2\times 20\ 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\ bits$

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

0

@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 ?

+1

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

+5

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?

+1

@ 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?

+1

@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?

+1

+8 votes

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*}$$

$$\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*}$$

+1 vote

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. **

+2

Actually, this is not ambiguous @Aghori.

Transmission time is always a part or RTT, but sometimes it is too small that it is better to leave it without affecting our answer. in this question https://gateoverflow.in/8056/gate2015-2_8, Transmission time is 1ms which is not negligible and you cant exculde it from your calculation.

0

Yes @reena_kandari it's not ambiguous because efficiency isn't same as link utilization, I will update the answer. Thanks

0

@Aghori, I also see the same example from forouzan. I'm too confused. Can you explain your this line?

"efficiency isn't same as link utilization"

"efficiency isn't same as link utilization"

0

@HemantParihar - Link utilization is simply the average traffic over a particular link expressed as a percentage of the total link capacity whereas link efficiency is the ratio of the time taken to transmit a frame to the total time it takes to transmit and acknowledge the frame or frames.

+1

@Aghori, both are same things

if you are sending $1$ packets of $L$ bits in one $RTT=Tp+2Tt$ (Assuimg $B bps$ bandwidth)

then according to you,

link utilization=$\frac{L}{(Tt+2tp)B}$=$\frac{L/B}{(Tt+2tp)}$=$\frac{Tt}{(Tt+2tp)}$=$\frac{1}{(1+2a)}$ where ${a=Tp/Tt}$

=time taken by sender to send the frame$/RTT$=Link effeciany

if you are sending $1$ packets of $L$ bits in one $RTT=Tp+2Tt$ (Assuimg $B bps$ bandwidth)

then according to you,

link utilization=$\frac{L}{(Tt+2tp)B}$=$\frac{L/B}{(Tt+2tp)}$=$\frac{Tt}{(Tt+2tp)}$=$\frac{1}{(1+2a)}$ where ${a=Tp/Tt}$

=time taken by sender to send the frame$/RTT$=Link effeciany

0

@ 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.

0 votes

** % Link Utilization = T.T/(T.T + 2*P.T)*100**

**For 50% link utilization: 50 = T.T/(T.T + 2*P.T)*100 **

**Therefore the relation is T.T = 2*P.T**

**NOW T.T=FRAME SIZE/BANDWIDTH**

**P.T = 20 ms(given)**

**So frame size = 2* 20 *10^(-3) 64 * 10^3**

**frame size=2560 bits**

**frame size = 2560/8 bytes**

**frame size = 320 bytes(Ans)**

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,370 answers

198,506 comments

105,275 users