Implementing the BLAST Protocol

Due date

Introduction

In this assignment you will be implementing the BLAST protocol. Information on the BLAST protocol can be found in previous editions of Peterson & Davie. You will implement BLAST on top of UDP.  You will further consider where and how to test your implementation, specifically, how to drop packets so that the BLAST packet recovery is exercised.

Acknowledgments

This lab is based on the BLAST protocol as defined by Peterson & Davie. It was written by Mike Erlinger at Harvey Mudd College.

Goals

• To implement a transport-layer protocol.
• To understand how to implement a protocol to a specification.
• To encounter protocol implementation issues.
• To experiment with testing and evaluating a new protocol.

Logistics

Students should pair up to complete this assignment. Write up your work in BOTH lab notebooks. You may discuss the material with whomever you wish. You may obtain help from anyone you wish, but you should clearly document that help.

You have two weeks to complete this assignment.

Preparation

To prepare for this assignment, read section 4.3.1 (pp. 408 - 413) in Peterson & Davie, 3rd edition, on the BLAST bulk transfer protocol. Because this material no longer appears in the current edition of the textbook, I will hand out photocopies prior to class on Friday.

Assignment

The BLAST header

The BLAST header has the following format:

ProtNum

Normally used to demultiplex BLAST messages. Since your client will not have any explicit protocols riding on top of BLAST, you should set this field to first four characters of your last name. The server will use whatever value you use in your messages.

MID 

Message ID: Used to differentiate multiple BLAST streams. Your client will only be dealing with a single stream, but you should code basic support for multiple streams, e.g., set up a running counter to handle new streams. The server will use whatever value you send to it in the initial message. 

Length 

Length (in bytes) of the data which follows the header.

NumFrags

Total number of fragments in this BLAST message. This is used to determine which message is the last one in the sequence.

Type

1 DATA
2 SRR

FragMask

Bitmask indicating packet number. DATA packets from the server should have only one of these bits set to indicate which packet this is. SRR packets should have bits set for every message that has been received so far and zeros for all missing messages.

Task 1 - Implement BLAST Sender and Receiver on the MathLAN

What follows below is an outline of subtasks.  You should implement the sender and receiver in tandem so that you can test both of them as you go along.

Use a large text string, one that will require several fragments, as the data for the client (sender) to send to the server (receiver). Your fragments do not need to be as large as the length field implies they can be; choose a size that is useful for testing. A typical Ethernet maximum frame size is 1 KB, and your fragments could be much smaller.

In order to make sure your sender is robust, you should modify your receiver to "lie" to the sender in order to simulate network conditions which are not present in the lab (specifically, packet loss, delay, and reordering). 

The receiver definitely must drop some packets in order to stress the protocol. When your receiver starts, it should accept a parameter that indicates how often to drop a packet, e.g., every 3rd packet.  I know this is not random, but it's easy to understand.

Step 1

After verifying that a packet is valid, the receiver should convert the FragMask to a packet number (ith bit set converts to the number i) and print the contents, something like this:

Step 2

Implement the LAST_FRAG counter on the receiver to help determine when a SRR should be sent. You may choose any resonable value for the timer length. When the timer expires, print a status message.

Step 3

When the last message arrives, or the LAST_FRAG timer expires, the receiver sends a SRR message back to the sender indicating which messages it has already received. You will need to modify the BLAST processing function to record which messages have been received as they come in.

Step 4

Add a RETRY timer (set whenever an SRR message is sent), in the receiver. The length of this timer is also up to you. When the timer expires the first and second times, the receiver should resend the SRR and reset the RETRY timer. If the timer expires a third time, the receiver should give up on the BLAST session.

Step 5

You should now have a BLAST receiver that receives the entire message and prints each part as it comes in. The receiver must now save these messages in a buffer and put them back together in the proper order. 

Use script to capture a sender and receiver interaction that demonstrates your BLAST implementation in action. This interaction must include "lost" packets and may include delayed or reordered packets.

Task 2

Assessment

Advice

• Make sure you have read and understand the book's description of BLAST before you begin. If you have questions, write them down and ask me during our lab meetings or office hours.
• The htons function is your friend.
• You should already know how to use UDP sockets from the lab on sockets. Recall that recvfrom() allows you to receive the IP address of the sender along with the contents of the UDP datagram.

• Example using timers (from OS class)
• Manipulating bitmaps with shift and bitwise-and operators

Discussion Questions

1. How much does performance depend on the settings of the various timers used to implement BLAST?
2. What guarantees does BLAST give you concerning message delivery?
3. What does BLAST not guarantee? Why not?
4. When would one choose TCP instead of BLAST as a transport layer protocol, or vice versa?
5. How long did you spend on this assignment?

Lab Notebook

Be sure to 

• include any relevant program source,
• document your code, and
• include your answers to the discussion questions.

Janet Davis (davisjan@cs.grinnell.edu)