cmsc417-f99 exam 1 solution

CMSC 417-F99

EXAM 1 SOLUTION

Fall 1999

1 [15 pts]. Solution

We first look at the behavior for a long transfer. Below, time stands for elapsed time (in ms), cw stands for congestion window, rtt stands for measured roundtrip time (in ms), and tns stands for time to next send (in ms).

    time   cong   roundtrip     time to     packets          
          window    time       next send     sent   
     0      2        20           20         0..1
    20      3        30           30         2..4
    50      4        40           40         5..8
    90      5        50           50         9..13
   140      6        60           60         14..19
   200      7        70           70         20..26
   270      8     timeout        250         27..34  (34 lost)
   520      4        40           40         34..37
   560      5        50           50         38..42
   610      6        60           60         43..48
   670      7        70           70         49..55
   740      8     timeout        250         56..63  (63 lost)
   990      4        40           40         63..66
   ...

Thus cw evolves in "saw-tooth" fashion, cycling through 4,5,6,7,8. Each "saw-tooth" cycle lasts 470 ms (= 740-270) and transfers 29 packets (30 packets are sent but 1 is lost).

Transfer time for 20 Kbyte file

20 packets suffice (since each packet carries 1 Kbyte). From above, we see that the transfer (including the ack time) is completed by time 200 ms; no timeouts are involved.

Transfer time for 10 Mbyte file

10 Mbyte file requires 10240 packets, which means 10240/29 cycles (ignoring the particulars of the starting and ending cycle), which means 10240*470/29 ms, which is approximately 160 seconds (since 470/29 is a bit more than 470/30, which is 15.7).

GRADING:

6 points for evolution from start upto timeout (time 0 to 270+): 2 for cw, 2 for rtt, 2 for packets sent.
4 points for obtaining evolution across timeout (time 270- to 520+): 1 for cw, 1 for rtt, 2 for packets sent.
2 points for obtaining saw-tooth cycle evolution (time 270 to 740).
1 point for part a result.
2 points for part b result: 1 for number of cycles, 1 for numerical answer.
Not using timeout value: -4 points.
Keeping rtt constant at 10 ms: -3 points.

2 [15 pts]. Solution

High-level code:

Receive(ACK, cj, w) {
  if (cj at bottom of send window)             |
       update sw;  // no change in na          | 2 points

  else if (cj in send window) // new ack       |
       update na, sw, sbuff;                   | 2 points

       wake-up UserTx if sleeping;             | 1 points

  Send datablocks in na..na+sw-1               | 3 points
}

Receive(D, datablock, cj) {
  if (cj in receive window)                    | 3 points
       put datablock at proper rbuff location; |

  if (next in-sequence is now available)       | 3 points
       update nr, rw ;                         |

       wake-up UserRx if sleeping;             | 1 points

       if rw=0          // OPTIONAL, can be done at timeout
          cancel timer  // no more data expected
}

The lower-level code is obtained by defining the modulo-N arithmetic and the buffer usage. There are many options for buffer usage; we consider one.

At the source, let the send window occupy sbuff[0..sw-1]. Thus space in sbuff[sw..RW-1] is used for buffering data that the user produces (via UserTx) but which cannot be sent yet. This gives the following:

Receive(ACK, cj, w) {
  int tmp := Mod(cj-na);    // Mod(x) denotes x modulo N
  if (0 <= tmp <= Mod(ns-na))
       na := Mod(na+tmp);
       sw := w;
       Remove first tmp items from sbuff;
       for i := 0 to min(sw, sbuff.length) - 1 {
           Send(D, sbuff[i], Mod(i+na));
       }
       if (tmp > 0) {
           X.notify()
       }
}

At the sink, note that datablocks received in sequence may have to be buffered until the user consumes them (via UserRx). Let variable ng denote the unbounded sequence number of the next datablock to be consumed by the user. As before, nr denotes the unbounded sequence number of the next in-sequence datablock to be received. Let the data awaiting consumption be in the first part of rbuff, that is, in rbuff[0..nr-ng-1]. Let the receive window occupy the rest of rbuff, that is, rbuff[nr-ng..RW-1]. Also assume that we can test whether or not rbuff[i] is empty. This gives the following:

Receive(D, datablock, cj) {
  int tmp := Mod(cj-nr);
  if (0 <= tmp <= rw-1) {
       if (rbuff[nr-ng+tmp] is empty)
          rbuff[nr-ng+tmp] := datablock;
  }
  if (tmp = 0) {
       // roll up nr as far as possible
       while ((rbuff[nr-ng] is not empty) and (nr-ng < RW) {
           nr := Mod(nr+1);
           rw := rw-1;
       }
       if (rw=0) {
           cancel timer
       }
       Y.notify();
  }
}

GRADING:

The points distribution is as indicated next to the high-level code.
Not handling the modulo-N arithmetic: -6 points (3 in each Receive).
Using receive window of at most 1, i.e., not buffering datablocks received out of sequence: -4 points.
No penalty for not showing buffer management.