Network Working Group Robert Lutz Internet Draft Stac Electronics W A Simpson Daydreamer expires in six months March 1995 PPP Stacker LZS Compression Protocol | draft-ietf-pppext-stacker-03.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, and 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 | ftp.is.co.za (Africa) nic.nordu.net (Europe) ds.internic.net (US East Coast) ftp.isi.edu (US West Coast) munnari.oz.au (Pacific Rim) Abstract The Point-to-Point Protocol (PPP) [1] provides a standard method for transporting multi-protocol datagrams over point-to-point links. Lutz & Simpson expires in six months [Page i] DRAFT Stacker LZS March 1995 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, with single or multiple compression histories, for compressing PPP encapsulated packets. Lutz & Simpson expires in six months [Page ii] DRAFT Stacker LZS March 1995 1. Introduction Starting with a sliding window compression history, similar to LZ1 [3], Stac Electronics developed a new, enhanced compression algorithm identified as Stacker LZS. The LZS algorithm is optimized to compress all file types as efficiently as possible. Even string matches as short as two octets are effectively compressed. The Stacker LZS 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 at the address and phone number listed with the author's address for further information. Lutz & Simpson expires in six months [Page 1] DRAFT Stacker LZS March 1995 2. LZS Packets Before any LZS packets may be communicated, PPP must reach the Network-Layer Protocol phase, and the Compression Control Protocol | must reach the Opened state. | Exactly one LZS datagram is encapsulated in the PPP Information field, where the PPP Protocol field indicates type hex 4021 (Stacker | LZS). | When LZS is negotiated as the primary compression algorithm, the PPP | Protocol field indicates type hex 00FB (link compressed datagram), or type hex 00FD (compressed datagram). The maximum length of the LZS 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 number. This value MUST be compressed, in the same fashion as when Protocol-Field-Compression is negotiated. The PPP Protocol number is followed by the original Information field. The length of the Information field before compression MUST NOT exceed the link Maximum Receive Unit (MRU). PPP Link Control Protocol packets MUST NOT be sent within compressed data. Padding The LZS Information field alway ends with the , which is used to disambiguate padding. This allows trailing bits as well as octets to be considered padding. 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: - The link has a high error rate. - The resources of the transmitter or receiver limit the ability Lutz & Simpson expires in six months [Page 2] DRAFT Stacker LZS March 1995 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 MAY rely on the Reset- Request and Reset-Ack messages of the Compression Control Protocol. The Data field of the CCP Reset-Request and Reset-Reply contains the two octet History Number to be reset, most significant octet first. Alternatively, the implementation MAY utilize a reliable link, as described in "PPP Reliable Transmission" [4]. The transmitter MAY reset a Compression History at any time. The receiver is implicitly notified of this event, and the decompression history will automatically be affected. The transmitter MUST reset a history after a CCP Reset-Request for a given History Number. Data Expansion The maximum expansion of Stacker LZS 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. When the expansion plus compression header exceeds the size of the peer's MRU for the link, the PPP packet MUST be sent without compression, in the original PPP packet form. If history checkpointing is not used, the transmitter resets the altered history. If it is detected that most packets are expanding (probably due to the use of already compressed data), then the transmitter SHOULD stop sending compressed packets, and reset its history on its next compressed data packet. Lutz & Simpson expires in six months [Page 3] DRAFT Stacker LZS March 1995 2.1. Packet Format A summary of the Stacker LZS packet 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | PPP Protocol | (History Number) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | (Check Value) | Compressed Data ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ PPP Protocol The PPP Protocol field is described in the Point-to-Point Protocol Encapsulation [1]. When the Stacker LZS 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. History Number The number of the compression history which was used, ranging from 2 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. Check Value By default, no check is added to the packet. 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. A two octet Cyclic Redundancy Check (CRC) MAY be used, instead of the LCB, after successful negotiation of the CRC option. The CRC MUST be initialized to FFFF(hex) at the beginning of each packet, and is based on the HDLC FCS-16 polynomial: Lutz & Simpson expires in six months [Page 4] DRAFT Stacker LZS March 1995 x^16 + x^12 + x^5 + 1 The ones compliment of the CRC is transmitted least significant octet first, which contains the coefficient of the highest term. A one octet Sequence Number MAY be used, instead of a LCB or CRC, 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, or the LCB or CRC is invalid, a CCP Reset-Request is sent, containing the full two octet History Number (which is one (1) when no History Number is present). Future valid compressed packets are ignored, for that history only, until a CCP Reset-Ack packet is received. The Sequence Number is not reset by the transmitter when the Reset-Ack is sent. Therefore, each new received detection of an out of sequence packet MUST increment the Identifier of the CCP Reset-Request. The receiver MUST continue ignoring valid compressed packets for a particular history, until the correct Reset-Ack Identifier for that History Number is received. Compressed Data The compressed PPP encapsulated packet. When the sender does not add Padding [1], any trailing zero octets are removed prior to transmission. A single trailing zero octet is appended upon receipt, after removal of any framing FCS. Lutz & Simpson expires in six months [Page 5] DRAFT Stacker LZS March 1995 2.2. Compressed Data := [] := 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 ... Lutz & Simpson expires in six months [Page 6] DRAFT Stacker LZS March 1995 3. Configuration Option Format Description The CCP Stacker-LZS Configuration Option negotiates the use of Stacker LZS on the link. By default or ultimate disagreement, no compression is used. A summary of the Stacker-LZS 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Length | History Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Check Mode | +-+-+-+-+-+-+-+-+ Type 17 Length 5 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. The value 1 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. Lutz & Simpson expires in six months [Page 7] DRAFT Stacker LZS March 1995 Check Mode The Check Mode indicates support of LCB, CRC or Sequence checking. 0 None (default) 1 LCB 2 CRC 3 Sequence Number Security Considerations Security issues are not discussed in this memo. 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. Lutz & Simpson expires in six months [Page 8] DRAFT Stacker LZS March 1995 Chair's Address The working group can be contacted via the current chair: Fred Baker Cisco Systems | 519 Lado Drive | Santa Barbara, California 93111 | EMail: fred@cisco.com | Author's Address Questions about this memo can also be directed to: Robert Lutz Stac Electronics 5993 Avenida Encinas Carlsbad, CA 92008 (619)431-7474 Email: stac/stac/bobl%stac_electronics@mcimail.com William Allen Simpson Daydreamer Computer Systems Consulting Services 1384 Fontaine Madison Heights, Michigan 48071 Bill.Simpson@um.cc.umich.edu bsimpson@MorningStar.com Lutz & Simpson expires in six months [Page 9] DRAFT Stacker LZS March 1995 Table of Contents 1. Introduction .......................................... 1 1.1 Licensing ....................................... 1 2. LZS Packets ........................................... 2 2.1 Packet Format ................................... 4 2.2 Compressed Data ................................. 6 3. Configuration Option Format ........................... 7 SECURITY CONSIDERATIONS ...................................... 8 REFERENCES ................................................... 8 CHAIR'S ADDRESS .............................................. 9 AUTHOR'S ADDRESS ............................................. 9