GATE CSE 2017 Set 1 | Question: 45

Question

The values of parameters for the Stop-and-Wait ARQ protocol are as given below:

• Bit rate of the transmission channel $= 1$ Mbps.
• Propagation delay from sender to receiver $= 0.75$ ms.
• Time to process a frame $= 0.25$ ms.
• Number of bytes in the information frame $= 1980$.
• Number of bytes in the acknowledge frame $= 20$.
• Number of overhead bytes in the information frame $= 20$.

Assume there are no transmission errors. Then, the transmission efficiency (expressed in percentage) of the Stop-and-Wait ARQ protocol for the above parameters is _____________ (correct to $2$ decimal places).

Comments

frame processing time means time elapsed to process a packet (removing header +copy data+ forming its acknowledgment ) at receiver side. so consider frame processing time for both end.

---

updated link: https://nptel.ac.in/content/storage2/courses/Webcoursecontents/IIT%20Kharagpur/Computer%20networks/pdf/M3L3.pdf

---

GO to the Root of Concept: Video Explanation with timestamp More Questions on Stop Wait Protocol | GATE PYQs 2016, 2017, 2006, 2023 MIT, Berkeley | With NOTES

Answer 1

Efficieny is usually calculated as, $\dfrac{\text{InfoFrame Transmit Time}}{\text{TotalTime}}$

Efficiency $=\frac{\text{InfoFrame Transmit Time}}{\text{InfoFrame Transmit Time
+InfoFrame Process Time+2$\times$ Prop Delay+AckFrame Transmit Time+AckFrame Process Time}}$

Reference to calculate efficiency formula:

• http://nptel.ac.in/courses/106106091/pdf/Lecture13_StopAndWaitAnalysis.pdf
• http://spinlab.wpi.edu/courses/ece230x/lec14-15.pdf

From the question it is not very clear wether frame processing time is mentioned about $\text{InfoFrame or AckFrame or Combined}.$ It is also explicitly not mentioned wether to consider Frame Processing time for $\text{ACK}$ or not. Thus, following are the different inferences that could be made from the question -

1. As Size of InfoFrame $(1980-2000 \;\text{Bytes})$ is very large as compared to AckFrame $(20\;\text{Bytes})$ one could assume the given processing time is for InfoFrame and processing time for $\text{AckFrame}$ is neglible. The processing time does depend on size of frame for various parameters one of them is checksum calculation.
   Check the below reference for more details -
    http://rp-www.cs.usyd.edu.au/~suparerk/Research/Doc/Stop-and-Wait_Simulation.pdf
2. It is also mentioned in the question that there are no trasmission errors. One can also think as an hint that since frames are successfully transmitted there is no need for $\text{ACK}$ processing at sender Side
3. Considering frame processing time given is combined both $\text{ACK+Info Frame}$
4. Considering frame processing time individually and which is the Ans in Official key ( 86.5 - 87.5 ) 

The below answers could be due to cases $1,2,3 -$
No. of Bytes in the Information frame  $= 1980\;\text{Bytes}$
(Not very clear from question whether it implies total bytes or data bytes )

No of OverHead Bytes $=20\; \text{Bytes}$

Assuming they have explicitly mentioned Overhead bytes -

Total Frame Size $=\text{No of Bytes in the Information frame + No of OverHead Bytes = 2000 B}$

InfoTransmission Time $=\dfrac{\text{InfoFrame Size}}{\text{Bandwidth}}$

$=\dfrac{2000\times 8}{1\times 10^6} = 16\;\text{ms}$

AckTransmissionTime $=\dfrac{20 \times 8}{1 \times 10^6}=0.16\;\text{ms}$

Efficiency $=\dfrac{16}{16+ 2\times 0.75 + 0.25 + 0.16}$

                 $=89.34\%$  ( After round-off )

Assuming bytes in information includes Overhead bytes -

InfoFrameTranmission Time $=15.84$

Efficiency = 89.23 % 

Range could be 87.5 - 89.34

Reference to the similar questions:

