Lab 5 - A Reliable Transport Protocol

Due - Tuesday April 5, 2011

This project will give you experience implementing a reliable application-layer protocol over UDP. While your protocol will not be as complex as TCP and will not operate at the transport layer, this assignment will give you an appreciation for the difficulty associated with implementing the components of a reliable protocol.

In your implementation of Lab 4, your proxies used TCP to exchange the contents of a web object cached at one proxy but not at another. For this lab, you will modify your proxies so that they use a UDP connection to exchange web objects, and you will implement a reliable protocol to ensure that all contents of a web object arrive at the receiver and are processed by the application in the correct order.

Requirements

1. Your application will send data in chunks of 20 bytes. Each DatagramPacket will contain no more than 20 bytes of actual data.
2. Each proxy must be capable of handling more than one connection simultaneously, for example proxy p1 may have two connections open, one to p2 who has requested object o1 and one to p3 who has requested object o2.
3. You may assume that there are no bit errors (e.g., rely on the UDP checksum to catch any bit errors), but packets may be completely lost or reordered.
4. A demonstration will be required on 4/5/2011. It is up to you to design a demonstration that provides convincing evidence that your implementation works. If you have any questions about this, plan to come to office hours to review your demonstration BEFORE the deadline.

It is up to you to design your protocol, but your grade will be based on the following elements:

1. Timeouts - Your protocol must use timeouts to detect the loss of a packet.
2. Sequence numbers - Your protocol must use sequence numbers and ensure that packets are processed in the correct order by the application. Your protocol may need to buffer packets that arrive out of order.
3. Acknowledgements - A receiver must be able to acknowledge receipt of a packet.
4. Connection setup - You must implement a handshake to establish the connection between sender and receiver.
5. Connection teardown - You must implement a procedure for ending the connection.
6. Pipelining - Your protocol must be pipelined. You may implement go-back-N, selective repeat, or a TCP-like hybrid. You will be asked to overview your chosen algorithm during your demonstration.

Hints

1. You'll need to design a way to generate loss for testing, for example you might generate a subclass of DatagramSocket that loses and reorders packets.
2. Consider starting by implementing a stop-and-wait protocol rather than a pipelined protocol.

Demo Guidelines

You will execute, at minimum, the following steps:

1. Launch p1.
2. Launch p2.
3. Launch p3.
4. Execute the necessary steps to ensure that p1 has a web object o1 cached. You can do this on the fly, or statically preconfigure p1 such that it has the cached object. Neither p2 nor p3 will have a cached copy of o1. It is suggested that o1 be a large object so that you may easily demonstrate transfer of the object.
5. Request o1 on browser/client connected to p2.
6. Request o1 on browser/client connected to p3.

Your demo must clearly demonstrate the following. It is recommended that you generously log events so that you may show how your program behaves. Your log messages need not look exactly like the examples, but they should look similar.

1. Connection setup - demonstrate that when p2 and p3 discover that p1 has a desired object, they send a message to initiate a connection, and p1 responds to the connection request.

Example:

on p2: [timestamp] Connection request sent to <p1 IP>.

on p1: [timestamp] Connection request received from <p2 IP>.

on p1: [timestamp] Connection request ACK sent to <p2 IP>.

on p2: [timestamp] Connection request ACK received from <p1 IP>.

on p2: [timestamp] Request for object <o1> sent to <p1 IP>.

on p1: [timestamp] Request for object <o1> received from <p2 IP>.

2. Sequence numbers - demonstrate that each packet has an associate sequence number.

Example:

on p1: [timestamp] Sending packet with SEQNO <number> to <p2 IP>.

on p2: [timestamp] Received packet with SEQNO <number> from <p1 IP>.

3. Acknowledgements - demonstrate that ACKs are sent for each packet. You may use cumulative ACKs or NACKs, so a single feedback packet may apply to more than one data packet.

Example:

on p1: [timestamp] Sending packet with SEQNO <number> to <p2 IP>.

on p2: [timestamp] Received packet with SEQNO <number> from <p1 IP>.

on p2: [timestamp] Sending ACK for packet <number> to <p1 IP>.

on p1: [timestamp] Received ACK for packet <number> from <p2 IP>.

4.Timeouts - demonstrate that timeouts occur when packets are lost.

Example:

on p2: [timestamp] Dropping ACK for packet <number>.

on p1: [timestamp] Timeout for packet <number>.

on p1: [timestamp] Resend packet <number>.

5. Packet reordering - demonstrate that your protocol correctly handles reordering of packets. Note, what you do when you receive an out-of-order packet depends on your algorithm. If you are implementing GBN, you will discard and you should log a message indicating this. Otherwise, you will buffer the packet. In either case, log whether you send a NACK or ACK for the lost packet. Your log messages will also demonstrate what happens when the delayed packet is eventually received.

Example:

on p1: [timestamp] Delay send of <number> to <p2 IP>.

on p1: [timestamp] Sending packet with SEQNO <number+1> to <p2 IP>.

on p2: [timestamp] Received out-of-order packet with SEQNO <number+1> from <p1 IP>.

6. Pipelining - demonstrate that multiple packets may be in-flight at any given time.

Example:

on p1: [timestamp] Sending packet with SEQNO <number> to <p2 IP>.

on p1: [timestamp] Sending packet with SEQNO <number+1> to <p2 IP>.

on p1: [timestamp] Sending packet with SEQNO <number+2> to <p2 IP>.

on p1: [timestamp] Received ACK for packet <number> from <p2 IP>.

on p1: [timestamp] Sending packet with SEQNO <number+3> to <p2 IP>.

on p1: [timestamp] Received ACK for packet <number+1> from <p2 IP>.

7. Multiple connections - demonstrate that p1 can maintain multiple simultaneous connections.

Example:

on p1: [timestamp] Sending packet with SEQNO <number> to <p2 IP>.

on p1: [timestamp] Sending packet with SEQNO <number+1> to <p2 IP>.

on p1: [timestamp] Sending packet with SEQNO <number> to <p3 IP>.

on p1: [timestamp] Received ACK for packet <number> from <p2 IP>.

on p1: [timestamp] Sending packet with SEQNO <number+2> to <p2 IP>.

on p1: [timestamp] Received ACK for packet <number> from <p3 IP>.

8. Connection teardown - demonstrate that the connection is closed when the transfer is complete.

Example:

on p1: [timestamp] Received ACK for packet <number> from <p2 IP>.

on p1: [timestamp] Transfer to <p2 IP> complete.

on p1: [timestamp] Connection teardown sent to <p2 IP>.

on p2: [timestamp] Connection teardown received from <p1 IP>.

on p2: [timestamp] Connection teardown ACK sent to <p1 IP>.

on p2: [timestamp] Connection to <p1 IP> closed.

on p1: [timestamp] Connection teardown ACK received from <p2 IP>.

on p1: [timestamp] Connection to <p2 IP> closed.

Submission

1. By the deadline, all source code and documentation must be checked in to SVN at /<username>/cs621/lab5.
2. A demonstration, to be scheduled on 4/5/2011, is required. Failure to demonstrate your work will result in a deduction of up to 20%.
3. Your class files must be packaged into a jar named lab5.jar. This jar file must be at the top level of the lab5 directory (i.e., https://www.cs.usfca.edu/svn/user/cs621/lab5/lab5.jar).
4. Provide a README that clearly indicates how to compile and run your program.
5. Late projects will receive a score of 0.
6. Projects that are submitted incorrectly will receive a deduction of up to 20%. This includes incorrectly named directories and missing source files. Double check your submission!