RFC 935

Reliable link layer protocols

📅 published January 1985, from ietf

Okay bestie, get ready, because RFC 935 is giving serious main character energy 💅✨ It's titled Reliable Link Layer Protocols, it's from the Network Working Group, and it's written by J. Robinson at BBN 🦋 The date is January 1985 🌸 It's a Request for Comments, so the author is inviting discussion and suggestions. Its header doesn't list any category, and it doesn't list anything it obsoletes or updates 🤷‍♀️

Status of This Memo 📜

Okay so this memo talks about two protocols that were proposed recently in RFC 914 and RFC 916, and then it suggests a protocol that could meet the same needs those memos were going after 💖 The actual goal is reliable communication between two programs over a full-duplex, point-to-point communication link. The RFCs are especially focused on doing that over an asynchronous link at relatively low speeds 🐢 The suggested protocol borrows from methods in existing national and international data link layer standards 🧩 This RFC proposes a protocol for the ARPA-Internet community and asks for discussion and suggestions for improvements 🫶 Distribution of this memo is unlimited 🌈

Introduction ✨

This RFC is motivated by the recent RFC 914 and RFC 916, which propose new standards for protocols that transfer serial data reliably over asynchronous communication lines 💌 In this note, the author sums up widely used standards that have been around for a while and might be a good fit for this environment 🍓 The hope is that these existing standards will turn out to meet the needs the new proposals are trying to address 🤞

In both the US and international standards areas, there are two major categories of serial data communication standards for the link layer 🎀 Those categories are character-oriented and bit-oriented 💜 Character-oriented is the older class. It's standardized in the US standard ANSI X3.28-1976, which superseded the original version from 1971, and in the ISO standards IS 1745, IS 2111, IS 2628 and IS 2629 📚 Even though these are often used in synchronous environments, where they're called binary synchronous (or bisynch), these standards use the term "basic mode" to describe their procedures 🙈 Bit-oriented is the newer class. It's standardized in the US standard ADCCP (Advanced Data Communication Control Procedures), ANSI X3.66- 1979, and in the ISO standard HDLC (High-level Data Link Control procedures), in IS 3309, IS 4335 and IS 7809 🦋

Other international standards, draft standards and vendor standards follow the ADCCP/HDLC procedures 💅 Some examples are SDLC (IBM), X.25 LAPB (CCITT), IEEE 802.2/ISO 8802.2 LLC (LAN Logical Link Control) and ISDN LAPD (CCITT) 🌸 Lots of vendors have built equipment that meets the character-oriented standards, in both synchronous and asynchronous environments, including all the major US mainframe manufacturers 🔥

The only other serial link layer protocol the author knows of that's as widely used as these is DEC's DDCMP (Digital Data Communications Message Protocol) 👑 It uses a character count instead of framing characters, but in other respects it's character-oriented too 🧚

The next sections of this note compare those three protocols on several bases. They pay special attention to the characteristics that make certain parts of each protocol suited to a low-speed, asynchronous, serial environment ⭐

Frame Structure 🧸

All serial protocols divide the data they transmit into units called frames 🎀 A frame is typically one to several hundred characters long 💖 The frame structure is the main difference that the three classes above are split on 💅

Character-Oriented Framing 🌷

Character-oriented protocols use two techniques to define a frame 🦋 First, the receiver has to figure out where characters start and stop 🧠 The technique for this is to send a number of unique characters before a frame starts, and the character usually used for this is the SYN character ✨

Heads up: this isn't required with asynchronous transmission 🙌 Since each character is already framed by start and stop bits, there's never any question about where characters begin and end 💜

The main technique for structuring a frame is using special framing characters to mark the start and end of a frame, and to mark parts of the frame (like the header and the text) 🌈 Some uses of character-oriented protocols require that these framing characters never show up in the header or text of the frame 🙅‍♀️ Others allow "transparent" transmission 🫧 Transparency is achieved by putting a unique control character, typically DLE, in front of each framing character 🎀 That way, every character can be sent as header or text, except for DLE itself 💖 To send DLE as header or text, the DLE is doubled 👯‍♀️