• https://gateoverflow.in/43981/isro-2013-41
• https://gateoverflow.in/39696/gate-2016-1-55

More Efficiency Concept Reference:

• http://nptel.ac.in/courses/Webcourse-contents/IIT%20Kharagpur/Computer%20networks/pdf/M3L3.pdf

Comments

@Bikram Sir / @Arjun Sir / @Debashish / @Habib could you please check this?

---

when you calculate efficiency, 

we need to consider two way  processing delay ,  one from sender side another from receiver side .

so total time to process frames = 0.25(at receiver for information frame) + 0.25(at sender for acknowledge frame) = 0.5 msec.

then you get 87.5% which match with gate key . 

---

@Bikram Sir is it worth challenging the official key on the basis of argument that usually the AckProcesssing time is negligible?

---

This question seems ambiguous, so better challenge ..

---

@yash any reference where it is ignored?

---

@Arjun Sir, Sorry I do not have standard references for putting any weight in my argument.Since in standard books they explicitly mention this line 'Assuming ACK processing time neglible..' But it is not the case here.

However intutively the frame size of Sender is 2000 B and frame size of Ack is only 20 B.Should not the ACK processing time be neglible?How can dataframe and ACK processing time be same with huge difference in size?

Also in previous year questions they used to be very precise and specifc in which they mention everything explicitly.But in this question during the exam it depends upon the thought process you had in your mind.

They have not mentioned clearly wether frame processing time is for information or ACK frame or both.

 Looking at the size of the frame one can also assume that the ACK processing time will be neglible. 

Here is though a vague reference -

https://books.google.co.in/books?id=iUI8BAAAQBAJ

in which assumption is made that processing/transmission time is neglibile since ACK/NACK frame size is small.

My request is can they not include this in range as well?

---

@yash

what about this line " Assume there are no transmission errors. " ?

if there is no errors all frames are correctly acknowledged then why consider processing delay at sender end ?

what do you think ?

---

@Bikram Sir, that is a another very Valid point. Although I took the processing time neglible based on size but mentioning explicitly that there are no transmission error can also be thought as another hint that AckProcessing time can be ignored. Although No Transmission error does not imply that frames will not be lost.

---

actually this question is ambiguous, i hope now you understand why ambiguous ..

so it is better to challenge the answer key to increase the range from 86.5 to 89.5 , i think :)

---

Thanks a lot @Bikram Sir for help and guidance and points you mentioned. I will Surely challenge this.

@Arjun Sir could you pls share your thoughts on the two points mentioned above regarding size and no transmission error?

---

 I think when processing delay is very small  it gets ignored, but here this is not the case here. Moreover, once a frame is fully processed (processing time =time spent for error checking + deciding the next node link depending on the destination address+looking at headers +.... so on )it is ready for transmission. So we have to consider the processing delay separately  for an individual frame , as well as for the ack frame  .

@Yash, can you please give a reference where it is mentioned less sized packet will have less processing delay?

From Wiki :"In a network based on packet switching, processing delay is the time it takes routers to process the packet header. Processing delay is a key component in network delay." 

---

@Shreya Roy please check the below references. Both of them includes that point-

http://spinlab.wpi.edu/courses/ece230x/lec14-15.pdf

https://books.google.co.in/books?id=iUI8BAAAQBAJ

Also the point you mentioned is about frame processing at the intermediate routers. The frame processing at the Sender and Reciever are different. My point is 87.X is not wrong ans but the based on the inferences you make 89.X can also be the ans and should be included in the range.

Another reference - http://rp-www.cs.usyd.edu.au/~suparerk/Research/Doc/Stop-and-Wait_Simulation.pdf

Please check the last page. Lot of details in it about processing time..

However, if timing is taking into account, the longer the packet size, the longer time needed to use for processing time, especially checksum algorithm. It results in longer delay between source and destination then.

---

I think this question was ambiguous and we should challenge it. I would be happy to contribute if someone could properly frame the issue for challenging along with proper explanation.

