You’ve already worked with TCP sockets in CSO1. In this lab you’ll learn how to add reliability on top of unreliable mailbox type model of a network.

You’ll have enough to do in this lab, we’ll not worry about doing it over an actual network. We’ve provided a simple network simulator for you.

1 Our Driver

We provide a network simulation driver program. It has the following pieces:

• Function void send(size_t len, void* data). You’ll invoke this to simulate sending unreliable packets over a network.

• Function skeleton void recvd(size_t len, void* data). This function is called by our simulation code (in waitForAllTimeouts) when packets are received. You’ll fill in details to describe what you would do on a packet receipt.

• Function int setTimeout(void (*callback)(void*), unsigned long ms, void *arg). You may invoke this to ask to have callback invoked after ms milliseconds (ms * 0.001 seconds), passing arg as the argument.

  On success, returns a positive identifier that may be used in clearTimeout. On failure, returns a special error code:

  • 0 if callback is NULL
  • -1 if ms is too far in the future (more than a minute)
  • -2 if you have too many pending callbacks scheduled (based on an implementation-defined limit guaranteed to be at least 16)

  The callback is executed once per setTimeout call, assuming it is not cleared with clearTimeout first.

  The actual invoking of callback will be done by the waitForAllTimeouts function.

• Function void clearTimeout(int timeoutID). If timeoutID was returned by setTimeout and the callback has not yet been invoked, unschedules that callback. Otherwise, does nothing.

• Function void waitForAllTimeouts(void). If there are no pending timeouts or messages, returns immediately. Otherwise, blocks until there are no scheduled timeouts or messages left, running a loop that calls the timeout callbacks and/or recvd as it waits.

  May not be called from a callback.

  Note, if you do not call this function then your program will stop before it receives any messages.

2 Protocol

Every message must have its first byte be a checksum. We’ll use a very simple checksum for this lab: the xor of all other bytes.

You should send the server a 4-byte message (plus a checksum) to initiate conversation. The first three bytes should be the ASCII characters for GET; the fourth should be an ASCII digit 0 through 9. The ASCII digit selects which message to retrieve (higher numbered messages are more difficult to handle), and is filled in from the command line argument in our supplied code. The server will then start sending you messages in discrete packets.

The first three bytes of each packet the server sends will be a checksum, a (1-based) sequence number, and the total sequence count. Both sequence number and sequence count will be encoded directly as a byte, not using ASCII.

After receiving a message, you should reply with a four-byte message (plus a checksum) to acknowledge it and request the next message. The first three bytes should be the ASCII characters for ACK; the fourth should be the sequence number you received. If the next message is not delivered, you should reply with the ACK of the last message you got in order (or re-send the GET if the very first message is not delivered) to request the next message be resent. However, messages may be delayed in transit and may arrive out of order. You should wait at least a few seconds before deciding a message will not arrive and re-sending its request.

Each GET will give a different message, and with a different level of errors you need to handle.

0. sends the full message without errors
1. sends the full message without errors, one a packet at a time, requiring you to ACK properly
2. sends messages unreliably; some messages never arrive and need to be re-requested
3. sends messages unreliably; some messages arrive in a corrupted state and need to be re-requested

You may assume that if a message has not arrived after a full second, it will not arrive.

3 Tips

• Work with a partner.

3.1 How the protocol works

• Messages with bad checksums are ignored by the server.

• You only have two kinds of messages you’ll ever send. It’s probably worth writing helper functions to send them (or just one helper to send both based on an argument).

• ACK0 does not work; use GET instead (with the correct message number).

3.2 Using setTimeout

• You can use setTimeout to make waitForAllTimeouts run something in the future. For example, the following prints 3, then 1, then 4, ending two seconds after it started.

    void pnum(void *num) {
        printf("%d\n", (int)num);
    }
    int main() {
        int one = setTimeout(pnum, 1000, (void *)1uL);
        int two = setTimeout(pnum, 500, (void *)2uL);
        int three = setTimeout(pnum, 100, (void *)3uL);
        int four = setTimeout(pnum, 2000, (void *)4uL);
        clearTimeout(two);
        waitForAllTimeouts();
    }

  Note that 2 is not printed out because of the call to clearTimeout.

  The waitForAllTimeouts function looks at the list of non-cleared timeouts, waits until each of those timeouts expire, and calls the callback function (pnum in this case) with the specified arguments (1, 3, and 4) in the case.

• Our API does not support any sleep-like function that waits for a certain amount of time, but you can achieve the same effects. For example, pseudocode like:

    void Example() {
        Foo();
        Sleep(1000); /* function that does not exist in our API */
        Bar();
    }

  (where Sleep(1000) would wait 1000 milliseconds) can be transformed to use our API as follows:

    void ExamplePartTwo(void *arg);
    void Example() {
        Foo();
        setTimeout(ExamplePartTwo, 1000, NULL);
    }
    void ExamplePartTwo(void *arg) {
        Bar();
    }

  (assuming that waitForAllTimeouts runs so it can call ExamplePartTwo. If Example itself was called by waitForAllTimeouts using recvd or callback, then returning from recvd or that callback will continue running waitForAllTimeouts. Otherwise (such as if Example was called from main()), the code that calls Example would need to later call waitForAllTimeouts.)

• A more challenging case for programming without any sleep-like function is when there would be local variables. For example, the previous transform doesn’t quite work on:

    void Example() {
        int x = Foo();
        int y = Foo();
        Sleep(1000); /* function that does not exist in our API */
        Bar(x, y);
    }

  because we need to do something wiht x and y. This is what we can use the arg parameter in setTimeout for:

    struct XYHolder {
        int x, y;
    }
    void ExamplePartTwo(void *arg); 
    void Example() {
        struct XYHolder *xy;
        xy = malloc(sizeof(struct XYHolder));
        xy->x = Foo();
        xy->y = Foo();
        setTimeout(ExamplePartTwo, 1000, xy);
    }
  
    void ExamplePartTwo(void *arg) {
        struct XYHolder *xy;
        xy = arg;
        Bar(xy->x, xy->y);
        free(xy);
    }

  In this case, we allocate space on the heap to store x and y, and pass a pointer to that space via setTimeout.

• The argument of your callbacks must be typed as a void *, but (via casting) can be any type of 8 or fewer bytes. Feel free to use NULL if you don’t need an argument.

• My solution used a few global variables for the information I wanted in every callback. It was 58 lines of reasonably-formatted C code.