Unit home

help3002

Lecture recordings
via LMS

Schedule

Unit outline

Resources

Textbooks

Extra reading

Look after yourself!

Labsheet 2 - sample solutions and discussion

4. [1-2 hours, HARDER] 🌶 🌶
   Q2 presented a complete stop-and-wait protocol which used acknowledgements to report the successful arrival of data frames. If a corrupted frame arrived, the receiver would simply ignore it and the sender's timeout mechanism would cause retransmission of the data frame.
   This protocol, although robust, introduces some inefficiency because the sender is not directly (or quickly) informed about a corrupt data frame arriving at the receiver. The sender actually only infers the data frame corruption after a timeout occurs. The use of an additional negative-acknowledgement frame will reduce this inefficiency.
   Modify a copy of the provided stop-and-wait protocol to also use negative-acknowledgements. Have the receiver reply with a negative-acknowledgement when a corrupt frame arrives.

   ---

   What are negative acknowledgments?

   Like (positive) acknowledgments, negative acknowledgments are a type of control frame between neighbouring (directly connected) Data Link Layers. A negative acknowledgment may be sent by a node receiving a corrupted frame, informing the sending side that a problem has been detected, and the sender may wish to do something about it - typically to retransmit any data frame "involved" in the error.
   As we know, errors can typically be one of two forms, either a data frame is corrupted, or it is lost entirely. Corrupted data frames can be detected at the receiver because their calculated checksum value is incorrect. Lost data frames can also be detected at the receiver when a frame other that the one expected by the receiver arrives before the expected frame (the data frames arrive out of order). In both cases, the receiver could choose to send a negative acknowledgment to the sender to indicate that it has detected a (possible) problem.

   Why?

   Our primary goal is to transmit as much information (messages) as possible in a fixed time. Any method which results in each message reaching its destination in a reduced time helps to meet this goal. If we need to transmit more control frames per true message to help this process, then this may not really matter provided that, in doing so, we don't consume much additional bandwidth. We would thus like to maximize messages/second rather than minimizing total traffic volume. If our additional control frames mean (as they will) that more frames are transmitted, that is justified if we get our messages through quicker.
   By sending negative acknowledgments, the receiver is informing the sender (hopefully, quickly) that something appears wrong, and the sender can react to this information quicker than having to wait for (the same?) information via a timeout. If the receiver's negative acknowledgments get back to the sender before a timeout happens (and the sender acts appropriately) we have sped up our protocols.

   How?

   Sending a negative acknowledgment when a problem is detected is the easy part. The challenge comes when a negative acknowledgment is received - what should we do with this? When a corrupt frame arrives, encouraging us to send a NACK, we must keep in mind that the frame may have originally been DATA, or an ACK, or (now) even a NACK. We can't tell because the header's FRAMEKIND may have been corrupted, turning one frame kind into another, or even into something meaningless. Moreover, other header fields may have been corrupted, so we can't send a NACK saying, for example, "I received a corrupt DATA frame with sequence number 1", because we don't know if the framekind or sequence number (or both) were corrupted.
   What should the receiver of a NACK do? The naive response is to retransmit the last DATA frame, suspecting that that was the frame that was corrupted. But think about this carefully - there are some circumstances when just retransmitting the last DATA is wasteful (it will be unwanted), or even worse (an undetected duplicate). A little clear reasoning will reveal when it's appropriate to retransmit the DATA.

   Implementation

   The approach taken here is that a NACK is really just a hint which may be safely ignored (this makes sense, as we start with a standard stopandwait.c implementation and have just added new NACK frames to it). The protocol worked without NACKs, so transmitting but ignoring them should not "break" the protocol.
   Every time that a corrupt frame is detected, the receiver of that frame transmits a NACK. As the contents of the frame was corrupted, we cannot use its frame kind, sequence number, or length to learn what the corrupt frame once was.
   When a NACK frame is received, it is used as a hint to suggest that the last data frame that was transmitted should possibly be retransmitted. In this regard, the action on receiving a NACK is like a timeout event. However, we should not retransmit the DATA frame if we know that that DATA frame has already been transmitted and received correctly - else we will be unnecessarily transmitting a duplicate frame.
   But how do we know that? Simple! If the frame has already been transmitted and received perfectly, then we will have already seen an ACK frame for it. We simply see if any DATA frame has yet to be ACKed by examining the corresponding sequence numbers. If they are different, we know that we should retranmsit; if they are the same, we have nothing to retransmit, and so the NACK may be safely ignored.
   An alternate approach is to only retransmit the DATA if it "looks correct". We can make the DATA look "incorrect" if we set a DATA frame's attribute to an invalid value, such as a length of -1, when an ACK arrives. Clearly we shouldn't retransmit DATA with a negative length!
   You may find a sample solution to the problem here: Q4-nacks.zip
   Note that it's a Zip archive, so you may wish to save its contents to a new directory:

     Length      Date    Time    Name
   ---------  ---------- -----   ----
         951  03-09-2024 03:01   1st.README
         396  03-09-2024 03:01   ATTRIBUTES.common
          71  03-09-2024 03:01   Makefile
          52  03-09-2024 03:01   NACKS
          58  03-09-2024 03:01   STOPANDWAIT
        5868  03-09-2024 03:01   nacks.c
        2585  03-09-2024 03:01   plot-to-html.sh
       37376  03-09-2024 03:01   plot1.png
       44434  03-09-2024 03:01   plot2.png
        4346  03-09-2024 03:01   stopandwait.c
   ---------                     -------
       96137                     10 files
   

   You can see the differences between stopandwait.c and nacks.c using the command:
   shell>  diff stopandwait.c nacks.c
   which (other than displaying a big comment in the code) shows that's there's very few new lines required.

   No silver bullet

   Note that negative acknowledgments do not provide significant improvements in all situations. As the two plots, below, show negative acknowledgments offer advantages in environments with high frame corruption, but little advantage when frame corruption is less likely. Can you reason why? What about for frame loss?