CSE 461 Project 1

Reliable, stream-oriented communications using the sliding window protocol

Due 5:00 pm, Tuesday, 10 February 1998

Note: this assignment is to be done in groups of 2-3. There will be a graded design review session with the TA sometime during the week prior to the due date. More information on this to follow. You have four slip days which you may use as you see fit across the three project assignments.

In this assignment, you will use a network simulator to implement and experiment with reliable communication protocols. The simulator will simulate a 'typical' internet link, with variable bandwidth and latency, packet reordering, and drops. These parameters are all configurable.

What you need to implement is a reliable sliding-window communication protocol. Your protocol should be able to correctly handle dropped and reordered packets, and extract at least 80% of the potential bandwidth on the link. The potential bandwidth is defined as:

mean bandwidth * (1 - packet drop rate)

You should be able to handle drop rates between 0 and 0.25. The default network parameters are:
Paramter Default value Allowable values Flag
MTU 20 bytes ?
Bandwidth 1.0 Mbit/sec 1.0 - 100.0 Mbit/sec bandwidth=<value>
Bandwidth SD 0.2 Mbit/sec 1/5 bandwidth -no-bandwidth-variation
Bandwidth Walk 0.5 0.0 - 1.0 bandwidth-walk=<value>
Latency 2 ms 1 - 100 ms latency=<value>
Latency SD 0.5 ms 1/4 latency -no-latency-variation
Latency Walk 0.5 0.0 - 1.0 latency-walk=<value>
Drop Prob 0.25 0.0 - 0.25 drop-prob=<value>
Turning off latency variation prevents reordering of packets. SD is standard deviation (the quantities are normally distributed). Walk is the tendency of the value's mean to walk with time. 1.0 is the maximum, 0.0 will keep the mean fixed thorugh time.

Provided Code

You are provided with an implementation of a simple stop-and-wait protocol. This is a particularly inefficient protocol (the choice of timeout is particularly poor), and gets somewhere on the order of 2% of the available bandwidth. Nevertheless, you will probably want to use it as a starting point for your sliding window protocol. The major reason for this is that this implementation gives you a bunch of pieces which are really useful for building send and receive algorithms where all operations run in zero simulated time (which is a requirement for all operations performed in response to timeouts and packet arrivals from the simulator. The three classes which are used to buffer data between the outside world (the send/receive threads above and the network simulator below) are: These classes are required because the provided code is set up to do all of its processing in response to acks and timeouts. The simulator requires that the code that handles packet arrival or timeout firing operate in zero simulated time, because while the timeout or arrival is being processed the simulated time cannot advance, so if that process were to wait for something that won't happen until the simulated future then the program would deadlock. The rules for code which may be run in response to timeouts or packet arrival are basically:
  1. General Java code is okay, as is calling synchronized methods of any class.
  2. Setting future timeouts and canceling current timeouts is okay.
  3. Queuing data on the NetworkInterface is okay.

  4. Using the Timer Wait functions is probably okay, hasn't been tested.
  5. Using the direct interface to the network is probably okay, but hasn't been tested.

  6. Using the Java condition variable wait() is highly dangerous. It will work only if the condition will be triggered without the advancement of simulated time. This is usually not the case. If you need to do this, take a look at the way it is done by the provided classes above using the Timer registration facility.
  7. Infinite loops are a definite no-no, unless they use the Timer registration facility both to allow and to prohibit the advancement of time when appropriate. Ask Andy about this if you feel the need to do infinite processing in response to timeouts/packet arrivals.

The provided implementation does not do connection setup. It simply assumes that the sender and the receiver start at the same point. Your implementation will need to negotiate a starting sequence number.

It is hopefully clear at this point that the provided code is provided for you. You should not have to change project1.java, and you should not change the network simulator, but you may change/delete/replace any of the other provided classes as you see fit. The hope is that they will shield you from the nastiness of thread programming, but if you want to hurt yourself, go right ahead :-)

Simulator Environment

The following files make up the project: The four provided client files show how to build a client application which uses the stop-and-wait protocol to send a stream of data. You should not need to modify project1.java nor any of the simulator files. iface.java provides a useful abstraction for dealing with the timing behavior of the network simulator, you may use it if you like. The code in sender.java and receiver.java should be adaptable for use in a sliding-window protocol, and you are free to use that as well.

The easist way to operate within the simulator environment is to use the timeout mechanism described in timer.java exclusively, in the way that the sample code does. The NetworkInterface, SendBuffer and ReceiveBuffer classes can be used to insulate you from all thread sychronization issues. If you want to modify or reimplement the behavior in these classes, you should read the following note on synchronization in the face of the timer.

Compiling and Running

This version of the assignment does not use packages, so it should be easy to compile and run. Copy all the Java files to a directory, add them all to your workspace, and compile. The command-line usage is 
java project1 [<seed>] 
              [-bandwidth=<value>]
              [-no-bandwidth-variation]
              [-latency=<value>]
              [-no-latency-variation] 
              [-drop-prob=<value>]
so working inside Visual J++ you will have to set the class to run as project1 and specifiy any arguments in the entry field until Project/Settings/Debug. The flag arguments are described above, the <seed> argument is an integer that will seed the random number generator. If omitted then the seed will be drawn from the current time. By specifying a seed, you can get consistent behavior of the network, which will make bug-tracking much easier. I strongly recommend that when tracking bugs you find a seed that causes your bug and then fix it until you fix the problem. When you think your program works, try a few runs without specifying the seed.

Stat-gathering code

If you want to use my code for gathering network statistics to judge the performance of your code, grab the two files below to replace your current inet.java and project1.java.

What this code does is to set up a monitoring object which logs all the packets and computes the number and time spent in resends, number of drops, number of wasted transmissions (any transmission after the first which succeeds) and fallow time (idle time before the packet was transmitted that could have been used more productively). After the program finishes it prints out this information for each sequence number, and the totals for the whole execution. You can use this to help figure out where you are being less that perfectly efficient. I generally turn on packet tracing and debug messages to print my windows, and log my runs to a file, so that I can peruse the stats to find a problem packet to investigate, and then go back to the traces and figure out what happened to it.

Design Reviews

Design review information and signups to follow.

Turnin

To turn in project 1, do the following:
  1. Grab the file turnin.class and put it in your project directory.
  2. Make sure all your .java files should be in this directory, and no extraneous .java files are there.
  3. Make a file readme.txt in your project directory that (at the very least) gives your names, describes your algorithm, and tells us how we should run it to see it work. A sample file, which shows what I'm after, is here. Remember: we will be reading this file, and it will benefit you to tell us anything that might be helpful when grading your project. Show us that it works.
  4. In your project directory, run the command (from the command line) 
    java turnin
    (or jview turnin for Visual J++ systems). You will need to be on a machine which is connected to the internet. Be patient. The server is slow and single threaded.
The turnin program prompts you for the student ID for the "first" student in the group. I don't really care whose SID you use, but make sure that if you submit more than once you keep using the same SID to identify the group. As long as you use the same SID you can submit as many times as you like. All turnins are saved, but unless we have some reason to do otherwise we will only look at the last one.

What you get back from turnin is a short receipt listing files and sizes received, the turnin time and the number of slip days used for this assignment.

If you have any problems with turnin, be sure to mail Andy (acollins@cs.washington.edu, and/or post to the email list.

acollins@cs.washington.edu