---

"Also the point you mentioned is about frame processing at the intermediate routers. The frame processing at the Sender and Receiver are different. " Please tell the difference ..

 According to the pdf you have shared :"Total time includes
 Time to transmit frame from sender to receiver
 Propagation time from sender to receiver
 Time to process frame at receiver
 Time to transmit ACK from receiver to sender
 Time to process ACK at sender" -lec14-15.pdf ,page 5

---

@Shreya Exactly they have mentioned explicitly about the processing of frame at Sender and Reciever.

And regarding the point, I meant some action that you mentioned wont be there for example deciding next hop link based on destination wont be there. Processing includes actions like looking at headers and checksum calculation to detect errors etc will be there which you mentioned. And Hence processing time is usually small for AckFrame as compared to InfoFrame.

@Shreya kindly note that I dont diasgree with the official key - 87.5 can be the ans. But the points mentioned above and looking at the ambiguity of the question Do you diasgree that ans can also be 89.X and range 87.5-89.34 would be more appropriate?

---

"some action that you mentioned wont be there for example deciding next hop link based on destination wont be there."Why deciding next hop will not be there?

@Yash ack will come from the destination host to the source host so the same routing will be followed for ack packet too.

and all we have assumed without considering intermediate nodes(since they have not mentioned anything like this).else would have considered intermediate node delays too.

---

@yash yes the question has 2 ambiguities. Worth debating. And a good chance they extend answer from 86.5-90.

---

@yash

1.

Number of bytes in the information frame = 1980.

Number of overhead bytes IN the information frame = 20.

I think this clearly means that information frame includes overhead i.e. Data = 1960 && Overhead = 20

---

2.  I think you are considering Transmission error as error while transmitting a frame whereas Transmission error means error that might occur while transmission as well as propagation of frame due to various reasons such as noise, signal distortion, jitter, etc Reference .

• "No Transmission error does not imply that frames will not be lost." 
  When do we say frames are lost? There are two main reasons: 1. Change of destination addresse due to transmission errors and 2.Timeout(TTL) due to congestion. Now both are not the point of discussion for obvious reasons. In short, No transmission error does imply that frames will not be lost.
