CPS 114 Introduction to Computer Networks: Labs
Lab 1: Reliable transport
Introduction
Your task is to implement a reliable sliding window transport layer on top of the user datagram protocol (UDP). You are NOT required to handle demultiplex traffic, but you should not rely on UDP's checksum to detect bit errors in packets.
In this assignment, you are provided with a library (rlib.h and rlib.c) and you have to implement some functions and data structures in reliable.c. rlib.[h|c] provides some useful helper functions. Your implementation should:
- Handle packet drops
- Handle packet corruption
- Allow multiple packets to be outstanding at any time (via the -w option).
- Handle packet reordering
- Detect any single-bit errors in packets
You will implement both the sender and receiver component of a transport layer. The sender will read a stream of data in, break it into fixed-sized packets suitable for UDP transport, prepend a control header to the data, and write this packet to the receiver. The receiver will read these packets, and write the corresponding data, in order, to a reliable stream.
Getting started
You should be able to finish your assignment on any machine in the department's linux cluster: linux.cs.duke.edu. If you prefer to finish your assignment on your own machine, you may download and install ubuntu. You may run Ubuntu a virtual machine such as the free VirtualBox. We do not support MAC or Windows. Sorry.
Download and untar the reliable.tar.gz.
xwy@linux21$ wget http://www.cs.duke.edu/courses/spring10/cps114/labs/lab1/reliable.tar.gz xwy@linux21$ tar xzvf reliable.tar.gz
Copy reliable.c-dist to reliable.c. Your task will be filling in the functions in this file.
You should be able to run the command make to build the reliable program. An example of the working program is given here.
On machine linux21, run:
xwy@linux21$./reliable 6666 linux22:5555
[listening on UDP port 6666]
On machine linux22, run:
xwy@linux22$./reliable 5555 linux21:6666
[listening on UDP port 5555]
When you are done with the assignment, anything you type on linux21 will show up on linux22 and vice versa.
Understanding the code
Packet format
There are two kinds of packets, Data packets and Ack-only packets. You can tell the type of a packet by length. Data packets vary from 12 to 512 bytes, and Ack packets are 8 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; Can be less than 500 bytes*/ }; typedef struct packet packet_t;
Every Data packet contains a 32-bit sequence number and 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 (use htonl/htons to write and ntohl/ntohs to read):
- cksum: 16-bit IP checksum (you can use the cksum(const void *, int) function on a packet to compute the value of the checksum). 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. 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. You should not assume that the UDP packet you receive is the correct length. The network might truncate or pad packets.
- ackno: 32-bit cumulative acknowledgment number. The sender of a packet has received all packets with sequence numbers earlier than ackno, and is waiting for the packet with a seqno of ackno. 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, whereas by contrast this protocol just numbers packets. That means that once a packet is transmitted, it cannot be merged with another packet for retransmission.
- data: Contains (len - 12) bytes of payload data for the application.
Requirements
Your transport layer must support the following:
-
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.
-
The seq number of the first packet in a new connection is always 1. The server can detect a new connection when it receives a packet with a sequence number of 1.
-
You must support a window size larger than 1. 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 and rel_demux functions you implement.
-
Your sender and receiver should ensure that data is written in the correct order, even if the network layer reordered packets. Your receiver should buffer as many packets as the sender may send concurrently. In other words, the sender window size (SWS) should equal the receiver window size (RWS), and both should be the same as the window field in the config_common structure.
-
The sender should resend a packet if the receiver does not acknowledge it within an appropriate time period. You can 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. 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 don't 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 5 times, after which if you want, the sender 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 be confusing for the grader as well as the tester.
Functions and data structures you need to implement
The reliable transport protocol connects the standard input and output of the sender and receiver processes together. You are provided with a library (rlib.[h|c]) and your task is to implement the following six functions: rel_create, rel_destroy, rel_recvpkt, rel_read, rel_output, rel_timer:
-
rel_create: The reliable_state structure encapsulates the state of each connection. The structure is typedefed to rel_t in rlib.c, but the contents of the reliable_state structure is 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 provided 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. You should also call rel_destroy when all of the following hold:
- Read an EOF from the other side (i.e., a Data packet with 0 bytes payload field).
- Read an EOF or error from your input (conn_input returned -1).
- All packets you sent have been acknowledged.
At least one side should also wait around for twice the maximum segment lifetime in case the last ack it sent got lost.
-
rel_recvpkt: When a packet is received, the library will call rel_recvpkt. and supplies 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 available again, so that you can once again call conn_input. (Do not loop calling conn_input if it returns -1, simply return and wait for the library to invoke rel_read!)
-
rel_output: To output data you have received in decoded UDP packets, call conn_output. This 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 have asked for. You must flow control the sender by not acknowledging packets if there is no buffer space available for conn_output. The library calls rel_output when output has drained, at which point you can call conn_bufspace to see how much buffer space you have and send out more Acks to get more data from the remote side.
-
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 packets need to be retransmitted.
Testing and Debugging
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 download the source code for our test and a reference implementation here. You may compile the reference implementation and the tester on any of the department's linux machined by typing "make" in the tester-src directory after you untar the source file. Your program ./reliable should be able to communicate with the reference implementation. The tester takes your program reliable as an input and runs it against the reference implementation. Run the command ./tester, and ./reference to see the list of options available. In particular, ./tester -L will list the set of tests we will run against your reliable program. The -v option will print out packet traces for you. You should NOT use the tester's -s option, and test for window sizes greater than 1.
Submitting
To submit the assignment, do the following:
- Run the command make submit, this should create a file called reliable.tar.gz.
- Upload reliable.tar.gz to the lab1 assignment on Blackboard.
Collaboration policy
You can discuss with anyone, but you must not look at each other's code, or copy code from others.
Acknowledgement
We thank the course staff of cs 144 at Stanford university for their support. This lab is adapted from one of their assignments.
Last updated: 01/2010