cmsc 417 Fall 2001
Exam 1

If you want your exam/project scores displayed on class page by last four digits of your SID, sign at right and give the last four digits of your SID:

Total points 30. Total time 75 mins. 3 problems over 4 pages. No book, no notes, no calculator.

1. [15 pts] 

This problem deals with TCP congestion control using the ``window-level'' model (in Note 5) and the scenario shown above. Assume the following:

• Source uses the standard TCP congestion control (slow-start, additive increase, multiplicative decrease) except that timeout value is constant at 200 ms.

• Packet payload is 1 KB. Source has initial cw (congestion window size) of 1 packet and initial sst (slow-start threshold) of 4 packets. The router queue holds at most 4 packets and serves a packet in 10 ms.

• Roundtrip time consists entirely of the delay encountered in the router queue (i.e., zero delay encountered by acks). Queue overflow is the only cause of packet loss. No other traffic enters the router queue.

1a.

Determine the following for a 20 KB file transfer: the transfer time in ms (from start to everything acked); the number of windows sent; and, for each window send, which 1 KB chunks are sent (answers for the first two window sends are shown below, assuming the file consists of chunks 0, 1, ..., 19):

  window send    file chunks sent
    1              0
    2              1, 2
    3
    .
    .

1b.

Determine the time to transfer a huge file of size F KB (e.g., F > 10⁶). Your answer is a function of F. Ignore initial and final ``transient'' effects.

2. [10 pts]  This problem deals with a variation of the sliding-window data transfer protocol in Note 4. Assume a TCP-like situation as follows:

• Sequence numbering is done per byte

• Data messages have the form (D,data,len,cj), where data is an array of bytes, len is the number of bytes in data and cj is the modulo-N sequence number of the start byte in data. (We have omitted source id and sink id fields.)

• The sink entity maintains the variables nr, rw, nc, rbuf as follows: nr and rw are as usual. nc is the unbounded sequence number of the byte to be next passed to the local user. rbuf is the receive buffer array. Each entry rbuf[i] has two fields: rbuf[i].data, containing a data byte; and rbuf[i].valid, a boolean that is true if and only if rbuf[i].data has a valid data byte. The first nr-nc entries (i.e., rbuf[0..nr-nc-1]) contain the bytes to be passed to the local user, and the next rw entries (i.e., rbuf[nr-nc .. nr-nc+rw-1]) correspond to the receive window.

Give the code for the receive data event at Sink. Specifically, indicate how rbuf, nr, rw, nc are updated upon reception of (D,data,len,cj).

Your code must not exceed 20 lines in total. Program elegance counts.

3. [5 pts]  Consider the sliding window data transfer protocol in Note 4 with the following changes:

• The channels only lose messages, i.e., no reordering, no duplication, no maximum message lifetime.

• Let SW = RW = W and N = 2*W - 1.

Does this protocol correctly transfer data, i.e., from Source user to Sink user in sequence without any loss.

If you answer YES, give a brief justification. If you answer NO, give an evolution of the protocol that transfers data out-of-sequence, starting from na=ns=nr=0 and empty channels.