V22.0480-005 Lab 5: Reliable transport

Due date: Thursday April 22, 3:30pm
Free extension to midnight if you attend lecture

Reading:

Sect 5.2.4 of textbook Computer Networks.

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 first half of this assignment, your implementation should:

Handle packet drops
Handle packet corruption
Provide trivial flow control
Provide a stream abstraction

Looking ahead a bit, your final assignment next week will build on this lab by adding more realistic flow control (i.e., a sliding window protocol like TCP). The main purposes of these 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 only needs to support one outstanding packet at a time. (In TCP terms, a window size of one.) That is, after your client sends packet n, it should not send packet n+1 until the server acknowledges that it received packet n.
As only one packet need be outstanding at once, the system already guarantees that the server will receive news packets in-order. Next week's lab will require a variable window size, however, so we suggest that you should already consider how you would correct any reordering caused by the network.

Your client should resend a packet if the server does not acknowledgment it within an appropriate time period. At this stage, you do not need to implement any backoff like TCP, and can instead merely retransmit a packet 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.

Getting Started

We supply you with a skeleton client, skeleton server, a test program, and some library functionality for sending and receiving packets asynchronously. The code can be found in ~class/src/reliable.tar.gz. To unpack, run:

% tar xvfz ~class/src/reliable.tar.gz
% cd reliable
% setenv AUTOCONF_VERSION 2.13
% sh ./setup
...
% setenv DEBUG -g
% ./configure
...
% gmake
...

You should start by testing you client and server just by writing data into STDIN on the client. Note that you need to start the server before starting the client, as the client should immediately attempt to connect to the server at the port specified.

% ./srvd [port]
% ./clntd [port]

The server (svrd) and client (clntd) expect you to give them the same port (> 1024). If your program is working correctly, anything you type into the client should output by the server to STDOUT.

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 might choose just to 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 both the client and server side corresponding to in-order packets. See section 5.2.4 in the textbook for some hints as to a possible implementation design.

While your client only needs to maintain a single linked-list (as we are assuming a single connection per client), your server should maintain a linked-list 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.

Our official test program can be run via;

%  ./rlbtester ./clntd ./srvd

For those that are curious, the tester works by interposing itself between the client and server: the client actually sends packets to the tester, not the server. The tester then just passes the packets on to the server, optionally dropping, corrupting, (and later, reordering) packets. The server's response also goes through the tester. In some sense, you can think of the tester as a unreliable network. As the testing program forks the client and server when it starts, it also controls their I/O, so writes data into the client, and reads data out from the server, comparing the two results.

Turning in the assignment

You must submit two files:

A complete software distribution of the reliable transport program,
A script file showing how you tested the program.

To build a software distribution, run the command:

% gmake distcheck
rm -rf reliable-0.0
...
==============================================
reliable-0.0.tar.gz is ready for distribution
==============================================
%

To turn in your distribution, copy it to the directory ~class/handin/lab5/username where username is your username:

% cp reliable-0.0.tar.gz ~class/handin/lab5/`logname`/
%

To create a script file, use the script command. When you run script, everything you type gets saved in a file called typescript. Press CTRL-D to finish the script. The typescript should be copied to the same directory as the software distribution. For example:

% script
Script started, output file is typescript
%  ./test-reliable ./rlbtester ./clntd ./srvd
rlbtester: success: read [Hello.]
rlbtester: success: read [This is only a test.]
rlbtester: success: read [Hello. This is only a test. Only a test, I say.
]
...
Finished test for message transmission...
rlbtester: success: read [Hello.]
...
Finished test for handling dropped packets...
rlbtester: success: read [Hello.]
...
Finished test for handling corrupted packets...
Finishing experiment: 12 out of 12 points

[Internal use only: mfreed @ Thu Apr 15 18:20:09 EDT 2004
    MD5 (./clntd) = d1535e178d5ada4113f6cc096b03ceba
    MD5 (./srvd) = d5611354fc06019b903d8fe85fe4cf98
% ^D Script done, output file is typescript
% cp typescript ~class/handin/lab5/`logname`/
%

If you have any questions, please contact us at netstaff (at) class cs nyu edu.