cmsc417-f01 exam 1 solution

CMSC 417-F01

EXAM 1 SOLUTION

Fall 1999

1 [15 pts]. Solution

1a: Transfer time for 20 Kbyte file

Since each packet carries 1 Kbyte, the file consists of packet chunks 0..19. The protocol evolves as follows, where send time is the time when the current window is sent (in ms), cw stands for congestion window, sst stands for congestion window, rtt stands for measured roundtrip time (in ms), and tns stands for time to next send (in ms).

  send time    sst    cw        rtt      packets 
         0      4      1        10         0
        10      4      2        20         1,2
        30      4      4        40         3,4,5,6
        70      4      5     timeout       7,8,9,10,11 (11 lost)
       270      3      1        10         11
       280      3      2        20         12,13
       300      3      4        40         14,15,16,17
       340      3      5        20         18,19

The file transfer is complete when packet 19 is acked. From above, this happens at time 360 ms. Also, 8 windows are sent.

GRADING:

10 points for part 1a: 5 for window evolution (cw, sst, packets sent); 5 for timing (3 for rtts, 2 for rto).
Incorrect cw evolution: -1, -2, or -3, depending on extent of cluelessness.
No packet lost: -1
No retransmission of lost packet: -1
Timeout without packet loss: -1
Not waiting for ack to be received: -1

1b: Transfer time for large file of F Kbyte file

We look at the behavior for a long transfer.

  send time    sst    cw        rtt      packets 
         0      4      1        10         0
        10      4      2        20         1,2
        30      4      4        40         3,4,5,6
        70      4      5     timeout       7,8,9,10,11 (11 lost)
       270      3      1        10         11
       280      3      2        20         12,13
       300      3      4        40         14,15,16,17
       340      3      5     timeout       18,19,20,21,22 (22 lost)
       540      3      1        10         22
       550      3      2        20         23,24
       ...

Thus cw evolves in "saw-tooth" fashion, cycling through 1,2,4,5. Each "saw-tooth" cycle lasts 270 ms (= 540-270) and transfers 11 packets (12 packets are sent but 1 is lost). So time required is F*270/11 ms (ignoring initial and final transients).

GRADING:

5 points for part 1b: 2 for sawtooth evolution of cw; 3 for extracting time and goodput of sawtooth.
2 points for noting that answer is F*(sawtooth period)/(sawtooth goodput)

2 [10 pts]. Solution

High-level code:

Receive(D, data, len, cj) {
  // if (cj in receive window)
  int tmp := (cj-nr) mod N;                         |
  if (0 <= tmp <= rw-1) {                           | 4 points

    // store data in rbuff locations starting at
    // nr-nc+tmp and stopping at nr-nc+tmp+len-1
    // (end of data) or nr-nc+rw-1 (end of window),
    // whichever is smaller
    for i := 0 to min(rw,len)-1 {                   |
        rbuff[nr-nc+tmp+i].data := data[i];         |
        rbuff[nr-nc+tmp+i].valid := true;           | 3 points
    }                                               |
    // note: no need to update rbuff[j].data
    // if rbuff[j].valid is already true.

    // advance nr as much as possible
    // decrementing rw correspondingly
    while ( rbuff[nr-nc].valid and rw>0 ) {         |
        nr := nr+1;                                 | 3 points
        rw := rw-1;                                 |
    }                                               |
  }
}

GRADING:

The points distribution is as indicated next to the high-level code.
Not handling the modulo-N arithmetic: -5 points

3 [5 pts]. Solution

The protocol does not correctly transfer data. Here is an example of an incorrect evolution, where messages are identified by their unbounded sequence number:

  na..ns  sw  nr..nr+rw-1  

  0..0    W      0..W-1
                         Source sends 0,1,...,W-1, Sink receives all
  0..W-1  W      W..2W-1
                         Sink receives 0 (either duplicate or retransmit)
                         and treats it as 2W-1 (because 2W-1 mod N is 0).

GRADING:

5 if answer and example correct. 2 if answer correct and example almost correct. 0 otherwise.