@Comment(-*-SCRIBE-*-) @Comment(SCRIBE Text Formatter Input for the KERMIT Byte Article) @Make @Use @Style @Style @Comment(Set desired spacing around various environments) @Modify @Modify @Modify @Modify @Modify @Modify @Modify @textform(dd="--") @define @define @define @Comment(Printing Device Dependencies) @Define @Case @set @begin(center) @MajorHeading(KERMIT) @Heading @blankspace(1.5) Frank da Cruz,@ @ Bill Catchings @blankspace(0.5) Columbia University Center for Computing Activities New York, N.Y. 10027 @i@foot @end(center) @blankspace(0.5inch) During recent years, the technical press has focused a lot of attention on developments in computer networking@dd()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 computers at a central site are complemented by many smaller systems scattered in the laboratories and departments. The past few years have witnessed the inexorable progress of diverse microcomputers, word processors, and professional workstations into offices and laboratories throughout 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 students 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. 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 applications, 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. @section(The Communication Medium) The only communication medium common to all computers, large and small, is the asynchronous serial telecommunication line, used for connecting terminals to computers. Standards for this medium are almost universally followed@dd()connectors, voltages, and signals (EIA RS-232-C @cite<--RS232>), character encoding (ASCII, ANSI X3.4-1977 @cite<--A34>), and bit transmission sequence (ANSI X3.15-1976 @cite<--A315,--A316>). Serial connections can be made in many ways: dedicated local lines (``null modem'' cables), leased telephone circuits, dialup connections. Dialup connections can be initiated manually from the home or office using an inexpensive acoustic coupler, or automatically from one computer to another using a programmable dialout mechanism. The asynchronous serial line offers the ordinary user a high degree of convenience and control in establishing intersystem 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: @Begin(Enumerate) @i@dd()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 characters. Noise corrupts data, perhaps in subtle ways that might not be noticed until it's too late. @i@dd()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. @i@dd()A line may stop working for short periods because 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. @End(Enumerate) 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 signals may be available for synchronization, and so forth. The serial telecommunication line provides no such safeguards, and we must therefore regard it as an intrinsically unreliable medium. @Section(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 transfer 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 acknowledged 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 @i@dd()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. @Section(Accommodating Diverse Systems) Most systems agree how to communicate at the lowest levels@dd()the EIA RS-232-C asynchronous communication line and the ASCII character set@dd()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. @SubSection(Mainframes vs Micros) A distinction must first be made between @i and @i. 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 communication port is strictly an external device. A mainframe is any system 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 controlling terminal specially. Full duplex systems echo incoming characters on the controlling terminal, but not on an assigned line. System command interpreters or user processes might take special action on certain characters on the controlling line, but not on an assigned line (for instance, control-C under CP/M or most DEC operating systems). Messages sent to a job's controlling terminal from other jobs could interfere 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 @i at the console, VM can test @i 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 happen. 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 certain of these features to be disabled, so file transfer protocols must be designed around them. @SubSection(Line Access) Line access can be either @i or @i. If full duplex, transmission 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 accommodate half duplex communication, but not vice versa. IBM mainframes are the most prevalent half duplex systems. @SubSection(Buffering and Flow Control) Some systems cannot handle sustained bursts of input on a telecommunications 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 @i mechanism, either in the data stream (XON/XOFF) or in parallel to it (modem control signals) @cite<--mcn>, 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 subject 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@dd()or worse@dd()on some hosts. For instance, the communications front end of the DECSYSTEM-2060 is designed on the statistical assumption that all terminal 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. @SubSection(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 behavior 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 @cite<--EBCDIC>, for internal 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@dd()UNIX translates carriage return into linefeed; most DEC operating systems keep the carriage return but also add a linefeed. @SubSection(Timing Out) Hosts may or may not have the ability to ``time out''. When exchanging 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. @SubSection(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 complicated 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 information is required to make the file valid. A simple generalized file transfer facility can be expected to transmit a file's name and contents, 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 @cite<--DAP> supports 42 different ``generic system capabilities'' (like whether files can be preallocated, appended to, accessed randomly, etc), 8 data types (ASCII, EBCDIC, executable, 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, 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) @cite<--ARPA>. 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 requires 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. Fortunately, most file transfer between unlike systems involves only textual information@dd()data, documents, program source@dd()which is sequential 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 @i 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 transformations 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. @SubSection(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 ASCII transmission is designed for them: a serial stream of 8-bit characters, 7 bits for data and 1 for parity, framed by start and stop bits for the benefit of the hardware@cite(--A315). 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, 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 @cite<--A34,--A315> 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 computers allow this flexibility, the ability to transfer binary data in this fashion cannot be assumed. @SubSection(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 lacking from some computers, either because they have not been implemented, or because they are proprietary and have not been purchased. Even when 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. @Section(KERMIT) Our protocol, which we call KERMIT, addresses the problems outlined above by setting certain minimal standards for transmission, and providing a mapping between disk storage organization, machine word and byte size, and the transmission medium. KERMIT has the following characteristics: @begin 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 characters 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 participate, 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 resume after lost packets. All transmission is in ASCII. Any non-ASCII hosts are responsible for conversion. ASCII control characters are prefixed and then converted to printable characters during transmission 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 between records to be preserved across unlike systems. Only a file's name and contents are transmitted@dd()no attributes. 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 systems. KERMIT need not be written in any particular language. It is not a portable program, but a portable protocol. @end 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. 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. @Section(Packets) KERMIT packets need to contain the data that is being transferred, plus minimum information to assure (with high probability) that the expected 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 arrange the fields within the packet. Since the transmission medium itself is character-@|oriented, it is not feasible to transmit bit strings of arbitrary length, as do the bit-@|oriented protocols like HDLC and SDLC @cite<--MCN>. 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. @SubSection(Control Fields) Most popular protocol definitions view the packet as layers of information, which pass through a hierarchy of protocol levels, each level adding its own information at the ends of an outbound packet or stripping its information from the ends of an incoming packet, and then passing 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 control characters), we can represent values from 0 to 94 with a single character. @Begin(Itemize) The @i is used to detect missing or duplicate packets. It is unlikely that a large number of packets could be lost, especially since packet @i is acknowledged before packet @i 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 enforced by specifying the @i with a single character; since there are 95 printable ASCII characters, this would be the maximum length, depending on how we count the control fields. The @i can be of fixed length. The actual length depends on the desired balance between and efficiency and error detection. @End(Itemize) The packet length and checksum act together to detect corrupted, missing, 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 transmission is complete. This can be accomplished with a @i field. The number of functions we need to specify in this field is small, so a single character can suffice here too. @SubSection(Packet Framing) We choose to mark the beginning of a packet with a distinguished start character, SOH (Start Of Header, @w, 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 input 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@cite<--A328>. 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: 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 characters 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. @SubSection(Encoding) When transmitting textual data, KERMIT terminates logical records with carriage-@|return linefeed combinations (CRLFs). On record oriented systems, 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 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 normally ``#''; the transformation is done by complementing bit 6 (adding or subtracting 64@-<10>, modulo 64). Thus control-A becomes ``#A'', control-Z becomes ``#Z'', US (control-@|underscore on most terminals) becomes ``#_''. 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 significantly 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 ASCII control character, then control-@|character quoting is also done. For instance, the byte 10000001@-<2> would be transmitted as ``&#A''. The ``&'' character itself can be included as data by quoting it (#&), and the control-@|quote character may have its 8th bit set (&##). 8th-bit quoting 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 instance, 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 @i(not) do to the data: @Begin(Itemize) @i(Fancy Data compression). If the data is known to be (or resemble) English text, a Huffman encoding @cite(--HUF,--DEK) 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 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 ASCII transmission don't mix well. @i(Error Correcting Codes). Techniques, such as Hamming codes @cite<--HAM>, 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. @i(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. @End(Itemize) @SubSection(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 sequence. 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) @cite<--MAR,--PRZ>, 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 implementation 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@-<10> in the worst case. The binary representation of this number is 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. 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 @i@+(16)+@i@+(12)+@i@+(5)+1 which is also used in some form with other popular transmission techniques, like ISO HDLC and IBM SDLC @cite<--MCN>. 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. Therefore, 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 @i(S), then the value of the single-@|character KERMIT checksum is given by @example<(@i + ((@i 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 transmitted arithmetic checksum is the ratio of the number of possible errors that cancel each other out to the total number of possible errors, which works out to be something like 1/2@+(@i), where @i is the number of bits in 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 @i(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 @cite<--MAR>. 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@dd()a parity bit on each character combined with a logical sum of all the characters (VRC @i LRC) would allow detection @i correction of single-@|bit errors without retransmission by pinpointing 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. @SubSection(Packet Layout) KERMIT packets have the format: @begin +------+-----------+-----------+------+------------+-------+ | MARK | char(LEN) | char(SEQ) | TYPE | DATA | CHECK | +------+-----------+-----------+------+------------+-------+ | | | | | | | +-- (application) --+ | | | | | | +-------------- (session) ------+ | | | +--------------------------------- (data link) ------------+ @end where all fields consist of ASCII characters, and the @i function converts a number in the range 0-94@-<10> to a printable ASCII character by adding 32@-<10>. In terms of the ISO network reference model @cite<--ISO>, 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@dd()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 required 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 conversions (EBCDIC/ASCII, insertion or stripping of CRLFs, etc). Finally, the remainder of the packet, the TYPE and DATA fields, are the province 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 transmission is always in stream ASCII, IBM implementations must convert from EBCDIC and insert CRLFs @i checksum computation. The fields of a KERMIT packet are as follows: @begin @u@\Start-of-packet character, normally SOH (ASCII 1). @u@\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 @i(char) function, packet character counts of 0 to 94@-<10> are permitted, and 96@-<10> is the maximum total packet length. @u@\The packet sequence number, modulo 100@-<8>. The sequence numbers ``wraps around'' to 0 after each group of 64@-<10> packets. @u@\The packet type, a single printable ASCII character, one of the following: @begin 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 @end @begin G@\Generic Command. A single character in the data field, possibly followed by operands, requests host-@|independent remote execution the specified command: @begin L@\Logout, Bye. F@\Finish, but don't logout. 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. @end C@\Host Command. The data field contains a string to be executed 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. Operation is exactly like a file transfer. @end @u@\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. @u@\The block check sequence, based on all the characters in the packet between, but not including, the mark and the check itself, one, two, or three characters in length as described above, each character transformed by @i. Normally, the single-@|character checksum is used. @end 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: @begin(example) ^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 @end(example) The ``@q<^A>'' represents the SOH (or Control-A) character. In the final packet shown, ``@q'' is the length. The ASCII value of the ``@q'' character is 69@-<10>, less 32 (the @i transformation, which is the opposite of @i) gives a length of 37. The next character tells the packet sequence number, in this case 6 (``@q<&>'' is ASCII 38). The next is the packet type ``@q'' for Data. The next characters, ``@q< of#M#Jconstructing a theory conta>'', form the data; note the prefixed carriage return and line feed. The final character, ``@q<5>'' is the checksum, which represents the number 21 (all numbers in this paragraph are in decimal). @SubSection(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 interpacket 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 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 transmission. 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. @Section(Protocol) The KERMIT protocol can be described as a set of @i and a set of @i[transitions] that define, for a given event, what action to take and what new state to change to. The inherent simplicity of the design, particularly 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: @begin +--------------+ | 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) | | +---------------+ @end For simplicity, some transitions are not shown in the diagram: @begin 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, containing 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. @end 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 arrives, 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 distinction between EOF and EOT, plus the File Header itself, allows files to 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. @begin +-----------+ | Send Init | +-----------+ | | (Get Good ACK) | (No more files to send) V +----------+ +-----------+ | Send EOT |<-------------| Send File |<---------------+ +----------+ +-----------+ | | | | (Good ACK) | (EOF) | | V | +-----------+ | +------>| Send Data |----------------+ | +-----------+ | | | | (Good ACK) | | +---------------+ @end 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 implementations 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. @subsection(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: @begin 1 2 3 4 5 6 7 8 9 10 +------+------+------+------+------+------+------+------+------+------------- | MAXL | TIME | NPAD | PADC | EOL | QCTL | QBIN | CHKT | REPT | CAPAS... +------+------+------+------+------+------+------+------+------+------------- @end 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 @i function (ASCII value + 32@-<10>) unless indicated otherwise. @begin @u@\The maximum length packet I want to receive, a number up to 94@-<10>.You respond with the maximum you want me to send. This allows systems to adjust to each other's buffer sizes, or to the condition of the transmission medium. @u