EECS 489 Homework #4

Due December 7th @ 1:30


Please include the last 4 digits of your SS number to assist in grade posting

Short answer section

  1. (12 points) Consider an ARQ algorithm running over a 20-km point to point fiber optic link. ((ARQ) Automatic Repeat reQuest a.k.a (PAR) Positive Acknowledgment with Retransmission)
    1. Compute the propagation delay for this link, assuming that the propagation speed is 2 * 10^8 m/s.
      20-km / ( 2*10^8 m/s ) = d (2d also acceptable)

    2. Suggest a suitable time-out value for the ARQ scheme to use.
      d * 2 + safety constant

    3. Why might it still be possible for the ARQ algorithm to time out and retransmit a frame, given this time-out value?
      Propagation delay is only one source of delays. Packets may experience delays by sitting in queues waiting to be processes and acknowledged. If these delays exceed the safety constant than ARQ will retransmit.

  2. (18 points) Suppose that we want to design a reliable data transfer protocol that only uses negative acknowledgments. The sender operates in a selective repeat fashion with an infinite window size (you may assume an infinitely large sequence number space), and only retransmits a packet when it receives a NACK from the receiver. The channel may lose or corrupt messages, and the delays are variable and unknown.
    1. Would sequence numbers be necessary in this protocol? Why or why not?
      Yes because how else would the receiver inform the sender which packets to retransmit if not by identifying each packet with some unique serial number. Furthermore, the receiver needs sequence number to be able to determine if packets were arriving out of order.

    2. Would a timer be necessary or advisable in this protocol? Why or why not? If so, would it be preferable to have the timer at the sender or receiver? Why?
      The sender would not need a retransmission timer by the definition of a protocol which only uses negative acknowledgments. The receiver would need a request for retransmission timer. The receiver could use a timer to test if the sender is done in case the sender fin got lost.

    3. Describe (in words or in pseudocode) the operation of a NACK-only receiver that would operate with this sender. If there are scenarios (no matter how unlikely) that your receiver would fail to operate reliably, identify these scenarios.
      A connection is established and sequence numbers are agreed upon. Packets are received and ordered. The largest chunk of consecutive serial numbers received would be passed up the protocol stack. After a gap in the sequence number space has existed for longer than some delay period, a NACK would be sent back to the sender at regular intervals until the packet corresponding to the missing sequence numbers is received.

      The disconnection handshake should inform the receiver of the last sequence number to allow it to determine if it received all the packets.

      This protocol has no flow control and hence a fast transmitter would be able to swamp a slow receiver.


    4. What would be the most important advantage of a NACK-based protocol?
      No ACKs would be sent saving network bandwidth.

  3. (10 points) Draw a timeline diagram for the sliding window algorithm using go-back-N-with-NACK discussed in lecture. Set both the sending and receiving window sizes equal to 3 frames for the following two situations. Use a time-out interval of about 2 * RRT. Assume a total of 8 frames are being sent and continue the time line until all 8 frames are received.
    1. The 4th frame is lost.
    2. The 4th, 5th and 6th frames (lost).
      Straight out of lecture.

  4. (5 points) Why does UDP exist? Would it not have been enough to just let the user process send raw IP packets?
    UDP multiplexes processes on the host by including a port number.

  5. (5 points) A CPU executes instructions at the rate of 100 MIPS (million instructions per second). Data can be copied 64 bits at a time at a cost of six instructions. If an incoming packet has to be copied twice, can this system handle a 1-Gbps line? For simplicity, assume that all instructions, even those instructions that read or write memory, run at the full 100-MIPS rate.
    In one second 1Gbs arrive. 1G / 64 * 2 = C copes need to be made. This would cost C * 6 = I instructions. If I is < 100 MIPS than the CPU can handle the bit stream.

  6. (5 points) Why is the third packet in the three-way handshake needed?
    If host A receives an unsolicited connection request from host B then it can refuse the connection.

  7. .

    Examine the figure to the right. Here both a CONNECTION REQUEST and an acknowledgment to a CONNECTION ACCEPTED which where floating around in the network arrive at host B. Both before host A gets a chance to reject the connection. This is unfortunate because host B has accepted the stale DATA packet with sequence number X causing unknown havoc. However the TCP handshake protocol does not have this problem and there is something wrong with this picture. How does TCP deal with this double duplicate delayed packet delivery scenario and what is wrong with this picture?

    The second delayed duplicate cannot have an ACK = Y because B delayed sending SEQ = Y until all ACK = Y in the network had died off. Hence, with ACK != Y, B rejects the second duplicate as a delayed packet.



  8. (7 points) Give an example of what could go wrong if a packet is sent with a sequence number assigned to it from the "forbidden zone".
    If the host machine dies and reboots and reopens the connection, the packet with the forbidden sequence number could be mistakenly interpreted by the receiver as having been sent after the connection was reopened corrupting the data.

  9. (5 points) (Comer 13.8 p.~228) What are the arguments for and against automatically closing idle connections?
    How long is idle?

  10. (10 points) (Comer 13.16, p.~229) Assume TCP is sending segments using a maximum window size (64 Kbytes) on a channel that has infinite bandwidth and an average round-trip time of 20 milliseconds. What is the maximum throughput? How does throughput change if the round-trip time increases to 40 milliseconds (while bandwidth remains infinite)?
    Every RTT 64Kbytes can be sent. If RRT is 20ms than 64Kbytes/20ms is the maximum throughput. If RTT doubles, throughput is halved.