[Docs] [txt|pdf] [Tracker] [WG] [Email] [Nits]
Versions: 00
PPP Working Group J. Carlson
Internet Draft IronBridge Networks
expires in six months S. Cheshire
M. Baker
Stanford University
November 1997
PPP Consistent Overhead Byte Stuffing (COBS)
<draft-ietf-pppext-cobs-00.txt>
Status of this Memo
This document is the product of the Point-to-Point Protocol
Extensions Working Group of the Internet Engineering Task Force
(IETF). Comments should be submitted to the ietf-ppp@merit.edu
mailing list.
Distribution of this memo is unlimited.
This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six
months. Internet-Drafts may be updated, replaced, or obsoleted by
other documents at any time. It is not appropriate to use Internet-
Drafts as reference material or to cite them other than as a
``working draft'' or ``work in progress.''
To learn the current status of any Internet-Draft, please check the
1id-abstracts.txt listing contained in the Internet-Drafts Shadow
Directories on ds.internic.net, nic.nordu.net, ftp.nisc.sri.com, or
munnari.oz.au.
Abstract
The Point-to-Point Protocol (PPP) [1] provides a standard method for
transporting multi-protocol datagrams over point-to-point links.
PPP also defines an extensible Link Control Protocol, which allows
the negotiation of optional frame encoding methods. This document
defines the Consistent Overhead Byte Stuffing (COBS) negotiation and
encapsulation procedure.
Carlson expires May 1998 [Page 1]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
Table of Contents
1. Introduction ........................................... 2
1.1. Conventions ............................................ 3
2. COBS Configuration Option Format ....................... 3
3. Encapsulation Method ................................... 5
3.1. Frame Transmission ..................................... 6
3.2. Frame Reception ........................................ 8
3.3. Zero-pair and zero-run encoding ........................ 9
3.4. Packet Preemption ...................................... 10
3.5. Recovery on LCP Renegotiation .......................... 12
3.6. Handling of Corrupted Data ............................. 12
4. Source Code ............................................ 13
4.1. Linear buffer encoding and decoding .................... 13
4.2. PPP/COBS Encoding with mbufs ........................... 16
4.2.1. PPP Context Handling ................................... 16
4.2.2. PPP Frame Transmission ................................. 17
4.2.3. Frame Reception ........................................ 23
5. Acknowledgments ........................................ 26
6. References ............................................. 26
7. Authors' Addresses ..................................... 26
1. Introduction
Standard PPP encapsulation on an asynchronous link uses an encapsula-
tion procedure called AHDLC, and on a Synchronous Optical Network
(SONET) or Synchronous Digital Heirarchy (SDH) link an encapsulation
procedure called Octet Synchronous [2]. These procedures are easy to
implement, require only a single character buffer and have good
error-recovery characteristics, but they have a worst case expansion
ratio of 100% where the user data consists of only hex 7D or 7E.
This draft describes a new encapsulation method for PPP due to origi-
nal work by Stuart Cheshire and Mary Baker at the Stanford University
Computer Science Department [3]. This new method is slightly more
complex than either of the two standard encodings and requires a 207
character buffer, but it has the same error-recovery characteristics
and has a worst-case expansion of less than 0.5%.
This low bound on worst-case expansion has a number of benefits. For
applications requiring Quality of Service (QoS) guarantees, it may be
necessary to over-provision a line using PPP by a factor of two in
order to deliver the requested bandwidth or to suffer possible queu-
ing delays when data do expand. For applications where the underly-
ing transport has message size limits, such as some radio protocols,
conventional PPP byte stuffing requires that the PPP Maximum Receive
Unit (MRU) and the associated network Maximum Transmission Units
Carlson expires May 1998 [Page 2]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
(MTUs) be reduced to half of the underlying hardware MTU. Even where
these considerations are not important, COBS options can provide
lower overhead than standard encoding methods, resulting in better
performance.
It should be noted that this concern over pathological data patterns
which double in size is not entirely academic. Certain protocols,
such as raw Pulse-Code Modulated (PCM) voice over User Datagram Pro-
tocol (UDP), can be prone to sending an excessive density of 7E char-
acters which will cause the standard encapsulations to double the
amount of actual data sent. Ironically, these protocols are pre-
cisely the ones that are likely to want guaranteed bandwidth ser-
vices. COBS avoids those expansion cases entirely because its
worst-case expansion in encoded data is less than 0.5%.
1.1. Conventions
The following language conventions are used in the items of specifi-
cation in this document:
o MUST, SHALL, or MANDATORY -- This item is an absolute require-
ment of the specification.
o SHOULD or RECOMMEND -- This item should generally be followed
for all but exceptional circumstances.
o MAY or OPTIONAL -- This item is truly optional and may be fol-
lowed or ignored according to the needs of the implementor.
2. COBS Configuration Option Format
A summary of the COBS Configuration Option format for the Link Con-
trol Protocol (LCP) is shown below. The fields are transmitted from
left to right.
0 1 2
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length | Flags |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type
To Be Determined
Carlson expires May 1998 [Page 3]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
Length
3
Flags
The flags are a single octet representing options which are passed
from the receiver to the transmitter. The most significant six
bits of this octet are reserved, and MUST be set to zero on
transmit and ignored on reception.
0 1 2 3 4 5 6 7
+-----+-----+-----+-----+-----+-----+-----+-----+
| Res | Res | Res | Res | Res | Res | PRE | ZXE |
+-----+-----+-----+-----+-----+-----+-----+-----+
These flags are:
ZXE If set to 1, then the receiver supports both zero pair
elimination (ZPE) and zero run elimination (ZRE).
PRE If set to 1, then the receiver supports packet preemp-
tion, which allows the sender to interrupt a COBS packet
in mid-stream to send a higher priority packet, and to
then return to the lower priority data.
This option is a boolean flag appearing at most once in a single
Configure-Request message. If it is present in a Configure-Request
message, then the sender wishes to receive data encoded using COBS
once LCP reaches Open state. If it is absent from the request, then
the sender does not wish to receive COBS data. If the option is
included in a Configure-Reject, then the sender is unable to transmit
using COBS and will continue to use the standard method for this link
(either Octet Synchronous or AHDLC) when LCP reaches the Open state.
The value of the Flags field is not negotiated because all COBS
transmitters SHALL be capable of handling all possible flag combina-
tions. Just as with MRU negotiation, where a receiver indicating
that it is prepared to receive packets up to 2048 octets in length
does not obligate its peer to actually send any packet with as many
as 2048 octets, a receiver indicating that it is prepared to receive
either of the optional COBS encodings does not obligate its peer to
actually send any packet using those encodings. Consequently, the
COBS option MUST NOT be included in a Configure-Nak message in reply
to a Configure-Request containing this option, even if the peer does
not implement some or all of the options that the receiver has indi-
cated its willingness to receive.
Carlson expires May 1998 [Page 4]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
An implementation that requires the use of COBS for normal operation
MAY, however, choose to send an "unsolicited" Configure-Nak with the
COBS option if the peer fails to include the COBS option in its
Configure-Request.
3. Encapsulation Method
Like the standard encapsulations, COBS uses an octet of hex 7E to
mark the bounds between frames. The value 7E does not appear in the
frame data itself. Using the value 7E helps ensure compatibility
with any existing software and hardware that may assume that the PPP
frame boundary marker is always 7E. It also aids recovery in the
case where errors occur and the transmitter and receiver are not in
agreement about whether COBS encapsulation is in effect. Because the
framing marker is the same regardless of whether COBS encapsulation
is in effect, frame boundaries are still detected correctly, and this
allows the error recovery described in section 3.5 to work very
easily.
COBS encapsulation is a simple reversible transformation that elim-
inates all instances of hex 7E from the frame to be transmitted.
This COBS encoding procedure is logically a two-step process,
although in real implementations both steps are performed in a single
loop for the sake of efficiency. The first step ("zero elimination")
eliminates all occurrences of zeroes from the data, while guarantee-
ing to add at most no more than 0.5% to the data size. This results
in a data packet containing only byte values hex 01 to hex FF, and no
zeroes. The second step ("7E substitution") replaces all occurrences
of hex 7E with hex 00, thereby producing a packet that does contain
zeroes but contains no instances of hex 7E.
The zero elimination step encodes any data packet using a series of
COBS code blocks. Each COBS code block begins with a single code
byte, followed by zero or more data bytes. The code byte determines
how many data bytes follow. The codes and their meanings are deter-
mined such that all possible data packets can be encoded as a valid
series of code blocks, and furthermore, even in the worst possible
case, there exists no valid encoding that adds more than 0.5% over-
head to the packet size. There is no pre-set limit to the length of
packet that may be encoded. The value zero is never used as a code
byte, nor does it ever appear as a data byte, which is why the output
of COBS zero elimination never contains any instances of the value
zero.
The 7E substitution step allows a linear code range to be used for
octet counts without concern for the potential end-of-frame marker in
the middle of the code space.
Carlson expires May 1998 [Page 5]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
The PPP/COBS codes and their meanings are listed below:
Code (n) Followed by: Meaning
-------- ------------ -------
00 Unused (framing character placeholder)
01-CF n-1 data bytes The data bytes, plus implicit trailing zero
D0 n-1 data bytes The data bytes, no implicit trailing zero
D1 Unused (resume preempted packet)
D2 Unused (reserved for future use)
D3-DF nothing a run of (n-D0) zeroes
E0-FE n-E0 data bytes The data bytes, plus two trailing zeroes
FF Unused (PPP error)
Code byte hex 00 is never used, in order to provide the required
"zero elimination" property.
Code byte hex D1 is never used (although value D1 may appear as a
data byte). If a COBS receiver observes that the first byte after a
framing marker is value D1, then it means that this new "packet" of
PPP data resumes transmission of a previously preempted packet (see
section 3.4).
Code byte hex D2 is never used (although value D2 may appear as a
data byte). Code byte hex D2 is reserved for future use.
Code byte hex FF is never used (although value FF may appear as a
data byte). If a COBS receiver observes that the first byte after a
framing marker is value FF, then this indicates that an error has
occurred (see section 3.5).
When negotiated, COBS goes into effect when LCP reaches the Open
state. When COBS is in effect, subsequent frames, including LCP mes-
sages such as Protocol-Reject, must be sent using COBS. If LCP
leaves the Open state, then COBS must be disabled. If LCP is renego-
tiated or if the peer is restarted, then COBS may be disabled
silently; this is detected by the procedure in section 3.5.
An implementation SHOULD disable COBS transmission before sending an
LCP Terminate-Request message.
3.1. Frame Transmission
As with AHDLC and Octet Synchronous encoding, a 7E is used to mark
the frame boundary. This value is guaranteed never to occur within
COBS encoded data.
The COBS zero elimination procedure effectively searches the packet
Carlson expires May 1998 [Page 6]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
for the first occurrence of value zero. To simplify the encoding
procedure, all packets are treated as though they end with a trailing
zero at the very end, after the standard CRC. This "phantom" octet
of hex 00 is automatically discarded after decoding at the receiving
end to correctly reconstruct the original packet data.
The number of octets up to and including the first zero determines
the code to be output. If this number is 207 or fewer, then this
number is output as the code byte, followed by the actual non-zero
bytes themselves. The zero is skipped and not output; the receiver
will automatically add the zero back in as part of the decoding pro-
cess. If there are 207 or more non-zero bytes, then code hex D0 is
output, followed by the first 207 non-zero bytes. This process is
repeated until all of the bytes of the packet (including the phantom
trailing zero at the end) have been encoded.
As an optional optimization, if the receiver has indicated its desire
to receive zero-pair and zero-run codes in its COBS Configuration
Option, then the transmitter MAY elect to encode zero pairs and zero
runs more efficiently. If a pair of 00 octets are found in the input
data after 0 to 30 non-zero octets, then the count of non-zero octets
plus E0 is output, followed by the non-zero octets, and both 00
octets in the input data are skipped. If a run of three to fifteen
00 octets are found in the input data, then the count of these 00
octets plus D0 is output and the 00 octets in the input data are
skipped. See section 3.3 below for more details.
If the receiver has indicated that it supports packet preemption and
the sender is also configured to support it, then it is possible to
preempt the state of the current COBS packet within two bytes and
send another. If preemption is required for a high-priority packet,
then the output state is checked. If the output is idle (no COBS
output is in progress) then the packet is sent normally. If the out-
put is busy (at least one data octet has been output for a packet in
progress), then an error is forced to interrupt the current packet
and the current packet being transmitted is saved but the COBS encod-
ing state is discarded, and the high-priority packet is then sent
using COBS encoding. When the high-priority packet is complete and
the terminating 7E has been sent, the sender MAY resume the saved
packet by issuing a D1 code after the terminating 7E, and then res-
tarting COBS encoding. If a subsequent high-priority packet requires
transmission instead, then it MAY be sent immediately. See section
3.4 below for more details.
Note that both of these options are proper supersets of the basic
encoding, so a transmitter that does not support an option which the
receiver does support will always send data that the receiver can
correctly decode. Likewise, if the receiver does not support a given
Carlson expires May 1998 [Page 7]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
option, the transmitter MUST disable its use of this encoding. This
arrangement allows the LCP negotiation for COBS to be quite simple.
The COBS count code FF is never used. Since a COBS count always fol-
lows a 7E, this means that a COBS encoder will never generate 7E FF.
This sequence is instead used to disable COBS in the event that LCP
is renegotiated; see section 3.5.
3.2. Frame Reception
The frame boundaries are located by a 7E as with AHDLC and Octet Syn-
chronous encodings. A frame boundary in the input stream terminates
the decoding process. If the boundary occurs at the end of a COBS
code block then the packet is deemed complete and the final trailing
("phantom") zero is removed before the packet is passed to the higher
layer for processing. If the boundary occurs within a COBS code
block then this is an error or, if the receiver supports it, a poten-
tial packet preemption. See section 3.4 below for more details on
packet preemption.
If the first octet of the frame is hex FF, then recovery is attempted
as in section 3.5. Otherwise, the stream of octets within a within a
frame is transformed by converting all instances of 00 to 7E. If the
first octet of the frame is hex D1, then this "packet" resumes
transmission of a previously preempted packet. See section 3.4 below
for more details on packet preemption. Otherwise, the COBS decoder
decodes the encoded byte stream as described below:
The COBS decoder reads the first byte (the code byte).
If the octet is D0, then 207 octets of data are copied from the input
stream to the frame, and no 00 octets are appended.
Otherwise, if the most significant four bits are 1101, and ZPE/ZRE is
implemented in the receiver, then the least significant four bits are
used as a count of 00 octets to append to the frame data. If ZPE/ZRE
is not implemented in the receiver, then this is an error.
Otherwise, if the most significant three bits are 111, and ZPE/ZRE is
implemented in the receiver, then this encodes a run followed by a
pair of zeroes. The least significant five bits are used as a count
of octets to read from the input data stream. These octets are
copied to the frame being decoded, and then two 00 octets are
appended to the frame data. If ZPE/ZRE is not implemented in the
receiver, then this is an error.
Otherwise, the value of the octet is a counter. Count-1 octets of
Carlson expires May 1998 [Page 8]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
the input stream are copied to the frame and a single 00 octet is
appended.
The decoding process then continues by reading the next code byte
from the input and repeating the decoding process described above
until all bytes of the input have been consumed.
3.3. Zero-pair and zero-run encoding
The goal of COBS encoding is to provide a standard that is suitable
for use on both the highest speed links and the lowest speed links.
One dilemma that faces designers of higher level protocols today is
that for efficiency at very high speeds it is beneficial to align
fields to 64-bit or even 128-bit boundaries. The IPv6 header format
is an example of this trend. Unfortunately this can often mean
inserting padding zeroes between fields to ensure proper alignment,
thereby wasting precious bandwidth when these packets are sent over
low speed links. Another common practice is for protocol designers
to define fields that are reserved for future expansion, accompanied
by the familiar phrase "MUST be set to zero on transmission and
ignored on reception." These extra unnecessary zeroes in packets also
waste bandwidth.
The purpose of COBS's zero-pair and zero-run encoding is to remove
this protocol designers' dilemma. COBS's zero-pair and zero-run
encoding can "compress out" block of zeroes from packet data, thereby
making the cost of these extra zeroes negligible. This allows proto-
col designers to design one single format for their protocol, without
being forced to choose between either favoring high speed or favoring
low speed links.
Particularly for string fields, it can be convenient to have a fixed
size field that is considerably longer than the typical string length
it holds, in order to keep a simple fixed-format packet structure
while at the same time not unduly limiting the length of string that
may be used in that field. As long as the unused bytes are zero-
filled, zero-pair and zero-run encoding will "compress out" those
unused bytes, making their cost negligible.
Zero-pair and zero-run encoding are not intended to compete with more
sophisticated (and more computationally costly) compression algo-
rithms such as Lempel-Ziv [4] or Huffman [5] encoding. On the very
slowest links, these compression algorithms may still be appropriate.
The highest compression ratios are achieved by algorithms such as Van
Jacobson's TCP header compression which take advantage of interdepen-
dencies between packets. However, this means that a single packet
Carlson expires May 1998 [Page 9]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
loss on the link can cause multiple packets to be unrecoverable,
which may not be appropriate for technologies such as wireless links
where packet loss rates are already relatively high.
One aspect of zero-run compression is that on reception this
compressed data has to be expanded back to its original size. On the
very highest speed links, where the link data rate is comparable to
the memory system bandwidth, this potential 15:1 expansion at the
receiver may be unacceptable. For this reason, the receiver may
request in its COBS Configuration Option that the sender *not* gen-
erate zero-pair (hex E0-FE) or zero-run (hex D3-DF) COBS codes. If
the receiver does not indicate its desire to receive zero-pair and
zero-run codes in its COBS Configuration Option, the transmitter MUST
not generate these codes.
The reverse situation -- of a COBS transmitter that does not imple-
ment zero-pair and zero-run encoding -- needs no negotiation. Even
if the receiver indicates its willingness to receive zero-pair and
zero-run codes of a transmitter that does not implement them, the
transmitter's output, while not containing those codes, will still be
a perfectly legal encoding of the packets. It may be a sub-optimal
encoding, but it is still a legal encoding that the receiver will
decode correctly.
3.4. Packet Preemption
On low speed links there can be conflicting goals. To provide effi-
ciency, it is desirable to allow packets to be as large as possible.
However, if a small high-priority packet arrives just as a large
low-priority packet begins transmission, the high-priority packet is
delayed until transmission of the large low-priority packet is com-
plete, which favors making the maximum packet size relatively small.
Packet preemption solves this dilemma by allowing the link to suspend
transmission of a low-priority packet immediately whenever a high-
priority packet needs to be sent, and then resume transmission of the
low-priority packet afterwards.
COBS packet preemption allows us to do this with at most two bytes of
additional overhead compared to sending the packets in the normal
sequential manner.
If the receiver has indicated in its COBS Configuration Option that
it supports packet preemption, then the transmitter can preempt a
low-priority packet at any time simply by forcing an error and then
beginning transmission of the high-priority packet. After the high-
priority packet(s) has (have) been sent, the sender resumes transmis-
sion of the preempted packet by transmitting a code hex D1 (resume
Carlson expires May 1998 [Page 10]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
preempted packet) and then resuming COBS encoded transmission from
the first untransmitted byte of the preempted packet.
During packet transmission, the transmitter is either in a state in
which it is transmitting data within a COBS block or it has just sent
the last octet of a COBS block and is preparing to send the code byte
to start a new COBS block. To force an error for packet preemption,
a 7E code must be sent within the data portion of a COBS block.
Therefore, if the transmitter is preparing to send a new counter when
preemption is necessary, it should either calculate and send that
counter first, or it should send a dummy counter of 02. In any case,
the 7E that follows will signal the preemption. The receiver will
detect an incomplete COBS code block as an error.
A receiver that supports packet preemption must maintain two packet
receive buffers. The two buffers are equal in status, but at any
point in time one buffer is the "active buffer" and the other is the
"inactive buffer". If an error occurs in the course of COBS decod-
ing, then the receiver treats it as a possible indication of packet
preemption. The receiver remembers the number of decoded bytes that
have been written into the active buffer, and the other buffer now
becomes the active buffer. The receiver then proceeds to receive
packets as normal into this buffer. When the receiver observes a
packet that begins with the byte value hex D1, it recognizes this as
an indication to resume a previously preempted packet. The active
and inactive buffers are again swapped, but now instead of beginning
writing to the start of the buffer, the receiver proceeds to append
bytes after any data that is already there. In the unlikely event
that the inactive buffer contains no bytes of data, this is not con-
sidered an error. A previous packet may have been preempted before
even a single byte of data was decoded, in which case having zero
bytes of data already in the buffer when the packet resumes is in
fact correct.
The following example shows a large packet preempted by two small
ones. The large packet contains the hex values "01 02 03 04 05 06
07" and the two small packets contain the values "11 12 13" and "21
22 23" respectively. If the large packet is preempted after three
bytes, the correct encoding of this data is:
7E 08 01 02 03 7E 04 11 12 13 7E 04 21 22 23 7E D1 05 04 05 06 07 7E
The byte-stream begins with the framing marker 7E. The encoder then
indicates that it plans to send seven non-zero bytes (COBS code hex
08). It then sends the first three of those non-zero bytes (01 02
03) before a pair of high-priority packets arrive. The sender then
interrupts the transmission of the low-priority packet with another
framing marker 7E, and sends the two high-priority packets. The
Carlson expires May 1998 [Page 11]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
receiver holds the three bytes of the partially received packet in
the inactive buffer while it is receiving the high-priority packets.
When the high-priority packets are complete, the sender sends a code
hex D1 to indicate that it is resuming transmission of the preempted
packet. The encoder indicates that it plans to send four non-zero
bytes (COBS code hex 05) and sends the remaining four bytes of the
low-priority packet.
Since packet preemption is most useful on low-speed links, high-speed
COBS implementations may elect not to implement packet preemption.
If the receiver does not indicate that is supports packet preemption
in its COBS Configuration Option, the transmitter MUST NOT preempt
packets.
The reverse situation -- of a COBS transmitter that does not imple-
ment packet preemption -- needs no negotiation. Even if the receiver
indicates its willingness to allow packet preemption, the
transmitter's output, while not containing any packet preemption,
will still be a perfectly legal steam of encoded packets.
3.5. Recovery on LCP Renegotiation
Since all implementations are required to send LCP frames with the
standard address and control fields, regardless of prior negotiation,
all LCP frames must begin with the hex sequence FF 03 C0 21 before
any byte-stuffing occurs.
The first octet of COBS data is always a counter value. Because of
the encoding methods chosen, this counter is never sent as FF. This
is to allow for recovery in case LCP is renegotiated or synchroniza-
tion is lost with the peer. Since LCP frames must begin with FF, any
frame seen when COBS is in use which begins with hex FF must
represent the start of an LCP frame without COBS enabled. The
receiver should disable COBS and revert back to Octet Synchronous or
AHDLC decoding as appropriate.
COBS speaking implementations using AHDLC MUST NOT default to escap-
ing FF when sending LCP frames unless COBS is explicitly disabled
since that would compromise this recovery mechanism.
3.6. Handling of Corrupted Data
If data are lost or corrupted during transmission, it is desirable
that the errors affect a minimum number of packets. For COBS, the
error characteristics are similar to AHDLC and Octet Synchronous
encodings.
Carlson expires May 1998 [Page 12]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
If one of the code byte octets is lost or corrupted, then the block
will be miscounted. This is likely to ultimately result in the
inclusion of the trailing 7E within the data portion of an erroneous
COBS block. The receiver will detect this as either an error (if it
does not support preemption) or as a preempted message. In the
latter case, the falsely preempted message will be discarded when the
next true preemption occurs. If the 7E still falls on a natural
boundary between COBS blocks, then COBS will not detect the error,
but the standard Frame Check Sequence (FCS) will be used to detect
the corruption.
If one of the data octets is corrupted, then the FCS will be used to
detect the corruption. As above, lost data octets will result in a
trailing 7E being included within the data portion of a message and
result in the loss of that one packet.
If the preemption-resume signal (D1) is lost, then the resumed data
stream will be treated as an independent frame and will be discarded
with an FCS error.
If data are corrupted such as to deliver 7E FF to a COBS receiver,
that receiver should restart LCP renegotiation due to the apparent
loss of state and should then restart COBS. For COBS encoding to be
viable on a given link, the probability of this type of corruption
must be acceptably low.
As with AHDLC and Octet-Synchronous, the loss of a 7E marker between
frames will result in the loss of those two frames.
4. Source Code
Two implementations are given for reference. The first implementa-
tion is a basic version which encodes and decodes linear blocks and
includes ZPE/ZRE. It is able to handle multiple blocks within one
coding unit by use of multiple sequential invocations.
The second is designed for a system using BSD-like mbufs for the PPP
stack and using a very simple FIFO buffer interface for data transmit
and receive. It includes standard 16-bit FCS generation and checking
and implements both the ZPE/ZRE option and the packet preemption
option.
4.1. Linear buffer encoding and decoding
typedef unsigned char u_char; /* 8 bit quantity */
Carlson expires May 1998 [Page 13]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
typedef enum
{
Unused = 0x00, /* Unused (framing character placeholder) */
DiffZero = 0x01, /* Range 0x01 - 0xCE: */
DiffZeroMax = 0xCF, /* n-1 explicit characters plus a zero */
Diff = 0xD0, /* 207 explicit characters, no added zero */
Resume = 0xD1, /* Unused (resume preempted packet) */
Reserved = 0xD2, /* Unused (reserved for future use) */
RunZero = 0xD3, /* Range 0xD3 - 0xDF: */
RunZeroMax = 0xDF, /* 3-15 zeroes */
Diff2Zero = 0xE0, /* Range 0xE0 - 0xFE: */
Diff2ZeroMax = 0xFE, /* 0-30 explicit characters plus 2 zeroes */
Error = 0xFF /* Unused (PPP LCP renegotiation) */
} StuffingCode;
/* These macros examine just the top 3/4 bits of the code byte */
#define isDiff2Zero(X) (((X) & 0xE0) == (Diff2Zero & 0xE0))
#define isRunZero(X) (((X) & 0xF0) == (RunZero & 0xF0))
/* Convert from single-zero code to corresponding double-zero code */
#define ConvertZP (Diff2Zero - DiffZero)
/* Allow generation of zero pair and zero run code blocks? */
int ZPZR = 1;
/* Highest single-zero code with a corresponding double-zero code */
#define MaxConvertible (ZPZR ? Diff2ZeroMax - ConvertZP : 0)
/* Convert to/from 0x7E-free data for sending over PPP link */
static u_char Tx(u_char x) { return(x == 0x7E ? 0 : x); }
static u_char Rx(u_char x) { return(x == 0 ? 0x7E : x); }
/*
* StuffData stuffs "length" bytes of data from the buffer "ptr",
* writing the output to "dst", and returning as the result the
* address of the next free byte in the output buffer.
* The size of the output buffer must be large enough to accommodate
* the encoded data, which in the worst case may expand by almost
* 0.5%. The exact amount of safety margin required can be
* calculated using (length+1)/206, rounded *up* to the next whole
* number of bytes. E.g. for a 1K packet, the output buffer needs to
* be 1K + 5 bytes to be certain of accommodating worst-case packets.
*/
#define FinishBlock(X) \
(*code_ptr = Tx(X), code_ptr = dst++, code = DiffZero)
static u_char *StuffData(const u_char *ptr, unsigned int length,
Carlson expires May 1998 [Page 14]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
u_char *dst, u_char **code_ptr_ptr)
{
const u_char *end = ptr + length;
u_char *code_ptr = *code_ptr_ptr;
u_char code = DiffZero;
/* Recover state from last call, if applicable */
if (code_ptr) code = Rx(*code_ptr);
else code_ptr = dst++;
while (ptr < end)
{
u_char c = *ptr++; /* Read the next character */
if (c == 0) /* If it's a zero, do one of these operations */
{
if (isRunZero(code) && code < RunZeroMax) code++;
else if (code == Diff2Zero) code = RunZero;
else if (code <= MaxConvertible) code += ConvertZP;
else FinishBlock(code);
}
else /* else, non-zero; do one of these operations */
{
if (isDiff2Zero(code)) FinishBlock(code - ConvertZP);
else if (code == RunZero) FinishBlock(Diff2Zero);
else if (isRunZero(code)) FinishBlock(code-1);
*dst++ = Tx(c);
if (++code == Diff) FinishBlock(code);
}
}
*code_ptr_ptr = code_ptr;
FinishBlock(code);
return(dst-1);
}
/*
* UnStuffData decodes "srclength" bytes of data from the buffer
* "ptr", writing the output to "dst". If the decoded data does not
* fit within "dstlength" bytes or any other error occurs, then
* UnStuffData returns NULL.
*/
static u_char *UnStuffData(const u_char *ptr, unsigned int srclength,
u_char *dst, unsigned int dstlength)
{
const u_char *end = ptr + srclength;
const u_char *limit = dst + dstlength;
while (ptr < end)
{
int z, c = Rx(*ptr++);
Carlson expires May 1998 [Page 15]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
if (c == Error || c == Resume || c == Reserved) return(NULL);
else if (c == Diff) { z = 0; c--; }
else if (isRunZero(c)) { z = c & 0xF; c = 0; }
else if (isDiff2Zero(c)) { z = 2; c &= 0x1F; }
else { z = 1; c--; }
while (--c >= 0 && dst < limit) *dst++ = Rx(*ptr++);
while (--z >= 0 && dst < limit) *dst++ = 0;
}
if (dst < limit) return(dst-1);
else return(NULL);
}
/* Example showing use of chained StuffData calls */
unsigned int StuffExample(const u_char *head, unsigned int hlength,
const u_char *data, unsigned int dlength,
u_char *dst)
{
u_char *ptr = dst;
u_char *stuffstate = NULL;
/* First stuff the packet header into the buffer */
ptr = StuffData(head, hlength, ptr, &stuffstate);
/* Then append the packet body to the stuffed header */
ptr = StuffData(data, dlength, ptr, &stuffstate);
/* Then return the total length of data generated */
return(ptr-dst);
}
4.2. PPP/COBS Encoding with mbufs
4.2.1. PPP Context Handling
struct cobs_context {
/* Transmit encoding state */
struct txcontext {
struct mbuf *bufs,*nextp;
short count,zskip,lcount;
} tx[2];
int txpri,txendofframe,txintr;
int txallowpri,txallowzxe;
/* Receive decoding state */
struct mbuf *mhead,*mtail;
Carlson expires May 1998 [Page 16]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
struct mbuf *savedpkt;
int rxcount,rxlcount,zadd;
u_short rxfcs;
u_short savedfcs;
u_char rxlchar;
};
/*
* Simple context initialization. User is responsible for setting
* cb.txallowpri and cb.txallowzxe based on the outcome of PPP
* negotiation.
*/
void
init_cobs_context(struct cobs_context *cb)
{
bzero(cb,sizeof(*cb));
cb->rxfcs = 0xFFFF;
}
4.2.2. PPP Frame Transmission
/*
* This is called once for each transmit-FIFO-empty interrupt. It
* takes a pointer to the transmit FIFO buffer and the available
* room in that buffer, and returns the number of bytes inserted.
* Priority is supported even if the peer doesn't support COBS
* priority interruption. If txallowpri is cleared, then priority
* packets are sent out on packet boundaries rather than as
* interrupts.
*/
int
ppp_cobs_xmit(struct cobs_context *cb, u_char *buffer, int buflen)
{
u_char *dp,chr,*obuf;
int len,count;
struct mbuf *mb,*mb2;
struct txcontext *tx;
if (buflen <= 0 || buffer == NULL || cb == NULL)
return 0;
/*
* If there's a high priority packet waiting and we're in the
* middle of sending a low priority one, then send the escape
* flag and switch.
*/
obuf = buffer;
Carlson expires May 1998 [Page 17]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
if (!cb->txendofframe && cb->tx[1].nextp != NULL &&
cb->txpri == 0) {
if (cb->tx[0].bufs == NULL)
cb->txpri = 1;
else if (buflen >= 2 && cb->txallowpri) {
cb->txpri = 1;
if (cb->tx[0].count == 0) {
*buffer++ = 0x02;
buflen--;
}
*buffer++ = 0x7E;
buflen--;
cb->tx[0].count = cb->tx[0].zskip = cb->tx[0].lcount = 0;
cb->txintr = 1;
cb->tx[1].lcount = -1;
}
}
tx = cb->tx + cb->txpri;
if ((mb = tx->bufs) == NULL) {
if ((mb = tx->nextp) != NULL) {
tx->nextp = mb->m_act;
mb->m_act = NULL;
}
}
count = tx->count;
while (buflen > 0) {
if (cb->txendofframe) {
switch (cb->txendofframe) {
case 1:
/*
* If the zero removal falls right on the end of
* the packet, then we need to add a dummy code to
* insert a 00 byte which will be deleted by the
* receiver.
*/
*buffer++ = 0x01;
buflen--;
cb->txendofframe = 2;
break;
case 2:
/* Packet done; send frame mark */
*buffer++ = 0x7E;
count = 0;
buflen--;
cb->txendofframe = 0;
tx->lcount = -1;
break;
Carlson expires May 1998 [Page 18]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
}
continue;
}
if (count == 0) {
if (mb == NULL) {
tx->bufs = mb;
tx->count = count;
if (cb->txpri == 1 && cb->tx[0].bufs != NULL) {
cb->txpri = 0;
tx = cb->tx;
mb = tx->bufs;
} else {
if (cb->tx[0].nextp == NULL &&
cb->tx[1].nextp == NULL)
break;
cb->txpri = (cb->tx[1].nextp != NULL);
tx = cb->tx + cb->txpri;
tx->bufs = mb = tx->nextp;
tx->nextp = mb->m_act;
mb->m_act = NULL;
}
count = tx->count;
if (cb->txpri == 0 && cb->txintr) {
cb->txintr = 0;
*buffer++ = 0xD1; /* Resume packet */
buflen--;
}
continue;
}
/* Do look-ahead for encoding modes */
dp = mtod(mb,u_char *);
if (*dp == 0 && cb->txallowzxe) {
mb2 = mb;
len = mb->m_len;
while (mb2 != NULL && count < 15)
if (*dp++ == 0) {
count++;
if (--len <= 0) {
do {
mb2 = mb2->m_next;
if (mb2 == NULL)
break;
dp = mtod(mb2,u_char *);
len = mb2->m_len;
} while (len <= 0);
}
} else
Carlson expires May 1998 [Page 19]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
break;
if (mb2 == NULL)
count++; /* Include phantom zero byte here */
}
if (count >= 3) {
tx->zskip = count;
chr = 0xD0 + count;
count = 0;
} else {
dp = mtod(mb,u_char *);
len = mb->m_len;
mb2 = mb;
count = 0;
while (mb2 != NULL && count < 207)
if (*dp++ != 0) {
count++;
if (--len <= 0) {
do {
mb2 = mb2->m_next;
if (mb2 == NULL)
break;
dp = mtod(mb2,u_char *);
len = mb2->m_len;
} while (len <= 0);
}
} else
break;
if (count == 207)
chr = 0xD0;
else {
chr = count+1;
tx->zskip = 1;
if (count <= 30 && cb->txallowzxe &&
mb2 != NULL) {
if (len <= 1)
do {
mb2 = mb2->m_next;
if (mb2 == NULL)
break;
dp = mtod(mb2,u_char *);
len = mb2->m_len;
} while (len <= 0);
if (mb2 == NULL || *dp == 0) {
chr = count + 0xE0;
tx->zskip = 2;
}
}
}
Carlson expires May 1998 [Page 20]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
}
tx->lcount = chr;
} else {
if (mb->m_len == 0) {
mb = m_free(mb);
continue;
}
chr = *mtod(mb,u_char *);
mb->m_len--;
mb->m_off++;
count--;
}
if (chr == 0x7E)
chr = 0;
*buffer++ = chr;
buflen--;
if (count == 0) {
count = tx->zskip;
while (mb != NULL && count > 0) {
len = mb->m_len;
if (len > count) {
mb->m_len -= count;
mb->m_off += count;
count = 0;
break;
}
count -= len;
mb = m_free(mb);
}
tx->zskip = 0;
while (mb != NULL && mb->m_len == 0)
mb = m_free(mb);
if (mb == NULL)
if (count == 0 && tx->lcount != 0xD0)
cb->txendofframe = 1;
else
cb->txendofframe = 2;
count = 0;
}
}
tx->bufs = mb;
tx->count = count;
return buffer-obuf;
}
/*
* This is called once for each out-bound packet. The arguments are
* the COBS state structure, the pointer to the out-bound mbuf chain,
Carlson expires May 1998 [Page 21]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
* and the priority level of the packet (0 or 1 for low or high).
*/
void
ppp_cobs_enqueue(struct cobs_context *cb, struct mbuf *mb, int pri)
{
u_short fcs;
u_char *dp;
int len;
struct mbuf *mb2;
struct txcontext *tx;
/*
* It turns out to be horribly complicated to support both the
* scan-ahead functions and the CRC calculation at the same time
* since the last byte of the CRC (or even both bytes) may be 00.
* Thus, it is necessary in this implementation to do the CRC
* first and the COBS encoding second in two separate steps. If
* the COBS output were fed into a simple linear output buffer
* big enough to hold the largest packet, then this could be
* greatly simplified.
*/
if (cb == NULL || mb == NULL)
return;
fcs = 0xFFFF;
for (mb2 = mb; mb2 != NULL; mb2 = mb2->m_next) {
dp = mtod(mb2,u_char *);
for (len = mb2->m_len; len > 0; len--)
fcs = (fcs >> 8) ^ fcstab[(fcs ^ *dp++) & 0xff];
}
mb2 = dtom(dp);
if (mb2->m_len+mb2->m_off > MMAXOFF-2) {
mb2->m_next = m_get(M_DONTWAIT,MT_PPPTX);
mb2 = mb2->m_next;
dp = mtod(mb2,u_char *);
}
fcs = ~fcs;
dp[0] = fcs&0xFF;
dp[1] = fcs>>8;
mb2->m_len += 2;
tx = cb->tx + pri;
if (tx->nextp == NULL)
tx->nextp = mb;
else {
for (mb2 = tx->nextp; mb2->m_act != NULL; mb2 = mb2->m_act)
;
mb2->m_act = mb;
}
Carlson expires May 1998 [Page 22]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
}
4.2.3. Frame Reception
/*
* This is called once for each FIFO-full-or-stale interrupt. It
* takes a pointer to the COBS state structure, the FIFO buffer
* pointer, and the length of the data in the FIFO. It in turn
* calls send_up_packet(struct mbuf *) if a packet has been received,
* or ppp_recv_error(void) if an error occurs, or disable_cobs(void)
* if the peer is apparently restarting LCP negotiation.
*/
void
ppp_cobs_rcv(struct cobs_context *cb, u_char *buffer, int len)
{
u_char *dp = NULL,chr,rxlchar;
struct mbuf *mb,*mb2;
int mlen = 0,count;
u_short fcs;
if ((mb = cb->mtail) != NULL) {
mlen = mb->m_len;
dp = mtod(mb,u_char *) + mlen;
}
fcs = cb->rxfcs;
count = cb->rxcount;
rxlchar = chr = cb->rxlchar;
while (len > 0) {
len--;
chr = *buffer++;
if (chr == 0x7E) {
rxlchar = chr;
if (count > 0) {
if (mb != NULL)
mb->m_len = mlen;
m_freem(cb->savedpkt);
cb->savedfcs = fcs;
cb->savedpkt = cb->mhead;
cb->zadd = 0;
mb = cb->mhead = NULL;
}
while (cb->zadd > 1) {
if (mb == NULL || mlen >= MLEN) {
mb2 = m_get(M_DONTWAIT,MT_PPPRX);
if (mb2 == NULL)
goto ppp_input_error;
if (mb != NULL) {
Carlson expires May 1998 [Page 23]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
mb->m_len = mlen;
mb->m_next = mb2;
} else
cb->mhead = mb2;
mb = mb2;
cb->mtail = mb;
dp = mtod(mb,u_char *);
mlen = 0;
}
*dp++ = 0;
fcs = (fcs >> 8) ^ fcstab[fcs & 0xff];
mlen++;
cb->zadd--;
}
if (mb == NULL)
m_freem(cb->mhead);
else if (count > 0 || fcs != 0xF0B8) {
ppp_input_error:
if (cb->mhead->m_next != NULL || mlen > 4)
ppp_recv_error();
m_freem(cb->mhead);
} else {
mb->m_len = mlen;
m_adj(cb->mhead,-2); /* Strip the CRC */
send_up_packet(cb->mhead);
}
cb->mtail = cb->mhead = mb = NULL;
count = cb->rxcount = cb->rxlcount = cb->zadd = 0;
fcs = cb->rxfcs = 0xFFFF;
continue;
}
if (chr == 0xD1 && rxlchar == 0x7E) { /* Resume code */
m_freem(cb->mhead);
mb = cb->mhead = cb->savedpkt;
if (mb != NULL) {
while (mb->m_next != NULL)
mb = mb->m_next;
cb->mtail = mb;
mlen = mb->m_len;
dp = mtod(mb,u_char *) + mlen;
} else {
dp = NULL;
mlen = 0;
}
fcs = cb->savedfcs;
cb->savedpkt = NULL;
rxlchar = chr;
continue;
Carlson expires May 1998 [Page 24]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
}
rxlchar = chr;
if (chr == 0)
chr = 0x7E;
for (;;) {
if (mb == NULL || mlen >= MLEN) {
mb2 = m_get(M_DONTWAIT,MT_PPPRX);
if (mb2 == NULL)
goto ppp_input_error;
if (mb != NULL) {
mb->m_len = mlen;
mb->m_next = mb2;
} else
cb->mhead = mb2;
mb = mb2;
cb->mtail = mb;
dp = mtod(mb,u_char *);
mlen = 0;
}
if (count > 0) {
*dp++ = chr;
fcs = (fcs >> 8) ^ fcstab[(fcs ^ chr) & 0xff];
mlen++;
count--;
break;
}
if (cb->zadd == 0) {
/* This can happen only if the peer starts renegotiating LCP */
if (chr == 0xFF) {
disable_cobs();
m_freem(cb->mhead);
m_freem(cb->savedpkt);
cb->mhead = cb->mtail = cb->savedpkt = NULL;
return;
}
switch (chr & 0xF0) {
case 0xD0:
cb->zadd = chr - 0xD0;
count = 0;
break;
case 0xE0:
case 0xF0:
count = chr - 0xE0;
cb->zadd = 2;
break;
default:
cb->zadd = (chr == 0xD0) ? 0 : 1;
count = chr-1;
Carlson expires May 1998 [Page 25]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
}
cb->rxlcount = count;
break;
}
cb->zadd--;
*dp++ = 0;
fcs = (fcs >> 8) ^ fcstab[fcs & 0xff];
mlen++;
}
}
if (mb != NULL)
mb->m_len = mlen;
cb->rxfcs = fcs;
cb->mtail = mb;
cb->rxcount = count;
cb->rxlchar = rxlchar;
}
5. Acknowledgments
This encapsulation method was first described in Stuart Cheshire's
Ph.D. Thesis at Stanford University.
6. References
[1] W. Simpson, "The Point-to-Point Protocol (PPP)", RFC 1661,
07/21/1994
[2] W. Simpson, "PPP in HDLC-like Framing", RFC 1662, 07/1994
[3] S. Cheshire and M. Baker, "Consistent Overhead Byte Stuffing,"
ACM SIGCOMM - Cannes, France, September 1997.
[4] J. Ziv and A. Lempel, "A Universal Algorithm for Sequential Data
Compression," IEEE Transactions on Information Theory, May 1977.
[5] D. A. Huffman, "A Method for the Construction of Minimum-
Redundancy Codes," Proceedings of the IRE, Vol.40, No.9, September
1952, pp.1098-1101.
7. Authors' Addresses
James Carlson
IronBridge Networks
5 Corporate Drive
Carlson expires May 1998 [Page 26]
INTERNET DRAFT Consistent Overhead Byte Stuffing November 1997
Andover MA 01810-2448
Phone: +1 978 691 4644
Fax: +1 978 691 6300
Email: carlson@wing.net
Stuart Cheshire
Stanford University
Stanford CA 94305
Phone: +1 650 723 9427
Email: cheshire@cs.stanford.edu
Mary Baker
Stanford University
Stanford CA 94305
Phone: +1 650 725 3711
Email: mgbaker@cs.stanford.edu
Carlson expires May 1998 [Page 27]
Html markup produced by rfcmarkup 1.119, available from
https://tools.ietf.org/tools/rfcmarkup/