COMPSCI 356 Computer Network Architectures: Lab 1 Reliable transport

Introduction

Your task is to implement a reliable sliding window transport layer on top of the user datagram protocol (UDP) which is unreliable. For example, 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
• 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

This reliable transport protocol supports two operation modes. The first mode is single-connection mode connecting the 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. For more details, please refer to Labs1&2 in CS144 at Stanford University.

In our assignment, you should finish implementing the single-connection mode with sliding window with sizes > 1, the second server/client mode is NOT required. This means you don't need to handle demultiplex traffic at server side in server/client mode. In the first mode, one reliable transport layer should include both the sender component and receiver component. Correspondingly, one reliable connection bewteen two processes will support two-way data transmission simultaneously and asynchronously. In one of the data links, the sender will keep reading data from a stream (STDIN) until an EOF is met, break it into fixed-sized packets suitable for UDP transport, prepend a controlheader to the data, and transmit this packet to the receiver. The receiver will read these packets, and write the corresponding data, in order, to a reliable stream (STDOUT).

Getting started

You should be able to finish your assignment on the VM image in lab0.

Download and extract the reliable.tar.gz.

Your task will is filling in the some functions in reliable.c.

You should be able to run the command make to build the reliable program. We provide the binary code of a sample implementation, whose name is reference. After you finish your assignment, the reliable program should have same function with reference. An example of the working program is given here.

On your VM image, run:

./reference 6666 localhost:5555
[listening on UDP port 6666]

Keep the terminal open. On another terminal, run:

./reference 5555 localhost:6666
[listening on UDP port 5555]

Now anything you type on one termianl will show up on the other terminal.

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:

• Each side's output should be identical to the other side's input, regardless of a lossy, congested, or corrupting UDP network layer. You will ensure reliable transport by having the recipient acknowledge packets send back to the sender, so the sender will detect missing acknowledgments and resend the dropped or corrupted packets.

• You should handle connection teardown 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), you should send an EOF to your output by calling conn_output with a len of 0.

• You must support a window size larger than 1. The window size is supplied by the -w command-line option. It appears in the window field in data structure config_common which is passed to the rel_create function 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.

• 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.

Implementation Details

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. As server/client mode is not required, leave rel_demux alone!

• 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 connection state. A rel_t is created by the rel_create function. The library provided will call rel_create directly for you. Actually in single connection mode, only one connection is made, so this function will only be called once.

• 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:

  • 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.
  • 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 supplies you with the packet.

• rel_read: To get the data that you must transmit to the receiver, keep calling conn_input until it drains. conn_input reads data from standard input. If no data is available at the moment, conn_input will return 0. Do not loop calling conn_input if it returns 0, simply return. At the point data become available again, the library will call rel_read for ONCE, so you can read from conn_input again. When an EOF is received, conn_input will return -1. Also, do NOT try to buffer the data from conn_input more than expected. The sender's window is the only buffer you got. When the window is full, break from the loop even if there could still be available data from conn_input. When later some ack packets are received and some slots in sender's window become vacant again, call 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 gave it. 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 and when.

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 test your code against our reference implementation. Your program reliable should be able to communicate with the program reference.

NETEM

I will use netem emulator to simulate the packet loss, delay, packet re-ordering and packet corruption environment on loopback network interface (localhost) to test your program's functionality.

Setup emulator

Before you use emulator, you should remove existing emulation on it. Type following commands on your terminal:

sudo tc qdisc del dev lo root
            

The command will remove any network emulation on your lo network interface.

Packet loss

Run following command on your terminal:

sudo tc qdisc add dev lo root netem loss 50%
            

Now you have setup a emulator on your lo interface. Packet loss ratio of your lo interface becomes 50%. You can ping localhost to see packet loss ratio. Note that the 4th word in command above is "add". If you have already setup the emulator and want to modify the configuration, you should change "add" to "change".

Packet delay

Run following command on your terminal:

sudo tc qdisc change dev lo root netem delay 100ms 20ms distribution normal
            

You can refer to netem's offical page above to see other configuration command.

Submitting

To submit the assignment, add a file called README with names of your group members. Run the command make submit, this should create a file called reliable.tar.gz.

Collaboration policy

You should finish this assignment in a group of two or three.

Acknowledgement

We thank the course staff of CS144 at Stanford University for their support. This lab is adapted from one of their assignments.