Bit-Oriented Framing 🍭

Bit-oriented protocols also use a unique character for frame delineation 🦋 Technically it's just an arbitrary bit-string, and it's called the FLAG 🚩 The FLAG gives frame synchronization 🤝 All the bits between two FLAGs make up one frame 🧩 A FLAG is a 0 bit, followed by six 1 bits, followed by another 0 bit 🌸 To make sure the FLAG never shows up by accident in the message data, the sender inserts an extra 0 bit after any five successive 1 bits in the data stream, and the receiver removes it 💅 That insertion of bits is called "stuffing" 🙈

Because stuffing results in arbitrary frame bit-lengths, bit-oriented protocols are generally only useful in synchronous transmission environments 😭 It's never been tried, but you could imagine an asynchronous setup where each FLAG character in the data gets translated into a two-character sequence that avoids FLAGs, and at least one other character gets translated the same way 🧚 For example, you could frame data with FLAGS, and send DLE-F to mean FLAG and DLE-DLE to mean DLE whenever those characters show up inside the frame 💜

Also, bit-oriented procedures don't require the number of bits between FLAGs to be an exact number of 8-bit characters 🌈 That's different from character-oriented protocols and DDCMP 👑 Character alignment may be imposed at higher layers instead, like it is in the X.25 Network Layer, for example ✨

Frame Structure in DDCMP 🧁

DDCMP uses a third approach to frame structure 🎀 Like character-oriented protocols, it uses a SYN character to get character synchronization before a frame starts, but you can't skip this over asynchronous lines (more on that below) 🫶 Inside the fixed-length header portion of the frame is a count field, which reports how many characters are in the variable-length text portion 🔢 Since no framing characters are needed at all, transparency isn't a problem 🙌 However, the sender and receiver have to receive the count properly to stay in frame synchronization, so the header is protected with a separate error control checksum, which is typically two characters long (see below) 💖 Also, once a header error has been detected, the count field has to be assumed invalid, so there must be a unique character sequence that introduces the next header. That way the receiver can regain synchronization with the sender 😤

So, the SYN characters before a frame are required even on asynch lines 🚨

Error Detection 🔍

Several types of error control may be used, and the various protocols above are pretty similar 💅 Most synchronous uses require a cyclic redundancy check sequence to be attached to each frame 🌸 It's a 16-bit sequence that's easy to generate and check in hardware with a shift register, and you can do it in software too, though it's more tedious: about 5-6 instructions per character sent or received, plus a 256 by 16-bit lookup table 🧮 DDCMP and bit-oriented protocols all require use of such a sequence 🦋 As noted above, DDCMP uses a check sequence twice, once for the header and once for the data 🎀

In some environments, weaker checks are used on character-oriented links 🥺 There are two forms. If the number of significant bits per character is only 7, then the parity bit can be set to achieve either odd or even parity 💜 ANSI standard X3.16-1976 specifies that odd parity should be used on synchronous links and even parity on asynchronous links 📏 The second type of check is "longitudinal parity," where one character is added to the frame so that the number of 1 bits in each bit position, summed over all the characters of the message and the check character, is even 🌈 In other words, the exclusive-or of all the characters is 0 🧠 Character parity and longitudinal parity may be used together 🫧

Note also that most character-oriented control messages, like the ones that poll, select, and acknowledge, are sent with only parity for error control 🙈

Sequence Control 🔁

All of these protocols provide reliable transmission by sequencing the frames and providing positive and (in some cases) negative acknowledgments 💖 Senders can ask the receiver for status if a reply is late ⏰

In character-oriented protocols, frames are implicitly numbered (typically), and only one may be outstanding at a time 🐢 Acknowledgments are explicitly numbered 🔢 One variant lets each block (frame) be explicitly numbered too, and in that case up to 7 may be outstanding 🌟

