1    Introduction

In this project, your task is to implement a reliable sliding window transport layer on top of the User Datagram Protocol (UDP). Please check the accompanying slides for details about the reliable sliding window transport layer.

In this project, you are provided with a library (rlib.h and rlib.c), and you have to implement some functions and data structures for which skeletons are provided (in reliable.c). You will probably find it useful to look through rlib.h, as several useful helper functions have been provided.

Additionally, a bu↵er implementation is provided (bu↵er.h and bu↵er.c) which you can optionally use. If you decide not to use it, overwrite the content of reliable.c with the content of reli- able blank skeleton.c. reliable.c is the only file you should have to edit to succesfully complete this assignment.

In general, your implementation should:

• Handle packet drops

• Handle packet corruption

• Provide trivial flow control

• Provide a stream abstraction

• Allow multiple packets to be outstanding at any time (using a limit given to your program as a run-time parameter, via the -w option)

• Handle packet reordering

• Detect any single-bit errors in packets

You will implement the client and server component of a transport layer. The client reads a stream of data (from STDIN), breaks it into fixed-sized packets suitable for UDP transport, prepends a control header to the data, and sends each packet to the server. The server reads these packets and writes the corresponding data, in order, to a reliable stream (STDOUT). Figure 1 presents a high-level overview of the system.

Figure 1: Overview of the reliable transport protocol

2    Requirements

Your transport layer must support the following:

• Each side’s output should be identical to the other side’s input, regardless of a lossy, con- gested, or corrupting network layer. You will ensure reliable transport by having the recipient acknowledge packets received from the sender; the sender will detect missing acknowledge- ments and resend the dropped or corrupted packets.

• You should handle connection tear down properly. When you read an EOF, you should send a zero-length payload (12-byte packet) to the other side to indicate the end of file condition. When you receive a zero-length payload and have written the contents of all previous packets (i.e., have written all output data with conn output), you should send an EOF to your output by calling conn output with a len of 0.

• You should support arbitrary window sizes. The window size is supplied by the -w command- line option, which will show up as the window field in the config common data structure passed to the rel create function that you have to implement. The same window size will be used for both sender and receiver.

• Your server and client should ensure that data is written in the correct order, even if the network layer reorders packets. Your receiver should bu↵er as many packets as the client may send concurrently. In other words, the sender window size (SWS) should equal the receiver window size (RWS).

• The sender should resend a packet if the receiver does not acknowledge it within an appro- priate time period. You need not implement any back-o↵ like TCP, and can instead merely send packet(s) whenever a sent packet has gone unacknowledged for the timeout period. The timeout period in milliseconds is supplied to you by the timeout field of the config common structure. The default is 2000 msec, but you may change this with the -t command-line option.

• Acknowledgements should be cumulative rather than selective. Like TCP, you acknowledge the next sequence number you are expecting to receive, which is 1 more than the largest in-order-sequence number you have received. You do not have to handle sequence number overflowing and wrapping in the lifetime of a connection.

• You can retry packets infinitely many times, and should make sure you retry at least five times, after which, if you want, the client can terminate the connection with an error. You can call rel destroy to destroy the state associated with a connection when you give up on retransmitting.

• Note: For debugging printfs you should use the Standard Error fprintf (stderr, . . .) and not print on standard output. This is because standard output is being used for the actual program output, and it will become confusing if the two ouputs are mixed.

3    Implementation Details

3.1    Packet Types and Fields

There are two kinds of packets, Data packets and Ack-only packets. You can tell the type of a packet by its length. Ack packets are 8 bytes, while Data packets vary from 12 to 512 bytes. The packet format is defined in rlib.h:

struct   packet {

uint16 t cksum ;       / ∗ Ack   and   Data   ∗/

uint16 t  len ;          / ∗ Ack   and   Data   ∗/

uint32 t  ackno ;       / ∗ Ack   and   Data   ∗/

uint32 t seqno ;       / ∗ Data   Only   ∗/

char  data [ 5 0 0 ] ;      / ∗ Data   only ;   Not   always   500   bytes ,   can   be    l e s s    ∗/

} ;

typedef  struct   packet packet t ;

Every Data packet contains a 32-bit sequence number as well as 0 or more bytes of payload. The length, seqno, and ackno fields are always in network byte order (meaning you will have to use htonl/htons to write those fields and ntohl/ntohs to read them). Both Data and Ack packets contain the following fields:

• cksum: 16-bit IP checksum (you can set the cksum field to 0 and use the cksum(const void *, int) function on a packet to compute the value of the checksum that should be in there).

Note that you  should  not  call  htons on the  checksum value  produced  by the cksum function–it is already in network byte order.

• len: 16-bit total length of the packet. This will be 8 for Ack packets, and 12 + payload- size for data packets (since 12 bytes are used for the header). An end-of-file condition is transmitted to the other side of a connection by a data packet containing 0 bytes of payload, and hence a len of 12. Note: You must examine the length field, and should not assume that the UDP packet you receive is the correct length. The network might truncate or pad packets. Packets with incorrect length are considered“corrupted”.

• ackno: 32-bit cumulative acknowledgment number. This says that the sender of a packet has received all packets with sequence numbers lesser than ackno, and is waiting for the packet with a seqno of ackno. Note that the ackno is the sequence number you are waiting for, that you have not received yet. The first sequence number in any connection is 1, so if you have not received any packets yet, you should set the ackno field to 1.

The following fields only exist in a data packet:

• seqno: Each packet transmitted in a stream of data must be numbered with a seqno. The first packet in a stream has seqno 1. Note that in TCP, sequence numbers indicate bytes. By contrast, this protocol just numbers packets. That means that once a packet is transmitted, it cannot be merged with another packet for retransmission. This should simplify your implementation.