• It is true that processing time depends on frame size and main parameter is calculation of CRC(as Stop-and-Wait ARQ protocol is DL layer's flow control mechanism). Now again it is clearly stated that there are no transmission errors then why do we need to calculate CRC?

---

3. What does process time mean in this scenario?

 As we don't need to calculate CRC now, processing time narrows down to some basic things such as checking sequence number, upper layer protocol, etc which can be done in constant time.

---

4.

Time to process A frame = 0.25 ms.

I think this means that time to process an individual frame is 0.25. Here we are talking about two types of frames Information frame and Acknowledge frame. So I think we should take process time for both the frames separately. 

---

These are my views. Let me know if I'm missing something.

---

@Kantikumar

When question says "no errors" it means no errors happened in the given scenario- not that the working scheme is decided assuming there will be no error. i.e., CRC checking etc. is still going on here, just that the result is always "no error".

---

@Kantikumar exactly, I dont disagree with any of your points you mentioned above. This is exactly my point, the question has certain ambiguity and each student in the exam must have made his own inference of the question in the limited time and my argument is to consider a valid range including all certain possibilities which could be the solution. Below are my thoughts -

1. Just as you thought that there are no tranmissions errors hence no need of CRC calculation one can also interpret as No need of AckProcessing at the Sender Side since no transmission errors. If No Transmission error implies frame will not be lost then it becomes more stronger argument that frame will be recieved correctly by the Reciever so why care about the processing time for ACK?

2. Just as you thought individual frame processing time is given but the question never mentions explicitly wether its talking about individual Info/Ack frame. Since nothing is mentioned one can also think it is combinely talking about a frame processing time Info+Ack. Do you think there could have been more clarity which frame they are referring to or mentioning processing time for each Infoframe/AcKFrame is 0.25 ?

3. Is there any standard reference where the frame processing time is consdiered same for Ack and Information frame? In all the standard links which I have mentioned above I observed each one considers separate mentioning of the parameter Time to process AckFrame and Time to process InfoFrame.Only for Propogation delay they use 2*Tp. Being a huge difference in the size of frame is it wrong to infer that there cannot be the same processing time practically ?

4. Apart from CRC computaion there are various other parameters involved like  time for header analysis, buffer analysis, decoding parameters which are likely to be more time consuming for an InfoFrame than AckFrame as AckFrames are ideally supposed to have simple parameters whereas more and complex parameters for InfoFrame is possible comparatively.

5. The range they have given is 86.5 - 87.5 but considering all the different combinations the range varies from 87.11 - 89.34. Those who have taken into consideration as individual frame processing time I agree their answer must be held valid but other interpretations of the question could also be made as defintely some clairty is missing from the question. 

Again the points I mentioned are just my thoughts and interpretations of the question. Kindly, Let me know if any mistakes or invalid points raised.

---

As @Arjun sir said "no errors" does not mean that there will be no calculation of CRC, etc. If all the functionalities are present then I suppose they could have been more precise with process time. With such a huge difference in size, process time should be different.

Also, I think, not processing Ack at receiver is not an option because in general any hop is not meant to handle only one connection, there might be multiple connections at the hop. In this case receiver has to process the Ack frame.

---

@kantikumar

 

this question obviously ambiguous, let them challenge it, i know you are correct and also i know what arguments yash put is also very correct ..  there is a high chance for this question to increase the range !!

---

image is from nptel lecture of iit khragpur

http://nptel.ac.in/courses/Webcourse-contents/IIT%20Kharagpur/Computer%20networks/pdf/M3L3.pdf

i have got answer as 88.44 

and was expecting to get 2 marks for it 

please tell me exactly what i have to write to challange this question please mention in comment

please mention @arjunsir

or anybody else this question is very important for me

also processing time for 1980 byte frame is 0.25 ms and also for 20 byte frame how is this possible ??

one can easily assume it for only information frame 

also in above image processing time is included only once for processing one frame.

---

@arjunsir please mention exactly what we should write to challenge this as they clearly said if they don't understand our claim then they will simply discard our claim.

---

@Rahul

This question ambiguous so it is  worth to  challenge the key .

What you write to them :

There are 4 different answers possible :

case 1) considering no overhead in ACK and taking frame processing time on sender side on ACK arrival. ans 88.10%

case 2) considering overhead in ACK and taking frame processing time on sender side on ACK arrival. ans 87.35%

case 3) considering no overhead in ACK and NOT taking frame processing time on sender side on ACK arrival. ans 89.34%

case 4) considering overhead in ACK and NOT taking frame processing time on sender side on ACK arrival. ans 88.54%

Answer range is given 86.5 to 87.5 in which only case 2 lies but questions directly states overhead in information frame which makes it ambiguous.

If we consider no processing time at sender ( as mention in the question very clearly that there is no transmission error hence no process time at sender side )  then it comes 89.34% which is case 3.

And you got 88.44 % which is almost same as Case 4 . 

so you can see any case can be correct. Range should be adjusted based on ambiguity.

given range is 86.5% to 87.5% we need to increase it , our demanded range should be 86.5 % to 89.5% .

hope it clears the cloud .

---

@Bikram Sir, Thank you for your efforts and help. Could you please also suggest should we also include the reference links as I have included above ( one link to support the claim that the processing time depends upon size of frame and the other just to refer the efficiency formula ) ?

---

yes, reference links along with above image which i upload all should be included ..

---

@yash also take into account this point in these years

https://gateoverflow.in/43470/gate2009-58?show=43470#q43470

https://gateoverflow.in/8363/gate2015-1_53?show=8363#q8363

 they clearly mention to consider process time at sender side but this year it is missing,, so add this 2 qstns in the list to point it out !

---

AND WE WON .

---

sir, is answer range increased??

---

@rahul singhal

