CSE 461 Autumn 2006
Homework 5: Transport Layer Design / Implementation

FAQ

• Bug report / fix:
  The symptom of the bug is that fewer unacknowledged packets are allowed on the wire than one might expect, given the value of MAX_IN_FLIGHT.

  At about line 623 in UW_461Socket.java we have to move the computation of the upper bound for the loop out of the loop. Here is the new code. The changes are the line initializing enabledCount just before the loop starts, and the use of that variable as the upper bound in the loop:

      // activate packets that are newly eligible for transmission
      enabledBase = lastEnabledPacketID;
      int enabledCount = MAX_INFLIGHT - (lastEnabledPacketID - lastAckNoReceived + 1);
      for (int i = 1;  i <= enabledCount; i++ ) {
          if ( !sendPacketBuffer.isInList(enabledBase+i) ) break;
          Thread pSender = new Thread( new packetSender(enabledBase+i, this) );
          pSender.start();
          lastEnabledPacketID++;
      }
  

• Hi, I downloaded the v0.9 source for the project. I extracted all of the files onto attu, but when I just call make I get 15 errors complaining that such and such package does not exist. Am I doing something wrong or is there just something java wants me to do before it will realize the folder/package structure?

  I build under cygwin, so the makefile uses classpath syntax for it. Unfortunately, the syntax under Linux is different. Change the semicolon in the classpath argument to javac in the makefile to a colon.

Version History

• V1.0.4 - 11/18/2006
  This version allows you to run your transport without using a reflector: simply start the sender and receiver without specifying a reflector argument.
  In the surprising case that you have already begun modifying the skeleton code, here are diff outputs of the changes: SendFile.java, ReceiveFile.java, UW_461Socket.java.

• V1.0.3 - 11/16/2006
  On the downside, slightly more than minor changes have been made. On the upside, the code is now both simpler and more robust.

Teams

Work in teams of 1 or 2.

Overview / Goal

The skeleton code implements a connection-based, reliable, datagram-oriented protocol using stop-and-wait. Needless to say, its throughput is terrible when the RTT is anything but trivial, i.e., basically always.

