This assignment is due no later than 1:00 p.m. on Thursday, 14 March.
This homework assignment has five questions; answer all of them. Please site references you use to answer your questions, including the textbooks you’re using.
If you mail in your assignment, please send a printable document
— a PostScript .ps
or PDF .pdf
document, for
example — and not a source document — a
Word .docx
or Latex .tex
document, for example.
Assume an infinite frame stream arriving at receiver R. If, waiting for the next frame to begin, R receives unknown bytes, then a frame's first flag byte has been damaged. R reads and tosses bytes until it reads the trailing flag byte. R is now ready to read the next frame, with one fame lost.
If R receives a bad frame, then the trailing flag byte has been damaged, and R has read the start of the next frame in a state where it was expecting the end of the previous, damaged, frame. R reads and tosses the bytes of the current frame until it reads the trailing flag byte, at which point it's ready to read the next frame. Two frames have been lost.
01100010
(that is, change it to 01000010
). Unfortunately for you,
the bank uses a CRC code to detect message changes. Fortunately for you, the
CRC generating polynomial is unprotected, and you may change it at your
convenience. What generating polynomial should you use to pull off your heist?
Demonstrate that your polynomial does what you want it to.
The check polynomial G(x) = 1 should do the trick. G(x) is a polynomial of degree 0, and so adds no parity bits to the message (alternatively: the result of dividing any polynomial by G(x) has zero remainder). The polynomial x would also work, but it's not a CRC check polynomial because it doesn't have a unit constant term (on the other hand, why would a master thief care about that).
Your colleague's protocol is broken because it has the receiver use an ack for two purposes: to acknowledge the last frame received and to indicate space left in the receiver's buffer. If the receiver acknowledges the last frame sent and indicates there's no space left in the buffer, the sender will not send any more frames. The receiver has nothing to acknowledge, and has no way of indicating that buffer space has been freed up.
One way to fix the protocol is to disentangle the ack message's dual purpose: an ack only acknowledges the last message and a new message indicates receiver buffer status. This fix doubles the receiver's overhead. Another fix is to the let receiver re-acknowledge the last frame received when buffer status has changed. Combining separate messages into a single message is a standard protocol optimization technique known as piggybacking, which, as you've just pointed out to your colleague, is useful for reducing message overhead but requires careful thought to make sure the combined purposes don't conflict.
A and B send a continuous stream of frames to each other using the sliding-window protocol. Assuming I contains a infinite (or effectively so) buffer space, for which of the systems A and B is it possible to determine the sliding window size from observing I in action? There is no frame loss. Justify your answer.
It's possible to determine the sliding-window size being used by the system attached to the fast link; it's not possible to determine the sliding-window size on the system attached to the slow link.
Whenever a frame arrives over the slow link, I transfers it to the fast link with zero buffering because the fast link is always able to accept a frame immediately. If I understands the data-link layer protocol, it may be able to snoop the acks for sequence numbers, but that fixes the maximum window size to within a constant factor.
In the other direction, frames from the fast link will spend some time waiting in buffers until the slow link is able to carry them. The system on the fast link will max out its window, with most of its frames sitting in I's buffers. The long-term maximum of I's buffer occupancy should be within one or two of the fast system's sliding window size, assuming a steady frame rate faster than the slow link can handle.Manchester encoding adds a timing signal to the data signals. Without perfect synchronization, a system has to lock onto the timing signal for synchronization. Collision damaged signals won't provide a timing pulse, and the receiving system (which could be the sender) will fail to synchronize, indicating a collision-damaged frame. (As a practical matter, collisions are detected via power levels; signals much stronger than they should be are probably the result of combined — that is, colliding — signals.)