2.993: Principle of Internet Computing

HW2 Solutions

1. (Peterson & Davie, 3.12)

  1. minimum propagation delay = 20 km/2x10^8 m/s

    2. = 0.1 ms.

  2. time-out > RTT = 0.2 ms. (Here, we assume that time-out is measured from the time the last bit of a packet is transmitted to the time the first bit of the next packet is transmitted. We also assume the size of an ACK packet is negligibly small. By using this definition for time-out, we need not know the size of a packet.)

  3. if 1) packet is lost, no ACK, 2)packet arrives, ACK lost, 3)packet arrives, ACK delayed

2. (Peterson & Davie, 3.13)

The sender can only send up to SWS packets before the frist packet is acknowledged. Thus, the receiver only needs to buffer a maximum of SWS packets.

3. (Peterson & Davie, 3.14)

The delay bandwidth product is 1Mbps x 2.5 sec = 2.5 Mbits. The delay in this case is RTT. Since each frame is 1KB (8192 bits), the maximum number of outstanding frames = 2.5M/8192 = 305

maximum SeqNum > (2*SWS - 1)= (2*305 - 1)= 609. (2^9=512, 2^10=1024) Thus, we need at least 10 bits.

4. (Peterson & Davie, 3.15)

Before we proceed, let's first clarify some confusion. One of the roles of sliding window scheme is flow control. The question is NOT whether it is a good idea to use sliding window for flow control, but rather HOW to use it effectively for flow control. One option is to delay ACK. You're aksed why this option is not good.

In terms of latency, we have so far addressed propagation delay, transmission time and queueing delay. Another type of latency is processing delay. Up till now, we have assumed that once a buffer receives a full packet, it empties out immediately (i.e., send the packet to the next higher layer for processing). But it is possible (due to processing delay) that the packet is still stored in the buffer, and not ready to receive new packets. Another scenario is a receiver (serving as a router) relaying packets to another destination with a smaller link capacity. (We saw this case in HW1.1). So, a solution is to delay ACK.

The figure sliding window/flow control illustrates the reasoning why it is not a good method:

  • In (a), the ideal case, (no processing delay) there is no need for flow control.
  • In (b), because of processing delay, there is not enough buffer space, and packet #4 is rejected. The buffer space is available after time T4.
  • In (c), ACK=2 is delayed so that packet #4 is accepted after T4. The problem is that it reduces the link utilization. And don't worry about retransmission after time-out. Remember: the sender selects time-out > RTT. The sender has no way of knowing ACK is delayed on purpose. It just assumes that it is the "real" RTT and adjusts its time-out to a larger value.

    •  

    (T. Minn)