info-kermit@ucbvax.ARPA (07/23/85)
From: Frank da Cruz <SY.FDC@CU20B.ARPA>
Info-Kermit Digest Tue, 23 Jul 1985 Volume 3 : Number 7
Kermit Sliding Window Proposal
----------------------------------------------------------------------
Date: Tue 23 Jul 85 10:30:00-EDT
From: Frank da Cruz
Subject: Kermit Sliding Window Proposal
This digest presents a proposal from a group at The SOURCE Telecomputing in
McLean, Virginia, for a sliding window extension to the Kermit protocol
(if you're not interested in protocol issues, skip the rest of this digest).
Like other extensions, this one is designed for "upward compatibility" with
Kermits that do not support this extension. It may be viewed as an
alternative to the long-packets extension proposed in V3 #4, or as
complementary to it. The question raised by the latter proposal also applies
here: Is the cost in complexity worth the improvement in performance? --
complexity not only in program size and logic, but also in explaining the
options to the user: even when Kermit programs implement windowing, when and
to what degree should it be used? When must it not be used?
The following proposal is not the only way to do sliding windows or to adapt
windows to Kermit. The method outlined is certainly not cast in concrete,
although Leslie's group is working on some prototype implementations. The
proposal is being put forth now to solicit ideas, suggestions, and opinions
from the world at large. Some areas to think about include:
. What is the effect on the portability of current Kermit programs? Since
windowing implies packets flowing in both directions at once, it will be
necessary to run separate input and output forks or else to handle packet
i/o at interrupt level. Neither of these techniques will be as portable
as the simple input-output sequences now used by most Kermit programs.
. What will be the effect in the many and varied environments in which
Kermit operates, and will operate in the future? These include public
networks, satellite links, local area networks, terminal concentrators,
TACs, PBX's, high-speed full-duplex error-correcting modems, ATT 56Kb
digital service, etc etc. In some cases windowing (or long packets)
could boost performance dramatically, in others it could prevent Kermit
from working at all.
. Does the particular method suggested strike the best balance among
improved performance, upward compatibility, and simplicity? Are there
obvious simple improvements to the proposed algorithms and heuristics?
. Can sliding (lurching) windows be done on half-duplex channels? Are
any modifications to the proposal required?
This digest will be followed closely by another, which will contain some
questions and answers about this proposal. Please read both digests before
responding.
------------------------------
Date: Mon 22 Jul 85 11:29:46-EDT
From: Leslie Spira <OC.SOURCE@CU20B>
Subject: Kermit Sliding Window Proposal
KERMIT WINDOWING PROTOCOL
DRAFT SPECIFICATION
Hugh Matlock, The SOURCE Telecomputing
June 12, 1985
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.
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.
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.
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.
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.
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 <latest
table entry>. 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 <two
past the latest table entry> to <window_size past the latest table
entry> 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 <one
past the latest table entry> to <one before the received packet>)
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
<the oldest table entry> to <the latest table entry>. The packet is
ACKed, then placed in the table, setting the ACKed bit.
4. A packet with sequence number outside of the range from <the
oldest table entry> to <window_size past the latest table entry> 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.)
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 outside of the table boundary is ignored and 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.
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 <latest table entry plus one>). 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.
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.
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.
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.
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.
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 pktSDW
User interrupt (7) set interrupt indicator (X/Z) Send_Eof
Other (8) send Error Abort
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
------------------------------
End of Info-Kermit Digest
*************************
-------