In bit-oriented protocols, frames are explicitly numbered, and up to 7 may be outstanding at a time 💅 An optional control field extension allows for up to 127 outstanding 🎀 There's also an alternate procedure, defined for use in both the ISDN LAPD environment and IEEE 802 LAN environments, that in effect uses a one-bit sequence number and one outstanding frame 🦋 And unsequenced, unacknowledged information frames can be used when frames don't need to be sent reliably 🫶

In DDCMP, the frames are explicitly numbered, and up to 255 may be outstanding 🌈

Addressing 📬

All of these protocols allow stations on a multipoint link to be addressed separately 💜 In LAN environments, both a sending address and a receiving address are required 🏠 Multipoint environments use a single address and assume one master station communicating with multiple addressed slave stations 👑 In bit-oriented protocols, the address provides extra information, since frames can be categorized as commands or responses 🧩 In that sense, the address gives you another control bit per frame ✨ It's still possible to operate without needing this distinction 🙌

Addresses are typically one character long, though bit-oriented protocols allow this field to be extended to arbitrary length 🍓 Character-oriented protocols use two-character (controller and terminal) addresses 🧚

For point-to-point operation, the address is clearly superfluous (except for distinguishing commands and replies in bit-oriented protocols), so you could imagine dispensing with it entirely 🥰

The Asynchronous Environment ✨

okay so the big question 🤔 is which of these protocols is best for the asynchronous environment? That depends on what "best" means, obviously 💅 One way to judge is to compare how much overhead each protocol adds to every frame it sends.

We're going to look at the overhead costs in two groups:

  • framing/transparency/error checking
  • and addressing/control

The two groups are independent of each other, even though the protocols above mix techniques from both. Also, hardware on minicomputer-class and bigger machines today supports the first group completely for these standard protocols, and this fact should allow for far greater performance from the gateway machine 🚀

To the extent that this hardware shows up on personal computers, it can be used there too to cut down protocol processing overhead. Here's the breakdown of framing costs in characters. RATP is included too, for comparison 🎀

Protocol   Frame   Check  Transp.  Total    F+C

char-or.     4       2       2       8       6
bit-or.      1       2       2       5       3
DDCMP        4       4       0       8       8
RATP         2       3       0       5       5

The transparency column is the expected cost in inserted characters to get transparency across a 256-byte frame. The bit-oriented number is a pessimistic guess 🙈 because I don't know the exact answer. It's somewhere between 0 and 8 characters, with the worst case happening when the data is all one bits. For character-oriented protocols we'd expect on average one DLE character in a 256-byte frame, and the worst case overhead (256 DLEs) is 256 bytes.

Because transparency depends so much on the user data, and because we ignored the cost of losing frame synchronization in the counting protocols (DDCMP and RATP), I think the comparison should be based on just the frame and checksum costs. For those two columns, character-oriented framing costs one more character per frame than RATP. That, plus its wide use and chip support in hardware, makes a strong case for using it over RATP for framing 💖

Bit-oriented framing, like I said before, is only appropriate on synchronous links. The character-oriented variant I made up above would have the same costs, but since it's not a standard, it isn't proposed here. So we end up with this frame format:

DLE STX <control and data ...> DLE ETX CRC CRC

One objection to character-oriented protocols, compared with character-count protocols, is that you have to examine every character as it arrives. Here's my answer:

  1. Under some circumstances, like when a header got hit with an error, the receiver will have to look at every character anyway.
  2. The environment for this protocol is a 1200 baud link, so at most 120 characters per second need examining. Even on a relatively slow personal computer, that should not present a problem 😤

We now turn to the content and format of the control information that comes before each link frame. There are three components to this cost: control, address, and acknowledgment. The address field allows multipoint configurations and is superfluous for the point-to-point environment proposed, but it is present in the public standards, and we restrict ourselves to those 📋

