cmsc417-f02 exam 1 solution

CMSC 417-F02

EXAM 1 SOLUTION

Fall 2002

1 [15 pts]. Solution

Since each packet carries 1 Kbyte, the file consists of packet chunks 0..25. The protocol evolves as follows, where window send identifies the instance of sending the window, chunks sent identifies the packets sent with "*" identifying a packet dropped at router, cw is the congestion window size, sst is the slow start threshold, router is the number of packets at the router just after the send, tns is the time to next send (in ms) and is tagged with rtt or rto, and send time is the time when the current window is sent (in ms).

  window send   chunks sent    cw    sst   router  tns       send time 
        1            0             1     8      1     10 (rtt)    0
        2            1,2           2     8      2     20 (rtt)    10
        3            3,4,5,6*      4     8      3     40 (rto)    30
        4            6             1     2      1     10 (rtt)    70
        5            7,8           2     2      2     20 (rtt)    80
        6            9,10,11       3     2      3     30 (rtt)   100
        7            12,13,14,15*  4     2      3     40 (rto)   130
        8            15            1     2      1     10 (rtt)   170
        9            16,17         2     2      2     20 (rtt)   180
       10            18,19,20      3     2      3     30 (rtt)   200
       11            21,22,23,24*  4     2      3     40 (rto)   230
       12            24            1     2      1     10 (rtt)   270
       13            25            2     2      2     20 (rtt)   280

The file transfer is complete when packet 25 is acked. From above, this happens at time 290 ms. Also, 13 windows are sent.

GRADING:

8 for window evolution (cw, sst, packets sent); 7 for timing (3 for rtts, 2 for rto).
Incorrect cw, sst evolution: -3 to -6, depending on extent of cluelessness.
Serious errors (no packet lost, no retransmission of lost packet, timeout without packet loss, not waiting for ack to be received): -3 to -4

2 [10 pts]. Solution

When a SACK message is received, the source should see if the message acknowledges any outstanding data, and if so, it should mark that data as acked.

What if the (SACK,cj,len) acknowledges na? That is, what if the unbounded sequence number j corresponding to cj equals na, or, more generally, [j..j+len-1] contains na. An obvious answer is that the source should update na (easy to do), and as a consequence update sw (but how to do this is not clear). In fact, this situation never arises, as the following argument shows.

Consider any (ACK,k,w) message and any (SACK,j,len) message sent by the sink, where we let j and k be unbounded sequence numbers (for clarity and without loss of generality).
If the ACK message was sent before the SACK message, then k is less than j and is not contained in [j..j+len-1], otherwise data j would not have been out-of-sequence at the sink when the SACK was sent.
If the ACK message was sent after the SACK message, then k is not contained in [j..j+len-1], otherwise data j would not have been the next in-sequence expected at the sink when the ACK was sent.
Because na is always the k in some ACK message, na will never be contained in the segment acked by a SACK message

This leads us to the following event handler for SACK reception:

Receive(SACK,cj,len) {
  // if (cj in outstanding packets)
  int tmp := mod(N, cj-na);
  if (1 ≤ tmp ≤ mod(N, ns-na)) {               | 4 points

    // mark data[j..k] as acked, where               |
    // j is unbounded seq number corresponding to cj |
    // and k is the smaller of cj+len-1 and ns-1.    | 6 points
    for i := tmp to tmp + min(len,ns-na)-1 {         |
        sbuff[i].ackd := true;                       |
    }                                                |
  }
}

GRADING:

The points distribution is as indicated above next to the code.
Mistakes in the modulo-N arithmetic and buffer handling: -2 to -8 points, depending on extent of cluelessness. Here are some common mistakes:

No modulo-N arithmetic at all: -7 pts.
Using cj rather than Mod(N,cj-na) in test: -4
Using Mod(N,cj-ns) rather than Mod(N,cj-na) in test: -3
Comparing tmp or cj vs ns or na (rather than ns-na): -4
Treating sbuff as indexed starting from na rather than 0: -3

Not checking for min(ns-na,len): -2 points
Updating na and sw when tmp not equal to 0 : -4 points

3 [5 pts]. Solution

The very high bandwidth and compute resources at the end points means that the propagation times are the only causes of delay; e.g., transmitting a message takes zero time, processing a received message takes zero time.

user 1 ----------- SYN -----------> user 2       T_1,2
user 1 <--------- SYN-ACK --------- user 2       T_2,1
user 1 ---- ACK-DATA(optional) ---> user 2       T_1,2
user 1 <--- DATA(user 3 addr) ----- user 2       T_2,1

user 1 ----------- SYN -----------> user 3       T_1,3
user 1 <--------- SYN-ACK --------- user 2       T_3,1
user 1 --- ACK-DATA(few octets) --> user 2       T_1,3
user 1 <-------- ACK  ------------- user 2       T_3,1

Total time taken is 2T_1,2 + 2T_2,1 + 2T_1,3 + 2T_3,1

If you close the connection between user 1 and user 2 before connecting to user 3 and you use separate FIN handshake for this, then there can be an additional delays (e.g., additional T_1,2 + T_2,1).

Many of you had user 1 send data to user 3 (or optional data to user 2) in a separate message (i.e., not in the ACK of the connection establishment). This does not affect the total time taken because this message is sent as soon as it becomes open (and transmitting a message takes zero time).

GRADING:

Correct handshake chart but inconsistent formula: -1 to -2
Incorrect but sensible handshake chart and consistent formula: -1 to -2.
Not using 3-way handshake in TCP connection establishment: -3
Common mistake: Having transmission of data (usually in separate message) contribute additional propagation delay: -3