home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Columbia Kermit
/
kermit.zip
/
archives
/
misc.tar.gz
/
misc.tar
/
bytedoc.txt
< prev
next >
Wrap
Text File
|
1988-08-16
|
93KB
|
2,911 lines
1
KERMIT
A SIMPLE FILE TRANSFER PROTOCOL FOR MICROCOMPUTERS AND MAINFRAMES
Frank da Cruz, Bill Catchings
Columbia University Center for Computing Activities
New York, N.Y. 10027
May 1983
During recent years, the technical press has focused a lot of atten-
tion on developments in computer networking -- the IEEE 802 committee,
TCP/IP, SNA, the latest VLSI Ethernet interface, fibre optics, satellite
communications, broadband versus baseband. But little attention has
been given to the single mechanism that may be the most widely used in
the real world for direct interprocessor communication: the so-called
``asynchronous protocol'', which is to be found in some form at almost
every institution where there is a need to transfer files between
microcomputers and central computers.
Columbia University is such an institution. Large timesharing com-
_______________
1
This is the original manuscript of the article published in BYTE
Magazine as "Kermit: A File Transfer Protocol for Universities", June
and July 1984. Some minor editorial differences exist between this
manuscript and the article as published. The Kermit file transfer
protocol is named after Kermit the Frog, star of the television series
THE MUPPET SHOW, used by permission of Henson Associates, Inc.
2
puters at a central site are complemented by many smaller systems scat-
tered in the laboratories and departments. The past few years have wit-
nessed the inexorable progress of diverse microcomputers, word proces-
sors, and professional workstations into offices and laboratories throu-
ghout the University, and into the homes or dormitory rooms of faculty,
students, and staff. As soon as these small machines began to appear,
their users asked for ways to exchange files with the central and
departmental systems.
At the same time, student use of our central systems was growing at an
astonishing rate. We could no longer afford to provide students with
perpetual online disk storage; we began to issue IDs per course, per
term. With the decreased longevity of the IDs came the need for stu-
dents to economically archive their files. Given a reliable way to from
the central mainframes and back, microcomputers with floppy disks could
provide inexpensive removable media ideal for this purpose.
The situation called for a file transfer mechanism that could work
among all our computers, large and small. We knew of none that could
handle the required diversity. Some were intended for use between
microcomputers, others between large computers, but none specifically
addressed the need for communication among the widest possible range of
computers, particularly between micros and our IBM and DEC mainframes.
Most commercial packages served a limited set of systems, and their cost
would have been prohibitive when multiplied by the large number of
machines we needed to support.
3
So we embarked on our own project. We were not well-versed in these
matters at the outset; we learned as we proceeded, and we're still
learning. This article discusses some of the issues and tradeoffs that
came up in the design, and illustrates them in terms of our result, the
KERMIT protocol for point-to-point file transfer over telecommunication
lines. Because commercial local area networking products are expensive,
not yet widely available, and unsuitable for one-shot or long-haul ap-
plications, humble asynchronous protocols such as KERMIT are likely to
be with us for a long time to come.
It is assumed the reader is familiar with common computing and
telecommunications terminology, and with the ASCII alphabet, which is
listed at the end of this article for reference.
* The Communication Medium
The only communication medium common to all computers, large and
small, is the asynchronous serial telecommunication line, used for con-
necting terminals to computers. Standards for this medium are almost
universally followed -- connectors, voltages, and signals (EIA RS-232-C
[1]), character encoding (ASCII, ANSI X3.4-1977 [2]), and bit transmis-
sion sequence (ANSI X3.15-1976 [3, 4]). Serial connections can be made
in many ways: dedicated local lines (``null modem'' cables), leased
telephone circuits, dialup connections. Dialup connections can be in-
itiated manually from the home or office using an inexpensive acoustic
4
coupler, or automatically from one computer to another using a programm-
able dialout mechanism. The asynchronous serial line offers the or-
dinary user a high degree of convenience and control in establishing in-
tersystem connections, at relatively low cost.
Once two computers are connected with a serial line, information can
be transferred from one machine to the other, provided one side can be
instructed to send the information and the other to receive it. But
right away, several important factors come into play:
1. Noise -- It is rarely safe to assume that there will be no
electrical interference on a line; any long or switched data
communication line will have occasional interference, or
noise, which typically results in garbled or extra charac-
ters. Noise corrupts data, perhaps in subtle ways that might
not be noticed until it's too late.
2. Synchronization -- Data must not come in faster than the
receiving machine can handle it. Although line speeds at the
two ends of the connection may match, the receiving machine
might not be able to process a steady stream of input at that
speed. Its central processor may be too slow or too heavily
loaded, or its buffers too full or too small. The typical
symptom of a synchronization problem is lost data; most
operating systems will simply discard incoming data they are
not prepared to receive.
3. Line Outages -- A line may stop working for short periods be-
cause of a faulty connector, loss of power, or similar
reason. On dialup or switched connections, such intermittent
failures will cause carrier to drop and the connection to be
closed, but for any connection in which the carrier signal is
not used, the symptom will be lost data.
Other communication media, such as the parallel data bus, have
safeguards built in to prevent or minimize these effects. For instance,
distances may be strictly limited, the environment controlled; special
5
signals may be available for synchronization, and so forth. The serial
telecommunication line provides no such safeguards, and we must there-
fore regard it as an intrinsically unreliable medium.
* Getting Reliable Communication over an Unreliable Medium
To determine whether data has been transmitted between two machines
correctly and completely, the two machines can compare the data before
and after transmission. A scheme that is commonly used for file trans-
fer employs cooperating programs running simultaneously on each machine,
communicating in a well-defined, concise language. The sending program
divides outbound data into discrete pieces, adding to each piece special
information describing the data for the receiving program. The result
is called a ``packet''. The receiver separates the description from the
data and determines whether they still match. If so, the packet is ack-
nowledged and the transfer proceeds. If not, the packet is ``negatively
acknowledged'' and the sender retransmits it; this procedure repeats for
each packet until it is received correctly.
The process is called a communication protocol -- a set of rules for
forming and transmitting packets, carried out by programs that embody
those rules. Protocols vary in complexity; our preference was for a
simple approach that could be realized in almost any language on almost
any computer by a programmer of moderate skill, allowing the protocol to
be adapted easily to new systems.
6
* Accommodating Diverse Systems
Most systems agree how to communicate at the lowest levels -- the EIA
RS-232-C asynchronous communication line and the ASCII character set
-- but there is rarely agreement beyond that. To avoid a design that
might lock out some kinds of systems, we must consider certain important
ways in which systems can differ.
. Mainframes vs Micros
A distinction must first be made between micros and mainframes. These
terms are not used perjoratively; a ``micro'' could be a powerful
workstation, and a ``mainframe'' could be a small minicomputer. For our
purposes, a micro is any single-user system in which the serial com-
munication port is strictly an external device. A mainframe is any sys-
tem which is ``host'' to multiple simultaneous terminal users, who log
in to ``jobs'', and where a user's terminal is the job's ``controlling
terminal''. Some mainframe systems allow users to ``assign'' another
terminal line on the same machine as an external input/output device.
Mainframe operating system terminal drivers usually treat a job's con-
trolling terminal specially. Full duplex systems echo incoming charac-
ters on the controlling terminal, but not on an assigned line. System
command interpreters or user processes might take special action on cer-
tain characters on the controlling line, but not on an assigned line
(for instance, control-C under CP/M or most DEC operating systems).
7
Messages sent to a job's controlling terminal from other jobs could in-
terfere with transmission of data. The ability of a system to test for
the availability of input on a serial line might depend on whether the
line is the job's controlling terminal or an assigned device; CP/M and
IBM VM/370 are examples of such systems. CP/M can test for data only at
the console, VM can test anywhere but the console.
Output to a job's controlling terminal may be reformatted by the
operating system: control characters may be translated to printable
equivalents, lower case letters specially flagged or translated to upper
case (or vice versa), tabs expanded to spaces. In addition, based on
the terminal's declared ``width'' and ``length'', long lines might be
``wrapped around'' or truncated, formfeeds translated to a series of
linefeeds, and the system may want to pause at the end of each screenful
of output. Input from a job's controlling terminal may also be handled
specially: lower case letters may be converted to upper case, linefeed
may be supplied when carriage return is typed, control characters may
invoke special functions like line editing or program interruption. The
DECSYSTEM-20 is an example of a computer where any of these might hap-
pen.
The moral here is that care must be taken to disable special handling
of a mainframe job's controlling terminal when it is to be a vehicle for
interprocessor communication. But some systems simply do not allow cer-
tain of these features to be disabled, so file transfer protocols must
be designed around them.
8
. Line Access
Line access can be either full or half duplex. If full duplex, trans-
mission can occur in both directions at once. If half duplex, the two
sides must take turns sending, each signaling the other when the line is
free; data sent out of turn is discarded, or it can cause a break in
synchronization. On mainframes, the host echoes characters typed at the
terminal in full duplex, but not in half duplex. Naturally, echoing is
undesirable during file transfer. Full duplex systems can usually ac-
commodate half duplex communication, but not vice versa. IBM mainframes
are the most prevalent half duplex systems.
. Buffering and Flow Control
Some systems cannot handle sustained bursts of input on a telecom-
munications line; the input buffer can fill up faster than it can be
emptied, especially at high line speeds. Some systems attempt to buffer
``typeahead'' (unrequested input), while others discard it. Those that
buffer typeahead may or may not provide a mechanism to test or clear the
buffer.
Systems may try to regulate how fast characters come in using a flow
control mechanism, either in the data stream (XON/XOFF) or in parallel
to it (modem control signals) [5], but no two systems can be assumed to
honor the same conventions for flow control, or to do it at all. Even
when flow control is being done, the control signals themselves are sub-
9
ject to noise corruption.
Our experiments with several host computers revealed that a burst of
more than about a line's worth of characters (60-100 characters) into a
terminal port at moderate speed could result in loss of data -- or worse
-- on some hosts. For instance, the communications front end of the
DECSYSTEM-2060 is designed on the statistical assumption that all ter-
minal input comes from human fingers, and it cannot allocate buffers
fast enough when this assumption is violated by sending continuous data
simultaneously from several microcomputers attached to terminal ports.
. Character Interpretation
Systems can differ in how they interpret characters that arrive at the
terminal port. A host can accept some characters as sent, ignore
others, translate others, take special action on others. Communications
front ends or multiplexers might swallow certain characters (typically
DC1, DC3) for flow control, padding (NUL or DEL), or for transfer of
control (``escape''). The characters that typically trigger special be-
havior are the ASCII control characters, 0-31 and 127. For instance, of
these 33 control characters, 17 invoke special functions of our
DECSYSTEM-20 command processor. However, all hosts and communication
processors we've encountered allow any ``printable'' character (ASCII
32-126) to reach an application program, even though the character may
be translated to a different encoding, like EBCDIC [6], for internal
10
use.
Some operating systems allow an application to input a character at a
time, others delay passing the characters to the program until a
``logical record'' has been detected, usually a sequence of characters
terminated by carriage return or linefeed. Some record oriented systems
like IBM VM/370 discard the terminator, others keep it. And there are
different ways of keeping it -- UNIX translates carriage return into
linefeed; most DEC operating systems keep the carriage return but also
add a linefeed.
. Timing Out
Hosts may or may not have the ability to ``time out''. When exchang-
ing messages with another computer, it is desirable to be able to issue
an input request without waiting forever should the incoming data be
lost. A lost message could result in a protocol ``deadlock'' in which
one system is waiting forever for the message while the other waits for
a response. Some systems can set timer interrupts to allow escape from
potentially blocking operations; others, including many microcomputers,
can not do so. When timeouts are not possible, they may be simulated by
sleep-and-test or loop-and-test operations, or deadlocked systems may be
awakened by manual intervention.
11
. File Organization
Some computers store all files in a uniform way, such as the linear
stream of bytes that is a UNIX file. Other computers may have more com-
plicated or diverse file organizations and access methods: record-
oriented storage with its many variations, exemplified in IBM OS/360 or
DEC RMS. Even simple microcomputers can present complications when
files are treated as uniform data to be transferred; for instance under
CP/M, the ends of binary and text files are determined differently. A
major question in any operating system is whether a file is specified
sufficiently by its contents and its name, or if additional external in-
formation is required to make the file valid. A simple generalized file
transfer facility can be expected to transmit a file's name and con-
tents, but not every conceivable attribute a file might possess.
Designers of expensive networks have gone to great lengths to pass
file attributes along when transferring files between unlike systems.
For instance, the DECnet Data Access Protocol [7] supports 42 different
``generic system capabilities'' (like whether files can be preallocated,
appended to, accessed randomly, etc), 8 data types (ASCII, EBCDIC, ex-
ecutable, etc), 4 organizations (sequential, relative, indexed, hashed),
5 record formats (fixed, variable, etc), 8 record attributes (for format
control), 14 file allocation attributes (byte size, record size, block
size, etc), 28 access options (supersede, update, append, rewind, etc),
26 device characteristics (terminal, directory structured, shared,
12
spooled, etc), various access options (new, old, rename, password, etc),
in addition to the better known file attributes like name, creation
date, protection code, and so on. All this was deemed necessary even
when the designers had only a small number of machines to worry about,
all from a single vendor.
The ARPA network, which attempts to provide services for many more
machines from many vendors, makes some simplifying assumptions and sets
some restrictions in its File Transfer Protocol (FTP) [8]. All files
are forced into certain categories with respect to encoding (ASCII,
EBCDIC, image), record format control, byte size, file structure (record
or stream), and it is generally left to the host FTP implementation to
do the necessary transformations. No particular provision is made, or
can be made, to ensure that such transformations are invertible.
DECnet is able to provide invertibility for operating systems like VMS
or RSX, which can store the necessary file attributes along with the
file. But simpler file systems, like those of TOPS-10 or TOPS-20, can
lose vital information about incoming files. For instance, if VMS re-
quires some type of file to have a specific blocksize, while TOPS-20 has
no concept of block size, then the blocksize will be lost upon transfer
from VMS to TOPS-20 and cannot be restored automatically when the file
is sent back, leaving the result potentially unusable.
Invertibility is a major problem, with no simple solution. For-
tunately, most file transfer between unlike systems involves only tex-
tual information -- data, documents, program source -- which is sequen-
13
tial in organization, and for which any required transformations
(e.g. blocked to stream, EBCDIC to ASCII) are simple and not dependent
on any special file attributes.
In fact, invertability can be achieved if that is the primary goal of
a file transfer protocol. All the external attributes of a file can be
encoded and included with the contents of the file to be stored on the
remote system. For unlike systems, this can render the file less than
useful on the target system, but allows it to be restored correctly upon
return. However, it is more commonly desired that textual files remain
intelligible when transferred to a foreign system, even if transfor-
mations must be made. To allow the necessary transformations to take
place on textual files between unlike systems, there must be a standard
way of representing these files during transmission.
. Binary Files versus Parity
Each ASCII character is represented by a string of 7 bits. Printable
ASCII files can be transmitted in a straightforward fashion, because AS-
CII transmission is designed for them: a serial stream of 8-bit charac-
ters, 7 bits for data and 1 for parity, framed by start and stop bits
for the benefit of the hardware [3]. The parity bit is added as a check
on the integrity of a character; some systems always transmit parity,
others insist on parity for incoming characters, still others ignore the
parity bit for communication purposes and pass it along to the software,
14
while still others discard it altogether. In addition, communication
front ends or common carriers might usurp the parity bit, regardless of
what the system itself may do.
Computer file systems generally store an ASCII file as a sequence of
either 7-bit or 8-bit bytes. 8-bit bytes are more common, in which the
8th bit of each byte is superfluous. Besides files composed of ASCII
characters, however, computers also have ``binary'' files, in which
every bit is meaningful; examples include executable ``core images'' of
programs, numbers stored in ``internal format'', databases with imbedded
pointers. Such binary data must be mapped to ASCII characters for
transmission over serial lines. When two systems allow the user-level
software to control the parity bit, the ANSI standards [2, 3] may be
stretched to permit the transmission of 8 data bits per character, which
corresponds to the byte size of most machines. But since not all com-
puters allow this flexibility, the ability to transfer binary data in
this fashion cannot be assumed.
. Software
Finally, systems differ in the application software they have. In
particular, no system can be assumed to have a particular programming
language. Even widespread languages like FORTRAN and BASIC may be lack-
ing from some computers, either because they have not been implemented,
or because they are proprietary and have not been purchased. Even when
15
two different systems support the same language, it is unrealistic to
expect the two implementations of the language to be totally compatible.
A general purpose file transfer protocol should not be geared towards
the features any particular language.
* KERMIT
Our protocol, which we call KERMIT, addresses the problems outlined
above by setting certain minimal standards for transmission, and provid-
ing a mapping between disk storage organization, machine word and byte
size, and the transmission medium.
KERMIT has the following characteristics:
- Communication takes place over ordinary terminal connections.
- Communication is half duplex. This allows both full and half
duplex systems to participate, and it eliminates the echoing
that would otherwise occur for characters arriving at a host
job's controlling terminal.
- The packet length is variable, but the maximum is 96 charac-
ters so that most hosts can take packets in without buffering
problems.
- Packets are sent in alternate directions; a reply is required
for each packet. This is to allow half duplex systems to par-
ticipate, and to prevent buffer overruns that would occur on
some systems if packets were sent back to back.
- A timeout facility, when available, allows transmission to re-
sume after lost packets.
- All transmission is in ASCII. Any non-ASCII hosts are respon-
sible for conversion. ASCII control characters are prefixed
and then converted to printable characters during transmission
16
to ensure that they arrive as sent. A single ASCII control
character (normally SOH) is used to mark the beginning of a
packet.
- Binary files can be transmitted by a similar prefix scheme, or
by use of the parity bit when both sides have control of it.
- Logical records (lines) in textual files are terminated during
transmission with quoted carriage-return/linefeed sequences,
which are transparent to the protocol and may appear anywhere
in a packet. Systems that delimit records in other ways are
responsible for conversion, if they desire the distinction be-
tween records to be preserved across unlike systems.
- Only a file's name and contents are transmitted -- no at-
tributes. It is the user's responsibility to see that the
file is stored correctly on the target system. Within this
framework, invertible transfer of text files can be assured,
but invertible transfer of non-text files depends on the
capabilities of the particular implementations of KERMIT and
the host operating systems.
- KERMIT has no special knowledge of the host on the other side.
No attempt is made to ``integrate'' the two sides. Rather,
KERMIT is designed to work more or less uniformly on all sys-
tems.
- KERMIT need not be written in any particular language. It is
not a portable program, but a portable protocol.
Thus KERMIT accommodates itself to many systems by conforming to a
common subset of their features. But the resulting simplicity and
generality allow KERMIT on any machine to communicate with KERMIT on any
other machine, micro-to-mainframe, micro-to-micro, mainframe-to-
mainframe. The back-and-forth exchange of packets keeps the two sides
synchronized; the protocol can be called ``asynchronous'' only because
the communication hardware itself operates asynchronously.
As far as the user is concerned, KERMIT is a do-it-yourself operation.
17
For instance, to transfer files between your micro and a mainframe, you
would run KERMIT on your micro, put KERMIT into terminal emulation mode,
which ``connects'' you to the mainframe, log in and run KERMIT on the
mainframe, then ``escape'' back to the micro and issue commands to the
micro's KERMIT to send or fetch the desired files. Any inconvenience
implicit in this procedure is a consequence of the power it gives the
ordinary user to establish reliable connections between computers that
could not otherwise be connected.
* Packets
KERMIT packets need to contain the data that is being transferred,
plus minimum information to assure (with high probability) that the ex-
pected data arrives completely and correctly. Several issues come up
when designing the packet layout: how to represent data, how to delimit
fields within the packet, how to delimit the packet itself, how to ar-
range the fields within the packet. Since the transmission medium it-
self is character-oriented, it is not feasible to transmit bit strings
of arbitrary length, as do the bit-oriented protocols like HDLC and SDLC
[5]. Therefore the smallest unit of information in a packet must be
the ASCII character. As we will see, this precludes some techniques
that are used with other communication media.
18
. Control Fields
Most popular protocol definitions view the packet as layers of infor-
mation, which pass through a hierarchy of protocol levels, each level
adding its own information at the ends of an outbound packet or strip-
ping its information from the ends of an incoming packet, and then pass-
ing the result along to the next level in the hierarchy. The fields for
each layer must be arranged so that they can be found, identified, and
interpreted correctly at the appropriate level.
Since KERMIT packets are short, it is important to minimize the amount
of control information per packet. It would be convenient to limit the
control fields to one character each. Since we have 95 printable
characters to work with (128 ASCII characters, less DEL and the 32 con-
trol characters), we can represent values from 0 to 94 with a single
character.
- The packet sequence number is used to detect missing or dupli-
cate packets. It is unlikely that a large number of packets
could be lost, especially since packet n is acknowledged be-
fore packet n+1 is sent. So the sequence number can be a
small quantity, which ``wraps around'' to its minimum value
when it exceeds a specified maximum value.
- To prevent long packets, a small maximum length can be en-
forced by specifying the packet length with a single charac-
ter; since there are 95 printable ASCII characters, this would
be the maximum length, depending on how we count the control
fields.
- The checksum can be of fixed length. The actual length
depends on the desired balance between and efficiency and er-
ror detection.
19
The packet length and checksum act together to detect corrupted, miss-
ing, or extra characters. These are the essential fields for promoting
error-free transmission. But so far, we've only considered packets that
carry actual file data; we will also require special packets composed
only of control information, for instance to tell the remote host the
name of the file that is about to come, or to tell it that the transmis-
sion is complete. This can be accomplished with a packet type field.
The number of functions we need to specify in this field is small, so a
single character can suffice here too.
. Packet Framing
We choose to mark the beginning of a packet with a distinguished start
character, SOH (Start Of Header, ASCII 1, Control-A). This character
cannot appear anywhere else within the packet. SOH was chosen because,
unlike most other control characters, it is generally accepted upon in-
put at a job's controlling terminal as a data character, rather than an
interrupt or break character on most mainframes. This is probably no
accident, since it was originally intended for this use by the designers
of the ASCII alphabet [9]. Should a system be incapable of sending or
receiving SOH, it is possible to redefine the start-of-packet character
to be any other control character; the two sides need not use the same
one.
There are three principal options for recognizing the end of a packet:
20
a fixed length, a distinguished packet-end character, and a length
field. There are arguments for and against each involving what happens
when characters, particularly a length or terminator, is lost or
garbled, which will be mentioned later. KERMIT uses a length field.
To take in a packet, a KERMIT program gets characters from the line
until it encounters the SOH. The next character is the length; KERMIT
reads and decodes the length and then reads that many subsequent charac-
ters to complete the packet. If another SOH is encountered before the
count is exhausted, the current packet is forgotten and a new one is
started. This stratagy allows arbitrary amounts of noise to be
generated spontaneously between packets without interfering with the
protocol.
. Encoding
When transmitting textual data, KERMIT terminates logical records with
carriage-return linefeed combinations (CRLFs). On record oriented sys-
tems, trailing blanks or length fields are removed and a CRLF appended
to outbound records, with the inverse operation performed on incoming
records. On stream oriented systems, incoming CRLFs may be translated
to some other terminator. Files, of course, need not have logical
records, in which case record processing can be skipped altogether, and
the file can be treated as a long string of bytes. This is known as
``image'' transfer, and can also be used between like systems where no
21
transformations are necessary.
In order to make each character in the packet printable, KERMIT
``quotes'' any unprintable character by transforming it to a printable
one and precedes it with a special prefix character. The prefix is nor-
mally ``#''; the transformation is done by complementing bit 6 (adding
or subtracting 64 , modulo 64). Thus control-A becomes ``#A'',
10
control-Z becomes ``#Z'', US (control-underscore on most terminals) be-
comes ``#_''. The prefix character is also used to quote itself:
``##''. Upon input, the reverse transformation is performed. Printable
characters are not tranformed. The assumption is that most files to be
transferred are printable, and printable files contain relatively few
control characters; when this is true, the character stream is not sig-
nificantly lengthened by quoting. For binary files, the average quoting
overhead will be 26.6% if all bit patterns are equally likely, since the
characters that must be quoted (the control characters, plus DEL, and
``#'' itself) comprise 26.6% of the ASCII alphabet.
KERMIT also provides a scheme for indicating the status of the 8th bit
when transferring binary files between systems that must use the 8th bit
for parity. A byte whose 8th bit is set is preceded by another special
quoting character, ``&''. If the low-order 7 bits coincide with an AS-
CII control character, then control-character quoting is also done. For
instance, the byte 10000001 would be transmitted as ``A''. The ``&''
2
character itself can be included as data by quoting it (#&), and the
control-quote character may have its 8th bit set (#). 8th-bit quoting
22
is only done when necessary; if both sides can control the parity bit,
then its value is preserved during transmission. If the 8th bit is set
randomly on binary files, then 8th-bit quoting will add 50% character
overhead. For some kinds of binary data, it could be less; for in-
stance, positive binary numbers in 2's complement notation do not to
have their high-order bits set, in which case at least one byte per word
will not be quoted.
A third kind of ``quoting'' implements rudimentary data compression.
At low speeds, the bottleneck in file transmission is likely to be the
line itself, so any measure that can cut down on use of the line would
be welcome. The special prefix character ``~'' indicates that the next
character is a repeat count (a single character, encoded printably) and
that the character after that (which may also have control or 8th-bit
prefixes) is repeated so many times. For instance ``~}A'' indicates a
series of 93 letter A's; ``~HB'' indicates a series of 40 control-B's
with the parity bit set. The repeat count prefix itself can be included
as text by quoting it with ``#''.
To keep the protocol simple, no other transformations are done. At
this point, however, it might be worth mentioning some things we did not
do to the data:
- Fancy Data compression. If the data is known to be (or
resemble) English text, a Huffman encoding [10, 11] based on
the frequency of characters in English text could be used. A
Huffman code resembles Morse code, which has variable length
characters whose boundaries can always be distinguished. The
more frequent the character, the shorter the bit string to
23
represent it. Of course, this scheme can backfire if the
character distribution of the data is very different from the
one assumed. In any case, variable length characters and AS-
CII transmission don't mix well.
- Error Correcting Codes. Techniques, such as Hamming codes
[12], exist for detecting and correcting errors on a per-
character basis. These are expensive in resources and complex
to program. KERMIT uses per-packet block check techniques,
which are explained below.
- Nibble Encoding. To circumvent problems with control and
8-bit characters, it would have been possible to divide every
character into two 4-bit ``nibbles'', sending each nibble as a
printable character (e.g. a hexadecimal digit). The character
overhead caused by this scheme would would always be 100%.
But it would be an easy way to transfer binary files.
. Error Detection
Character parity and Hamming codes are forms of ``vertical redundancy
checks'' (VRCs), formed by combining all the bits of a character in one
way or another. The other kind of check that can be used is the
``longitudinal redundancy check'' (LRC), which produces a ``block check
character'' formed by some combination of each character within a se-
quence. The sending side computes the LRC and sends it with the packet;
the receiving side recomputes it for comparison. There are various
forms of LRCs. One form produces a ``column parity'' character, or
``logical sum'', whose bits are the exclusive-ORs of the corresponding
bits of the data characters. Another is the ``checksum'' which is the
arithmetic sum of all the characters in the sequence, interpreted
numerically. Another is the ``Cyclic Redundancy Check'' (CRC) [13, 14],
24
which passes the characters through what amounts to a shift register
with imbedded feedback loops, producing a block check in which each bit
is effected in many ways by the preceding characters.
All of these techniques will catch single-bit errors. They vary in
their ability to detect other kinds of errors. For instance, a double-
bit column error will always go undetected with column parity, since the
result of XORing any two bits together is the same as XORing their
complements, whereas half the possible double bit errors can be caught
by addition because of the carry into the next bit position. CRC does
even better by rippling the effect of a data bit multiply through the
block check character, but the method is complex, and a software im-
plementation of CRC can be inscrutable.
Standard, base-level KERMIT employs a single-character arithmetic
checksum, which is simple to program, is low in overhead, and has proven
quite adequate in practice. The sum is formed by adding together the
ASCII values of each character in the packet except the SOH and the
checksum itself, and including any quoting characters. Even non-ASCII
hosts must do this calculation in ASCII. The result can approach
12,000 in the worst case. The binary representation of this number is
10
10111011100000, which is 14 bits long. This is much more than one
character's worth of bits, but we can make the observation that every
character included in the sum has contributed to the low order 7 bits,
so we can discard some high order bits and still have a viable validity
check.
25
The KERMIT protocol also allows other block check options, including a
two-character checksum and a three-character 16-bit CRC. The two-
character checksum is simply the low order 12 bits of the arithmetic
sum, broken into two printable characters. The CRC sequence is formed
from the 16-bit quantity generated by the CCITT-recommended polynomial
16 12 5
X +X +X +1 which is also used in some form with other popular trans-
mission techniques, like ISO HDLC and IBM SDLC [5]. The high order 4
bits of the CRC go into the first character, the middle 6 into the
second, and the low order 6 into the third.
Some care must be taken in the formation of the single-character block
check. Since it must be expressed as a single printable character,
values of the high order data bits may be lost, which could result in
undetected errors, especially when transferring binary files. There-
fore, we extract the 7th and 8th bits of the sum and add them back to
the low order bits; if the arithmetic sum of all the characters is S,
then the value of the single-character KERMIT checksum is given by
(S + ((S AND 300)/100)) AND 77
(numbers are in octal notation). This ensures that the checksum, terse
though it is, reflects every bit from every character in the packet.
The probability that an error will not be caught by a correctly trans-
mitted arithmetic checksum is the ratio of the number of possible errors
that cancel each other out to the total number of possible errors, which
n
works out to be something like 1/2 , where n is the number of bits in
26
the checksum, assuming all errors are equally likely. This is 1/64 for
the single character checksum, and 1/4096 for the 2-character checksum.
But the probability that errors will go undetected by this method under
real conditions cannot be easily derived, because all kinds of errors
are not equally likely. A 16-bit CRC will detect all single and double
bit errors, all messages with an odd number of bits in error, all error
bursts shorter than 16 bits, and better than 99.99% of longer bursts
[13]. These probabilities all assume, of course, that the block check
has been identified correctly, i.e. that the length field points to it,
and that no intervening characters have been lost or spuriously added.
A final note on parity -- a parity bit on each character combined with
a logical sum of all the characters (VRC and LRC) would allow detection
and correction of single-bit errors without retransmission by pinpoint-
ing the ``row'' and ``column'' of the bad bit. But control of the
parity bit cannot be achieved on every system, so we use the parity bit
for binary data when we can, or surrender it to the communication
hardware if we must. If we have use of the 8th bit for data, then it is
figured into the block check; if we do not, then it must be omitted from
the block check in case it has been changed by agents beyond the
knowledge or control of the KERMIT program.
27
. Packet Layout
KERMIT packets have the format:
+------+-----------+-----------+------+------------+-------+
| MARK | char(LEN) | char(SEQ) | TYPE | DATA | CHECK |
+------+-----------+-----------+------+------------+-------+
| | | | |
| | +-- (application) --+ |
| | | |
| +-------------- (session) ------+ |
| |
+--------------------------------- (data link) ------------+
where all fields consist of ASCII characters, and the char function con-
verts a number in the range 0-94 to a printable ASCII character by ad-
10
ding 32 .
10
In terms of the ISO network reference model [15], 8-bit bytes are
presented to the KERMIT program by the hardware and operating system
software comprising the physical link layer. Correct transmission is
ensured by the packet-level routines that implement the data link layer
using the outer ``skin'' of the packet -- the MARK, LEN, and CHECK
fields. The network and transport layers are moot, since KERMIT is a
point-to-point affair, in which the user personally makes all the re-
quired connections. The session layer is responsible for requesting
retransmission of missing packets or ignoring redundant ones, based on
the SEQ field; the presentation layer is responsible for any data con-
versions (EBCDIC/ASCII, insertion or stripping of CRLFs, etc). Finally,
the remainder of the packet, the TYPE and DATA fields, are the province
28
of the application layer; our application, of course, is file transfer.
In any particular implementation, however, the organization of the
program may not strictly follow this model. For instance, since trans-
mission is always in stream ASCII, IBM implementations must convert from
EBCDIC and insert CRLFs before checksum computation.
The fields of a KERMIT packet are as follows:
MARK Start-of-packet character, normally SOH (ASCII 1).
LEN The number of ASCII characters, including quoting characters
and the checksum, within the packet that follow this field, in
other words the packet length minus two. Since this number is
expressed as a single character via the char function, packet
character counts of 0 to 94 are permitted, and 96 is the
10 10
maximum total packet length.
SEQ The packet sequence number, modulo 100 . The sequence numbers
8
``wraps around'' to 0 after each group of 64 packets.
10
TYPE The packet type, a single printable ASCII character, one of
the following:
D Data
Y Acknowledge (ACK)
N Negative Acknowledge (NAK)
S Send Initiate (Send-Init)
R Receive Initiate
B Break Transmission (EOT)
F File Header
Z End of file (EOF)
E Error
G Generic Command. A single character in the data field,
possibly followed by operands, requests host-independent
remote execution the specified command:
L Logout, Bye.
F Finish, but don't logout.
29
D Directory query (followed by optional file
specification).
U Disk usage query.
E Erase (followed by file specification).
T Type (followed by file specification).
Q Query server status.
and others.
C Host Command. The data field contains a string to be ex-
ecuted as a system dependent (literal) command by the
host.
X Text display header, to indicate the arrival of text to be
displayed on the screen, for instance as the result of a
generic or host command executed at the other end. Opera-
tion is exactly like a file transfer.
DATA The ``contents'' of the packet, if any contents are required
in the given type of packet, interpreted according to the
packet type. Nonprintable ASCII characters are prefixed with
quote characters and then ``uncontrollified''. Characters
with the 8th bit set may also be prefixed, and a repeated
character can be prefixed by a count. A prefixed sequence may
not be broken across packets.
CHECK The block check sequence, based on all the characters in the
packet between, but not including, the mark and the check it-
self, one, two, or three characters in length as described
above, each character transformed by char. Normally, the
single-character checksum is used.
The packet may be followed by any line terminator required by the host,
carriage return (ASCII 15) by default. Line terminators are not part of
the packet, and are not included in the count or checksum. Terminators
are not necessary to the protocol, and are invisible to it, as are any
characters that may appear between packets. If a host cannot do single
character input from a TTY line, then a terminator will be required for
that host.
Here are some sample KERMIT data packets:
30
^AE"D No celestial body has required J
^AE#Das much labor for the study of its#
^AE$D#M#Jmotion as the moon. Since ClaA
^AE%Dirault (1747), who indicated a way7
^AE&D of#M#Jconstructing a theory conta5
The ``^A'' represents the SOH (or Control-A) character. In the final
packet shown, ``E'' is the length. The ASCII value of the ``E'' charac-
ter is 69 , less 32 (the unchar transformation, which is the opposite
10
of char) gives a length of 37. The next character tells the packet se-
quence number, in this case 6 (``&'' is ASCII 38). The next is the
packet type ``D'' for Data. The next characters, `` of#M#Jconstructing
a theory conta'', form the data; note the prefixed carriage return and
line feed. The final character, ``5'' is the checksum, which represents
the number 21 (all numbers in this paragraph are in decimal).
. Effects of Packet Corruption
What are the consequences of transmission errors in the various
fields? If the SOH is garbled, the packet will be treated as inter-
packet garbage, and lost. If any other character within the packet is
garbled into SOH, the current packet will be discarded, and a new
(spurious) packet detected. If the length is garbled into a smaller
number, then a character from the data field will be misinterpreted as
the checksum; if larger, then the program will probably become stuck
trying to input characters that will not be sent until one side or the
other times out and retransmits. If the sequence number, type, any of
31
the data characters, or the checksum itself is garbled, the checksum
should be wrong. If characters are lost, there will most likely be a
timeout. If noise characters are spontaneously generated, they will be
ignored if they are between packets, or will cause the wrong character
to be interpreted as the checksum if they come during packet transmis-
sion.
Most kinds of errors are caught by the checksum comparison, and are
handled by immediate retransmission. Timeouts are more costly because
the line sits idle for the timeout period. The packet design minimizes
the necessity for timeouts due to packet corruption: the only fields
that can be corrupted to cause a timeout are the SOH and the packet
length, and the latter only half the time. Lost characters, however,
can produce the same effect (as they would with a fixed-length block
protocol). Had a distinguished end-of-packet character been used rather
than a length field, then there would be a timeout every time it was
corrupted. It is always better to retransmit immediately than to time
out.
32
* Protocol
The KERMIT protocol can be described as a set of states and a set of
transitions that define, for a given event, what action to take and what
new state to change to. The inherent simplicity of the design, par-
ticularly the requirement that each packet must be acknowledged, reduces
the number of states and actions, and the amount of state information
that must be maintained, to a minimum.
Here is a simplified version of a state diagram for KERMIT receiving a
file:
+--------------+
| Receive Init |
+--------------+
|
| (Get Send Init Packet)
|
(Get EOT Packet) V
+--------------+
(Done) <------------------| Receive File |<---------------+
+--------------+ |
| |
| (Get File | (Get EOF Packet)
| Header Packet) |
V |
+--------------+ |
+------>| Receive Data |----------------+
| +--------------+
| |
| | (Get Data Packet)
| |
+---------------+
For simplicity, some transitions are not shown in the diagram:
33
- If in any state a bad packet is received or a timeout occurs,
a null transition back to the same state occurs, with a NAK
for the expected packet.
- In any state an error may occur that can cause the transfer to
terminate. For instance, the target disk might fill up. The
side that encountered the error sends an error packet, con-
taining an informative error message, and quits. Upon receipt
of the error packet, the other side displays the message on
the screen (if it is in control of the screen) and also quits.
- Actions that are taken on each transition, such as opening a
file when a File Header packet is received, are not shown; in
particular each packet successfully received is ACK'd.
The receiver starts out in Receive Init state and waits for the other
side to send a Send-Init packet. If any other kind of packet is
received, or the Send-Init does not arrive within the timeout interval,
a NAK is sent. Timeouts or NAKs can occur up to a threshold which, when
exceeded for a particular packet, causes the protocol to assume that the
connection has become unusable, and to give up. After the Send-Init ar-
rives, the state becomes Receive File; KERMIT waits for a File Header
packet containing the name of the file which is to come. When the file
header arrives, KERMIT opens a new file using the name provided (perhaps
transformed to suit local naming conventions, or to avoid a name
collision), and switches to Receive Data state. KERMIT then receives
the contents of the file, until an EOF (End Of File) packet arrives. At
that point KERMIT switches back to Receive File state. If another file
is to be sent, another File Header packet will follow, otherwise an EOT
(End Of Transmission) packet will terminate the transfer. The distinc-
tion between EOF and EOT, plus the File Header itself, allows files to
34
be sent in groups. EOF marks the end of a file, EOT marks the end of a
group. This distinction also allows the two sides to disconnect
cleanly: the EOF must be ACK'd before the sender will believe the file
has been transmitted correctly; the EOT will follow, but if the ACK
which is sent in response is lost, no harm will be done since both sides
are terminating anyway.
The state transitions for a sending KERMIT are similar. In each
state, instead of waiting for particular packet types, KERMIT sends the
appropriate packet and waits for an ACK. If the ACK does not arrive
within the allotted time, or a NAK appears instead of an ACK, the same
packet is retransmitted. A send operation begins with a Send-Init
packet, includes one or more files, each starting with a File Header,
followed by one or more data packets, followed by EOF. When all the
specified files have been sent, an EOT packet closes the connection and
terminates the operation.
35
+-----------+
| Send Init |
+-----------+
|
| (Get Good ACK)
|
(No more files to send) V
+----------+ +-----------+
| Send EOT |<-------------| Send File |<---------------+
+----------+ +-----------+ |
| |
| (Good ACK) | (EOF)
| |
V |
+-----------+ |
+------>| Send Data |----------------+
| +-----------+
| |
| | (Good ACK)
| |
+---------------+
Base-level KERMIT provides that during any particular transaction, the
sender is the ``master'' and the receiver is the ``slave''. These roles
may be reversed in the next transaction; any KERMIT implementation is
capable of acting as either master or slave. In addition, mainframe im-
plementations may also be put in a kind of permanent slave, or
``server'', mode in which all commands come in command packets from the
master, or ``user'' KERMIT.
36
. Initial Connection
To allow a diverse group of computers to communicate with one another,
an exchange takes places during initial connection in which the two
sides ``configure'' each other. The sending KERMIT includes setup
parameters in its Send-Init packet and the receiving KERMIT responds
with an ACK packet containing the corresponding parameters as they apply
to itself. The Data field of the Send-Init packet looks like this:
1 2 3 4 5 6 7 8 9 10
+------+------+------+------+------+------+------+------+------+-------------
| MAXL | TIME | NPAD | PADC | EOL | QCTL | QBIN | CHKT | REPT | CAPAS...
+------+------+------+------+------+------+------+------+------+-------------
The fields are as follows (the first and second person ``I'' and ``you''
are used to distinguish the two sides). Fields are encoded printably
using the char function (ASCII value + 32 ) unless indicated otherwise.
10
MAXL The maximum length packet I want to receive, a number up to
94 .You respond with the maximum you want me to send. This al-
10
lows systems to adjust to each other's buffer sizes, or to the
condition of the transmission medium.
TIME The number of seconds after which I want you to time me out
while waiting for a packet from me. You respond with the amount
of time I should wait for packets from you. This allows the two
sides to accommodate to different line speeds or other factors
that could cause timing problems.
NPAD The number of padding characters I want to precede each incoming
packet; you respond in kind. Padding may be necessary for a
half duplex system that requires some time to change the direc-
tion of transmission.
PADC The control character I need for padding, if any, XOR'd with 100
octal to make it printable. You respond in kind. Normally NUL
(ASCII 0), some systems use DEL (ASCII 177). This field is ig-
nored if the value NPAD is zero.
37
EOL The character I need to terminate an incoming packet, if any.
You respond in kind. Most systems that require a line ter-
minator for terminal input accept carriage return for this pur-
pose. (Can you see the Catch-22 here?)
QCTL The printable ASCII character I will use to quote control
characters and prefix characters, normally ``#''. You respond
with the one you will use.
QBIN The printable ASCII character I want to use to quote characters
which have the 8th bit set, for transmitting binary files when
one or both systems cannot use the parity bit for data. Since
this kind of quoting increases both processor and transmission
overhead, it is normally to be avoided.
CHKT Check Type, the method for detecting errors. ``1'' for single-
character checksum (the normal method), ``2'' for two-character
checksum, ``3'' for three-character CRC-CCITT. If your response
agrees, the designated method will be used; otherwise the
single-character checksum will be used. Other check types may
also be added.
REPT The prefix character I will use to indicate a repeated charac-
ter. This can be any printable character other than blank
(which denotes no repeat count prefix), but ``~'' is recom-
mended. If you don't respond identically, repeat counts will
not be done. Groups of 4 or more identical characters may be
transmitted more efficiently using a repeat count, though an in-
dividual implementation may wish to set a higher threshhold.
CAPAS An extendable bit mask encoded printably, to indicate whether
certain advanced capabilities, such as file-attribute packets,
are supported.
Reserved Fields
The next four fields are reserved for future use. Sites wishing
to add their own parameters to the initial connection exchange
should start at the fifth field after the capability mask in or-
der to remain compatible with other KERMIT programs.
Naturally, the three prefix characters must be distinct and should be
chosen to be uncommonly used printable characters, to minimize further
overhead from having to prefix them when they are found in the data.
Trailing fields within the DATA field may be omitted, in which case
they will assume appropriate defaults. Defaults for intermediate fields
can be elected by setting those fields to blank. Every parameter has an
38
appropriate default, and in fact the entire data field of the Send Init
packet or its ACK may be left empty to accept all defaults. The more
exotic paramaters are at the end, and reflect more recent developments
in the KERMIT protocol; earlier implementations can still communicate
with newer ones, since there will not be agreement to use these options.
The Send-Init mechanism preserves compatibility from the very earliest
KERMIT to the very newest.
There is no protracted negotiation; everything must be settled in a
single exchange. Some parameters, however, are outside the scope of
this exchange and must be set even before the very first packet is sent.
For instance, if the receiving computer can only read characters with
odd parity but the sending computer sends them with even parity, the
Send-Init packet will never arrive successfully. In cases like this,
the user may have to issue some preliminary commands to inform one or
both KERMITs about the vagaries of the other system. Another example is
the packet terminator (EOL) mentioned above -- if the receiving KERMIT
requires one that the sending KERMIT doesn't know about, the Send-Init
will never get through.
For these reasons, most implementations of KERMIT provide SET commands
for all the parameters listed above, and some others as well.
39
. Rules and Heuristics
During a file transfer, one KERMIT sends information packets -- file
headers, data, and so forth, and the other KERMIT sends only ACKs or
NAKs in response. The most important rule in the KERMIT protocol is
1. ``Wait for a response before sending the next packet.''
This prevents buffer overruns, and allows participation by half duplex
systems. Of course, KERMIT should not wait forever; a timeout should
occur after a few seconds if the expected packet has not arrived. Upon
timeout, a sending KERMIT retransmits the current packet; a receiving
KERMIT re-ACKs the current packet or NAKs the expected one.
Some interesting heuristics are used in the KERMIT protocol to boost
efficiency and improve error recovery. A number of important rules take
care of the cases when packets are lost in transmission. The first can
be stated as
2. ``A NAK for the next packet implies an ACK for the current
packet.''
A NAK with packet number n+1 means the receiving KERMIT got packet n,
sent an ACK that was never received, and not knowing that the ACK didn't
get through (since we don't ACK an ACK), is now waiting for packet n+1,
which was never sent. In this case, we simply send packet n+1. An im-
portant exception is when the missing ACK is for a Send-Init packet; do
40
you see why? The next rule,
3. ``ACK and discard redundant packets.''
handles the situation where the same packet arrives again. The sending
KERMIT timed out waiting for an ACK which was sent, but lost, and
retransmitted the packet. The receiver must discard the redundant data
and ACK the packet again; to do otherwise could have undesirable ef-
fects, like adding the same data to a file twice or opening the same
file multiple times. Note that the situation resulting from a lost ACK
depends upon which side times out first.
KERMIT must handle another situation arising from possible lost pack-
ets:
4. ``NAK the expected command.''
The potential problem occurs in either the Receive Init state or when a
KERMIT server is waiting for a command. In either case KERMIT won't
know whether communication has begun if the other side's initial packet
was lost. KERMIT can't assume the other side will time out and
retransmit, so it must check periodically by sending a NAK for packet
zero. If KERMIT gets no response it assumes nothing has happened yet
and goes back to sleep for a while.
But sending periodic NAKs opens the door to the buffering problem.
Some systems buffer input for a device; when a program isn't looking for
input some or all the input is saved by the computer for future re-
41
quests. This can cause problems when talking to a KERMIT server or
sending a file to a KERMIT in receive wait. If some time has elapsed
since activating the remote KERMIT and escaping back and starting up the
local KERMIT, a number of NAKs may have accumulated in the local
KERMIT's input buffer, so:
5. ``Clear the input buffer at the beginning of a transfer.''
If the input buffer is not cleared, the local KERMIT will think the
remote side is having trouble receiving the first packet. In an effort
to get the packet through, it will be sent again; this repeats for every
NAK waiting in the input buffer. By the time the first ACK is finally
encountered in the buffer, a number of duplicates of the first packet
will have been sent out. If this number exceeds the NAK threshhold, the
connection will be broken. If not, however, the second packet will be
retransmitted once for each of the extra ACKs the remote KERMIT cor-
rectly sent for the duplicate first packets. This can continue throu-
ghout the file transfer, causing each packet to be sent many times. So,
in addition,
6. ``Clear the input buffer after reading each packet.''
Any computer that buffers its input should clear its input buffer before
the transfer and after each packet that arrives successfully. But since
not all systems provide a clear-buffer function, we may add another
rule:
42
7. ``Discard redundant ACKs.''
In the situation just described, the first packet would be sent out mul-
tiple times, once for each buffered NAK. Upon receipt of the first ACK,
the second packet would go out, but the next response would be another
ACK for the first packet; by rule 7, KERMIT would simply take in the
redundant ACK, ignore it, and look for the next ACK, until it got the
desired one, in violation of the spirit of Rule 1.
If we allowed ourselves to violate Rule 1, we could add a final rule,
``An ACK for packet n also ACKs all previous packets,'' as is done in
network protocols like DDCMP [16], allowing data packets to be sent in a
continuous stream. KERMIT cannot use this rule for many reasons: se-
quence number wraparound, buffer overflows, locking out half duplex sys-
tems (how can they NAK a bad packet if they can't get control of the
line?). Thus if we violate rule 1, it must be only in a very minor way.
. Example
Here is a sequence of packets from a real file transfer. Each packet
starts with Control-A, shown as ^A.
43
^A) SH( @-#^ Send Init
^A) YH( @-#% ACK for Send Init
^A+!FMOON.DOC2 File Header
^A#!Y? ACK for File Header
^AE"D No celestial body has required J First Data packet
^A#"Y@ ACK for first Data packet
^AE#Das m%%%uch labor for the study of its# Second Data packet, Bad
^A##N8 NAK for second Data packet
^AE#Das much labor for the study of its# Second Data packet again
^A##YA ACK for second Data packet
^AE$D#M#Jmotion as the moon. Since ClaA etc...
^A#$YB
(many packets omitted here)
^AD"Dout 300 terms are sufficient.#M#JU Last Data packet
^A#"Y@ ACK for last Data
^A##ZB EOF
^A##YA ACK for EOF
^A#$B+ EOT
^A#$YB ACK for EOT
In the first packet, we see following the control-A the packet length
``)'' (41 , less 32, or 9), followed by the packet type, S (Send-Init),
10
followed by the appropriate parameter declarations: maximum packet
length is H (72-32=40), timeout is ``('' (40-32=8), number of padding
characters is 0 (space=32-32=0), the padding character is 0, end-of-line
is ``-'' (45-32=13, the ASCII value of carriage return), the
control-quote character is ``#'', and the remaining fields are omitted,
defaulting to appropriate values. The final character ``^'' is the
single-character checksum, computed as follows (all numbers and computa-
tions in octal, and ``sp'' represents a space):
) sp S H ( sp @ - #
51 + 40 + 123 + 110 + 50 + 40 + 100 + 55 + 43 = 674
44
674 + (674/300) = 676
676 AND 77 = 76;
char(76) = 76+40 = 136 = "^"
The receiver ACKs with its own parameters, which are the same. Then
comes the file header, the file, EOF, and EOT. One data packet was cor-
rupted by a burst of ``%'' characters, NAK'd, and retransmitted.
* Performance
For text files (documents or program source), assuming an average line
length of 40 with lines separated by a carriage-return/linefeed pair,
the only control characters normally found in the text file, we see
about 5% overhead for prefixing of control characters. Assuming no line
terminators for packets (although one or both sides may require them),
no retransmissions or timeouts, and no time wasted for the line to turn
around between packet and response, then for average packet length p,
using a single-character checksum, the KERMIT protocol overhead consists
of:
5 control field characters in the data packet
5 characters in the acknowledgement packet
+ 0.05p for control character quoting
This gives 10/p + 0.05 overhead. E.g. if the packet length is 40,
there is 30% overhead. If p is 96 (the maximum), there is about 15%.
45
These figures will vary with the average line length and the frequency
of other control characters (like tabs and formfeeds) in the file, and
will go up with immediate retransmissions, and way up with delayed
retransmissions. For binary files, the quoting overhead will be higher.
But transmission overhead can also go down dramatically if prefix encod-
ing is used for repeated characters, depending on the nature of the data
(binary data containing many zeroes, highly indented or columnar data or
program text will tend to benefit). Each file transfer also gets a
fixed overhead for the preliminary (Send Init, File Header) and ter-
minating (EOF, EOT) packets.
If the mainframe end of a connection is heavily loaded, it may take
considerable time to digest and process incoming characters before
replying. On half duplex mainframes, there may be a pause between send-
ing and receiving, even if the load is light; this might be used to ad-
vantage by preparing the next packet in advance while waiting for the
current ACK. Another problem may occur on heavily loaded mainframes
-- undesirable timeouts. Timeouts are intended to detect lost packets.
A heavily loaded system may take longer than the timeout interval to
send a packet. For this reason, mainframe KERMITs should take the re-
quested timeout interval only as a minimum, and should adjust it for
each packet based on the current system load, up to a reasonable max-
imum.
On a noisy line, there is a greater likelihood of corrupted packets
and therefore of retransmission overhead. Performance on noisy lines
46
can be improved by reducing the packet length, and thus the probability
that any particular packet will be corrupted, and the amount of time re-
quired to retransmit a corrupted packet. A KERMIT program can
unilaterally adjust the packet length according to the number of
retransmissions that are occurring. Short packets cut down on
retransmission overhead, long packets cut down on character overhead.
* ``User Interface''
KERMIT was designed from a mainframe perspective. Like many mainframe
programs, KERMIT issues a prompt, the user types a command, KERMIT ex-
ecutes the command and issues another prompt, and so on until the user
exits from the program. Much care is devoted to the command parser,
even on microcomputer versions. The goal is to provide English-like
commands composed of sequences of keywords or operands, with abbrevia-
tions possible for any keyword in any field down to the minimum unique
length, and with ``?'' help available at any point in a command. Not
all implementations need follow this model, but most do.
The basic commands are SEND and RECEIVE. These allow most KERMITs to
exchange files. Operands can be the name of a single file, or a file
group designator (e.g. with ``wildcards'') to transmit multiple files in
a single operation. Although some systems may not provide wildcard file
processing, the KERMIT protocol allows it.
The CONNECT command provides the mechanism for logging in and typing
47
commands at the remote host, which is necessary in order to start the
KERMIT on that side. The CONNECT facility provides character-at-a-time
transmission, parity selection, remote or local eching, and the ability
to send any character, including the ``escape character'' that must be
used to get back to the local KERMIT. However, there is no error detec-
tion or correction during CONNECT, just as there normally is none be-
tween an ordinary terminal and a host.
When two systems are dissimilar, a SET command is provided to allow
them to accommodate each other's peculiarities, for instance SET PARITY
ODD to add odd parity to all outbound characters, or SET LOCAL-ECHO to
do local echoing when connected as a terminal to a half duplex system.
The SET command must sometimes be used to supply information to the tar-
get system on how to store an incoming file with respect to block size,
byte size, record format, record length.
Most KERMIT implementations take special care to reassure the user
during file transfer. The names of the files being transferred are
shown, and a dynamic display is made of the packet traffic, showing suc-
cessful transmission of packets as well as timeouts and retransmissions.
Messages are issued when the user connects to the remote system or es-
capes back from it, and KERMIT prompts identify the implementation.
Helpful error messages are displayed when necessary; these may emanate
from either the local or the remote system. The final disposition of
the transfer is clearly stated, complete or failed.
The actions required of the KERMIT user depend upon the degree to
48
which the KERMIT programs involved have implemented the specification.
Minimal implementations require that the user connect to the remote
host, start KERMIT there, issue a SEND (or RECEIVE) command, escape back
to the local machine, and issue the complementary RECEIVE (or SEND) com-
mand. All this must be done for each transfer. More advanced implemen-
tations allow the remote side to run as a ``server'' and to take all its
instructions in special command packets from the local KERMIT; all that
is required of the user on the remote end is to connect initially in or-
der to start the server. The server will even log itself out upon com-
mand from the local KERMIT. A minimal server can process commands to
send files, receive files, and shut itself down.
Here is an example of a session in which the user of an IBM PC gets
files from a DECSYSTEM-20. The actions shown are required for minimal
KERMIT implementations. The parts the user types are underlined, com-
ments begin with ``!'' or appear in italics. Everything else is system
typeout.
A>kermit ! Run Kermit on the PC.
Kermit V1.20
Kermit-86> ! This is the Kermit prompt for the PC.
Kermit-86>connect ! Connect to the DEC-20.
[Connecting to host. Type CTRL-]C to return to PC.]
! You are now connected to the DEC-20.
Columbia University CU20B ! The system prints its herald.
@terminal vt52 ! Set your terminal type (optional).
@login my-id password ! Login using normal login method.
(The DEC-20 prints various messages.)
49
@kermit ! Run Kermit on the DEC-20.
Kermit-20> ! This is Kermit-20's prompt.
Kermit-20>send *.for ! Send all FORTRAN files.
^]c ! Type the escape sequence to return to the PC.
[Back at PC.]
Kermit-86>receive ! Tell the PC files are coming.
(The progress of the transfer is shown continuously on the screen.)
Transfer Complete.
Kermit-86>connect ! Get back to the DEC-20.
[Connecting to host. Type CTRL-]C to return to PC.]
Kermit-20>exit ! Get out of Kermit-20.
@logout ! Logout from the DEC-20.
Logged out Job 55, User MY-ID, Account MY-ACCOUNT, TTY 146,
at 24-Apr-83 15:18:56, Used 0:00:17 in 0:21:55
^]c ! Now "escape" back to the PC,
[Back at PC.]
Kermit-86>exit ! and exit from the PC's Kermit.
The session is somewhat simpler when the remote KERMIT is being run as
a server. The user must still CONNECT, log in, and start KERMIT on the
remote end, but need never again CONNECT to issue subsequent SEND,
RECEIVE, EXIT, or LOGOUT commands, even though many transactions may
take place. All actions can be initiated from the PC.
50
* Advanced Features
An optional feature of the KERMIT protocol is a special packet
designed to express the attributes of a file in a compact and generic
manner. The receiver may either attempt to use the attributes to the
incoming file, or archive them for later use. Attributes include not
only file characteristics but also the intended disposition -- store,
print, submit for batch processing, send as mail, etc. Other optional
features include mechanisms for gracefully interrupting, delaying, or
suspending operations in progress; alternate forms of packet data encod-
ing; filename conversion, local file management, raw data transmission
and capture; command macro definition, etc.
Although KERMIT was never intended to fulfill the role of a general
purpose network server, its design has made it simple to add new func-
tions. A KERMIT server has the ability to accept commands in packets
from a remote KERMIT. The basic commands are for sending or fetching
files and for shutting down the server. Other commands may require dis-
play of text at the user's terminal, which is controlled by the local
KERMIT. For example, a directory listing could be requested; the
resulting text is sent back to the local KERMIT exactly as if a file
were being transferred, except the destination is the user's screen,
rather than a disk file. (Or it could be disk file too.) With this
ability in place, it is possible to implement all sorts of commands, for
instance to delete a file, show who's logged in, inquire about disk
51
space, verify access to a directory, submit batch jobs, send messages,
and so forth.
The ability of the KERMIT server to perform host functions can be ad-
ded very simply under certain operating systems. For instance, under
UNIX [17], KERMIT can ``fork'' a shell with commands to perform any
function possible under UNIX, redirecting the standard output through a
process (KERMIT itself) that encapsulates it into KERMIT packets and
sends it along.
A server with these capabilities could provide convenient access to a
timesharing system by users at personal workstations, without requiring
the users to be directly involved with the host. If, for instance,
workstations had dedicated connections to a host, and the host had dedi-
cated KERMIT servers for each such line, users could get access to and
manage their host files completely by commands typed at the workstation.
Taking this idea one step further, the workstation system software could
be modified to make the whole process transparent by incorporating a
KERMIT-like protocol in its file access logic -- fetching and updating
host files as necessary behind the user's back. Since the demands
placed on a host by KERMIT are relatively modest, many more simultaneous
users could probably be serviced in this way. This approach could be a
relatively painless entree into the distributed, networked environment
of tomorrow. When local area network protocols become mature and the
hardware economical and widespread, KERMIT can be replaced by ``the real
thing''. But for the ordinary computer user for whom dedicated connec-
52
tions are impractical, ``do-it-yourself'' KERMIT, or some facility like
it, will be a valuable tool for years to come.
* Conclusion
The need for a cheap, convenient file transfer capability among
diverse systems is pressing, and there are certainly many efforts
similar to ours under way at many places. We hope that this article may
contribute to those efforts; we don't claim to have the last word on any
of the issues raised here, and expect that this article may flush some
other approaches out of the woodwork. We have billed KERMIT as a
``simple'' protocol; anyone who has read this far will begin to ap-
preciate what must go into the more complicated protocols used in real
networks, or when ``integration'' of micro and mainframe is a major goal
-- demand paging of remote files, remote database queries, distributed
editing and computation.
Meanwhile, the KERMIT protocol has been proven successful, and con-
tinues to grow in popularity. As of this writing, implementations exist
for more than 50 computer systems. Some of the major ones include:
Machine Operating System Language
DECsystem-10 TOPS-10 MACRO-10
DECSYSTEM-20 TOPS-20 MACRO-20
IBM 370 Series VM/CMS IBM Assembler
VAX-11 VMS Bliss-32
VAX, SUN, PDP-11, etc UNIX C
PDP-11 RT-11, RSX, RSTS MACRO-11
8080, 8085, or Z80 CP/M 8080 ASM
8086, 8088 PC DOS, MS DOS IBM PC Assembler
Apple II 6502 Apple DOS DEC-10/20 CROSS
53
Some of these have been contributed or enhanced by the institutions
listed in the acknowledgements, below. No single implementation neces-
sarily includes all the features mentioned in this article, but all are
able to communicate at least at base level. Additional implementations
are in preparation, and present ones are being enhanced.
Columbia University is willing to provide all KERMIT programs,
sources, manuals, and other documentation to computing centers, academic
or corporate, in return for a modest fee to cover costs for media,
printing, postage, labor, and computing resources. Only magnetic tape
and listings can be shipped. We cannot produce floppy disks; instruc-
tions are included for bootstrapping the microcomputer implementations
from the mainframe computers. Details will be provided on request;
write to:
KERMIT Distribution
Columbia University Center for Computing Activities
7th Floor, Watson Laboratory
612 West 115th Street
New York, NY 10025
The protocol specification supplemented by examples of existing KERMIT
implementations allows new implementations to be created with relative
ease. In the past, KERMIT implementors have shared their work with
other KERMIT users by contributing it to the Columbia KERMIT library.
We hope that this practice will continue until KERMIT has spread through-
out the known world.
54
* Acknowledgements
In designing the initial KERMIT protocol, we studied several models,
primarily the ANSI recommendation [9]. other include the Stanford
University DIALNET project, the University of Utah ``Small FTP''
project, and the Stanford University Medical Center TTYFTP project.
And we examined some real networks, like ARPANET and DECnet.
Acknowledgements also to the many sites that have contributed new KER-
MIT implementations or enhanced old ones: Stevens Institute of Technol-
ogy, Digital Equipment Corporation, the National Institutes of Health,
Cornell University, the University of Toronto, the University of Ten-
nessee, the University of Toledo, Cerritos College, and others. Thanks
to Dr. Howard Eskin for help with this article.
55
* The ASCII Alphabet
Dec Oct Character Dec Oct
000 000 NUL (^@) 064 100 @
001 001 SOH (^A) 065 101 A
002 002 STX (^B) 066 102 B
003 003 ETX (^C) 067 103 C
004 004 EOT (^D) 068 104 D
005 005 ENQ (^E) 069 105 E
006 006 ACK (^F) 070 106 F
007 007 BEL (^G) 071 107 G
008 010 BS (^H) 072 110 H
009 011 HT (^I) 073 111 I
010 012 LF (^J) 074 112 J
011 013 VT (^K) 075 113 K
012 014 FF (^L) 076 114 L
013 015 CR (^M) 077 115 M
014 016 SO (^N) 078 116 N
015 017 SI (^O) 079 117 O
016 020 DLE (^P) 080 120 P
017 021 DC1 (^Q) 081 121 Q
018 022 DC2 (^R) 082 122 R
019 023 DC3 (^S) 083 123 S
020 024 DC4 (^T) 084 124 T
021 025 NAK (^U) 085 125 U
022 026 SYN (^V) 086 126 V
023 027 ETB (^W) 087 127 W
024 030 CAN (^X) 088 130 X
025 031 EM (^Y) 089 131 Y
026 032 SUB (^Z) 090 132 Z
027 033 ESC (^[) 091 133 [
028 034 FS (^\) 092 134 \
029 035 GS (^]) 093 135 ]
030 036 RS (^^) 094 136 ^
031 037 US (^_) 095 137 _
032 040 (SP) 096 140 `
033 041 ! 097 141 a
034 042 " 098 142 b
035 043 # 099 143 c
036 044 $ 100 144 d
037 045 % 101 145 e
038 046 & 102 146 f
039 047 ' 103 147 g
040 050 ( 104 150 h
041 051 ) 105 151 i
042 052 * 106 152 j
56
043 053 + 107 153 k
044 054 , 108 154 l
045 055 - 109 155 m
046 056 . 110 156 n
047 057 / 111 157 o
048 060 0 112 160 p
049 061 1 113 161 q
050 062 2 114 162 r
051 063 3 115 163 s
052 064 4 116 164 t
053 065 5 117 165 u
054 066 6 118 166 v
055 067 7 119 167 w
056 070 8 120 170 x
057 071 9 121 171 y
058 072 : 122 172 z
059 073 ; 123 173 {
060 074 < 124 174 |
061 075 = 125 175 }
062 076 > 126 176 ~
063 077 ? 127 177 DEL
57
* References
The following publications provided useful guidance or diversion in
the development of KERMIT.
[1] EIA Standard RS-232-C
Electronic Industries Association, 2001 Eye Street N.W.,
Washington DC 20006, 1969, 1981.
[2] ANSI X3.4-1977, Code for Information Interchange
American National Standards Institute, 1430 Broadway, NYC 10018,
1977.
[3] ANSI X3.15-1976,
Bit Sequencing of ASCII in Serial-By-Bit Data Transmission
1976.
[4] ANSI 3.16-1976, Character Structure and Character Parity Sense for
Serial-By-Bit Data Communication in ASCII
1976.
[5] McNamara, J.E.
Technical Aspects of Data Communication.
Digital Press, 1982.
[6] Mackenzie, C.E.
Coded-Character Sets: History and Development.
Addison-Wesley, 1980.
[7] DNA Data Access Protocol (DAP) Functional Specification
Digital Equipment Corporation, 1980.
AA-K177A-TK.
[8] Neigus, N.J.
File Transfer Protocol for the ARPA Network
Bolt Beranek and Newman, Inc., 1973.
RFC 542, NIC 17759. Available in the ARPANET Protocol Handbook,
NTIS AD/A-052 594.
[9] ANSI X3.28-1976, Procedures for the Use of Control Characters of
ASCII in Specified Data Communications Links
1976.
58
[10] Pierce, J.R., and Posner, E.C.
Applications of Communications Theory: Introduction to Communica-
tion Science and Systems.
Plenum Press, 1980.
[11] Knuth, D.E.
The Art of Computer Programming. Volume I: Fundamental Al-
gorithms.
Addison-Wesley, 1973.
[12] Hamming, R.W.
Error Detecting and Error Correcting Codes.
Bell System Technical Journal 29:147-160, April, 1950.
[13] Martin, James.
Teleprocessing Network Organization.
Prentice-Hall, 1970.
[14] Perez, Aram.
Byte-wise CRC Calculations.
IEEE MICRO 3(3):40-50, June, 1983.
[15] ISO Reference Model for Open Systems Interconnection (OSI)
International Organization for Standardization (ISO), 1982.
Draft Proposal 7498.
[16] DNA Digital Data Communications Message Protocol (DDCMP) Func-
tional Specification
Digital Equipment Corporation, 1980.
AA-K175A-TK.
[17] Thomas, R. and Yates, J.
A User Guide to the UNIX System.
OSBORNE/McGraw-Hill, 1982.