Acknowledgments are shown if the protocol requires them explicitly. A "0" means the acknowledgments may be included in the control information for traffic in the opposite direction, and they only need to be sent explicitly when no reverse traffic is present (and are thus assumed to take no required overhead). Only character-oriented protocols have required acknowledgments.

             Cont.   Addr.    Ack    Total
char-or.     0       3       2       5
bit-or.      1       1       0       2
DDCMP        3       1       0       4
RATP         1       0       0       1

Again, the bit-oriented procedures give the lowest overhead among the public standards, and in this case there's no conflict in using them in the asynchronous environment. In fact, even if all the other aspects of RATP were adopted, I believe the control field codings of the bit-oriented procedures are a more efficient use of the channel, are widely implemented, and allow for adding more functions later if wanted. As stated above, there are several protocols in the bit-oriented family. I would recommend use of LAPB, since it's the most widely known of the family 👑

For those not familiar with bit-oriented control procedures, I've included a quick summary of them in Appendix A. Refer to the standards listed at the end of this note for more detail.

RATP Compared to Public Protocols

As the tables above show, RATP doesn't represent a significant savings compared to other widely-used protocols 😬

Given frame lengths of 13 bytes, which seems to be the minimum for Thinwire II (RFC 914), 8 characters' overhead using the public standards is 61% vs 46% for RATP's 6 characters. On a 1200 baud line, the bandwidth available assuming only such short frames is thus 74 vs 82 characters per second, respectively. Since 1/13 of these are actually user data, the typing rates these protocols support using TCP/IP are pretty low, like 5.6 vs 6.3 characters per second. Clearly, a bigger cost is still the 12 characters of overhead in Thinwire II (or 40 for TCP/IP with no compression) 🙃

The costs improve dramatically when the number of user characters per frame increases. So file transfer, or even line-blocked typing, should perform adequately. As frame size grows, the cost of the extra 2 characters per frame to use standard protocols rapidly drops to a few percent or less 📈

RATP does allow one optimization that the standard protocols can't achieve: a one-character format that reduces the per-frame overhead to 3 characters (or 4 if a 16-bit CRC is used). However, in the scenario where single-character messages make sense, a user typing characters with no higher-layer protocols, the extra overhead probably isn't a problem, since the link is still lightly loaded enough that the extra overhead is a small percentage of the available bandwidth. Also, allowing multiple frames in flight helps reduce the bottleneck caused by having one frame outstanding at a time. 🧚

On Check Sequences

Both RFCs 914 and 916 propose relatively simple check sequences that can be easily computed in a general-purpose processor. In one case it's an additive check, and in the other it's an exclusive-or (or parity) check. Although the additive check is slightly more powerful than the exclusive-or, both are relatively weak compared to CRC techniques 🫶

Since the intended network-layer protocol (IP) provides similar checks on its header, and the transport layer (TCP) checksums its header and data, you might wonder whether protection should be provided at the link layer at all, or if it should, whether these checks are good enough. Providing for recovery at the TCP layer leads to slow recovery times, so this approach will probably yield too poor a level of service for noisy links. More importantly, the link layer control field needs a certain degree of protection to prevent needless loss or duplication of frames in the face of line errors.

A CRC check, in combination with the additive checks provided by IP and TCP, yields error protection that is greater than either check by itself. This is because the two techniques address fundamentally different characteristics of the possible errors. The degree of increase is substantial compared with two additive checks. If two additive checks are cascaded, there are many types of two-bit failures that will pass both the link layer and TCP/IP checking 😭

Although I don't want to include a detailed error analysis in this note, I would support the use of a CRC type of error check because of the far greater level of protection it affords. As I pointed out, the cost per character is roughly 5-6 instructions, assuming the use of a 256 by 16-bit lookup table. Again, at 120 characters per second, the increased cost isn't deemed to be too great 🔥

