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-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.
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
The use of an additional negative-acknowledgement frame will reduce this
Modify a copy of the provided stop-and-wait protocol to also use
Have the receiver reply with a negative-acknowledgement when a corrupt
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.
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.
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.
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:
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?