through 0xff (except 0x5e) in Control Escape format. Since these
octet values are not negotiable, this does not solve the problem
of receivers which cannot handle all non-control characters.
Also, since the technique does not affect the 8th bit, this does
not solve problems for communications links that can send only 7-
bit characters.
A few examples may make this more clear. Packet data is
transmitted on the link as follows:
0x7e is encoded as 0x7d, 0x5e.
0x7d is encoded as 0x7d, 0x5d.
0x01 is encoded as 0x7d, 0x21.
Some modems with software flow control may intercept outgoing DC1
and DC3 ignoring the 8th (parity) bit. This data would be
transmitted on the link as follows:
0x11 is encoded as 0x7d, 0x31.
0x13 is encoded as 0x7d, 0x33.
0x91 is encoded as 0x7d, 0xb1.
0x93 is encoded as 0x7d, 0xb3.
Aborting a Transmission
On asynchronous links, frames may be aborted by transmitting a "0"
stop bit where a "1" bit is expected (framing error) or by
transmitting a Control Escape octet followed immediately by a
closing Flag Sequence.
Time Fill
On asynchronous links, inter-octet and inter-frame time fill MUST
be accomplished by transmitting continuous "1" bits (mark-hold
state).
Note: On asynchronous links, inter-frame time fill can be
viewed as extended inter-octet time fill. Doing so can save
one octet for every frame, decreasing delay and increasing
bandwidth. This is possible since a Flag Sequence may serve as
both a frame close and a frame begin. After having received
any frame, an idle receiver will always be in a frame begin
state.
Robust transmitters should avoid using this trick over-
zealously since the price for decreased delay is decreased
reliability. Noisy links may cause the receiver to receive
garbage characters and interpret them as part of an incoming
frame. If the transmitter does not transmit a new opening Flag
Sequence before sending the next frame, then that frame will be
appended to the noise characters causing an invalid frame (with
high reliability). Transmitters should avoid this by
transmitting an open Flag Sequence whenever "appreciable time"
has elapsed since the prior closing Flag Sequence. It is
suggested that implementations will achieve the best results by
always sending an opening Flag Sequence if the new frame is not
back-to-back with the last. The maximum value for "appreciable
time" is likely to be no greater than the typing rate of a slow
to average typist, say 1 second.
B. Fast Frame Check Sequence (FCS) Implementation
B.1. FCS Computation Method
The following code provides a table lookup computation for
calculating the Frame Check Sequence as data arrives at the
interface. This implementation is based on [7], [8], and [9]. The
table is created by the code in section B.2.
/*
* u16 represents an unsigned 16-bit number. Adjust the typedef for
* your hardware.
*/
typedef unsigned short u16;
/*
* FCS lookup table as calculated by the table generator in section
* B.2.
*/
static u16 fcstab[256] = {
0x0000, 0x1189, 0x2312, 0x329b, 0x4624, 0x57ad, 0x6536, 0x74bf,
0x8c48, 0x9dc1, 0xaf5a, 0xbed3, 0xca6c, 0xdbe5, 0xe97e, 0xf8f7,
0x1081, 0x0108, 0x3393, 0x221a, 0x56a5, 0x472c, 0x75b7, 0x643e,
0x9cc9, 0x8d40, 0xbfdb, 0xae52, 0xdaed, 0xcb64, 0xf9ff, 0xe876,
0x2102, 0x308b, 0x0210, 0x1399, 0x6726, 0x76af, 0x4434, 0x55bd,
0xad4a, 0xbcc3, 0x8e58, 0x9fd1, 0xeb6e, 0xfae7, 0xc87c, 0xd9f5,
0x3183, 0x200a, 0x1291, 0x0318, 0x77a7, 0x662e, 0x54b5, 0x453c,
0xbdcb, 0xac42, 0x9ed9, 0x8f50, 0xfbef, 0xea66, 0xd8fd, 0xc974,
0x4204, 0x538d, 0x6116, 0x709f, 0x0420, 0x15a9, 0x2732, 0x36bb,
0xce4c, 0xdfc5, 0xed5e, 0xfcd7, 0x8868, 0x99e1, 0xab7a, 0xbaf3,
0x5285, 0x430c, 0x7197, 0x601e, 0x14a1, 0x0528, 0x37b3, 0x263a,
0xdecd, 0xcf44, 0xfddf, 0xec56, 0x98e9, 0x8960, 0xbbfb, 0xaa72,
0x6306, 0x728f, 0x4014, 0x519d, 0x2522, 0x34ab, 0x0630, 0x17b9,
0xef4e, 0xfec7, 0xcc5c, 0xddd5, 0xa96a, 0xb8e3, 0x8a78, 0x9bf1,
0x7387, 0x620e, 0x5095, 0x411c, 0x35a3, 0x242a, 0x16b1, 0x0738,
0xffcf, 0xee46, 0xdcdd, 0xcd54, 0xb9eb, 0xa862, 0x9af9, 0x8b70,
0x8408, 0x9581, 0xa71a, 0xb693, 0xc22c, 0xd3a5, 0xe13e, 0xf0b7,
0x0840, 0x19c9, 0x2b52, 0x3adb, 0x4e64, 0x5fed, 0x6d76, 0x7cff,
0x9489, 0x8500, 0xb79b, 0xa612, 0xd2ad, 0xc324, 0xf1bf, 0xe036,
0x18c1, 0x0948, 0x3bd3, 0x2a5a, 0x5ee5, 0x4f6c, 0x7df7, 0x6c7e,
0xa50a, 0xb483, 0x8618, 0x9791, 0xe32e, 0xf2a7, 0xc03c, 0xd1b5,
0x2942, 0x38cb, 0x0a50, 0x1bd9, 0x6f66, 0x7eef, 0x4c74, 0x5dfd,
0xb58b, 0xa402, 0x9699, 0x8710, 0xf3af, 0xe226, 0xd0bd, 0xc134,
0x39c3, 0x284a, 0x1ad1, 0x0b58, 0x7fe7, 0x6e6e, 0x5cf5, 0x4d7c,
0xc60c, 0xd785, 0xe51e, 0xf497, 0x8028, 0x91a1, 0xa33a, 0xb2b3,
0x4a44, 0x5bcd, 0x6956, 0x78df, 0x0c60, 0x1de9, 0x2f72, 0x3efb,
0xd68d, 0xc704, 0xf59f, 0xe416, 0x90a9, 0x8120, 0xb3bb, 0xa232,
0x5ac5, 0x4b4c, 0x79d7, 0x685e, 0x1ce1, 0x0d68, 0x3ff3, 0x2e7a,
0xe70e, 0xf687, 0xc41c, 0xd595, 0xa12a, 0xb0a3, 0x8238, 0x93b1,
0x6b46, 0x7acf, 0x4854, 0x59dd, 0x2d62, 0x3ceb, 0x0e70, 0x1ff9,
0xf78f, 0xe606, 0xd49d, 0xc514, 0xb1ab, 0xa022, 0x92b9, 0x8330,
0x7bc7, 0x6a4e, 0x58d5, 0x495c, 0x3de3, 0x2c6a, 0x1ef1, 0x0f78
};
#define PPPINITFCS 0xffff /* Initial FCS value */
#define PPPGOODFCS 0xf0b8 /* Good final FCS value */
/*
* Calculate a new fcs given the current fcs and the new data.
*/
u16 pppfcs(fcs, cp, len)
register u16 fcs;
register unsigned char *cp;
register int len;
{
ASSERT(sizeof (u16) == 2);
ASSERT(((u16) -1) > 0);
while (len--)
fcs = (fcs >> 8) ^ fcstab[(fcs ^ *cp++) & 0xff];
return (fcs);
}
B.2. Fast FCS table generator
The following code creates the lookup table used to calculate the
FCS.
/*
* Generate a FCS table for the HDLC FCS.
*
* Drew D. Perkins at Carnegie Mellon University.
*
* Code liberally borrowed from Mohsen Banan and D. Hugh Redelmeier.
*/
/*
* The HDLC polynomial: x**0 + x**5 + x**12 + x**16 (0x8408).
*/
#define P 0x8408
main()
{
register unsigned int b, v;
register int i;
printf("typedef unsigned short u16;\n");
printf("static u16 fcstab[256] = {");
for (b = 0; ; ) {
if (b % 8 == 0)
printf("\n");
v = b;
for (i = 8; i--; )
v = v & 1 ? (v >> 1) ^ P : v >> 1;
printf("0x%04x", v & 0xFFFF);
if (++b == 256)
break;
printf(",");
}
printf("\n};\n");
}
C. LCP Recommended Options
The following Configurations Options are recommended:
SYNC LINES
Magic Number
Link Quality Monitoring
No Address and Control Field Compression
No Protocol Field Compression
ASYNC LINES
Async Control Character Map
Magic Number
Address and Control Field Compression
Protocol Field Compression
Security Considerations
Security issues are briefly discussed in sections concerning the
Authentication Phase, and the Authentication-Protocol Configuration
Option. Further discussion is planned in a separate document
entitled PPP Authentication Protocols.
References
[1] Electronic Industries Association, EIA Standard RS-232-C,
"Interface Between Data Terminal Equipment and Data
Communications Equipment Employing Serial Binary Data
Interchange", August 1969.
[2] International Organization For Standardization, ISO Standard
3309-1979, "Data communication - High-level data link control
procedures - Frame structure", 1979.
[3] International Organization For Standardization, ISO Standard
4335-1979, "Data communication - High-level data link control
procedures - Elements of procedures", 1979.
[4] International Organization For Standardization, ISO Standard
4335-1979/Addendum 1, "Data communication - High-level data
link control procedures - Elements of procedures - Addendum 1",
1979.
[5] International Organization For Standardization, Proposed Draft
International Standard ISO 3309:1983/PDAD1, "Information
processing systems - Data communication - High-level data link
control procedures - Frame structure - Addendum 1: Start/stop
transmission", 1984.
[6] International Telecommunication Union, CCITT Recommendation
X.25, "Interface Between Data Terminal Equipment (DTE) and Data
Circuit Terminating Equipment (DCE) for Terminals Operating in
the Packet Mode on Public Data Networks", CCITT Red Book,
Volume VIII, Fascicle VIII.3, Rec. X.25., October 1984.
[7] Perez, "Byte-wise CRC Calculations", IEEE Micro, June, 1983.
[8] Morse, G., "Calculating CRC's by Bits and Bytes", Byte,
September 1986.
[9] LeVan, J., "A Fast CRC", Byte, November 1987.
[10] American National Standards Institute, ANSI X3.4-1977,
"American National Standard Code for Information Interchange",
1977.
[11] Reynolds, J., and J. Postel, "Assigned Numbers", RFC1060,
USC/Information Sciences Institute, March 1990.
Acknowledgments
Much of the text in this document is taken from the WG Requirements
(unpublished), and RFCs 1171 & 1172, by Drew Perkins of Carnegie
Mellon University, and by Russ Hobby of the University of California
at Davis.
Many people spent significant time helping to develop the Point-to-
Point Protocol. The complete list of people is too numerous to list,
but the following people deserve special thanks: Rick Adams (UUNET),
Ken Adelman (TGV), Fred Baker (ACC), Mike Ballard (Telebit), Craig
Fox (NSC), Karl Fox (Morning Star Technologies), Phill Gross (NRI),
former WG chair Russ Hobby (UC Davis), David Kaufman (Proteon),
former WG chair Steve Knowles (FTP Software), John LoVerso
(Xylogics), Bill Melohn (Sun Microsystems), Mike Patton (MIT), former
WG chair Drew Perkins (CMU), Greg Satz (cisco systems) and Asher
Waldfogel (Wellfleet).
Chair's Address
The working group can be contacted via the current chair:
Brian Lloyd
Lloyd & Associates
3420 Sudbury Road
Cameron Park, California 95682
Phone: (916) 676-1147
EMail: brian@ray.lloyd.com
Author's Address
Questions about this memo can also be directed to:
William Allen Simpson
Daydreamer
Computer Systems Consulting Services
P O Box 6205
East Lansing, MI 48826-6025
EMail: bsimpson@ray.lloyd.com