Moreover, using a standard CRC allows for the possibility that the serial line chip's own CRC generation and checking hardware may be used. Although such chips may not be present in the PCs in the environment envisioned, they're likely to be available in the gateway machine that the PCs talk to 💜

Data Compression: An Aside

I find the proposed methods of data compression of RFC 914 particularly interesting. I see them as independent of the choice of the underlying link layer protocol, as it is in RFC 914. I'm not aware of any character-oriented compression like this in common use in the communication world. The only techniques that come close are in statistical multiplexing devices, which sometimes also include adaptive Huffman coding to reduce link bandwidth. Since the Thinwire II approach can recognize much longer repeated sequences than a Huffman code, I expect the potential savings are correspondingly greater 🌈

I would like to see a version of the Thinwire protocols that allows for the template idea, but keeps it independent of the higher-layer protocols in use. One way to achieve this is to allow templates to be encoded and exchanged between the communicating parties when they start up, and perhaps adaptively as conditions warrant. I'd expect this sort of approach might well have widespread applicability beyond the TCP/IP environment addressed in RFC 914. The most important gain for this environment is removal of the apparent exorbitant overhead that IP and TCP seem to present for use over slow links 🐢

Summary

The link layer protocol I would advocate for asynchronous, dialup communication between PCs would use transparent, character-oriented framing, a 16-bit CRC error check, and the control procedures of LAPB. The CRC should be either CRC-16 or the CCITT CRC used in X.25, with the latter probably being preferred. Modern link chips tend to support both of these if they support either ✨

Evolution of integrated circuits that directly implement all of the public standards will dramatically drop the cost and raise the reliability of new implementations of standard protocols. Chip manufacturers have little motivation to address standards that aren't widely used 🍓

Overhead for the suggested protocol is 8 characters per frame. Up to 7 frames may be outstanding at a time in either direction of transfer. Choice of an appropriate maximum frame size is application-dependent, and would certainly be influenced by the quality of the physical connection. However, I believe that IP datagrams are acceptable frames for dialup 1200 baud service 🦋

Non-standard modifications that would save a little link overhead would be to dispense with the one-character address field, and to use the RATP count-oriented frame structure. These are not recommended, because they depart from common practice and yield modest improvements at best 🙅‍♀️

Postscript 💌

okay bestie, the author has a little fun fact for us 🦋 If you know the early history of the Telenet Public Data Network, this proposal is basically the same as the original link layer protocol spec for that network, circa 1976 😭 The differences: the control procedures back then, known as LAP, have been superseded by the more powerful and efficient LAPB, and their access links (like all X.25 access links) are synchronous instead of asynchronous. They didn't set out to get this result, they just noted it in passing 🙈

Now for the author's personal take on where personal computer access to data networks is going 👀 They think X.25 will rapidly become the protocol of choice. Already there's third-party support (for IBM PC) and vendor support (for Wang PC) for X.25 💅 CCITT is also circulating a proposal for accessing an X.25 data network over a dial-up X.25 connection, called recommendation X.32 ✨ So they feel the type of communication in this RFC and in RFCs 914 and 916 will only be used for a relatively short period of time 💀 Their prediction for the future: LAN or X.25/X.32 for the data link layer and access, X.25 and/or ISO IP for the network layer, and TCP and/or ISO TP4 for the transport layer 🌈

