Changelog:
- 27 Oct 2023: update netlab.tar’s libnetsim.a to support waitForAllTimeouts() being called multiple times; also adjust make flags some
- 30 Oct 2023: be more explicit that number after GET selects which message to retrieve and that this is is filled in from the command line by the supplied code
- 30 Oct 2023: fix bug where simulator would mishandle clearTimeout() of a currently active callback; adjust supplied code to not print out extra NULs
- 31 Oct 2023: be more explicit about checkoff requirements
- 31 Oct 2023: update netlab.tar to make
./netlab 0
(not required for lab) avoids sending duplicate messages for single ACKs - 1 Nov 2023: be more explicit that waitForAllTimeouts is what calls recvd and timeout callbacks; mention that it needs to run in Sleep example
- 2 Nov 2023: explicitly state that acknowledging the previous message requests the next one be sent/resent
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.
Possibly working with a partner —
Download netlab.tar [last updated 31 Oct] on a linux system (e.g., with
wget https://www.cs.virginia.edu/~cr4bd/3130/F2023/files/netlab.tar
).Extract it and enter the directory (e.g., with
tar xvf netlab.tar; cd netlab
).Test it with
make ./netlab 0
You should see a welcome message appear, ending with a
!
.Edit
netlab.c
so that you also see messages for./netlab 1
,./netlab 2
, etc. See below for a description of the messages the (simulated) server you are communicating with expects, including when you need to send acknowledgment or resend requests if you don’t receive a response.Show a TA your code or submit it to the submission site.
- To get full credit for checkoff, you should finish
./netlab 1
and show significant progress on./netlab 2
. (We’d like you to complete./netlab 2
if you’re able to in the lab time, but we intend to give credit if you make a significant attempt but don’t manage.) ./netlab 3
is quite a bit harder and is recommended if you have time, but not required for checkoff/submission- If you are submitting instead of checking off, we require
./netlab 1
and./netlab 2
to be complete
- To get full credit for checkoff, you should finish
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 havecallback
invoked afterms
milliseconds (ms * 0.001
seconds), passingarg
as the argument.On success, returns a positive identifier that may be used in
clearTimeout
. On failure, returns a special error code:0
ifcallback
isNULL
-1
ifms
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 withclearTimeout
first.The actual invoking of
callback
will be done by thewaitForAllTimeouts
function.Function
void clearTimeout(int timeoutID)
. IftimeoutID
was returned bysetTimeout
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/orrecvd
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.
To send the array of bytes [0, 1, 2, 5]
you actually
send a five-byte message: [0^1^2^5, 0, 1, 2, 5]
.
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.
If the server plans to send two packets, one containing
[3, 1]
and the other [4, 1, 5]
, they will
actually arrive as [1^2^3^1, 1, 2, 3, 1]
and
[2^2^4^1^5, 2, 2, 4, 1, 5]
.
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.
- sends the full message without errors
- sends the full message without errors, one a packet at a time,
requiring you to
ACK
properly - sends messages unreliably; some messages never arrive and need to be re-requested
- 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).
ACK
0 does not work; useGET
instead (with the correct message number).
3.2 Using
setTimeout
You can use
setTimeout
to makewaitForAllTimeouts
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 toclearTimeout
.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
-like function that waits for a certain amount of time, but you can achieve the same effects. For example, pseudocode like:sleep
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 frommain()
), the code that calls Example would need to later callwaitForAllTimeouts
.)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
andy
. This is what we can use thearg
parameter insetTimeout
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
andy
, and pass a pointer to that space viasetTimeout
.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 useNULL
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.