Labs 1 & 2: Reliable transport

Due date: Thursday, October 8 @ the beginning of class (part 1).
Due date: Thursday, October 15 @ the beginning of class (part 2).


Your task is to implement a reliable, stop and wait (lab 1) and sliding window (lab 2) transport layer on top of the user datagram protocol (UDP). You will use IP addresses and UDP port numbers to demultiplex trafic, but not otherwise rely on UDP--in particular you should not rely on UDP's checksum to detect bit errors in packets.

This assignment is split into two labs. In the first lab you just need to support a single direct connection between two udp ports one on the server and the other on the client, and you can use the stop and wait protocol. In lab 2, you extend the functionality to support demultiplexing of several connections at the server as well as to support a sliding window with sizes > 1. (Recall that stop and wait is equivalent to sliding window with a window size of 1). The picture below shows how the system should look like after Lab 2 is implemented: diagram of completed assignment

In this assignment, 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). In general you will probably find it useful to look through rlib.h, as several useful helper functions have been provided.

In general your implementation should:

You will implement both the client and server component of a transport layer. The client will read a stream of data in (either from STDIN, in the first lab, or from a reliable TCP connection for lab 2), break it into fixed-sized packets suitable for UDP transport, prepend a control header to the data, and write this packet to the server. The server will read these packets, and write the corresponding data, in order, to a reliable stream (STDOUT in lab 1, and a TCP connection in lab 2).

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 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[500]; /* Data only; Not always 500 bytes, can be less */
        typedef struct packet packet_t;

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

The following fields only exist in a data packet:

To conserve packets, a sender should not send more than one unacknowledged Data frame with less than the maximum number of bytes (500), somewhat like TCP's Nagle algorithm.


Your transport layer must support the following:

Implementation Details

There are two modes of operation of the reliable transport protocol:

The first mode is single-connection mode, and connects standard input and output of the two processes together. The second is multi-connection mode, in which a client accepts TCP (or unix-domain) socket connections and relays them over UDP to a server that connects to a TCP port or unix-domain socket.

You are provided with a library (rlib.h/rlib.c) and your task is to implement the following seven functions: rel_create, rel_destroy, rel_recvpkt, rel_demux (Lab 2), rel_read, rel_output, rel_timer:

Lab 1

To get started on Lab 1, download and untar the assignment package.

Copy reliable.c-dist to reliable.c and fill in the functions there.

You should be able to run the command make to build the reliable program. When you are done with lab 1, two instances of reliable should be able to talk to one another. An example of the working program is given here (with what you type in green).

On machine myth15, run:

myth15:~/test/reliable> ./reliable 6666 myth14:5555
[listening on UDP port 6666]
Hello I am typing this on myth14.

On machine myth14, run:

myth14:~/test/reliable> ./reliable 5555 myth15:6666
[listening on UDP port 5555]
Hello I am typing this on myth14.

Now anything typed on myth14 will show up on myth15 and vice versa.

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

For testing purposes, you may wish to test your code against our reference implementation of the source code. The reference is an x86_64 linux binary. If you wish to test on other architectures, you will need to build the reference implementation from source. (You will need a recent version of ghc on your machine, and must use the command ghc --make reference.hs to compile it.)

Lab 2

For lab 2, you will extend your solution to lab 1 to support two additional features:

  1. A sliding send and receive window larger than one packet, and
  2. Connection demultiplexing.

The first feature is relatively straight forward. When you run the reliable program with the -w argument, it should set the sender and receiver window sizes to be whatever the supplied argument is. For example, the following command should select a window size of 5:

myth15:~/test/reliable> ./reliable -w 5 6666 myth14:5555
[listening on UDP port 6666]

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.

Connection demultiplexing is used when running the reliable program in server mode, which is selected by the -s switch. For example, the following command:runs reliable in server mode:

myth15:~/test/reliable> ./reliable -s -w 5 1111 localhost:2222
[listening on UDP port 1111]

Unlike single-connection mode, which you've been using up until this point, in server mode the argument localhost:2222 specifies a TCP, rather than UDP port. At this point reliable may accept multiple connections from different clients on different client UDP ports, all sending packets to port 1111 on the server. The reliable program will get all of these packets, but since they are all destined to the same UDP port, the rlib code doesn't know which connection they belong to. Therefore, received packets will be passed to the function rel_demux.

In server mode, the library never calls rel_recvpkt. Instead, you must look up the rel_t structure for a packet based on the client's UDP sockaddr_storage. You will find the addreq function that compares two sockaddr_storage structures for equality useful here.

In server mode, reliable input and output no longer come from standard input and output. Instead, for each new connection set up, the library creates a TCP connection to the TCP port specified (localhost:2222 in the example above). There is a utility uc that came with the reliable.tar.gz bundle that allows you to listen to a particular TCP port, so that you can test your library. Just run, e.g., ./uc -l 2222 to listen for one connection on a particular TCP port. (You'll have to run it again in a different terminal if you want to accept more than one connection.)

There is also a client mode, selected by -c. You shouldn't need any special support in your software for client mode, as long as you are using the rel_t structure correctly. Client mode allows you accept TCP connections and relay them to a reliable server on a particular UDP port. For instance:

myth15:~/test/reliable> ./reliable -c -w 5 3333 localhost:4444
[listening on TCP port 3333]

The above command accept connections on TCP port 3333, and for each connection, allocates a new UDP port and uses that port to talk to a reliable server listening on port 4444. The uc command without the -l flag allows you to connect to a TCP port. For instance, to test the above, run ./uc localhost 3333.

Getting Started

To get started you have to log into a machine managed by Stanford ITSS as described on the ITSS webpage .You may login remotely or use one of the computer labs, for example, the myth machines located in Gates B08.We will test your code on the myth cluster, and the instructions given here assume this environment. To log in remotely you can download Putty and use that. Also you can develop remotely using VNC Server/Viewer . To use VNC just download and install VNC viewer. When you have done this run the command "vncserver" on a myth machine for example(maybe connect to it via putty) and then use the new 'X' desktop it returns to connect to the machine via you VNC viewer.


Your program interoperate with the reference implementation (link is an x86_64 linux binary). There is also a tester program available here (x86_64 linux binary). Source code for both is available here (though you will need GHC and Data.Binary to compile it).

Run the tester giving it your ./reliable program as an argument. By default the tester program will run all tests, not use server mode, and set a window size of one. The following options may be useful to you:

Note: Regardless of any extensions you may have received, you may not resubmit lab 1 after downloading the tester.


To submit the assignment, you must do two things:

Collaboration policy

You should direct most questions to the class newsgroup, but not post source code there.

You must write all the code you hand in for the programming assignments, except for code that we give you as part of the assignment and system library code. You are not allowed to show your code to anyone else in the class or look at anyone else's solution. You also must not look at solutions from previous years. You may discuss the assignments with other students, but do not copy each others' code.