cmsc 417 Fall 2001
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.
- 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
2 1, 2
- Determine the time to transfer a huge file of size
F > 106).
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
where data is an array of bytes,
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:
are as usual.
is the unbounded sequence number of the byte to be
next passed to the local user.
is the receive buffer array.
Each entry rbuf[i]
has two fields:
rbuf[i].data, containing a data byte;
a boolean that is true if and only if
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
upon reception of
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.
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.