Lab 04: Passing Structured Data Through Network, Computing UDP Checksum



The material developed for this lab was developed by Professor Felipe Perrone (Bucknell University). Modified by Professor Xiannong Meng. Some of this lab is based on material from Unix Network Programming Volume 1, by W. Richard Stevens, Bill Fenner, and Andrew M. Rudoff (Addison Wesley, 2004).

Permission to reuse this material in parts or in its entirety is granted provided that the credits note is not removed. Additional students files associated with this lab, as well as any existing solutions can be provided upon request by e-mail to perrone[at]bucknell[dot]edu.


So far we have practiced passing information such as a string or a number across the network using TCP or UDP. The general programming pattern of accomplishing such a task is as follows. On the sending side:

bytes_sent = sendto(sock, buffer, length); /* sending side */
On the receiving side, if we know the length of receiving, such as the size of an integer, we'd do the following.
bytes_received = recvfrom(sock, &intval, sizeof(int));
If we don't know the exact size of receiving, we'd set a limit on the receiving size. If a text string is the incoming data, we typically need to terminate it.
bytes_received = recvfrom(sock, buffer, MAXLENGTH); /* receiving side */
buffer[bytes_received] = 0;
Alternatively, the sender can terminate the string by itself and send the NULL byte as the part of the string.
char * buffer = "hello, world!\0"; // 13 chars plus '\0'
bytes_sent = sendto(sock, buffer, strlen(buffer)+1);  // send the '\0'
However, how do we send a linked list of data across the network? In principle, there is no difference in sending a string or sending a structured node. As far as the network is concerned, they are all a collection of bytes. What we need to do is to traverse through the linked list on the sending side, pack each node into a sending buffer, and send the buffer over as a byte stream. On the receiving side, the receiver need to save the data into a buffer and reconstruct each node and the entire list. The key here is both sides have to share the structure of the list node.

In this lab, you will exercise how to send and receive linked lists over the network.

The second component of the lab is to compute the internet checksum. We learned the checksum concept and algorithm in the context of UDP. We called it UDP checksum. The same idea applies to various protocol layers such as the network layer. Thus we also call the checksum internet checksum. The basic algorithm to compute the checksum is described in the textbook and discussed in our lecture. We apply consecutively one's complement sum to each of the 16-bit unit in the entire UDP packet, including the header and the data. At the end, we invert the computed value to arrive at the checksum. Your lab work will develop a function that computes the internet checksum for a given collection of byte.

The third part of the lab is to actually use the checksum function developed above to construct UDP packets to send and receive packets. The sender computes the checksum, inserts it into a UDP packet, and sends the packet to a receiver. The receiver, upon receiving the packet, computes the checksum using the same algorithm. If the resultant checksum is zero, the packet is considered received correctly. Otherwise some errors occurred to the packet.


Create a directory in your local git repository called lab04, as in


Copy all files from ~cs363/Spring16/student/labs/lab04/ to your own lab directory. You should see six files, list.h and list.c that implements a basic linked list, a pair of TCP client/server programs, which are the same as what you see at the course website, and two programs related to checksum. One is called test-checksum.c, the other is called inet-checksum-skeleton.c. You don't have to use the list programs or the client/server programs if you have your own linked list implementation or your own TCP client/server programs.

Create an answers.txt text file that will contain your answers to some of the questions in the lab exercises.

Problem 1: Sending structured data over the network

In the past exercises, we have learned how to send character strings between network applications. A typical application scenario in which a sender sends a string of characters pointed by the variable buf to a receiver looks as follows.

On the sender side:

char * buf = "hello world!"
size_sent = write(s, buf, strlen(buf));

On the receiver side:

char * buf = (char*)malloc(MAXSIZE+1); // don't know the size ahead of time
size_read = read(s, buf, MAXSIZE);
buf[size_read] = 0; // terminate the string

Now consider how we might send structured data that are not simply string of characters! For example, if a structure which can be used in a linked list is defined as follows.

If your program has a collection of data of the struct node_t type, how do you send such a collection of data from a sender to a receiver? In this part of the lab, we will exercise on this topic.

Let's first consider how to send one such piece of structure to a remote computer. Assume we are using TCP (UDP programming would be very similar), and you have established a connection between the sender and receiver properly. The general idea is that the sender will send a collection of memory bytes representing the data to the receiver. This collection of memory bytes starts with the memory location where the variable resides and the length of this collection is the size of the structure.

The key to solve this problem is to access the correct memory location where the data is stored. There are two possible ways to access the address of a variable. One is to use the address of operator ("&") to get the address of a variable; the second is to directly use the address of a variable assigned when using malloc() or calloc() calls. The following code segment in TCP illustrates the concept.

The receiver side can simply read the data into a properly defined variable of the same type.

How do we send a linked list of such nodes? The approach is to have the client traverse through the linked list from beginning to end, sending one node at a time to the server. Since we don't know the number of nodes in a linked list ahead of time, the server (receiver) side would have to loop until no more data is coming.

An alternative way to send or receive structured data is to store the received data in a generic buffer. When all is received, the receiver can recover the structured data from the generic buffer. Try the following. On the client side, send one structured node as it was in the previous step. On the server side, instead of reading the data into the structured variable, define a generic buffer char * buf;, allocate a maximum amount of memory to it, e.g., define and use a constant BUFFSIZE of 4096 bytes. Once the data is read into the generic buffer, it can be casted as a piece of structured data as follows.

In your answers.txt explain how the last C statement works, in particular, what the phrase &(buf[total_count]) mean. Mark this answer as Problem 1.1.

