CPS 114 Introduction to Computer Networks: Labs

Lab 4: Congestion control

Introduction

Your task is to complete the design and implementation of a reliable transport protocol using the sliding window protocol. You will need to implement both reliability and congestion control, but you may use your code from Lab 1 for the reliability function.

We provide you with a link emulator (relayer), a file generator (generator), and a library (rlib.[h|c]). You will implement some functions and data structures in reliable.c. rlib.[h|c] provides some useful helper functions. Your tasks include:

You will implement both the sender and receiver sides of a transport layer. The sender will read in a file (the generator can generate an file of arbitrary size), break it into fixed-sized packets (1000 bytes), add a control header to the data, and send the file to the receiver through an congested link. The receiver will read these packets, and write the corresponding data to an output file. A correct implementation must guarantee that the received file is identical to the sent file.

Figure 1 shows an experiment setup. A1 sends file1 to A2. B1 sends file2 to B2. Both files, file1 and file2, can be generated by the generator. These connections share the bottleneck link L, which is emulated by the relayer code we provide. You are required to implement a congestion control algorithm that efficiently and fairly utilizes L's capacity.

Figure 1: dumbbell topology

In lab 1, you have implemented a duplex sliding window protocol. For this lab, you only need to implement one-direction data transfer. For instance, in Figure 1, A1 runs in the sender mode and sends data to A2. A2 runs in the receiver mode, and will only send ACK packets (not data packets) back to A1.

Getting started

You should be able to finish your assignment on any machine in the department's linux cluster: linux.cs.duke.edu. linux21-30 is recommended for the relayer. If you prefer to finish the assignment on your own machine, you may download and install ubuntu. You can run Ubuntu in a virtual machine such as the free VirtualBox software. We do not support MAC or Windows. Sorry.

Download and untar the lab4.tar.gz. 

xwy@linux21$ wget http://www.cs.duke.edu/courses/spring10/cps114/labs/lab4/lab4.tar.gz
xwy@linux21$ tar xzvf lab4.tar.gz

There are three components in the tarball: (1) generator, (2) relayer, and (3) the reliable directory. You can use following command to generate arbitrary size of file 

xwy@linux21$ ./generator <file size in byte> <file name>

The relayer emulates link L in Figure 1. You can set the relayer's parameters in the configuration file config.xml. Presently, this config file shows the configuration in Figure 1. The relayer supports the following configuration parameters:

After finishing these configurations, you can start the relayer on linux25 with the following command: 

xwy@linux25$ ./relayer config.xml

Next, you need to set up receiver A2 on linux22 and receiver B2 on linux24. First run make to compile the reliable. Then run 

xwy@linux22$ ./reliable -r output1 -w 200 20000 linux25:50002
xwy@linux24$ ./reliable -r output2 -w 200 40000 linux25:50004
The "-r" option puts this reliable instance in the receiver mode where it should only send ACK packets back to the sender but not data packets. The "output1" and "output2" options are the output file names. The "-w 200" option sets the receiver's max receiving window size to 200 packets. The rest of the options are the local port, the relayer's DNS name, and the corresponding relaying port that connects to the reliable instance.

The last step is to set up the sender A1 on linux21 and sender B1 on linux23. Run 

xwy@linux21$ ./reliable -s file1 10000 linux25:50001
xwy@linux23$ ./reliable -s file2 30000 linux25:50003
Similarly, the "-s" option puts this reliable instance in the sender mode, in which it will read in file1, break it into fixed-sized packets (1000 bytes), add a header, and send packets to the receiver. The rest is the reliable's local port, the relayer's DNS name and port number. The "-w" option is optional. You can either explicitly tell the sender the receiver's max receiving window size by the "-w" option, or in your protocol, the receiver tells its max receiving window size to the sender.

By now you have established Figure 1's topology. After you implementing the sender and receiver correctly, A1(on linux21) will send file1 to A2(on linux22), and A2 will write the received data to output1. B1(on linux23) will send file2 to B2(on linux24), and B2 will write the received data to output2. To simplify the configuration, you may run all the above components on one machine.

Understanding the code

Packet format

There are two types of packets, Data packets and Ack-only packets. You can tell the type of a packet by length. The length of a data packet varies from 16 to 1016 bytes, and ACK packets are of 12 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 rwnd;  /* Ack and Data */
          uint32_t seqno; /* Data only */
          char data[1000]; /* Data only; Can be less than 500 bytes*/
        };typedef struct packet packet_t;

The length, seqno, ackno and rwnd fields are always in big-endian order (use htonl/htons to write and ntohl/ntohs to read):

Most fields are exactly the same as in Lab 1. Here we add another field "rwnd" in both data and ack packet header. Receiver can use this field to tell the sender the size of its receiving window, and the sender can adjust its sending window according to this rwnd.

Requirements

To complete this lab, you need to first modify a few places of your lab1 code to implement reliability with the new packet header format. You can use diff to check if the received file is exactly the same as the original file. Then you will need to implement congestion control.

In your document, you should describe your congestion control algorithms clearly. You can borrow ideas from RFCs and research papers. But you may still need to adjust some parameters, or modify the existing algorithms. In your writeup, you should justify your design choices. You are also required to analyze the performance of your algorithm. For example, in Figure 1, A1 sends a 100MB file to A2. B1 send another 100MB file to B2 at the same time. (1) How much time does each transmission take? (2) What is each sender's throughput? (3) Does your algorithm fully utilize the link's bandwidth? (4) Is the bottleneck link shared fairly by the two senders? For example, Figure 2 shows the cwnd size and throughput under the config.xml configuration. What can you tell from these Figures? (5) You should draw your own figures and analyze them.

Figure 2: cwnd and throughput

You may find the following references helpful for your design and analysis.

Functions and data structures you need to implement

For this lab, you are also required to fill the 6 functions you have done in Lab 1. There are some small changes.

Submitting

There is no test case for this lab. You are required to write up a lab document to explain your protocol design and performance analysis. To submit the assignment, do the following:

Collaboration policy

For this lab, you can form a team of two students to complete the assignment. If your code does not pass all lab1 tests, finding a partner whose code did will be very useful. You can discuss with anyone, but you must not look at other teams' code, or copy code from other teams.

Acknowledgment

The skeleton code of this lab is taken from this assignment.

Last updated: 04/2010