Untitled Document

CIS 410/510 Introduction to Computer Networks
Fall 1999

Program 2: Selective Acknowledgments

Handed Out: 11 November 1999
Due: 30 November 1999 online by 5pm

May be done in groups of 2 or 3. See the syllabus for restrictions.
Because this is group work, any program that fails to compile or that crashes will be given a 0.

Overview

You will write a file transfer protocol that uses selective acknowledgments to achieve reliability. The selective acknowledgment (SACK) protocol will be implemented on top of an unreliable UDP socket interface. By varying the error rate of the socket interface, you can test whether your SACK reliability mechanism is working properly. Once you have completed the programming portion of the assignment, you will do some simple experiments to compare the performance of SACK with ARQ.

SACK Protocol

The selective acknowledgment (SACK) protocol consists of three parts:

Opening Handshake
Before transferring any data, the client executes the following code to be sure the server knows which sequence number it is starting with:
- Send an open packet to the server including an opening sequence number and set a timer. The opening sequence number is chosen randomly.
- If the client receives an open ack, start the file transfer.
- If the timer expires without receiving an open ack, resend the open packet.
- Resend the open packet forever if an open ack is never received.
Meanwhile, the server executes the following:
- When the server receives an open packet, it stores the starting sequence number and responds by sending an open ack to the client with the same sequence number.
- If the server receives a data packet, begin receiving the file. Any subsequent open packets are invalid and should be dropped.
- If the server receives another open packet before any data packets, store the starting sequence number again and respond with an openack.
- Any data packets received before any open packet arrive are invalid and should be dropped.
File Transfer
Once the client receives the open ack, it starts sending a file to the server using data packets. Each data packet contains up to 1000 bytes of data. The client maintains a set of outstanding packets called Out, initialized to the empty set. Each time the client transmits a packet, it adds it to Out. Likewise, when a packet is acknowledged, the client removes the corresponding packet from Out. When the size of the set falls below the window size, the client transmits additional packets to fill the window and adds them to Out. When a timeout occurs, the packet in Out with the smallest sequence number is the one that is retransmitted.
Once the server receives the open packet, it can start receiving data. The receiver maintains a set of due packets called Due. When the server gets an open packet with sequence number X, it sets Due equal to {X,Y,Z}, where Y = X + 1 and Z = Y + 1. Whenever the receiver gets a packet, it sends an acknowledgment (only for that packet). If the packet is in Due, then it removes it and adds a new packet to Due with a sequence number that is one larger than the largest sequence number currently in Due.
Closing Handshake
Once the client has reliably sent the entire file, it should do a three-way handshake to signal the end of the file to the server. The client executes the following:
- Send a close packet to the server and set a short timer.
- If the client receives a close packet, respond with a close ack and exit.
- If the timer expires without receiving a close packet, resend the close packet.
- Resend the close packet a maximum of 5 times and then exit.
Meanwhile, the server executes the following:
- When server receives a close packet, it responds by sending a close packet to the client and setting a long timer.
- If the server receives a close ack, exit.
- If the server receives another close packet, respond with a close packet again and reset the long timer.
- If the timer expires without receiving any other close packets, exit.

Note that packet loss can occur at any time during the operation of the protocol. If you are viewing a web version of this document, then you can view a diagram of the opening and closing handshakes.

For the opening handshake and data transfer phases both use timers of 100000 microseconds. For the closing handshake, the short timer should be 100000 microseconds and the long timer should be 1 second.

Comparison of ARQ and SACK

Plot the transfer time versus the error rate for both ARQ and our SACK protocol. Do this by using a large file and measuring the time it takes to transfer this file between the client and server. Vary the loss rate gradually from 0% to larger values. Repeat each measurement enough times to get a meaningful average and use enough points to get a smooth plot. Your maximal loss rate should be large enough to get a useful comparison between ARQ and SACK, but small enough so that you are not spending most of your time waiting for the protocol to try to transfer the file. Use a window size of 4.

Write a one-page (single-spaced) description of your results and turn it in with your graphs.

Graduate students should also vary the window size to see if that produces different results.

Supplied Code

I am supplying you with code that implements ARQ, which uses cumulative acknowledgments. You should copy arq.h to sack.h and copy arq.cc to sack.cc. You can then modify the sack files to implement selective acknowledgments for file transfer. Be sure to add sack.o to the appropriate places in the Makefile.

This means the opening handshake and closing handshake are already written for you. In addition, the supplied ARQ code implements sequence number wrapping and an Internet-style checksum. You should preserve these features in your solution.

The supporting files are in:


   /cs/classes/cis510networks/program2

These files include:

Makefile	Has the information needed to compile the programs. You should first type make depend to create dependencies (be sure mkdep has execute permission). This will allow you to recompile only the necessary modules when you change a file. To compile the programs, type make. To remove any object files, type make clean.
client.cc	The client does argument parsing for parameters relevant to the reliability protocols (ARQ or SACK) and then sends a file to the server. Possible arguments are listed in the code. Your client should be able to use either ARQ or SACK to transfer the file.
server.cc	The server operates like the client except it receives a file instead of sending it. Possible arguments are listed in the code. Your server should be able to use either ARQ or SACK to receive the file.
udp_socket.h/.cc	Defines a UDP socket interface. This will create a UDP socket between the client and server, then allow you to send and receive data over this socket. The data transfer over this socket is unreliable. Note that because you will be using the socket over a single link, you may not see any real packet loss. To allow you to test your protocols in a truly unreliable environment, the socket interface allows you to emulate unreliability through a set of parameters. These parameters are:
packet.h	Defines formats for the packets exchanged by the client and server.
arq.h/.cc	Defines the ARQ file transfer protocol. This protocol operates as described in the book, with cumulative acknowledgments.
cache.h/.cc	Defines a packet cache. This is used by the ARQ protocol to cache a windows' worth of packets. You may reuse this code for SACK if you like, but it is not required.
random.h/.cc	Interface to a random number generator, used by ARQ and the UDP socket interface.
debug.h/.cc	Functions that help you to print debugging comments.

See the files for more details.

Error Checking

The following lists the packet errors you should check for. If one of these errors occurs, ignore the packet and print out an error message using the methods in debug.h. The error must be printed using text exactly like the errors printed in the ARQ code.

Short Packet (amount of data received is less than the size of a packet)
Bad Packet Type (if you expect an ack and get something else)
Bad Sequence Number (sequence number of an ack is not one that you need)
Bad Checksum (checksum of data packet doesn't result in zero)
Late Ack Packet (you send data then wait for an ack and none arrive)
Late Close Packet
Late Open Ack Packet

Keep in mind that there may be multiple places where you need to check for these errors. You must also check for failure of every system call that you use and, if a failure occurs, use the perror() system call to report the error and immediately exit the program.

Debugging

You must use the debugging interface defined in debug.h to print out any debugging comments. This way you can turn off the extra comments via the command line.

Output

Your server program should print out the file being transferred (to standard output), along with any error messages that occur. The client should only print out any error messages that occur. Grading will be based on exactly matching the output of a solution program that runs as described in this handout. You can find sample output in the class directory so you can test your program's abilities.

Deliverables

You should submit all your source code (including the files I have supplied). The code should be documented. Do not submit any object code. Use the submit program documented in the Assignments section of the class web page. You should also turn in a hard-copy of your graphs with a page of text explanation of your results. You can do this by putting the papers under my door.

Grading

During grading, I will run your client and server and check if it transfers files according to the selective acknowledgment protocol. I will check to be sure your client and server interoperate with a solution client and server. Borderline grades can be pushed up or down a level by the quality of the documentation.