The following is the text of the section "BLAST Algorithm" from Peterson & Davie, now deleted from the fourth edition. BLAST Algorithm The basic idea of BLAST is for the sender to break a large message passed to it by some high-level protocol into a set of smaller fragments, and then for it to transmit these fragments back-to-back over the network. Hence the name BLAST -- the protocol does not wait for any of the fragment to be acknowledged before sending the next. The receiver then sends a _selective retransmission request_ (SRR) back to the sender, indicating which fragments arrived and which did not. (The SRR message is sometimes called a _partial_ or _selective_ acknowledgement.) Finally, the sender retransmits the missing fragments. In the case in which all the fragments hav earrived, the SRR serves to fully acknowledge the message. Figure 5.13 gives a representative timeline for the BLAST protocol. sender receiver | | | --- frag1 ------------>| | --- frag2 ------------>| | --- frag3 -----x | | --- frag4 ------------>| | --- frag5 ------x | | --- frag6 ------------>| |<----SRR----------------| | --- frag3 ------------>| | --- frag5 ------------>| |<----SRR----------------| Fig 5.13 (ascii representation) We now consider the send and receive sides of BLAST in more detail. On the sending side, after fragmenting the message and transmitting each of the fragments, the sender sets a timer called DONE. Whenever an SRR arrives, the sender retransmits the requested fragments and resets timer DONE. Should the SRR indicate that all the fragments have arrived, the sender frees its copy of the message and cancels timer DONE. If timer DONE ever expires, the sender frees its copy of the message; that is, it gives up. On the receiving side, whenever the first fragment of a message arrives, the receiver initializes a data structure to hold the individual fragments as they arrive and sets a timer LAST_FRAG. This timer counts the time that has elapsed since the last fragment arrived. Each time a fragment for that message arrives, the receiver adds it to this data structure, and should all the fragments then be present, it reassembles them into a complete message and passes this message up to the higher-level protocol. There are four exceptional conditions, however, that the receiver watches for: * 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. There are three aspects of BLAST worth noting. First, two different events trigger the initial transmission of an SRR: the arriveal of the last fragment and the firing of the LAST_FRAG timer. In the case of the former, because the network may reorder packets, the arrival of the last fragment does not necesarily imply that an earlier fragment is missing (it may just be late in arriving), but since this is the most likely explanation, BLAST aggressively sends an SRR message. In the latter case, we deduce that the last fragment was either lost or seriously delayed. Second, the performance of BLAST does not critically depend on how carefully the timers are set. Timer DONE is used only to decide that it is time to give up and delete the message that is currently being worked on. This timer can be set to a fairly large value since its only purpose is to reclaim storage. Timer RETRY is only used to retransmit an SRR message. Any time the situation is so bad that a protocol is reexecuting a failure recovery process, performance is the last thing on its mind. Finally, timer LAST_FRAG has the potential to influence performance -- it sometimes triggers the sending by the receiver of an SRR message -- but this is an unlikely event: It only happens when the last fragment of the message happens to get dropped in the network. Third, while BLAST is persistent in asking for and retransmitting missing fragments, it does not guarantee that the complete message will be delivered. To understand this, suppose tha ta message consists of only one or two fragments and that these fragments are lost. The receiver will never send an SRR, and the sender's DONE timer will eventually expire, causing the sender to release the message. To guarantee delivery, BLAST would need for the sender to time out if it does not receive an SRR ind then retransmit the last set of fragments it had transmitted. While BLAST certainly could have been designed to do this, we chose not to because the purpose of BLAST is to deliver large messages, not to guarantee message delivery. You might wonde rwhy we put any retransmission capability at all into BLAST if we need to put a guaranteed delivery mechanism above it anyway. The reason is that we'd prefer to retransmit only those fragments that were lost rather than having to retransmit the entire larger message whenever one fragment is lost. So we get the guarantees from the higher-level protocol but some improved efficiency by retransmitting fragments in BLAST. BLAST Message Format The BLAST header has to convey several pieces of information. First, it must contain some sort of message identifier so tha tall the fragments tha tbelong to the same message can be identified. Second, there must be a way to identify where in the original message the individual fragments fit, and likewise, an SSR must be able to indicate which fragments have arrived and which are missing. Third, there must be a way to distinguish the last fragment, so that the receiver knows when it is time to check to see if all the fragments have arrived. Finally, it must be possible to distinguish a data message from an SRR message. Some of these items are encoded in a header field in an obvious way, but others can be done in a variety of different ways. Figure 5.14 gives the header format used by BLAST. The following discussion explains teh various fields and considers alternative designs. Fig 5.14: 0 16 31 +-----------+-----------+ | ProtNum | +-----------+-----------+ | MID | +-----------+-----------+ | Length | +-----------+-----------+ | NumFrags | Type | +-----------+-----------+ | FragMask | +-----------+-----------+ | Data | | | | | +-----------+-----------+ The MID field uniquely identifies this message .... [ set of fragments ] The Type field indicates whether this is a DATA message or an SRR message.... The Length field indicates how many bytes of data are in _this_ fragment; it has nothing to do with the length of the entire message. The NumFrags field indicates how many fragments are in this message. Finally, the FragMask field is used to distinguish among fragments. It is a 32-bit field that is used as a bit mask. For messages of Type == DATA, the ith bit is 1 (all others are 0) to indicate that this packet carries the ith fragment. For messages of Type == SRR, the ith bit is set to 1 to indicate that the ith fragment has arrived.