Corporate and Professional Publishing Group

An Engineering Approach to Computer Networking

by S. Keshav

ISBN 0-201-63442-2 * Hardcover * 688 pages * 1997

Book Description · Preface · Glossary · Bibliography · Solutions · Slides · Simulator · Exercises · Errata · Cover (73K) · Ordering Information · C&P Welcome Page.

Error Control

Goal

In this assignment, you have to modify the supplied template (called ecn_error.c) to perform error control. You have to add two kinds of error control to the code. First, you have to detect and correct bit corruption using a Hamming (7,4) code. Second, you have to use timeouts and retransmissions to corect for lost packets.

How to do the assignment

First, read Chapter 12 of the textbook. Pay particular attention to Sections 12.2.3 12.4.6 and 12.4.7.

Files

In this assignment you will use the REAL simulator as before. Your code should be in a file called "sim/sources/ecn_error.c". This files contains a node that does error control. The name of that function should be "ecn_error()" (similar to "ecn_dummy.c" and "ecn_dummy()").

Put the file "ecn_error.c" into the "sim/sources" directory (see below), and the file "link_state.l" into the "sim/ecn" directory (these have already been done on turing. If you have your own makefile, you will need to make the changes shown below).

Add the following lines in the two makefiles:

    "sim/sources/makefile":

        functions = ecn_error.c
        functionobj = ecn_error.o

    "sim/makefile":

        sourceobj = sources/ecn_error.o

Note: you may have to do "make depend" to create necessary dependencies for the
new files.

Details

The node function in ecn_error.c has to be modified so that the sender reads data from a file and places the data in a packet's data field. (If there isn't enough data to fill a packet, the packet->size field should indicate the actual number of bytes in the data field.) The data field in the packet is corrupted by the transmission line. To see how this happens, look at the code in kernel/channels.c. The input file is called ecn/error.l. The parameters loss_prob, corruption_prob, and loss_burst_size control the error and corruption characteristics of the line.

To detect and correct bit corruption, each 4 bits in the input file should be encoded in a 7 bit perfect Hamming code. For the purpose of the assignment, you may waste one bit per byte, so that each nibble in the input file corresponds to a byte in the packet.

In order to recover from lost packets, you should use the packet loss detection and correction techniques described in Chapter 12 of the text. For the assignment, you may ignore the choice of ISN, and just use 0.  ACKs carry a cumulative acknowledgment in the sequence number field. The receiver keeps track of the sequence numbers of the packets it has seen. These allow it to compute the last-in-sequence packet, whose sequence number it places in the cumulative acknowledgment. For example, if the receiver receives packets 1,2,3,4,6,7 in that order, the cumulative acks should carry sequence numbers 1,2,3,4,4,4. To help you, the template defines an array called seen, of size MAX_WINDOW_SIZE. The receiver should mark this array at position  seq_no % MAX_WINDOW_SIZE every time it sees a packet with a given sequence number or seq_no. Continuing with the example, if seen is of size 10, then the receiver would have marked positions 1, 2, 3, 4, 6, and 7. On receiving a packet with sequence 5, the cumulative ack would increase to 7, and the receiver would reset positions 1-7, so that subsequent acks carry a cumulative ack of 7 (at least).

The source should set a timeout every time it sends a packet, where the timeout interval is a function of the measured round trip time. More precisely, a source should measure round trip times and set a timeout for 2* smoothed RTT every time a packet is sent. If the timer for a packet expires before an acknowledgment for the packet is received, the source should retransmit the packet. For example, if packet 4 is timed out, on a timeout, the source should retransmit the packet.

The file to transfer to the destination node is the ecn_error.c file itself. The destination node should copy out packets to a file called ../tnew. To see if your protocol works correctly, use

                        'diff sources/ecn_error.c tnew'.

Send data from the source at the rate of one packet per simulated second. Set the line speed to 8000 bits/second. The packet data field should be 500 bytes long (= 4000 bits). The ack data size should be 0.

Every time the sender sends data, it should print out the following:

• TIME Sender (node 1) (SEQ NO) -->

where TIME is the current time and SEQ NO is the current sequence number (incremented by sender each time a packet is sent).

Every time the receiver receives data, it should print out:

• TIME Receiver (node 2) <-- (SEQ NO), SEQ_NO .

The receiver should print an error message on detecting packet loss or corruption.

Every time the sender receives an ACK, it should print:

• TIME Sender (node1) <-- ACK (CUMULATIVE SEQ NO)

It should also print out the sequence number of the packet retransmitted on a timeout.

The template file has quite a bit of the solution in it. I actually tested the solution, and deleted some lines from it, so you can be sure that that a solution exists!

What to submit (IMPORTANT)

• You should send in only one file "ecn_error.c" by email (to snorri@cs.cornell.edu). Don't send it as an attachment.
• Your submission should print out the events described above. We will not test you on the format of your printfs, so it doesn't matter if you have additional printfs in the code (the template file already has quite a few debugging printfs).
• Don't uuencode it and don't tar it.
• In the previous assignments some students have sent binaries, don't do that.
• The body of the email should only contain the C file (no comments from you).
• Don't use C++ comments (use /* ... */ but not // ...).

Grading

To test your solution, we will do a diff as described earlier. Grades are all or nothing.