yes, the range is increased as i comment above

 86.5% to 87.5% was previous key   , now after new key published the range  become 86.5 % to 89.5% .

---

@bikram THanks... ur answer helped me a lot.. and links too...from where do u get to know these helpfull links? ..i dont get these

---

the question should clearly mention that overhead bytes IN ADDITION TO THE DATA BYTES they gave the question as OVERHEAD BYTES IN THE DATA AS 20 means anyone thinks that it is included in the data and hence if we do the same as above we get 0.884 and one more thing is efficiency when calculated we have to calculate the transmission time for only useful bytes right ? means out of 1980 we numerator should have transmission time for only 1960 bytes and transmission time for overhead is at denominator

---

Acknowledgement transmission time : (20 * 8 * 10^3) / 10^6 = 0.16 ms

factor 8 is missing.

---

@yg92 information frame does not contaion overhead so we have to add overhaed .so your second answer seems to be wrong

---

Here frame size is 200 bytes which 16000 bits hence transmission time is 16ms out of which 20bytes which is 160 bits are overhead so while calculating useful time shouldn't we consider only 15840bits as 160 bits are overhead and useful time will be 15.84ms

 

Hence efficiency = 15.84/(16+0.25+0.16+0.75+0.75) =.8844x100 = 88.44%

---

@Bikram Is it not given that overhead is only for Information Frame? So, why are you considering case 2 and case 4? 

---

Is it necessary  to write range in NAT question  in gate?

How to determine  the range?

---

what was the answer in the official key?

---

As per GATE 2017 official key answer was $86.5$ to $89.5$

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

https://web.archive.org/web/20201229173406if_/https://www.gate.iitg.ac.in/2017answers/CS1.pdf#page=2

---

@Arjun @gatecse sir

Official answer is 86.5 to 89.5 (https://gate.iitk.ac.in/doc/papers/2017/cs_2017.pdf) 

see question no. 45 of set 1.

not 86.5 to 87.5(as mention in the above answer).

Answer 2

Transmission efficiency = $\frac{Transmission-time-for-useful-data}{Total-time}$

Useful data = Information frame - Overhead = 1980 - 20 = 1960 B.

Transmission time for useful data = $\frac{1960*8}{10^{6}}$ = 15.68 msec.

Total transmission time for Information frame(with overhead) = $\frac{1980*8}{10^{6}}$ = 15.84 msec.

Total transmission time for Acknowledge frame = $\frac{20*8}{10^{6}}$ = 0.16 msec.

RTT = 2 * Propagation delay = 2 * 0.75 = 1.5 msec.

Time to process frames = 0.25(at receiver for information frame) + 0.25(at sender for acknowledge frame) = 0.5 msec.

$\therefore$ Total time = 15.84 + 0.16 + 1.5 + 0.5 = 18 msec.

$\therefore$ Transmission efficiency = $\frac{15.68}{18}$ = 0.8711 = 87.11%

$\therefore$ 87.11 should be answer.

Comments

HRK they had asked to round-off. SO should be 89.34%

---

@Sudeep Yes, I had edited it with 0.5 msec but someone again edited my answer. With 0.5 I'm getting 87.11%.

---

Why are we not considering ack frame with info frame?

Answer 3

Time to transmit (Overhead+Data)=(1980*8)/10⁶ =15840  micro.sec

Time to transmit (Data)=(1960*8)/10⁶ =15680  micro.sec

Time to transmit (Ack)=(20*8)/10⁶ =160  micro.sec

One way Processing Delay=250 micro.sec  ,Two way=500   micro sec

One way Propagation Delay=750 micro.sec ,Two way=1500   micro sec

Efficiency=(Time to send Data)/(Total Time)=(15680/(15840+160+500+1500))=15680/18000=0.8711=87.11%

https://www.eecis.udel.edu/~cshen/450419/notes/reliable.pdf

Comments

@arjun sir.. do we take the entire frame into consideration while calculating transmission efficiency for stop and wait or we consider only its useful data part?

Answer 4

solution........