The University of Western Australia
Computer Science and Software Engineering
 
 

Department of Computer Science and Software Engineering

CITS3002 Computer Networks

Labsheet 2 - sample solutions and discussion

This labsheet mostly provided an introduction to cnet, so most tasks don't have 'solutions'. However Q4 provided a challenge, not requiring complicated coding, just a logical solution requiring a good demonstration of understanding.


  1. [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 of 8 files, so you may wish to save its contents to a new directory:

      Length      Date    Time    Name
    ---------  ---------- -----   ----
          951  03-17-2020 09:22   1st.README
          275  03-17-2020 09:22   ATTRIBUTES.common
           49  03-17-2020 09:22   Makefile
           52  03-17-2020 09:22   NACKS
           58  03-17-2020 09:22   STOPANDWAIT
         5785  03-17-2020 09:22   nacks.c
         2160  03-17-2020 09:22   plot-to-html.sh
         4679  03-17-2020 09:22   stopandwait.c
    ---------                     -------
        14009                     8 files
    

    You can see the differences between stopandwait.c and nacks.c using the command:

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

Chris McDonald

March 2020.

This Page

Written by: [email protected]