***Change from November 11, 1985 draft definition. Change is to section 4.4 ** Changes from July 19 draft definition indicated by ** at left margin. Changes are to section 4.3 and section 5.3 KERMIT WINDOWING PROTOCOL December 6, 1985 DRAFT VERSION 1.3 1 INTRODUCTION The windowing protocol as defined for the Kermit file transfer protocol is based on the main premise of continuously sending data packets up to the number defined by a set window size. These data packets are continuously acknowledged by the receive side and the ideal transfer occurs as long as they are transmitted with good checksums, they are transmitted in sequential order and there are no lost data packets or acknowledgements. The various error conditions define the details of the windowing protocol and are best examined on a case basis. There are five stages that describe the overall sequence of events in the Kermit protocol. Three of these stages deviate from the original protocol in order to add the windowing feature. Stages 1 through 5 are briefly described on the following page. The three stages (1, 3 and 4) which deviate from the original protocol are then described in greater detail in the pages that follow. DRAFT PROPOSED DEFINITION Page 1 KERMIT WINDOWING PROTOCOL December 6, 198 2 OVERALL SEQUENCE OF EVENTS STAGE 1 - Propose and Accept Windowing The send side requests windowing in the transmission of the Send-Initiate (S) packet. The receive side accepts windowing by sending an acknowledgement (ACK packet) for the Send-Initiate packet. STAGE 2 - Send and Accept File-Header Packet The send side transmits the File-Header (F) packet and waits for the receive side to acknowledge it prior to transmitting any data. STAGE 3 - Transfer Data The sending routine transmits Data (D) packets one after the other until the protocol window is closed. The receiving side ACKs good data, stores data to disk as necessary and NAKs bad data. When the sender receives an ACK, the window may be rotated and the next packet sent. If the sender receives a NAK, the data packet concerned is retransmitted. STAGE 4 - Send and Accept End_of_File Packet As the sender is reading the file for data to send, it will eventually reach the end of the file. It then waits until all outstanding data packets have been acknowledged, and then sends an End-of_File (Z) packet. When the receive side gets the End-of-File packet it stores the rest of the data to disk, closes the file, and ACKs the End-of_File packet. The protocol then returns to Stage 2, sending and acknowledging any further File-Header (F) packets. STAGE 5 - End of Transmission Once the End-of-File packet has been sent and acknowledged and there are no more files to send, the sender transmits the End-of-Transmission (B) packet in order to end the ongoing transaction. Once the receiver ACKs this packet, the transaction is ended and the logical connection closed. DRAFT PROPOSED DEFINITION Page 2 KERMIT WINDOWING PROTOCOL December 6, 198 3 PROPOSE AND ACCEPT WINDOWING (STAGE 1) The initial connection as currently defined for the Kermit protocol will need to change only in terms of the contents of the Send-Initiate packet. The receiving Kermit waits for the sending Kermit to transmit the Send-Initiate (S) packet and the sending packet does not proceed with any additional transmission until the ACK has been returned by the receiver. The contents of the Send-Init packet, however, will be slightly revised. The data field of the Send-Init packet currently contains all of the configuration parameters. The first six fields of the Send-Init packet are fixed as follows: 1 2 3 4 5 6 +--------+--------+--------+--------+--------+--------+ | MAXL | TIME | NPAD | PADC | EOL | QCTL | +--------+--------+--------+--------+--------+--------+ Fields 7 through 10 are optional features of Kermit and fields 7 through 9 will also remain unchanged as defined for the existing protocol: 7 8 9 10 +--------+--------+--------+--------+ | QBIN | CHKT | REPT | CAPAS | +--------+--------+--------+--------+ Field 10 is the capability field and requires N number of bytes depending on the number of capabilities defined for kermit. Each bit position of these 6-bit fields corresponds to a capability with the low order bit used to indicate whether or not another capability byte follows. If the low order bit is "1" then another capability byte follows. If the low order bit is "0" then the current byte is the last capability byte. The second through sixth bit positions represent capabilities in the same way. If a bit position is set to 1 then the capability it represents is present. If the bit position is set to 0 then the capability it represents does not exist. Currently, there are only 3 capabilities defined for Kermit as follows: #1 Reserved #2 Reserved #3 Ability to accept "A" packets (file attributes) The windowing capability will constitute a fourth capability and the fourth bit of the capability field will be set to 1 if the kermit implementation can handle windowing. #4 Ability to handle windowing. DRAFT PROPOSED DEFINITION Page 3 KERMIT WINDOWING PROTOCOL December 6, 198 The remaining fields of the Send-Init packet are either reserved for future use by the standard Kermit protocol or reserved for local site implementations. The four fields following the capability field are reserved for the standard Kermit protocol. We propose the use of field 11 to be used to specify the "Window Size" for all kermits 11 12 13 14 15 16 - N +--------+--------+--------+--------+--------+------------------+ | WINDW | RESV1 | RESV2 | RESV3 | RESV4 | LOCAL Reserved | +--------+--------+--------+--------+--------+------------------+ 11. WINDW The window size to be used encoded printably using the char() function. The window size may range from 1 to 31 inclusive. The sender will specify the window size it wishes to use and the receiver will reply (in the ACK packet) with the window size it wishes to use. The window size actually used will be the minimum of the two. If the receiver replies with a window size of 0 then no windowing will be done. DRAFT PROPOSED DEFINITION Page 4 KERMIT WINDOWING PROTOCOL December 6, 198 4 TRANSFER DATA (STAGE 3) The sequence of events required for the transmission of data packets and confirmation of receipts constitute the main functions of the windowing protocol. There are four main functions which can be identified within this stage. These are: - the sender's processing of the data packets, - the receiver's handling of incoming packets, - the sender's handling of the confirmations, - the error handling on both sides. The following discussion details the specific actions required for each of these functions. Refer to the state table at the end of this document for the specific action taken on a "received message" basis for the full protocol. 4.1 The Sender's Processing of Data Packets The sender instigates the transmission by sending the first data packet and then operating in a cyclical mode of sending data until the defined window is closed. Data to be sent must be read from the file, encoded into the Kermit Data packet, and saved in a Send-Table. A Send-Table entry consists of the data packet itself (which makes convenient the re-send of a NAKed packet), a bit which keeps track of whether the packet has been ACKed (the ACKed bit), and a retry counter. The table is large enough to hold all the packets for the protocol window. Before each transmission, the input buffer is checked and input is processed, as described below. Transmission is stopped if the protocol window "closes", that is, if the Send-Table is full. DRAFT PROPOSED DEFINITION Page 5 KERMIT WINDOWING PROTOCOL December 6, 198 4.2 The Receiver's Handling of Incoming Packets The receiver keeps its own table as it receives incoming data packets. This allows the receiver to receive subsequent packets while it is waiting for a re-send of an erroneous or lost packet. In other words, the incoming packets do not have to be received in sequential order and can still be written to disk in order. A Receive-Table entry consists of the data packet, a bit which keeps track of whether a good version of the packet has been received (the ACKed bit), and a retry counter for the NAKs we send to request retransmissions of the packet. The table is large enough to hold all the packets for the protocol window. The different possibilities for a received packet are: 1. A new packet, the next sequential one (the usual case) 2. A new packet, not the next sequential one (some were lost) 3. An old packet, retransmitted 4. An unexpected data packet 5. Any packet with a bad checksum These are discussed separately below. 1. The next new packet has sequence number one past the . The packet is ACKed, and the Receive-Table is checked for space. If it is full (already contains window_size entries) then the oldest entry is written to disk. (This entry should have the ACKed bit set. If not, the receiver aborts the file transfer.) The received packet is then stored in the Receive-Table, with the ACKed bit set. 2. If the packet received has sequence number in the range to then it is a new packet, but some have been lost. (The upper limit here represents the highest packet the sender could send within its protocol window. Note that the requirement to test for this case is what limits the maximum window_size to half of the range of possible sequence numbers) We ACK the packet, and NAK all packets that were skipped. (The skipped packets are those from to ) The Receive-Table is then checked. The table may have to be rotated to accomodate the packet, as with case 1. (This time, several table entries may have to be written to disk. As before, if any do not have the ACKed bit set, they will trigger an abort.) The packet is then stored in the table, and the ACKed bit set. 3. A retransmitted packet will have sequence number in the range to . The packet is ACKed, then placed in the table, setting the ACKed bit. DRAFT PROPOSED DEFINITION Page 6 KERMIT WINDOWING PROTOCOL December 6, 198 4. A packet with sequence number outside of the range from to is ignored. 5. If the packet received has a bad checksum, we must decide whether to generate a NAK, and if so, with what sequence number. The best action may depend on the configuration and channel error rate. For now, we adopt the following heuristic: If there are unACKed entries in our Receive-Table, we send a NAK for the oldest one. Otherwise we ignore the packet. (Notice that this will occur in a common case: when things have been going smoothly and one packet gets garbled. In this case, when we later receive the next packet we will NAK for this one as described under Case 2 above.) DRAFT PROPOSED DEFINITION Page 7 KERMIT WINDOWING PROTOCOL December 6, 198 4.3 The Sender's Handling of Confirmations The sender's receipt of confirmations controls the rotation of the Send-Table and normally returns the sender to a sending state. The sender's action depends on the packet checksum, the type of confirmation (ACK or NAK), and whether the confirmation is within the high and low boundaries of the Send-Table. If the checksum is bad the packet is ignored. When the sender receives an ACK, the sequence number is examined. If the sequence number is outside of the current table boundaries, then the ACK is also ignored. If the sequence number is inside of the current table boundaries then the ACKed bit for that packet is marked. If the entry is at the low boundary, this enables a "rotation" of the table. The low boundary is changed to the next sequential entry for which the ACKed bit is not set. This frees space in the table to allow further transmissions. When the sender receives a NAK, the table boundaries are checked. A NAK inside the table boundary indicates that the sender must re-send the packet. The sender first tests the packet's retry counter against the retry threshold. If the threshold has been reached, then the transfer is stopped (by going to the Abort state). Otherwise, the retry counter is incremented and the packet re-sent. ** A NAK outside of the table boundary causes the sender to send ** the earliest unACKed packet, or if all have been ACKed, the ** next packet. The retry counter is tested and incremented as above. DRAFT PROPOSED DEFINITION Page 8 KERMIT WINDOWING PROTOCOL December 6, 198 4.4 Error Handling for Both Sides Three situations are discussed here: Sender timeout, Receiver timeout, and invalid packets. If certain packets are lost, each side may "hang", waiting for the other. To get things moving when this happens each may have a "timeout limit", the longest they will wait for something from the other side. If the sender's timeout condition is triggered, then it will send the oldest unACKed packet. This will be the first one in the Send-Table. If the receiver's timeout condition is triggered, then it will send a NAK for the "most desired packet". This is defined as either the oldest unACKed packet, or if none are unACKed, then the next packet to be received (sequence number ). The packet retry count is not incremented by this NAK; instead we depend on the timeout retry count, discussed next. For either the sender or receiver, the timeout retry count is incremented each time a timeout occurs. If the timeout retry limit is exceeded then the side aborts the file transfer. Each side resets the retry count to zero whenever they receive a packet. In addition, as with the existing Kermit, any invalid packet types received by either side will cause an Error packet and stop the file transfer. *** TIMEOUT AVOIDANCE HEURISTIC Section added through An additional heuristic will prevent most timeouts due to lost stars ACKs or NAKs. The sender re-sends the earliest packet (the packet below blocking the window) if the following conditions are true: 1. The Sender's window is blocked. 2. The Retry Count for the earliest packet is zero. 3. An ACK (or optionally also NAK) for any later packet has been received. This heuristic takes advantage of the fact that ACKs and NAKs should normally be received in order. Receipt of a later ACK implies that the earliest ACK was lost. Therefore, we can anticipate that a timeout is likely to occur and avoid it by resending (once) the packet blocking the window. The packet is only sent once (i.e. if the retry count is zero) to avoid *** complicating error recovery. DRAFT PROPOSED DEFINITION Page 9 KERMIT WINDOWING PROTOCOL December 6, 198 5 SEND AND ACCEPT END_OF_FILE PACKET (STAGE 4) There are several ways to end the file transfer. The first is the normal way, when the sender encounters an end-of-file condition when reading the file to get a packet for transmission. The second is because of a sender side user interrupt. The third is because of a receiver side user interrupt. Both of these cause the received file to be discarded. In addition either side may stop the transfer with an Error packet if an unrecoverable error is encountered. 5.1 Normal End of File Handling When the sender reaches the end of file, it must wait until all data packets have been acknowledged before sending the End-of-File (Z) packet. To do this it must be able to check the end-of-file status when it processes ACKs. If the ACK causes the Send-Table to be emptied and the end-of-file has been reached, then a transition is made to the Send_Eof state which sends the End_of_File packet. When the receiver gets the End_of_File packet, it writes the contents of the Receive-Table to the file (suitably decoded) and closes the file. (If any entries do not have the ACKed bit set, or if errors occur in writing the file, the receiver aborts the file transfer.) If the operation is successful, the receiver sends an ACK. It then sets its sequence number to the End_of_File packet sequence number and goes to Rcv_File state. 5.2 Sender User Interrupt Whenever the sender checks for input from the data communications line, it should also check for user input. If that indicates that the file transfer should be stopped, the sender goes directly to the Send_Eof state and sends an End_of_File packet with the Discard indication. It will not have to wait for outstanding packets to be ACKed. When the receiver gets the End_of_File packet with the Discard indication it discards the file, sets its sequence number to the End_of_File packet sequence number, and goes to RcvFile state. DRAFT PROPOSED DEFINITION Page 10 KERMIT WINDOWING PROTOCOL December 6, 198 5.3 Receiver User Interrupt Whenever the receiver checks for input from the data communications line, it also should check for user input. If that indicates that the file transfer should be stopped, the receiver sets an "interrupt indication" of X (for "stop this file transfer") or of Z (for "stop the batch of file transfers"). When the receiver later sends an ACK, it places an X or Z in the data field. When the sender gets this ACK, it goes to the Send_Eof state and sends the End_of_File packet with the Discard indication, as above. ** The sequence number of the End_of_File packet is the (sequence ** number of the ACK with Discard) + 1. When the receiver gets the End_of_File packet with the Discard indication, it discards the file, sets its sequence number to the End_of_File packet sequence number, and goes to RcvFile state. DRAFT PROPOSED DEFINITION Page 11 KERMIT WINDOWING PROTOCOL December 6, 198 5.4 LOW LEVEL PROTOCOL REQUIREMENTS The Kermit windowing protocol, as defined in this document, makes certain assumptions about the underlying transmission and reception mechanism. First, it must provide a full-duplex channel so that messages may be sent and received simultaneously. Second, it will prove advantageous to be able to buffer several received messages at the low level before processing them at the Kermit level. This is for two reasons. The first is that the Kermit windowing level of the protocol may take a while to process one input, and meanwhile several others may arrive. The second reason is to support XON/XOFF flow control. If Kermit receives an XOFF from the data communications line, it must wait for an XON before sending its packet. While it is waiting, the low level receive must be able to accept input. Otherwise a deadlock situation could arise with each side flow controlled, waiting for the other. DRAFT PROPOSED DEFINITION Page 12 KERMIT WINDOWING PROTOCOL December 6, 198 5.5 KERMIT WINDOWING PROTOCOL STATE TABLE The following defines the inputs expected, the actions performed, and the succeeding states for proposed new Send_Data_Windowing and Rcv_Data_Windowing states. If both sides agree on windowing in the Send Init exchange, then instead of entering the old Send_Data or Rcv_Data states from Send_File or Rcv_File, we enter the new Send_Data_Windowing or Rcv_Data_Windowing. SEND_DATA_WINDOWING Rec'd Msg Action Next State --------- ------ ---------- No input/Window closed (1) Wait for input SDW No input/Window open (2) Read file, encode packet, SDW Place in table, mark unACKed, Send packet ACK/ X or Z (3) set interrupt indicator (X/Z) Send_Eof ACK/outside table -ignore- SDW ACK/inside table (4) mark pkt ACKed, SDW or Send_Eof if low rotate table, if file eof & table empty then goto Send_Eof NAK/outside table -ignore- SDW NAK/inside table (5) test retry limit, SDW re-send DATA packet Bad checksum -ignore- SDW Timeout (6) re-send oldest unACKed pkt SDW User interrupt (7) set interrupt indicator (X/Z) Send_Eof Other (8) send Error Abort DRAFT PROPOSED DEFINITION Page 13 KERMIT WINDOWING PROTOCOL December 6, 198 RCV_DATA_WINDOWING Rec'd Msg Action Next State --------- ------ ---------- DATA/new (1) send ACK RDW if table full: file & rotate store new pkt in table DATA/old (2) send ACK, store in table RDW DATA/unexpected -ignore- RDW Z/discard (3) discard file Rcv_File Z/ (4) write table to file & close Rcv_File if OK send ACK, else Error or Abort Bad checksum (5) send NAK for oldest unACKed RDW Timeout (6) send NAK for most desired pkt RDW User Interrupt (7) Set interrupt indicator X or Z RDW Other (8) send Error pkt Abort DRAFT PROPOSED DEFINITION Page 14