Homework #6 Solutions
cs349 -- Networks

Questions 19, 20, 23 and 26 from Chapter 2

19) Consider an ARQ algorithm running over a 20-km p-to-p fiber.

a) Compute the prop delay assuming that the speed of light in
   fiber is 2 * 10^8 m/s

   20 * 10 ^ 3
   ----------- = 10 * 10^-5 = 10^-4s = 100 us
    2 * 10 ^ 8

b) Suggest a suitable timeout

   In general, one rtt + the maximum additional time expected.

   In this case the only source of delay we expect is processing
   time at the receiver, so we might add just a little.

   200 us + a little

c) Why might it still be possible for the sender to time out?

   The most obvious cause would be that the frame or ACK gets
   dropped.  But if this really is a p-to-p fiber, then that
   wouldn't happen if the fiber were intacts.  So the only
   possibilities I can think of are: (1) fiber breaks, (2)
   receiver is down, (3) receiver takes too long to generate
   an ACK.


20) Suppose you are designing a sliding window protocol for
    a 1 Mbps p-to-p link to the moon, which has a one-way
    latency of 1.25 seconds.  Assuming that each frame carries
    1 KB of data, what is the minimum number of bits you need
    for the sequence number?

    Two step to get the answer: find the window size based
    on delay-bw product, then find the max sequence number
    needed.

    delay bw = rtt * bw = 2.5 s * 1 Mbps = 2.5 Mb

    How many frames is that?

         2.5 Mb / 8000 bits per frame = 312.5

    Approximate maximum sequence number = 625

    Easily handled by 10 bits.

23) In stop and wait, suppose that both sender and receiver retransmit
    immediately on receipt of a duplicate ACK or data frame.

a) Draw a timeline that shows what happens if the first
   data frame is duplicated.  How long will the duplications
   continue.

b) Suppose that ACKs can also time out; i.e. they are retransmitted
   if no reply comes in a given time.  How might the Sorcerer's
   Apprentice bug get started?

   At the end of the tranmission, the receiver will ACK the last
   packet and the sender will not reply, causing the receiver to
   duplicate the ACK, and then we're off to the races.

   (Actually, this one is odd, since the sender might not resend
   due to a duplicate final ACK.)

26) Draw a timeline diagram for the SWA with SWS = RWS = 3

a) Frame 4 is lost.

   The sender detects the error when it gets a duplicate ACK.

b) Frames 4-6 are lost.

   The sender detects the error when it times out.