CMSC 417 F99

Exam 1

Name:_______________

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

1. [15 pts]

This problem deals with TCP congestion control, using the ``per-window'' model (defined in Note 5). For the data flow from Source to Sink shown above, assume the following: Source is either in multiplicative decrease or additive increase (i.e., congestion window decreases by half upon timeout and increases by 1 upon receiving ack of previous window). Timeout value at the Source is constant at 250 ms (milliseconds). Packet payload is 1 Kbyte. Roundtrip time consists entirely of the delay encountered in the router queue (i.e., zero delay encountered by acks). The router queue holds at most 7 packets, and needs 10 ms to serve a packet. Queue overflow is the only cause of packet loss. No other traffic enters the router queue.

a.

How many seconds does it take to transfer a 20Kbyte file, starting with congestion window size of 2 packets.

b.

How many seconds does it take to transfer a 10 Mbyte file, starting with congestion window size of 2 packets.

2. [15 pts]  This problem deals with a variation of the sliding-window data transfer protocol defined in Note 4. Recall that the source maintains send window, ns and na, and sends (D, datablock, cj) messages; the sink maintains receive window and nr, and sends (ACK, cj, w) messages, where cj is a modulo-N sequence number and ns, na, nr are unbounded integers. (We have omitted source id and sink id fields.)

In this problem, you have to ``implement'' a version of the protocol where

• The source does not maintain any timers, and hence does no timeouts or retransmissions. It sends data messages only in response to ack receptions.

  
  

• The sink maintains timers and handles retransmissions. It send an ack message upon a timeout.

  
  

• To have a datablock transferred to Sink, the Source's user calls UserTx(datablock). This blocks if Source has no free buffer space (by doing a X.wait(), where X is an object for synchronization purposes only). The Source buffer is of size RW (datablocks).

  
  

• To get a datablock, the Sink's user calls UserRx(datablock). This blocks if Sink has no in-sequence datablock (by doing a Y.wait(), where Y is an object for synchronization purposes only). The Sink buffer is of size RW.

The outline of the protocol is given below.

Source

Variables
 sbuff; // buffer of size RW datablocks
 ns;    // {0, 1, ...}
 na;    // {0, 1, ...}
 sw;    // {0, 1, ..., RW}

UserTx(datablock) {
  // called by Source's user
  if sbuff can hold datablock
    then put datablock in sbuff
    else X.wait()
}

Receive(ACK, cj, w) {
  update variables;
  wake up Source user if needed;
  send data messages if needed;
}

Sink

Variables
  rbuff; // buffer of size RW datablocks
  nr;    // {0, 1, ...}
  rw;    // {0, 1, ..., RW}

UserRx( datablock ) {
  // called by Sink's user
  if next-in-sequence datablock available
    then return that datablock
    else Y.wait()
}

Receive(D, datablock, cj){
  update variables;
  wake up Sink user if needed;
  send ack if needed;
}

Timeout {
  send ack;
  restart timer;
}

Give the code for the Receive(ACK, cj, w) and Receive(D, datablock, cj) events.

Your code must not exceed 20 lines in total. Program elegance counts. You lose points for long/inelegant code.

In your code, assume that the entries of a buffer can be accessed by indexing starting from 0 (at the head) and ending at n-1 (where n is the number of items in buffer). Assume operations like Remove(item) (returns item at the head if any and removes it from the buffer) and Append(item) (append item at the tail of the buffer).