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.
- error in reading from network
- packet from wrong host (or port, except for packet 1)
- packet with incomplete header (ie size < HEADERSIZE)
- wrong MID field (we will not use ProtNum)
- wrong Type
- wrong NumFrags (all packets should have the same value here)
- FragMask has multiple bits set
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:
- If
the last fragment arrives (the last fragment is specially marked)
but the message is not complete, then the receiver determines
which fragments are missing and sends an SRR to the sender. It
also set a timer called RETRY.
- If timer LAST_FRAG expires,
then the receiver determines which fragments are missing and sends
an SRR to the sender. It also sets timer RETRY.
- If timer RETRY
expires for the first or second time, then the receiver
determines which fragments are still missing and retransmits an
SRR message.
- If timer RETRY expires for the third time, then
the receiver frees the fragments that have arrived and cancels
timer LAST_FRAG; that is, it gives up.
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:
- information about every packet received
- the final message size
- a message checksum (I'm still looking for appropriate code here)
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.