As per Relevance of the word procedure, we have this rfc below:
Network Working Group J.
Request for Comments: 935
January 1985
RELIABLE LINK LAYER
Status of This
This RFC discusses protocols proposed recently in RFCs 914 and 916,
and suggests a proposed protocol that could meet the same
addressed in those memos. The stated need is reliable
between two programs over a full-duplex, point-to-point
link, and in particular the RFCs address the need for
communication over an asynchronous link at relatively low speeds
The suggested protocol uses the methods of existing national
international data link layer standards. This RFC suggests
proposed protocol for the ARPA-Internet community, and
discussion and suggestions for improvements. Distribution of
memo is unlimited
This RFC is motivated by recent RFCs 914 and 916, which propose
standards for protocols that transfer serial data reliably
asynchronous communication lines. In this note, I
widely-used standards that have been in existence for some time
might be appropriate for this environment. I hope that the
standards will be found to meet the needs the new proposals seek
address
In both the US and international standards areas, there are two
categories of serial data communication standards for the link layer
These categories are character-oriented and bit-oriented. The
is the older class; it is standardized in the US standard
X3.28-1976 (which superseded the original version of 1971), and
the ISO standards IS 1745, IS 2111, IS 2628 and IS 2629.
frequently used in synchronous environments, wherein the name
synchronous (or bisynch) is used, these standards use the term "
mode" to describe their procedures. The latter class is
in the US standard ADCCP (Advanced Data Communication
Procedures), ANSI X3.66- 1979, and in the ISO standard
(High-level Data Link Control procedures), in IS 3309, IS 4335 and
7809.
Other international standards, draft standards and vendor
follow the ADCCP/HDLC procedures. Among these are SDLC (IBM), X.25
LAPB (CCITT), IEEE 802.2/ISO 8802.2 LLC (LAN Logical Link Control
and ISDN LAPD (CCITT). Many vendors have built equipment which
Robinson [Page 1]
RFC 935 January 1985
Reliable Link Layer
the character-oriented standards, in both synchronous
asynchronous environments, including all the major US
manufacturers
The only other serial link layer protocol known to the author in
wide use as these is DEC's DDCMP (Digital Data Communications
Protocol). This protocol uses a character count instead of
characters, but is in other respects a character-oriented protocol
The next sections of this note will compare the three protocols
on several bases, paying particular attention to the
that make particular aspects of the protocol appropriate to
low-speed, asynchronous, serial environment
Frame
All serial protocols divide the data to be transmitted into
known as frames. A frame is typically one to several
characters in length. The frame structure is the major
used above to divide the protocols into three classes
Character-Oriented
Character-oriented protocols use two techniques for defining a frame
First, it is necessary to determine where characters start and stop
The technique used for this purpose is to transmit a number of
characters prior to the start of a frame. The character
used for this is the SYN character
Note that this is not required when using asynchronous transmission
Since each character is itself framed by start and stop bits,
is never a question of where characters begin and end
The main technique for structuring a frame is the use of
framing characters to delineate the start and end of a frame, and
delineate portions of the frame (such as header and text). Some
of character-oriented protocols require that these characters
appear in the header or text of the frame, while others
"transparent" transmission. Transparency is obtained by
each framing character by a unique control character, typically DLE
In this way, all characters may be sent as header or text, except
DLE. In order to allow DLE to be sent in the header or text, the
is doubled
Robinson [Page 2]
RFC 935 January 1985
Reliable Link Layer
Bit-Oriented
Bit-oriented protocols also use a unique character (technically,
is just an arbitrary bit-string) for frame delineation, which is
FLAG. This character provides frame synchronization. All
between two occurrences of FLAGs constitute a frame. The FLAG is a 0
bit, followed by six 1 bits, followed by another 0 bit. In
that the FLAG character not appear mistakenly in the data of
message, the sender inserts (and the receiver removes) an extra 0
after any five successive 1 bits in the data stream
Because this insertion of bits ("stuffing") results in
frame bit-lengths, bit-oriented protocols are generally useful
in synchronous transmission environments. Although it has never
attempted, however, one could imagine an asynchronous
where each FLAG character that appears in the data is translated
a two- character sequence that avoids FLAGs, and at least one
character is similarly translated. For example, one could frame
with FLAGS, and send DLE-F to mean FLAG and DLE-DLE to mean DLE
these characters occur within the frame
Note that bit-oriented procedures do not require that the number
bits between FLAGs be an exact number of 8-bit characters,
distinction to character-oriented protocols and DDCMP. The
for character-alignment may be imposed at higher layers, as it is
for example, in X.25 Network Layer
Frame Structure in
DDCMP uses a third approach to frame structure.
character-oriented protocols, it uses a SYN character to
character synchronization prior to starting a frame, but one
dispense with this over asynchronous lines (see below).
within the fixed-length header portion of the frame is a count field
which reports how many characters are contained in
variable-length text portion. Since no framing characters
required at all, transparency is not a problem. However, because
count must be received properly for the sender and receiver to
in frame synchronization, the header is protected with a
error control checksum, which is typically two characters long (
below). Also, once a header error has been detected, the count
must be assumed to be invalid, and so there must be a
character sequence that introduces the next header in order that
receiver can regain synchronization with the sender
Therefore, the SYN characters preceding a frame are required even
asynch lines
Robinson [Page 3]
RFC 935 January 1985
Reliable Link Layer
Error
Several types of error control may be used, and the various
above are similar. Most synchronous uses require a cyclic
check sequence be attached to each frame. This is a 16-bit
which can be easily generated and checked in hardware using a
register, and can be somewhat more tediously done in software
about 5-6 instructions per character sent or received, and a 256
16-bit lookup table. DDCMP and Bit-oriented protocols all
use of such a sequence. As noted above, DDCMP uses a check
twice, once for the header and once for the data
In some environments, weaker checks are used on character-
links. These take two forms. If the the number of significant
per character is only 7, then the parity bit can be set to
either odd or even parity. ANSI standard X3.16-1976 specifies
odd parity should be used on synchronous links and even parity
asynchronous links. The second type of check is "
parity", wherein one character is added to the frame so that
number of 1 bits in each bit position summed over all the
of the message and the check character is even. In other words,
exclusive-or of all the characters is 0. Character parity
longitudinal parity may be used together
Note also that most character-oriented control messages, such
those that poll, select, and acknowledge, are sent with only
for error control
Sequence
All these protocol provide reliable transmission by sequencing
frames and providing positive and (in some cases)
acknowledgments. Senders can ask the receiver for status if a
is late
In character-oriented protocols, frames are implicitly
(typically) and only one may be outstanding at a time
Acknowledgments are explicitly numbered. One variant allows
block (frame) to be explicitly numbered as well; in this 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. Optional control field
allows for up to 127 outstanding. An alternate procedure that
been defined for use both in the ISDN LAPD environment and in
Robinson [Page 4]
RFC 935 January 1985
Reliable Link Layer
802 LAN environments uses, in effect, a one-bit sequence number
one outstanding frame. Also, unsequenced, unacknowledged
frames can be used when frames need not be sent reliably
In DDCMP, the frames are explicitly numbered and up to 255 may
outstanding
All of these protocols allow for addressing stations on a
link separately. In LAN environments, both a sending and
address are required, whereas multipoint environments use a
address and assume one master station communicating with
addressed slave stations. In bit-oriented protocols, the
provides extra information in that frames can be categorized
commands or responses; in this sense, the address provides
control bit per frame. However, it is possible to operate
needing this distinction
Addresses are typically one character long; bit-oriented
allow for extension of this field to arbitrary length
Character-oriented protocols use two-character (controller
terminal) addresses
For point-point operation, the address is clearly superfluous (
to distinguish commands and replies in bit-oriented protocols);
might imagine dispensing with it
The Asynchronous
Which of these protocols is best for the asynchronous environment
This depends on the definition of "best", of course. One means
judging is to compare the amount of overhead that each protocol
add to each frame sent
We will examine the overhead costs in two groups
framing/transparency/error checking
and addressing/control
The two groups of functions are independent of each other,
though the protocols mentioned above use specific combinations
techniques from these two groups. Also, hardware available
minicomputer-class and larger machines today supports the first
of functions completely for these standard protocols; this
should allow for far greater performance from the gateway machine
Robinson [Page 5]
RFC 935 January 1985
Reliable Link Layer
To the extent that such hardware becomes available for
computers, it can also be used there to reduce the
processing overhead. Here's a breakdown of framing costs
characters. RATP is also included for comparison
Protocol Frame Check Transp. Total F+
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 indicates the anticipated cost in
characters to achieve transparency across a 256-byte frame.
figure for bit-oriented protocols is a pessimistic guess, because
don't know the exact answer; it is between 0 and 8 characters,
the worst case occurring when the data is all one bits.
character-oriented protocols, we would expect on average one
character in a 256-byte frame; the worst case overhead (256 DLEs)
256 bytes
Because transparency is so much a function of the user data,
because we have ignored the cost of loss of frame synchronization
the counting protocols (DDCMP and RATP), I argue that we should
the comparison on the frame and checksum costs only. For these
columns, character-oriented framing costs one more character
frame than RATP. This, plus its wide use and hardware chip support
create a strong case for its use in preference to RATP for framing
Bit-oriented framing, as noted previously, is appropriate only
synchronous links. The character oriented variant I postulated
would have the same costs, but as it is not a standard, it is
proposed here. So we now have constructed the following
format
DLE STX DLE ETX CRC
One objection to using character-oriented protocols as opposed
character-count protocols is that it is necessary to examine
character as it arrives. I respond to this objection as follows
1. Under some circumstances, such as when a header has been
with an error, it will be necessary for the receiver to look
every character anyway
2. The environment for this protocol is a 1200 baud link;
Robinson [Page 6]
RFC 935 January 1985
Reliable Link Layer
120 characters per second need to be examined at a maximum.
on a relatively slow personal computer, this should not present
problem
We now turn our attention to the content and format of the
information preceding each link frame. There are three components
this cost, control, address, and acknowledgment. The address
allows multipoint configurations and is superfluous for
point-to-point environment proposed, but it is present in the
standards and we restrict ourselves to those
Acknowledgments are shown if they are required explicitly by
protocol. A "0" indicates that the acknowledgments may be
in the control information for traffic in the opposite direction,
only need be sent explicitly when no reverse traffic is present (
thus are assumed to take no required overhead).
character-oriented protocols have required acknowledgments
Cont. Addr. Ack
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 provide the lowest overhead
the public standards, but in this case there is no conflict in
them in the asynchronous environment. In fact, even if all the
aspects of RATP were to be adopted, I believe the control
codings of the bit- oriented procedures represent a more
use of the channel, are widely implemented, and allow for addition
more functions later if desired. As stated above, there are
protocols in the bit-oriented family. I would recommend use of LAPB
since this is the most widely known of the family
For those not familiar with bit-oriented control procedures, I
included a quick summary of these procedures in Appendix A. Refer
the standards listed at the end of this note for more detail
Robinson [Page 7]
RFC 935 January 1985
Reliable Link Layer
RATP Compared to Public
As can be seen from the above tables, RATP does not represent
significant savings compared to other widely-used protocols
Given frame lengths of 13 bytes, which appears to be the minimum
Thinwire II (RFC 914), 8 characters' overhead using the
standards represents 61% versus 46% for RATP's 6 characters. On
1200 baud line, the bandwidth available assuming only such
frames is thus 74 versus 82 characters per second, respectively
Since 1/13 of these are actually user data, the typing
supported by these protocols using TCP/IP are pretty low, like 5.6
versus 6.3 characters per second. Clearly a bigger cost is
found in the 12 characters overhead in Thinwire II (or 40 for TCP/
with no compression).
The costs improve dramatically when the number of user characters
frame increases. Thus, file transfer, or even line-blocked typing
should perform adequately. As frame size grows, the cost of
extra 2 characters per frame to use standard protocols rapidly
to a few percent or less
RATP does allow one optimization which cannot be achieved in
standard protocols - the use of a one-character format that
the per-frame overhead to 3 characters (or 4 if a 16-bit CRC
used). However, in the scenario wherein single-character
make sense, a user typing characters (with no higher
protocols), the extra overhead is probably not a problem since
link is still lightly enough loaded that the extra overhead is
a small percentage of the available bandwidth. Also,
multiple frames in flight helps reduce the bottleneck caused
having one frame at a time outstanding
On Check
Both RFCs 914 and 916 propose to use relatively simple
sequences, which can be easily computed in a general-
processor. In one case, this is an additive check and in the
it is an exclusive-or (or parity) check. Although the additive
is slightly more powerful than the exclusive-or, both are
weak compared to CRC techniques
Since the intended network-layer protocol (IP) provides for
checks on its header, and the transport layer (TCP) checksums
header and data, one might question whether the protection
also be provided at the link layer at all, or if it should, then
these checks good enough? Providing for recovery at the TCP
Robinson [Page 8]
RFC 935 January 1985
Reliable Link Layer
leads to slow recovery times, so this approach will probably
too poor a level of service for noisy links. More importantly,
link layer control field needs a certain degree of protection
prevent needless loss or duplication of frames in the face of
errors
A CRC check, in combination with the additive checks provided by
and TCP, yield an error-protection that is greater than that
by either check by itself. This is because the two
address fundamentally different characteristics of the
errors. The degree of increase is substantial compared to that
two additive checks. That is, if two additive checks are cascaded
there are many types of two-bit failures that will pass both the
layer and TCP/IP checking
Although I don't wish to include a detailed error analysis in
note, I would support the use of a CRC type of error check because
the far greater level of protection it affords. As I pointed out
the cost per character is roughly 5-6 instructions, assuming the
of a 256 by 16-bit lookup table. Again, at 120 characters
second, the increased cost is not deemed to be too great
Moreover, use of a standard CRC allows for the possibility that
serial line chip's own CRC generation and checking hardware may
used. Although such chips may not be present in the PCs in
environment envisioned, they are likely to be available in
gateway machine to which the PCs talk
Data Compression: An
I find the proposed methods of data compression of RFC 914
particularly interesting. I see these as independent of the
of the underlying link layer protocol, as it is in RFC 914. I
aware of no such character-oriented compression that is in common
in the communication world. The only techniques that come close
in statistical multiplexing devices, which sometimes also include
adaptive Huffman-coding to reduce link bandwidth. Since the
II approach can recognize much longer repeated sequences than
Huffman code, I expect that the potential savings are
greater
I would like to see a version of the Thinwire protocols which
for the template idea, but which keeps it independent of the
layer protocols in use. One way to achieve this is to
templates to be encoded and exchanged between the
parties when they start up, and perhaps adaptively as
warrant. I would anticipate that this sort of approach might
Robinson [Page 9]
RFC 935 January 1985
Reliable Link Layer
have widespread applicability beyond the TCP/IP environment
in RFC 914. The most important gain for this environment is
of the apparent exorbitant overhead that IP and TCP seem to
for use over slow links
The link layer protocol I would advocate for asynchronous,
communication between PCs would use transparent, character-
framing, a 16-bit CRC error check, and the control procedures
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
support both of these if they support either
Evolution of integrated circuits that directly implement all of
public standards will dramatically drop the cost and raise
reliability of new implementations of standard protocols.
manufacturers have little motivation to address standards that
not widely used
Overhead for the suggested protocol is 8 characters per frame. Up
7 frames may be outstanding at a time in either direction
transfer. Choice of an appropriate maximum frame size
application-dependent, and would certainly be influenced by
quality of the physical connection; however, I believe that
datagrams are acceptable frames for dialup 1200 baud service
Non-standard modifications that would save a little link
would be to dispense with the one-character address field, and to
the RATP count-oriented frame structure. These are not recommended
because they depart from common practice and yield
improvements at best
Those familiar with the early history of the Telenet Public
Network should recognize that this proposal is essentially the
as the original link layer protocol specification for that network
circa 1976, except that the control procedures used at that time
known as LAP, have now been superseded by the more powerful
efficient LAPB, and their access links, as all X.25 access links,
synchronous rather than asynchronous. I did not set out to
this result, but just note it in passing
My personal view of where the world of personal computer access
data networks is heading is that X.25 will rapidly become
protocol of choice. One already sees third-party (for IBM PC)
Robinson [Page 10]
RFC 935 January 1985
Reliable Link Layer
vendor (for Wang PC) implementations of X.25. CCITT is circulating
proposal for accessing an X.25 data network using a dial-up X.25
connection, as recommendation X.32. Thus, I feel that the type
communication proposed in this RFC and RFCs 914 and 916 will be
for a relatively short period of time. The future holds, I believe
LAN or X.25/X.32 data link layer and access, X.25 and/or ISO
network layer, and TCP and/or ISO TP4 transport layer
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
Interchange (ASCII)", American National Standards Institute, Inc.,
1968.
ANSI X3.16-1976, "American National Standard Character Structure
Character Parity Sense for Serial-by-Bit Data Communication in
American National Standard Code for Information Interchange",
American National Standards Institute, Inc., 1976.
ANSI X3.28-1976, "American National Standard Procedures for the
of the Communication Control Characters of American National
Code for Information Interchange in Specified Data
Links", American National Standards Institute, Inc., 1976.
ANSI X3.66-1979, "American National Standard for Advanced
Communication Procedures (ADCCP)", American National
Institute, Inc., 1979.
International Standard 1745, "Information Processing - Basic
control procedures for data communication systems",
Organization for Standardization (ISO), 1975.
International Standard 2111, "Data Communication - Basic mode
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.
Robinson [Page 11]
RFC 935 January 1985
Reliable Link Layer
International Standard 3309, "Data Communication - High-level
link control procedures - Frame structure", ISO, 1982.
International Standard 4335, "Data Communication - High-level
link control procedures - Consolidation of elements of procedures",
ISO, 1982.
International Standard 7809, "Data Communication - High-level
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
in the Packet Mode and Connected to Public Data Networks by
Circuit", The International Telegraph and Telephone
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
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).
Robinson [Page 12]
RFC 935 January 1985
Reliable Link Layer
Appendix A - Bit-Oriented Control Field
There are three control field formats. The primary one is used
data frames (called "information frames" in the standards), and
coded as follows
8 7 6 5 4 3 2 1 <- bit number, 1 sent
0 (signifies data frame
S S S send seq , bit 2 low-
P/F poll/final bit, for
R R R receive seq (ACK
Acknowledgments are cumulative. Recovery is typically to back up
continue from the lost frame. Use of the poll/final bit is
the scope of this note
Acknowledgments may also be sent in supervisory frames, coded
follows
8 7 6 5 4 3 2 1 <- bit number, 1 sent
0 1 (signifies supervisory frame
T T frame type (see below
P/F poll/final bit, for
R R R receive seq (ACK
Up to four frame types are possible; only two are required.
first is called RR, for "receive ready", and indicates
and that the receiver is prepared to process more frames. The other
RNR for "receive not ready", is used for flow control of the sender
If flow control is not necessary, I suppose even this frame could
dispensed with
The other supervisory frames, "reject" and "selective reject",
varieties of negative acknowledgement that ask for retransmission
all and one (respectively) of previously transmitted frames
Positive acknowledgment and retransmission are the only
necessary procedures, however
The third frame format is called Unnumbered. Many possible
are specified in the various standards for these frames,
initializing the link, reset sequence numbers, etc. The basic
is
8 7 6 5 4 3 2 1 <- bit number, 1 sent
1 1 (signifies unnumbered frame
T T T T T frame
P/F poll/final bit, for
Robinson [Page 13]
if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.
RFC documents can be found at I.E.T.F.
Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX
