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) 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]