BLAST programming assignment

Comp 343/443, Fall 2008

Last-minute BLAST implementation notes

You will implement the client side of the BLAST protocol of Peterson & Davie. This is intended as the bottom layer of a multi-layer RPC protocol, implementing fragmentation, reassembly, and selective acknowledgements. BLAST is somewhat "theoretical"; its primary purpose is as an example, and a formal implementation specification was never developed.

In the 4th edition of Peterson & Davie, BLAST is replaced by DCE-RPC, which includes a selective-acknowledgement mechanism of its own (but quite likely based on that of BLAST). See Fig 5.18. For convenience, here is the description of BLAST from P&D Edition 3.

I have implemented a BLAST server. You are to implement the client, with its two timers RETRY and LAST_FRAG. You will send a request packet (consisting of a single 4-byte number representing the "request number") to a designated port on a designated server (currently port 2222 on host ulam2.cs.luc.edu), and a BLAST server on the host will send your end an appropriate message, divided by BLAST into fragments. You will have to manage the sending of SRR's (selective ACKs here), and also the timers LAST_FRAG and RETRY. The "request" protocol is embedded in the bclient.java file, below; you do not otherwise need to worry about this.

Your program should also handle the DONE timer in the following sense: if nothing is received after the initial request is sent within interval DONE, then your client should give up. In other words, you do not retransmit the original requests if nothing happens.

The current implementation of the server sends its reply from a new port; your client will have to be aware of this, and should make an effort to determine that all BLAST fragments actually come from the same server port. Note that the first fragment will have to be treated separately in this regard; until it arrives, you do not know the port number for the others.

Error Checking

An important part of the project is to check for error conditions that may occur. Here is a list. Note that some of these are logically ordered; for example, if a packet isn't from the right host, then you shouldn't worry about whether it has a complete header! And if it doesn't have a complete header, you shouldn't worry about whether the header fields are right.
Receiving a duplicate fragment is not an error. Note that inconsistent MID or NumFrags (or port) values will be detectable only upon receiving packets after the first; upon receiving the first packet you simply set these for subsequent reference. Ideally, if the first packet has an incomplete header (or comes from the wrong host), you should ignore it completely (ie do not record its MID value, etc).

It is not immediately obvious, upon sending a request and receiving a response fragment, whether that response is due to your request, or whether that response is an old fragment from a previous request. In theory this is to be handled at the CHAN layer, which we are not implementing. In practice, you are to ignore this point, and assume the first valid-looking fragment received is in fact part of the response to your request. You are therefore to extract the MID packet-header value and the UDP source-port value for that first fragment; all remaining fragments must have these same values.

As a rule, packet sanity checking goes in bclient.java at the point of the comment
            // we *should* do some sanity checks on the packet just received!!

SRRs

You will send back an SRR if you receive the last fragment (as indicated by the fact that the bit that is turned on in FragMask is in position NumFrags-1). You will also send back the current SRR whenever a timer expires (except when it is time to give up). Finally, you should send back the final SRR once all the fragments have arrived. In Fig 5.12 in the text, the final SRR is sent upon receipt of Fragment 5, because all the other fragments (including Fragment 6) have already been received. Note that for some of the test examples, you won't actually receive all the fragments (simulating the loss of those fragments) until you've sent an SRR acknowledging the first batch received.

Termination

Your transfer has been successful if you have received each fragment indicated by the NumFrags field of the original packet. The SRR you send back will then have all bits from 0 to NumFrags-1 turned on. (To turn on the ith bit of a variable mask, use "mask |= (1 << i)".) An unsuccessful transfer is one where the RETRY timer has fired for MAX_RETRIES, or some other unrecoverable error has occurred. Note that good network design means that you should avoid treating errors as unrecoverable unless absolutely necessary:
    Be liberal in what you accept, and conservative in what you send.

Files

There are two files for you to work with: blastpkt.java, which defines the packet format and which you should view as essentially read-only, and bclient.java, which is a starter file that you are to modify into a working program.

Your first step is to delete the break; at the end of the main while loop, so that you receive all the fragments sent.

Your next step is to figure out how to send an SSR; you send this when enough time has elapsed (eg blastpkt.RETRY), and under other conditions as outlined below. You will generally put timeout responses at the top of the while loop, conditional on enough time having elapsed since you started, and then have the hard timeout (the InterruptedIOException) result in a continue statement (bringing you right back to the top of the while loop). This handles the problematic case where you in fact never have a hard timeout, because "noise" packets (server retransmissions?) keep arriving at a regular rate, but in fact you have not received everything you expect. 

Once you've started sending SRRs, and have implemented appropriate error checking (above), you should be ready to determine whether or not you're really receiving the proper data, and getting it in the proper order.

The details for sending SRRs are in the P&D BLAST description; the main points are as follows:
To implement these, you will check at the top of the loop (or in some other uniform location) for whether the last fragment has just arrived, and what the current time is (System.currentTimeMillis()), and the count of past RETRY expirations. The current RETRY timer has expired if the current time is more than blastpkt.RETRY milliseconds from the (saved) time when RETRY was last set; ditto for LAST_FRAG.

Testing

Your first problem using my server for testing is even reaching it. The problem is firewalls, and the way the UDP port change works. You contact my server, and it answers from a different port, and if you're behind a NAT firewall it has no way of recognizing this new port and so the packet is blocked.

I've created a windows server executable blasts.exe. It should run under windows, provided you have cygwin installed. Similarly, here is a linux server executable. If you take this approach, run the server on the same machine as the client, and configure the client to access host "localhost" by default.  The alternative, for now, is to come into Loyola. Even from inside Loyola you might have problems, so I am also running the server on 10.38.2.67.

Once you can get through at all, if you ask for message 0 from my server, a message is returned containing the number N of other messages currently supported (as a single 32-bit word, in network byte order); this response is handled in bclient.java, below. You should then request each of these messages, 1 through N, in turn. For each message, you should print out:
Some of the messages will have packet losses or reordering artificially introduced by my server; it will be the job of your client to straighten these out.

You do not need to print out the message received. However, it should be possible to do so, to System.out; in order to preserve this as a way of printing messages, nothing else should go to System.out. All other messages (including the every-packet status messages) should go to System.err!

You should calculate the MD-5 checksum on each complete message as received, and print that out (using the byte2string(byte[]) method I've included in bclient.java). For each block of data byte[] buf, this means calling md.update(buf), or, if you just want to include the range buf[i] ... buf[i+len-1], use md.update(buf, i, len). Blocks of data must be processed by md.update in their proper order.