Optimize the throughput characteristics of the protocol. Your goal should be for a connection using the protocol to be able to achieve very high throughput for itself, under as wide a range of real conditions (e.g., RTT's and bottleneck link bandwidths), as possible. Unlike TCP, you're not worried that if your implementation ignores congestion control it might render the Internet unstable. (Whether or not that means you should completely ignore explicit congestion estimation and reactivity in your protocol is an issue for your design.)

Methodology

To speed things up, you need first to know what the bottleneck is - which part of the design is currently most limiting performance. As the skeleton code implements stop-and-wait, it's pretty clear that that is the limiting factor. Once that is addressed, though, it is much less clear what comes next.

"If it ain't broke, don't fix it." If it isn't the bottleneck, improving it won't result in much gain. It's crucial to try to identify the performance bottleneck before working on some change, so that you don't waste your time working on something that seems like it should be the issue but that isn't.

The methodology suggested by the web/writeup pages of the RFID assignment would be a reasonable approach here: analyze what you're currently obseving, hypothesize how to best improve the bottleneck (including convincing yourself why the altered system should be faster), and then try it by implementing.

The Testbed

To help test your design, the skeleton code includes a file transfer application. (That application runs on top of your work, the transport -- the assignment is not about file transfer, so don't modify the file transfer application to try to improve performance that way.) It has two components, SendFile and ReceiveFile. Both components are capable of communicating using a number of protocols:

• using native UDP or TCP directly across the Internet
• using versions of UDP and TCP that connect the two sides through a remote reflector
• using your protocol, directing packets through a remote reflector

The command line switch names for the protocols are udp, tcp, uwudp, uwtcp, and uw461. The first two use the native protocols, without reflection. The uwXXX protocols use reflection.

These alternatives should help you assess how well your protocol is doing, and what the bottlenecks might be (e.g., protocol design limitations vs. CPU costs of our Java implementation vs. the network).

Reflectors run on Planetlab nodes. The status of the nodes we're using is here. (The set of nodes in use will change perhaps frequently, so check that page from time to time.) The refelector code is supplied, so you can also run one yourself. That might be useful while debugging.

Information on command line options for invoking the sample application and the reflector are available using their -? switch.

The Source

Java Version

The source has been developed using Java 1.4.2_13. It has been built and run on Java 1.5 (e.g., attu), but got a warning about use of a deprecated interface.

Build Procedure

To build, just say make in the root directory of the source. That does a clean, and then builds make.java, which imports most everything and so forces it to be re-compiled. I think. You should also be able to just re-compile make.java to build, but neither I nor anyone I've talked with understands what Java is doing for builds. I've used make many (many) times with no problems, though.

Technical Project Management

When you turn in your code, we must be able to build it, and to execute the sample application, in the same manner we could for the initial distribution, so that we can script testing. Do not do anything that breaks that. Common examples from the last programming assignment are moving code out of packages and moving source files up to the root directory. Doing those things is understandable -- packages might not be familiar to you. If you have trouble building the code, or understanding the build process and how the source and directory structure relate to it, ask us. (There is almost no reason why you should undestand those things at this point, so don't worry about that.)

It would be prudent download the source and verify that you can (a) build it, and (b) run the sample application, as soon as possible. If things go well, it will only take a couple of minutes. If not, finding that out early will be a lot less stressful than finding it out, say, during Thanksgiving break.

Brief Source Structure Overview

All (useful) code is in one of four packages: examples, reflector, transport, and util. examples contains user applications that use the various transports that have been implemented. More on those in a bit. util has small helper classes, e.g., one that implements a Semaphore. The reflector package contains code implementing the reflector. If it's useful to you at all, it's most likely so that you can run you own copy of the reflector while debugging. (The reflector is built automatically by the build procedure, and is run by executing reflector.PacketReflectorMgr.)

Package transport contains implementations for the three protocols: reflected native UDP; reflected native TCP; and reflected 461 protocol. You will be modifying the last. All of the relevant code is in reflector/UW_461Socket.java. (reflector/UW461PacketReflector.java contains related but irrelevant code. It is releated in the sense that if you alter the existing 461 packet header in any way other than simply extending it with new fields, the reflector code in that file may break.)

Applications

Package examples contains three example applications. Files Client.java and Server.java implement a remote Hello World. It is TCP based, and has not been converted (from the form it was in when I took it from the web) to be able to the reflected form of TCP, nor any of the UDP based protocols.

TCPChat.java implements a simple, GUI'ed chat program. It also uses TCP. It has been adapted to run the reflected form of TCP, but not the UDP based protocols.

SendFile.java and ReceiveFile.java implement a (very bad) file transfer application. It can use all of the protocols, both UDP and TCP based. For this homework, it represents "every application" - your code needs to work with it, but not any other, as yet unwritten, applications.

Running the File Transfer Application

1. Pick a Planetlab-hosted reflector, and note its host name and port.
2. Start the file receiver, for example:

   [attu4] ~/cse461/ftpProject> java -classpath ".:argparser.jar" examples/ReceiveFile -type uw461
   -f received.txt -r planetlab03 38754
   

   (except given on one line) executed in the root directory of the file tree. (Note: The separator character for classpath is a colon on Linux machines, and a semi-colon on Windows/cygwin.) It prints the hostname / IP address / port number it is now listening on:

   Waiting for uw461 packets at 128:208:1:140 (attu4.cs.washington.edu) port 39005
   

   (It prints it once to System.out and once to System.err so you can redirect the former to a file but still see the port number, which you need in the next step.)
3. Start the send side, providing the receiver's host/port as one of the arguments:

   $ java -classpath '.;argparser.jar' examples/SendFile -type uw461 -f transport/UW_461Socket.java
   -r planetlab03 38754 -dest attu4 39005
   Sent 33393 bytes in 78 msec.
   

   (Note the semi-colon in classpath here, as it was run on a Windows box.) Using your source file as the thing to be sent is perhaps unwary, but it is conveniently a not-too-big not-too-small, multi-packet sized file.

You can (should?) set $CLASSPATH to make these commands simpler. How to do that depends on the kind of system and shell you're using, so I won't even try to cover all the possibilities here. (Simple shell scripts can also make invocation much less painful. Again, exactly how to do that depends on too many things to make it possible to give details here.)

Debugging

You have the source...

As well, there is a facility already built into the skeleton 461 transport code and file transfer app that causes them to print debugging information as they run. To enable, give the -d switch when invoking each side of the application. (To see all the switches for an application, invoke it with the -? switch.) Here's an example of what is printed:

$ java -classpath '.;argparser.jar' examples/SendFile -type uw461 -f transport/UW_461Socket.java
-r planetlab03 38754 -dest attu4 39007 -d
Sending packet of length 1260
Sending packet of length 1260

State = 2 Sending packet:
UDP dest: 128.208.4.199 47926
UDP length: 1280
UDP Offset: 0
UDP buf length: 1280
Type: 1111
Length: 1260
Dest IP/Port: 128.208.1.140 39007
Src IP/Port: 128.208.2.93 2732
Seqno: 1

State = 2 Received:
UDP dest: 128.208.1.140 39007
UDP length: 20
UDP Offset: 0
UDP buf length: 1280
Type: 2222
Length: 0
Dest IP/Port: 0.0.0.0 0
Src IP/Port: 128.208.1.140 39007
Seqno: 2
Sending packet of length 1260

Each packet that is sent or recieved is dumped (at a point as close to the actual send/receive as possible). State is the current state of the protocol FSA. The UDP fields are taken from the UDP header on the packet; the other fields are the 461 protocol's header. The first two and the final line are printed by the application (SendFile); the others are printed by the 461 protocol transport.

Everything, including exception stack traces, is printed to System.out, so you can redirect that to a file for long traces. (Note that tracing undoubtedly slows down packet processing significantly, and may in fact cause one side to fail to respond for so long that it causes the other side to conclude it has crashed, at least with the current settings of the protocol parameters.)

The App(s) / Naming Hosts / attu

You can run both ends of the file transfer application on one machine, if you like, but that is of course more likely to make the CPU the bottleneck (rather than the network). You can even run a reflector on that same machine, at least for testing. There is a widely implemented special name for the host you're running on, localhost. You can use that name to mean "this host, whatever it is."

The example applications take switches that name a remote host/port. Documentation for the Java calls being used inside the apps claims that either a hostname (e.g., "ginger.cs.washington.edu") or an IP address can be given, but only hostnames seem to work. That presents a likely confusion when using attu - it's not the name of one host, it's the name of four distinct hosts, meaning four distinct IP addresses. When you say "attu", the name is translated to one of those four IP addresses effectively at random. So, if you ssh to attu and run ReceiveFile, say, make sure you check out which of the four attu you're on and use it's specific name. (Try echo $HOSTNAME to figure out which you're on.)

Deliverables

• Create a file named README.txt in the root directory of your project file tree. Include as the first few lines of that file the names and email addresses of the people on your team.

• Include a short report as the remainder of the README.txt file. Your report should say clearly (and at appropriate length) what changes you made to the transport, why you thought they were necessary before you made them, what effect they had on performance, what you think the next step would be to further improve performance, and any evidence you have supporting your guess about what the next step should be. (For instance, after your changes, what factor(s) is most limiting throughput?) Note that we're more interested in a conceptual description of changes you made than details about its implementation in the code. (The one exception that comes to mind would be if you thought it was important to reduce the CPU overhead of running the protocol. In that case, you should say what you did to try to achieve that.)

• Hand in your code, after packaging it up using this procedure:

  1. Fetch script createTurninFile.sh and put it in root directory of your project file tree.

  2. Make sure the script is runnable: chmod u+x createTurninFile.sh.

  3. Run it: ./createTurninFile.sh. It will have a brief look around, to make sure it looks like it's in the right place. It will then do a make. If that doesn't succeed, it will exit with an error message. If that does succeed, it will create a file with a name in the style of zahorjan-hw5.tar.gz.

     (Note that these tests are there to try to increase the odds that we can script running you projects. Success of this script file doesn't necessarily mean we will be able to run your code, but I think it greatly increases the odds.)

  4. Turnin the file just created, using the turnin command in the following style: turnin -c cse461 -p homework5 zahorjan-hw5.tar.gz.

Obtainables

• Reflector status page

• Skeleton code Javadoc
  Your code will all be in transport/UW_461Socket.java.

• Protocol FSA graph
  This explains how opening and closing connections works. It is in all likelihood at most only very slightly related to what you'll be doing for the assignment.

Turn-In Procedures

See section Deliverables, above.

Grading

Grading will be done primarily on the basis of the writeup. We expect we will run all the code, and will have a look at the performance achieved, but we don't expect to be reading everyone's code nor grading on the beauty of choice of variable names.