|
|
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.
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?
Chris McDonald
March 2024.
|
