Network Working Group Kevin Schneider Internet Draft ADTRAN, Inc. expires May 1995 PPP LZS-DCP Compression Protocol (LZS-DCP) draft-ietf-pppext-lzs-dcp-00.txt Status of this Memo This document is a submission to the Point-to-Point Protocol 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.'' Please check the 1id-abstracts.txt listing contained in the internet-drafts Shadow Directories on nic.ddn.mil, ds.internic.net, vernera.isi.edu, nic.nordu.net, or munnari.oz.au to learn the current status of any Internet Draft. Abstract The Point-to-Point Protocol (PPP) [1] provides a standard method for transporting multi-protocol datagrams over point-to-point links. The PPP Compression Control Protocol [2] provides a method to negotiate and utilize compression protocols over PPP encapsulated links. This document describes the use of the Stacker LZS data compression algorithm for compressing PPP encapsulated packets, using a DCP header [6]. To distinguish this protocol from the Standard PPP Stacker LZS compression protocol [5], it will be referred to as the LZS-DCP Compression Protocol. Schneider expires May 1995 [Page i] DRAFT LZS-DCP November 1994 1. Introduction Starting with a sliding window compression history, similar to LZ1 [3], Stac Electronics developed a compression algorithm identified as Stacker LZS. Motorola has proposed a packet format for a portable data compression protocol known as DCP [6]. This document specifies a technique for using both the Stacker-LZS algorithm and the DCP within the context of PPP. A TR30.1 ad hoc committee is currently working on a standard for data compression for DSUs. The ad hoc committee has decided to use PPP for this purpose, but along with a compression protocol that incorporates the compressor synchronization mechanism proposed in [6]. This document is a result of that effort. It defines a new compression protocol, LZS-DCP, to be used under CCP. This compression protocol defines a DCP compatible data format for the Stacker-LZS data compression algorithm. A notable difference between LZS-DCP and other non-DCP compression protocols is that LZS-DCP uses the Reset-Request and Reset-Ack bits in the DCP header instead of the CCP Reset-Request and Reset-Ack packets to keep the compressor and decompressor synchronized. The Stacker LZS-DCP compression algorithm supports both single compression history communication and multiple compression history communication. A single compression history will require the minimum amount of memory to implement, but may not provide as much compression as a multiple history implementation. Often, many streams of information are interleaved over the same link. Each virtual link will transmit data that is independent of other virtual links. Using multiple compression histories can improve the compression ratio of a communication link by associating separate compression histories with separate virtual links of communication. 1.1. Licensing Source and object licenses are available on a non-discriminatory basis. Hardware implementations are also available. Contact Stac Electronics for further information. 1.2. Specification of Requirements In this document, several words are used to signify the requirements Schneider expires May 1995 [Page 1] DRAFT LZS-DCP November 1994 of the specification. These words are often capitalized. MUST This word, or the adjective "required", means that the definition is an absolute requirement of the specification. MUST NOT This phrase means that the definition is an absolute prohibition of the specification. SHOULD This word, or the adjective "recommended", means that there may exist valid reasons in particular circumstances to ignore this item, but the full implications must be understood and carefully weighed before choosing a different course. MAY This word, or the adjective "optional", means that this item is one of an allowed set of alternatives. An implementation which does not include this option MUST be prepared to interoperate with another implementation which does include the option. 1.3. Terminology This document frequently uses the following terms: datagram The unit of transmission in the network layer (such as IP). A datagram may be encapsulated in one or more packets passed to the data link layer. frame The unit of transmission at the data link layer. A frame may include a header and/or a trailer, along with some number of units of data. packet The basic unit of encapsulation, which is passed across the interface between the network layer and the data link layer. A packet is usually mapped to a frame; the exceptions are when data link layer fragmentation is being performed, or when multiple packets are incorporated into a single frame. peer The other end of the point-to-point link. silently discard This means the implementation discards the packet without further processing. The implementation SHOULD provide the capability of logging the error, including the contents of the silently discarded packet, and SHOULD record the event Schneider expires May 1995 [Page 2] DRAFT LZS-DCP November 1994 in a statistics counter. 2. LZS-DCP Packets Before any LZS-DCP packets are communicated, PPP must reach the Network-Layer Protocol phase, and the CCP Control Protocol must reach the Opened state. Exactly one LZS-DCP datagram is encapsulated in the PPP Information field, where the PPP Protocol field indicates type hex 00FD (compressed datagram). The maximum length of the LZS-DCP datagram transmitted over a PPP link is the same as the maximum length of the Information field of a PPP encapsulated packet. Prior to compression, the uncompressed data begins with the PPP Protocol ID Field. Protocol-Field-Compression MAY be used on this value, if has been sucessfully negotiated for the link. The PPP Protocol ID Field is followed by the original Information field. The length of the uncompressed data field is limited only by the allowed size of the compressed data field and the higher protocol layers. PPP Link Control Protocol packets MUST NOT be sent within LZS-DCP packets. PPP Network Control Protocol packets MUST NOT be sent within LZS-DCP packets. Padding PPP padding is not allowed in a LZS-DCP packet. However, on compressed packets, padding may be accomplished by extending the data field with zeros following the (see Section 2.1.1). This is referred to as LZS Padding. The LCB, if present, is always the octet preceding the frame CRC. Reliability and Sequencing When no Compression History is kept, the algorithm does not depend on a reliable link, and does not require that packets be delivered in sequence. However, per packet compression results in a lower compression ratio than it could be on a stream. Some reasons for resetting the history on a per packet basis include: Schneider expires May 1995 [Page 3] DRAFT LZS-DCP November 1994 - The link has a high error rate. - The resources of the transmitter or receiver limit the ability to maintain a compression history between packets. When Compression Histories are negotiated, the packet sequence MUST be preserved within specific History Numbers. There is no sequence requirement between different History Numbers. To enable this feature, the implementation MUST rely on the Reset- Request and Reset-Ack bits of this protocol. These signalling bits apply to the history number of the packet containing them. This requires that the history number field be the same size in both directions of a link. Any data in the packet is processed after the signalling bits are processed. The transmitter MAY reset a Compression History at any time. Because the Stacker-LZS algorithm is a sliding window algorithm, the decompressor does not require an explicit notification of the reset event. The transmitter MUST reset a history after a Reset-Request for a given History Number. Data Expansion The maximum expansion of Stacker LZS-DCP is 12.5%. A Maximum Receive Unit (MRU) MAY be negotiated that is 12.5% larger than the size of a normal packet. Then, packets can always be sent compressed regardless of expansion. The transmitter MAY send an uncompressed LZS-DCP packet at any time, although the typical use of uncompressed LZS-DCP packets is as an anti-expansion mechanism. When the expansion plus compression header exceeds the size of the peer's MRU for the link, the data MUST be sent as an uncompressed LZS-DCP packet. An uncompressed LZS-DCP packet is transmitted according to the format shown in Section 2.1, with the C/U bit set to 0 (Uncompressed-Data). If the Configuration Option Field 'Process Mode', is set to a value of 1 (Process-Uncompressed), uncompressed LZS-DCP packets are processed by both the compressor and the decompressor, updating the histories of each. If the Process Mode Field is set to a value of 0 (None), AND the compressor has modified its history before sending the uncompressed packet, the Schneider expires May 1995 [Page 4] DRAFT LZS-DCP November 1994 compressor history must be reset. (Reset is not required if the compressor history can be restored to its previous state.) 2.1. Packet Format A summary of the LZS-DCP packet format 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | PPP Protocol | DCP-Header | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | (History Number) | (Seq Num) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Data ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | (LCB) | +-+-+-+-+-+-+-+-+ PPP Protocol The PPP Protocol field is described in the Point-to-Point Protocol Encapsulation [1]. When the LZS-DCP compression protocol is successfully negotiated by the PPP Compression Control Protocol [2], the value is 00FD hex. This value MAY be compressed when Protocol-Field- Compression is negotiated. DCP-Header The DCP-Header is nominally one octet in length, but may be extended through the use of the extension bit. The format of the DCP-Header is as follows: 0 1 2 3 4 5 6 7 +-----+-----+-----+-----+-----+-----+-----+-----+ | E | C/U | R-A | R-R | Res | Res | Res | C/D | +-----+-----+-----+-----+-----+-----+-----+-----+ E - Extension Bit The E bit is the extension bit. If set to 0, it indicates that another octet of the DCP-Header is present. Currently, this Schneider expires May 1995 [Page 5] DRAFT LZS-DCP November 1994 bit is always set to 1, since the DCP-Header field is only one octet long. C/U - Compressed/Uncompressed Bit The C/U indicates whether the data field contains compressed or uncompressed data. A value of 1 indicates compressed data (often referred to as a compressed packet), and a value of 0 indicates uncompressed data (or an uncompressed packet). R-A - Reset-Ack R-R - Reset-Request The DCP-Header includes Reset-Request and Reset-Ack Bits in order to provide a mechanism for indicating a decompression failure in one direction of a compressed link without affecting traffic in the other direction. A decompression failure MAY be determined using the sequence number and/or LCB mechanism. To indicate a decompression failure, an implementation MUST transmit a packet with the Reset-Request Bit set to 1. The Data field MAY be filled with data, compressed or uncompressed, or be left empty. Once a Reset-Request has been sent, the data in any compressed packets received is discarded until a packet containing a Reset-Ack is received. It is the responsibility of the receiver to ensure the reliability of the reset request-acknowledge mechanism. This may require the transmission of an additional Reset-Request before a Reset-Ack will be received. Upon reception of a packet containing a Reset-Request, the transmitting compressor MUST be reset to an initial state, which includes resetting or clearing the history buffer. If the data field of the packet containing the Reset-Request contains data, it is delivered to the local receiver as a normal data packet. In addition to the reset of the compressor, a packet MUST be transmitted with Reset-Ack bit set to 1. The data field of this packet MUST be filled with data. If no data is ready for transmission, the transmitter MUST wait until data is ready before sending the Reset-Ack. On receipt of a Reset-Ack, the receiving decompressor MAY be reset to an initial state. (A reset is not required since the incoming data packets will not reference the old history buffer). After reset, any compressed or uncompressed data contained in the packet is processed. Reset-Requests and Reset-Acks are specific to the history number of the packet containing them. Schneider expires May 1995 [Page 6] DRAFT LZS-DCP November 1994 Res - Reserved These bits are reserved and MUST be set to 0 C/D - Control/Data This bit is used by DCP to provide in-band negotiation in applications where out-of-band negotiation methods are not provided. Since CCP provides an out of band negotiating mechanism, this feature is not used in this application. All packets MUST set this bit to a value of 0, which signifies that the packet is a data packet. (Packets containing only Reset- Requests are classified as data packets.) History Number The number of the compression history which was used, ranging from 1 to the negotiated History Count. If the negotiated History Count is less than 2, this field is removed. If the negotiated History Count is 2 or more, but less than 256, this field is 1 octet. If 256 or more histories are negotiated, this field is 2 octets, most significant octet first. If multiple histories are used in one direction on a link, the history number field MUST be present on all packets in both directions, and sized according to the largest number of histories in either direction. If multiple histories are used, this field MUST be present in uncompressed as well as compressed packets. Sequence Number A one octet Sequence Number MAY be used, after successful negotiation of the Sequence Number option. The Sequence Number begins with one (1), and wraps to zero (0). This number is relative to the History Number used. On receipt, if Sequence Number one (1) follows any other number than zero (0), or is otherwise out of sequence, a Reset-Request is sent, in a packet containing the same History Number as that which detected a packet out of sequence. Future valid compressed packets are ignored, for that history only, until a packet containing a Reset-Ack is received. Schneider expires May 1995 [Page 7] DRAFT LZS-DCP November 1994 The Sequence Number is not reset by the transmitter when a packet containing a Reset-Ack is sent. The decompressor should resynchronize (reset) its local sequence number counter when a packet containing a Reset-Ack is received. Sequence numbers are used on all packets, compressed or uncompressed. Therefore, the receiver increments its counter upon receiving an LZS-DCP packet, whether it contains compressed or uncompressed data. Data This field contains uncompressed or compressed data, depending on the state of the C/U bit in the Header. This length of this field is always an integer number of octets. For compressed packets, the data field MUST begin with a complete codeword and end with the (see Section 2.1.1), which may be followed with additional octets containing only zeros. There MUST be only one per packet. To save on bandwidth, any trailing zero octets may be removed prior to transmission. A single trailing zero octet is appended upon receipt, after removal of any framing FCS and the LCB, if present. Longitudinal Check Byte A simple one octet Longitudinal Check Byte (LCB) MAY be used, after successful negotiation of the LCB option. The LCB MUST be initialized to FF(hex) at the beginning of each packet, and is the Exclusive-OR of each octet of the original uncompressed data. The LCB is only included on compressed packets, and is always located in the octet immediately prior to the frame CRC. On receipt, if the LCB is invalid, a Reset-Request is sent, in a packet containing the same History Number as that which was detected with the invalid LCB. Schneider expires May 1995 [Page 8] DRAFT LZS-DCP November 1994 2.1.1. Compressed Data The Stacker-LZS compression algorithm is Defined in ANSI X3.241 [7]. The format of the compressed data is repeated here for informational purposes. := [] := 0 | 1 := (8-bit byte) := := 1 | (7-bit offset) 0 (11-bit offset) := 110000000 := 1 | 0 := 00 = 2 1111 0110 = 14 01 = 3 1111 0111 = 15 10 = 4 1111 1000 = 16 1100 = 5 1111 1001 = 17 1101 = 6 1111 1010 = 18 1110 = 7 1111 1011 = 19 1111 0000 = 8 1111 1100 = 20 1111 0001 = 9 1111 1101 = 21 1111 0010 = 10 1111 1110 = 22 1111 0011 = 11 1111 1111 0000 = 23 1111 0100 = 12 1111 1111 0001 = 24 1111 0101 = 13 ... 3. Configuration Option Format The LZS-DCP Configuration Option negotiates the use of LZS-DCP on the link. By default or ultimate disagreement, no compression is used. This Configuration Option is used in CCP, and can be used in other negotiation mechanisms. The default values listed below were chosen by the TR30.1 ad hoc committee on compression of synchronous data. All implementations must support the default values. A summary of the LZS-DCP Configuration Option format is shown below. The fields are transmitted from left to right. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 Schneider expires May 1995 [Page 9] DRAFT LZS-DCP November 1994 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | History Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Check Mode | Process Mode | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 23 Length 6 History Count The History Count field is two octets, most significant octet first, and specifies the maximum number of Compression Histories. The value 0 indicates that the implementation expects the peer to reset the Compression History at the beginning of every packet. If this value is seleted, the transmitter MUST set the Reset-Ack bit of every packet that contains compressed data. The value 1 is the default value and is used to indicate that only one history is maintained. Other valid values range from 2 to 65535. The peer is not required to send as many histories as the implementation indicates that it can accept. Check Mode The Check Mode indicates support of LCB and/or Sequence checking. The use of check mode None (0) is discouraged for history counts greater than zero. 0 None 1 LCB 2 Sequence Number 3 Sequence Number + LCB (default) Process Mode The Process Mode specifies how uncompressed packets are handled. A value of None (0) indicates that uncompressed packets are not processed by the decompressor. A value of Process-Uncompressed Schneider expires May 1995 [Page 10] DRAFT LZS-DCP November 1994 (1) indicates that uncompressed packets are processed by the decompressor to update the history. 0 None (default) 1 Process-Uncompressed Security Considerations Security issues are not discussed in this memo. Acknowledgements This document is based on, and uses much of the text of [5]. References [1] Simpson, W., Editor, "The Point-to-Point Protocol (PPP)", STD 51, RFC 1661, Daydreamer, July 1994. [2] Rand, D., "The PPP Compression Control Protocol (CCP)", work in progress. [3] Lempel, A. and Ziv, J., "A Universal Algorithm for Sequential Data Compression", IEEE Transactions On Information Theory, Vol. IT-23, No. 3, May 1977. [4] Rand, D., "PPP Reliable Transmission", RFC 1663, Novell, July 1994. [5] Lutz, B., Simpson, B. "PPP Stacker LZS Compression Protocol", work in progress. [6] Motorola Information Systems Group, "Data Compression Protocol (DCP) Proposal", TR-30.1 ad hoc contribution (email reflector), September 21, 1994. [7] ANSI X3.241, "American National Standard Data Compression Method, Adaptive Coding with Sliding Window fo Information Interchange", currently unpublished. Schneider expires May 1995 [Page 11] DRAFT LZS-DCP November 1994 Chair's Address The working group can be contacted via the current chair: Fred Baker Senior Software Engineer Cisco Systems 519 Lado Drive Santa Barbara, California 93111 (805) 681-0115 EMail: fred@cisco.com Author's Address Questions about this memo can also be directed to: Kevin Schneider Adtran, Inc. 901 Explorer Blvd. Huntsville, AL 25806 (205) 971-8024 Email: kevin@adtran.com Schneider expires May 1995 [Page 12] DRAFT LZS-DCP November 1994 Table of Contents 1. Introduction .......................................... 1 1.1 Licensing ....................................... 1 1.2 Specification of Requirements ................... 1 1.3 Terminology ..................................... 2 2. LZS-DCP Packets ....................................... 3 2.1 Packet Format ................................... 5 2.1.1 Compressed Data ................................. 9 3. Configuration Option Format ........................... 9 SECURITY CONSIDERATIONS ...................................... 11 REFERENCES ................................................... 11 CHAIR'S ADDRESS ........................................... 12 AUTHOR'S ADDRESS ............................................. 12