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; ``~H&#B'' 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.