Computer Networking

Homework 3, 28 February 2013


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.

  1. Assuming PPP-like framing, what would be the largest number of frames lost at the receiving end if one if the flag bytes were changed due to error. The only error that can occur is a single flag byte turning into a non-flag byte. Explain your answer.


    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.

  2. You are a master thief, and have discovered that you can steal all a bank's money by flipping the sixth rightmost (third leftmost) bit in the message 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).

  3. A colleague of yours has a cleaver idea for improving the sliding-window protocol: the receiver only sends ACKs when it has received a frame and it has room in its buffer for the next frame. Unfortunately for your colleague, the improved sliding-window protocol occasionally deadlocks (the sender has frames the send, the receiver has buffer space for more frames, but no frames are sent). What suggestions would you make to your colleague to fix the protocol? Assume the sequence numbers are properly sized.


    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.

  4. Two systems A and B are connected by an intermediate system I. One of the links AI or BI is much faster than the other.

    a simple network

    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.
  5. Ethernets use Manchester encoding. Assuming that hosts sharing the Ethernet are not perfectly synchronized, why does this allow collisions to be detected soon after they occur, without waiting for the CRC at the end of the packet?


    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.)


This page last modified on 2013 March 24.