• data: Contains (len - 12) bytes of payload data for the application.

To limit the number of packets, a sender should not send more than one unacknowledged data frame with less than the maximum number of bytes (500 of data, 512 considering the header).

3.2    Implementations Details

In this project, you are provided with a library (rlib.h/rlib.c). The following details the six functions that you will be implementing for this project.

• rel create: The reliable state structure encapsulates the state of each connection. The structure is typedefed to rel t in rlib.h, but the contents of the structure are defined in reliable.c, where you should add more fields as needed to keep your per-connection state. A rel t is created by the rel create function. The library will call rel create directly for you.

• rel destroy: A rel t is deallocated by rel destroy(). The library will call rel destroy when it receives an ICMP port unreachable (signifying that the other end of the connection has died). You should also call rel destroy when all of the following hold:

– You have read an EOF from the other side (i.e., a Data packet of len 12, where the payload field is 0 bytes).

– You have read an EOF or error from your input (conn input returned -1).

– All packets you have sent have been acknowledged.

– You have written all output data with conn output.

Note that to be correct, at least one side should also wait around for twice the maximum segment lifetime in case the last ack it sent got lost, the way TCP uses the FIN WAIT state, but this is not required.

• rel recvpkt: When a packet is received, the library will call rel recvpkt and supply you with the rel t.

• rel read: To get the data that you must transmit to the receiver, call conn input. conn input reads from standard input. If no data is available, conn input will return 0. At that point, the library will call rel read once data is again available again, so that you can once again call conn input. Do not loop calling conn input if it returns 0; simply return and wait for the library to invoke rel read! Do not accept more into your send bu↵er than the sliding window permits; call again rel read when you were able to move the sending sliding window in rel recvpkt in order to fill up the send bu↵er again.

• rel output: To output data you have received in decoded UDP packets, call conn output. conn output function outputs data to STDOUT. You may find the function conn bufspace useful–it tells you how much space is available for use by conn output. If you try to write more than this, conn output may return that it has accepted fewer bytes than you gave it. You must flow-control the sender by not acknowledging packets if there is no bu↵er space available for conn output. You should schedule the calling of rel output.

• rel timer: The function rel timer is called periodically, currently at a rate 1/5 of the retransmission interval. You can use this timer to inspect packets and retransmit packets that have not been acknowledged. Do not retransmit every packet every time the timer is fired! You must keep track of which, and when, packets need to be retransmitted.

4    Task

Your task is to implement the six functions (rel create, rel destroy, rel recvpkt, rel read, rel output, rel timer) described in Section 3.2.

Download and untar the project package from the course website. The six functions you need to implement are all in the file reliable .c. This is the only file you need to modify for the assignment. You should be able to run the command make to build the reliable program.

When you are done with the project, two instances of reliable should be able to talk to one another. An example of the working program is given here.

On one shell, run:

On another shell, run:

Now anything typed on one shell will show up on the other shell.

The value specified for the -w argument is stored in the window field of the config common data structure. You should access it as cc->window in the rel create function, and store the value somewhere in the reliable state structure so you have access to it in other functions.

For debugging purposes, you may find it useful to run ./reliable with -d command-line option. This option will print all the packets your implementation sends and receives.

9    F.A.Q.

Can we assume that the UDP packet length received is correct?

No. As stated above, you must examine the length field, and should not assume that UDP packet you receive is the correct length. The network might truncate or pad packets. Packets with incorrect length are considered corrupted.

How are rel output, conn output, and conn bufspace related?

• conn output: outputs data to STDOUT. Call this function with received data.

• conn bufspace: returns the space available for use with conn output. Calls to conn output have limited space, as there is an underlying bu↵er. If you call conn output with more   data than it can handle, conn output may return that it has accepted fewer bytes. In   order to avoid passing in too much data, call conn bufspace to find out how much   space is available.

• rel output: Once the data passed in to conn output is all sent, the library will call rel output in order to continue processing any more data available.

Should Acks be piggybacked on top of outgoing data packets?

Piggybacking Acks is preferable but not required.

Assume packets 1-5 are received, and I output packets 1-3, but I do not have space

to output 4 and 5 (even though I have them bu↵ered). What should I do?

Only Ack packet 6 once you have space for packets 4 and 5. This helps to rate limit the sender.

Does the tester restart a new version of the ./reliable binary for each test?

No. We recycle a running instance of your program and put in new calls to rel create. So if you don’t handle tear down correctly, you can have one test a↵ecting another test.

Do we retransmit each packet individually or always just retransmit all unacknowl- edged packets?

Either is fine for correctness, but the preferred action is to retransmit just one packet (rather than a whole window).

Do we have to handle multiple connections at the same time?

No, your code can work for only one sender and only one receiver, hence, connection demul- tiplexing is unnecessary.

How do we obtain the current time?

//  Now   in   milliseconds

struct timeval now;

gettimeofday(&now, NULL) ;

long now ms = now . tv sec ∗ 1000 + now . tv usec / 1000;

What about byte ordering?

The length, seqno, and ackno fields of a packet are always in big-endian order (also called network byte order). Your machine might use little-endian. The functions ntohl(), ntohs(), htonl() and htons() might come in handy.

When running the test on my own machine I get an error that loading the shared library libgmp failed.

We encourage you to use the Virtual Machine image we provide in order to save time from such errors and because we will test your code on the same machine. To solve the prob- lem you have to create a symlink: sudo ln -s /usr/lib/x86 64-linux-gnu/libgmp.so.10 /us- r/lib/libgmp.so.3. Please ensure that in the end your code compiles on the Virtual Machine.

How do I start the virtual machine?

Perform the following steps:

a) Download the virtual machine using the link in the project pdf:

• https://nd .ethz .ch/external/blank-ubuntu-networks .zip or