Now that you have a basic understanding how to pass structured data across the network, complete the lab exercises so that the client sends a linked list of structured data to the server. The server stores the received data in a generic buffer first, then recovers the linked list and prints out the contents.

Just for fun, you may consider sending the following Confucius quotes from one computer to another using the structure defined earlier in this lab. The variable len can be changed to count as an index, the variable rate can be used to indicate a ranking. Each node in the linked list should contain one statement of Confucius that is between a pair of quotes. You don't have to use these quotes. Feel free to use any other you see fit. The exact meanings of these variables are not critical. The key is to pass a linked list of nodes, where each node contains a string (a quote), an integer, a double, and a character.

Note that although the following example asks you send five nodes only, your program should be able to handle arbitrary number of nodes.

In your answers.txt write the appropriate answers to questions below (not all need a text answer, as some will be segments of programs.) You are asked to accomplish the following tasks, one at a time.

  1. Create a simple C program called test-sizeof.c. In the program use the sizeof operator to find out how many bytes of memory a structure defined above (struct node_t) occupies. Explain why such a node takes this many bytes. Mark the answer as Problem 1.2.
  2. Copy tcp-client.c to list-sender.c, and tcp-server.c to list-receiver.c. Create an appropriate Makefile. Revise the programs so that the client is able to send one structure to the server and the server is able to retrieve the values in the structure by printing the information within the structure on the screen on the receiving side. In your answers.txt briefly explain how your program works to send and receive one node at a time. A few sentences suffice. Mark the answer as Problem 1.3.
  3. Revise the program so that the client can send a linked list of structures to the server and the server is able to retrieve the data one node at a time and print the information on the screen. In your answers.txt briefly explain how your program works to accomplish this task. A few sentences suffice. Mark the answer as Problem 1.4.
  4. Revise the program so that the receiver uses a generic buffer to store the data first, then recovers the structured data back into a linked list.

Clean up the files by removing all object files, executable files, backup files, etc. by calling proper make object. Add and commit all your files to your git repository before continuing.

Problem 2: Computing internet checksum

The basic algorithm of computing internet checksum is described by an example in our textbook on page 203, and it was discussed in our lectures. Here is an outline.

You are given a test program named test-checksum.c and a skeleton program inet-checksum.c. In the program test-checksum.c you will see that three test cases are given. You should not change anything in this program. You are supposed to complete the function inet_checksum() based on the above algorithm. Feel free to consult the internet and discuss with your classmates. But you need to actually write the code yourself.

Here are some relevant information with which you may or may not be familiar.

After completing the function inet_checksum(), compile and run the program test-checksum.c. Correct any errors in your implementation of inet_checksum(). Include the screen output of compiling and running the program test-checksum.c in your answers.txt and label it as Problem 2.

Clean up the files by removing all object files, executable files, backup files, etc. by calling proper make object. Add and commit all your files to your git repository before continuing.

Problem 3: Sending UDP packets through simulated network

Equipped with the UDP (or internet) checksum function, you are to build actual UDP packets and send them through network using a TCP connection. You will use a pair of TCP client/server program as your medium. (You can simply use the pair tcp-client.c and tcp-server.c.) In the client program, you build a UDP packet and send it to the server. The server sends the packet back with or without a bit alteration. The client is to check the correctness of the echoed packet using the checksum coming with the UDP packet. Here is an outline of the algorithm of the client side.

On the server side it looks like as follows.

In order to make UDP packets, you'd need to define the packet structure as follows (you can find the information from /usr/include/netinet/udp.h). First define the UDP header,

Then define the entire UDP packet,

You can define the constant MAXUDPSIZE as 65527 for this exercise. Explain the reason for the value of this constant. Also can you elaborate the differences between defining an array here as the data and defining a character pointer and then dynamically allocating memory for it? Put your answers in answers.txt as Problem 3.1.

The function to create a UDP packet should have the following signature. You may vary it as needed. But this signature should outline the general need.

int create_UDP_pkt(uint16_t src_port, uint16_t dst_port,
                   char * data, (struct udp_packet_t *)pkt);

The meaning of the parameters should be clear. The first three parameters are given by the calling function. The last parameter is the output parameter which contains the built packet from the given data. The function should return the total length of the packet. Though the length is returned through the pkt parameter as well, it is easier to just check the return value of the function for success or failure.

The general flow is that you create a UDP packet first without the actual value of checksum, though you must initialize the checksum to be zero. You then use the function you built in Problem 2 to compute the checksum and set the checksum value in the UDP packet after the UDP packet is built.

Explain why you have to initalize the checksum in the original UDP packet to be zero. If the initial checksum takes other value, what might happer? Put your answers in your answers.txt, mark it as Problem 3.2.

Recall the UDP checksum can be used easily to see if a packet is corrupted. In our case, the receiver side (the client) will simply compute the checksum against the received packet. If the resulting checksum is zero, the packet is not corrupted. Otherwise it is.

The exercise is to send and receive UDP packets with their checksums. You need to create a client program that sends UDP packets to a server program. The server program sends back the packet, possibly with a bit flipped. The client program then checks received UDP packet from the server to see if the packet is corrupted using UDP checksum. Print an appropriate message for each echoed UDP packet the client receives from the server.

Name your client program udp-sender.c which should be a TCP client program, and your server program reflectord.c which should be a TCP server program. Complete the pair of programs for their functionality. Run the program multiple times and show the checksum can catch errors when the server decides to flip a bit in the packet. Copy and paste the screen output on the client side to your answers.txt and mark it as Problem 3.3.

Clean up the directory by executing make clean, assuming you have created an appropriate Makefile. Add, commit, and push all files to your git repo.

Congratulations, you've finished this lab!