The materials in this lab come from various sources, including textbooks and websites. A partial list of textbooks that contribute to the ideas in the lab include our textbook Computer Networking: A top-down approach by Kurose and Ross, Computer Networks by Tanenbaum, and Computer Networks by Peterson and Davie. The code for CRC Model comes from the paper and discussion by Ross Williams on the subject.
In one of our earlier labs, we learned how to use internet checksum to test if a piece of data contains any error. While checksum can detect bit errors, Cyclic Redundancy Check, or CRC, can detect and correct many more errors than internet checksum can, as we discussed in the class. In this lab, we will learn how CRC can be used to detect errors.
We will use a set of three UDP socket programs to accomplish this task. The first program, source., sends a piece of data to a gateway (gateway.c), before reaching the final receiver (sink.c). When data is sent from the source, a CRC is computed and sent as a part of the data. The gateway, acting as the simulated network media, randomly determines if the data will be altered before being forwarded to the sink. After receiving the data from the gateway, the sink checks to see if the data is correctly received by computing the CRC again using the same algorithm and generating function as those used by the source. (The sink and source have to agree on which algorithm and generating function to use before exchanging data.)
The basic idea of a checksum is for the sender to compute a checksum value using certain algorithms. The checksum is then sent along with the data. When receiving the data along with the checksum, the receiver performs a checksum computation to see if the data has been altered. The simplest mechanism is a parity check, one that computes the number of one bit (or zero bit), the checksum bit is then added to the data to make either an odd parity or even parity check. The internet checksum, as we learned, is an algorithm that is a step further from the simple parity check algorithm. A more elaborate and effective checksum mechanism is Cyclic Redundancy Checksum which is based on the algebra theory. That is, if the remainder R(x) results from D(x)/G(x), where D(x) is an n bit data, G(x) is an r+1 bit generating function, and R(x) is an r bit sequence, then the data sequence D(x) with R(x) attached to the end, effectively S(x) = D(x)*2^r+R(x) will be received by the receiver. When the receiver performs the same division operation S(x)/G(x), the remainder should be 0. If the remainder is not a zero, the data received contains error(s).
While the basic idea of CRC as a checksum is not very complicated, the implementation of CRC in any programming language does involve many engineering challenges, mainly because CRC may not always be at the boundary of a byte and the fact that one has to shift through each bit of the data to compute CRC. You will find many interesting CRC computation related discussions and solutions on the web. Here we will use one of the well-known solution by Ross Williams.
In this lab, you will create a collection of three UDP programs, source.c, sink.c and gateway.c, so that the source sends a message of certain length along with a CRC to the gateway, which in turn forwards data to the sink. The gateway can randomly alter the message with certain probability. The sink will be responsible for checking the errors in the message using CRC. The sink simply prints the result to its screen, reporting either an error, or the message is received correctly.
We list the tasks as multiple problems to help you solve the problem in pieces. You could do it in one step if you feel comfortable about your solution.
Copy all files from ~cs363/Spring16/student/labs/lab08/* You should see a set of seven files. The use of these files will become clear as you work through the lab exercises.
Create the trio source.c, gateway.c and sink.c so that the message is sent from the source to the sink, via the gateway. For now each of the three programs can print a simple message such as Message sent in xxx bytes. or Message received in xxx bytes.. Use UDP sockets so the programs don't have to be connection based. Use your assigned port numbers for the first two programs, and use port + 100 for your third program.
The invocation of the programs may look as follows.
The order of running the program should be sink first, then the gateway, then the source. You can run all three programs on the same terminal by putting the first two programs to the background.
In this part of the lab, no error checking is used, though you could have the sink to print the message, or the length of the message, or both to indicate the programs are working fine.
Revise the source.c so that instead of just creating a message of certain length, the source opens a file from the name given at the command line using the system call open and send the content of the file to the gateway. The general strategy is as follows.
You can try the program with any files, text or non-text. You can certainly try your programs on the files that you copied from the lab directory, Declaration of Independence, or Lincoln's Gettysburg Address, or the image file JLH.jpg. The last file should cause the program to stop because its size is larger than what a UDP packet can handle.
As mentioned before, implementing a CRC program can be involved. We will use Ross Williams's solution in our lab. Read a bit the paper by Ross Williams at the following website. The point is to give you a sense what is involved in computing a generic CRC.
http://www.ross.net/crc/crcpaper.html
Next read a bit more the file crcmodel.h, especially, the section "How to Use This Package" where Williams discussed how to set up and use the program. Once you understand how to use Williams's program, create a program called crctest.c following Williams's instruction that can test the CRC model program. (The Makefile you received already contains an entry for the target crctest.)
make
./crctest
After your crctest is working correctly, your task is then to create a function that your program could call from source and sink when a message is prepared to be sent to the gateway, and when the message is received by the sink. The API for this function should look something like this.
unsigned int generate_crc(char * buffer, int len)
where the buffer parameter is the data for which you try to generate the CRC, len is the length of the data. Note that though we use char * as the type for the parameter, the data could be binary. Thus a separate variable len is needed because we can't rely on the likes of strlen() to compute the length of the data for us. The function returns the computed CRC that can be used by the calling function.
It might be the easiest if you simply copy the file crctest.c to be something like crc-api.c and revise the main() function in crc-api.cgenerate_crc(). You will need to remove unnecessary activities in the current main() function to make it a stand-alone function.
Once the generate_crc() is written, you need to call it within the source.c right before sending the message to the gateway. As a matter of fact, you need to generate the CRC for the message and attach the generated CRC as a part of the message (trailer). How do we attach the CRC to the end of data (an array of bytes)? One way to accomplish the task is to allocate extra r bytes for the message buffer. Assume the length of the text to be sent is n. Then you'd need to allocate n+r bytes, where the first n bytes are for the data and the last r bytes are for the CRC. Once the data is read into the buffer, you can attach the CRC to the end of the data by the following mechanism.
memcpy(&(buffer[n]), &crc, length_of_crc)
where length_of_crc should be r. We have done similar buffer manipulations a number of times so far in other exercises.
Your next task is to revise the sink.c so that the sink will determine if the data is correct by computing the CRC checksum that comes with the data. If the data is not corrupted, the checksum now should be zero. If a non-zero checksum is the result of the computation, an error exists. The sink should report it to its screen. (No correction or retransmission is involved in this exercise.)
Test your programs as you develop. Create an answer.txt to record a session or two in which both successful transmission of data without error(s) and cases when error(s) are detected. One of the tests should include the Lincoln's Gettysburg Address. Print the checksum for the text. You can use copy-and-paste mechanism, or some screen capture program such as script to record your sessions. Please do not include graphics-based screen-capture result. Also in the answer.txt please give the instructions how to compile and run your programs.
Submission
When you're done with the lab problems, make sure you remove unnecessary files, then submit the work to Gitlab.
Revise the programs so they can send and receive files larger than the UDP data size.
Congratulations! You just finished this lab.