References 📚

  • RFC 914, "Thinwire Protocol", Farber, Delp and Conte, 1984.
  • RFC 916, "Reliable Asynchronous Transfer Protocol", Finn, 1984.
  • "Technical Aspects of Data Communication", McNamara, Digital Press, 1977.
  • ANSI X3.4-1968, "American National Standard Code for Information Interchange (ASCII)", American National Standards Institute, Inc., 1968.
  • ANSI X3.16-1976, "American National Standard Character Structure and Character Parity Sense for Serial-by-Bit Data Communication in the American National Standard Code for Information Interchange", American National Standards Institute, Inc., 1976.
  • ANSI X3.28-1976, "American National Standard Procedures for the Use of the Communication Control Characters of American National Standard Code for Information Interchange in Specified Data Communication Links", American National Standards Institute, Inc., 1976.
  • ANSI X3.66-1979, "American National Standard for Advanced Data Communication Procedures (ADCCP)", American National Standards Institute, Inc., 1979.
  • International Standard 1745, "Information Processing - Basic mode control procedures for data communication systems", International Organization for Standardization (ISO), 1975.
  • International Standard 2111, "Data Communication - Basic mode control procedures - Code independent information transfer", ISO, 1973.
  • International Standard 2628, "Basic mode control procedures - Complements", ISO, 1973.
  • International Standard 2629, "Basic mode control procedures - Conversational information message transfer", ISO, 1973.
  • International Standard 3309, "Data Communication - High-level data link control procedures - Frame structure", ISO, 1982.
  • International Standard 4335, "Data Communication - High-level data link control procedures - Consolidation of elements of procedures", ISO, 1982.
  • International Standard 7809, "Data Communication - High-level data link control procedures - Consolidation of classes of procedures", ISO, 1984.
  • Recommendation X.25, "Interface between Data Terminal Equipment (DTE) and Data Circuit Terminating Equipment (DCE) for Terminals Operating in the Packet Mode and Connected to Public Data Networks by Dedicated Circuit", The International Telegraph and Telephone Consultative Committee (CCITT), 1980 (to be revised, 1984).
  • Recommendation Q.920, "ISDN User-network Interface Data Link Layer - General Aspects", CCITT, 1984 (draft E).
  • Recommendation Q.921, "ISDN User-network Interface Data Link Layer Specification", CCITT, 1984 (draft E).
  • Draft International Standard 8802.2, "Local Area Network Standards, Logical Link Control", ISO, 1984 (draft).
  • Draft Proposed Addendum to DIS 8802.2, "Single Frame Service", IEEE, 1984 (Eighth Draft).

Appendix A - Bit-Oriented Control Field Contents 🎀

okay so there are three control field formats 🧚 The main one is used for data frames (called "information frames" in the standards), and it's coded like this:

      8  7  6  5  4  3  2  1  <- bit number,  1 sent first
                           0     (signifies data frame)
                  S  S  S        send seq , bit 2 low-order
              P/F                poll/final bit, for recovery
      R  R  R                    receive seq  (ACK)

Acknowledgments are cumulative ✨ Recovery is typically to back up and continue from the lost frame. Using the poll/final bit is beyond the scope of this note, so we're leaving that one alone 🙈

Acknowledgments can also be sent in supervisory frames, which look like this:

      8  7  6  5  4  3  2  1  <- bit number,  1 sent first
                        0  1     (signifies supervisory frame)
                  T  T           frame type (see below)
              P/F                poll/final bit, for recovery
      R  R  R                    receive seq  (ACK)

Up to four frame types are possible, but only two are required 💖 The first is called RR, for "receive ready", and it indicates acknowledgment and that the receiver is prepared to process more frames. The other one is RNR, for "receive not ready", and it's used for flow control of the sender. If flow control isn't necessary, the author supposes even this frame could be dispensed with 💅

The other supervisory frames, "reject" and "selective reject", are varieties of negative acknowledgement. They ask for retransmission of all (reject) or one (selective reject) of the previously transmitted frames 👀 Positive acknowledgment and retransmission are the only really necessary procedures, though 🫶

The third frame format is called Unnumbered 🌸 Lots of possible functions are specified in the various standards for these frames, including initializing the link, resetting sequence numbers, etc. The basic format is:

      8  7  6  5  4  3  2  1  <- bit number,  1 sent first
                        1  1     (signifies unnumbered frame)
            T  T  T     T  T           frame type
                    P/F                poll/final bit, for recovery

That's the whole thing, bestie! 🌈👑

📦 where this page comes from