Lab 3: Reliable transport

Due date: Wednesday, April 30 @ the beginning of class.
Free extension to Saturday, May 3 @ 5pm if you attend class on Wed

Introduction

Your task is to implement a reliable, stream-based transport layer on top of the user datagram protocol. You can view this assignment as implementing a simple TCP-like protocol in user space. In this assignment, your implementation should:

Handle packet drops
Handle packet corruption
Provide trivial flow control
Provide a stream abstraction
Allow multiple (4) packets to be outstanding at any time
Handle packet reordering

The main purpose of this assignment is to gain some experience to the difficulties in implementing TCP, without actually dealing with all the complexities of its specification.

For simplicity, you will only implement data flowing in one direction -- from the client to the server. Traffic back from the server will only entail acknowledgment messages for reliability and flow control.

You will implement both the client and server component of a transport layer. The client will read a stream of data in from STDIN, 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 stream to STDOUT.

Requirements

Your transport layer must support the following:

The output of the server should be identical to the client's input, irrespective of a lossy, congested, or corrupting network layer. You will ensure reliable transport by having the server acknowledge messages received from the client, so that the client may resend dropped or corrupted packets.

As reliable transport is inherently a stateful protocol, your transport layer should handle simple connection establishment. Connection need only entail a simple two-part protocol (e.g., like a single SYN-ACK handshake for TCP).

Your transport layer need not handle connection tear-down (e.g., in the manner TCP uses FIN packets). Thus, you don't need to implement much of the TCP state machine.

Your transport layer must support FOUR outstanding packets at a time. (In TCP terms, a window size of four.)

Your server should ensure that packets are written in the correct order, even if the network layer reordered packets. (And as multiple packets can be outstanding at any time, this can happen.) Your server may simply drop packets received out of order and expect that the client will resend them if you like.

Your client should resend a packet if the server does not acknowledgment it within an appropriate time period, although ensuring that the total number of outstanding packets is still at most 4. You need not implement any backoff like TCP, and can instead merely send packet(s) whenever the timer function is called (see below).

Network communication is restricted by the network MTU, thus you can fit at most 1460 bytes in each packet you send (i.e., 1500 byte Ethernet MTU - 40 byte UDP+IP header for underlying transport). However, your client might receive more than 1460 bytes of data from its input. Still, your client and server must operate in a way that ensures data is not lost and long inputs are output in the same form.

Acknowledgements should be cumulative rather than selective. Also, because the sequence numbers are 32 bits and they count packets rather than bytes, you may assume that if you start with a low initial sequence number that it will not overflow in the lifetime of a connection.

Getting Started

To get started, log in to a 32-bit linux machine (myth or pod), and copy the starter directory:

% cp -r /usr/class/cs144/src/reliable .

These files are also archived in a tarball here.

You can then start editing the clntd.c, srvd.c, and reliable_utils.h starter files. (Do not modify reliable_pkt.c, reliable_socket.c, or timer.c.) You may want to add more files (for example, to define the interface to the send/receive queues, which are currently just the empty structs snd_state and rcv_state in reliable_utils.h).

If you want to add a source file that is linked in only with the client target, add it to the CLIENT_SRCS line in the Makefile. If you want to add a source file that is linked in only with the server target, add it to the SERVER_SRCS line in the Makefile. If you want to add a source file that is linked in with both the client and server targets, add it to the SHARED_SRCS line in the Makefile. For example, suppose you create a "packet_list.c" file that implements foo() and bar(), and whose function prototypes you have added to reliable_utils.h. Then you should add packet_list.c to the SHARED_SRCS line, as everyone is importing the definitions in reliable_utils.h.

Some good general coding guidelines can be found on the CS244A coding guidelines page, including some strategies for dealing with handling errors.

Interfaces and hints

You will need to modify the files clntd.c, srvd.c, and reliable_utils.h. We have provided a basic framework for sending and receiving packets; obviously, you can add other functions or files if you so want.

In clntd.c, you should modify four functions:

handle_data receives a buffer of data read in from STDIN, to be sent to the server.
handle_ack receives a buffer of data received back from the server.
clntconn is called when the client immediately starts and should send a connection request to the server.
timer is called once every 100 milliseconds; you might use this function for actually sending packets (both for the first time and retransmissions) to the server.

In srvd.c, you should modify the handle_pkt function that receives packets sent for the client. When data is correctly received in-order, the server should write it out to STDOUT.

Note that we've provided a bunch of functionality that you might find useful; the functions are declared in reliable_utils.h. For example, you do not need to open or read from sockets yourself, the client and server already just create such sockets and then call add_fd (int fd), which registers the socket with our run engine (see timer.c). This engine polls alls registered sockets and then calls the corresponding handle_pkt on the server or client when appropriate. To write to a socket, you should use the following function:

     int sendpkt (int fd, struct sockaddr_in *to, char *buf, u_int len);

In reliable_utils.h, you should define some header type in struct reliable_hdr that may include such things as a sequence and acknowledgment number, a packet flag type, and a checksum. (See, for instance, TCP's headers on page 383 of the textbook.) Note that as the underlying UDP transport already includes source and destination port, this should not be included in your header. Each packet you send should start with this control header; all information in the control header should be in network-byte-order.

Note that we provide the function in_cksum (u_char *pkt, int len) for computing a packet checksum. This checksum should also cover your header, although note that the checksum field in the header should be set to 0 before actually computing the checksum on the packet header and data. The checksum allows each party to detect any corruption during transmission; corrupted packets should merely be dropped (which of course causes the reliability component of your implementation to resend the dropped packet.)

You are probably going to want to define some type of linked-list structure on the client side corresponding to in-order packets that have either not been sent or not been acknowledged by the server.

While your client only needs to maintain a single linked-list (as we are assuming a single connection per client), your server should maintain some state per connection. For example, your server might demultiplex a packet to the correct connection based on the from address of the packet.

Testing the assignment

You should initially test your program by hand, i.e., creating a server and client, then typing data into the client's STDIN.

Submitting

To submit, run

make submit

from your project directory and submit the resulting tarball on the submission page.

Collaboration policy

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. You are not allowed to look at anyone else's solution (and you're not allowed to look at solutions from previous years). You may discuss the assignments with other students, but you may not look at or copy each others' code.

Grades

Click here to see your grade.