Network Working Group Robert Lutz Internet Draft Stac Electronics expires in six months October 1993 PPP Stacker LZS Compression Protocol draft-ietf-pppext-stacker-00.txt Status of this Memo This document is the product of the Point-to-Point Protocol Working Group of the Internet Engineering Task Force (IETF). Comments should be submitted to the ietf-ppp@ucdavis.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, nnsc.nsf.net, nic.nordu.net, ftp.nisc.sri.com, 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, with single or multiple compression histories, for compressing PPP encapsulated packets. Lutz expires in six months [Page i] DRAFT Stacker LZS October 1993 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 bytes 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. Using multiple compression histories can improve the compression ratio of a communication link by associating separate compression histories with separate virtual links of communication. In general, each virtual link will transmit data that is independent of other virtual links. 1.1. Licensing Source and object licenses are available on a non-discriminatory basis for either a royalty or fixed price arrangement. Hardware implementations are also available. Patent indemnity is included with the license. Lutz expires in six months [Page 1] DRAFT Stacker LZS October 1993 2. LZS Packets Before any LZS packets may be communicated, PPP must reach the Network-Layer Protocol phase, and the CCP 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 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 MAY be compressed when Protocol-Field- Compression is negotiated. PPP Link Control Protocol packets MUST NOT be sent within compressed data. Padding The LZS Information field contains an integral length field, which is used to disambiguate padding. When expansion has resulted in the number of octets specified in the length, the remainder of the packet is considered padding. This allows trailing bits as well as octets to be considered padding. Reliability and Sequencing By default, the Compression History will be reset for each LZS packet. In this case, the algorithm does not depend on a reliable link and does not require that packets be delivered in sequence. Optionally, each Compression History may be reset at the discretion of the transmitter. Use of this feature requires a reliable link, as described in "PPP Reliable Transmission" [4], and expects the packets to be delivered in sequence. When a transmitter resets a Compression History, no other indication needs to be sent to the receiver, other than that provided within the compressed information. Data Expansion The maximum expansion of Stacker LZS is 12.5%. Lutz expires in six months [Page 2] DRAFT Stacker LZS October 1993 When the expansion exceeds the size of the peer's Maximum Receive Unit for the link, the expanded packet is sent in multiple PPP frames. When such frames are delivered out of sequence, the parity check in each frame will detect the failure. When expansion is detected, the PPP packet MAY be sent without compression. Any following LZS packet will indicate a reset of its Compression History. 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Uncompressed Length | Compressed Data ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LCB / CRC | +-+-+-+-+-+-+-+-+- - - - - - - -+ 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 should be used. This field is only present when the negotiated History Count is greater than one. If the negotiated History Count is one, this field is removed, a reduction of 2 octets. Uncompressed Length The number of octets which were in the original PPP encapsulated Lutz expires in six months [Page 3] DRAFT Stacker LZS October 1993 packet, prior to compression. Compressed Data The compressed PPP encapsulated packet. LCB or CRC By default, a simple Longitudinal Check Byte (LCB) will be appended to each packet. The LCB MUST be initialized to FF(hex) at the beginning of each packet. The LCB is one octet, and is the Exclusive-OR of each octet of the original, uncompressed data. If the CRC option is successfully negotiated, a CRC will be appended to each packet in place of the LCB. The CRC MUST be initialized to FFFF(hex) at the beginning of each packet. The CRC is two octets, and is based on the following polynomial: x^16 + x^12 + x^5 + 1 Lutz expires in six months [Page 4] DRAFT Stacker LZS October 1993 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 | Reset Mode | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type (5) Length 6 History Count The History Count field is two octets, and specifies the maximum number of Compression Histories. Valid values range from 1 to 65768. Check Mode The Check Mode indicates support of LCB or CRC checking. All implementations MUST support LCB parity. 1 LCB 2 CRC Reset Mode The Reset Mode indicates support for maintaining a Compression History for more than a single packet. All implementations MUST Lutz expires in six months [Page 5] DRAFT Stacker LZS October 1993 support the Single Packet mode. 1 Single Packet 2 Multiple Packets Lutz expires in six months [Page 6] DRAFT Stacker LZS October 1993 Security Considerations Security issues are not discussed in this memo. References [1] Simpson, W.A., "The Point-to-Point Protocol (PPP)", work in progress. [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", work in progress. Acknowledgments Editting and formatting by Bill Simpson. Lutz expires in six months [Page 7] DRAFT Stacker LZS October 1993 Chair's Address The working group can be contacted via the current chair: Fred Baker Advanced Computer Communications 315 Bollay Drive Santa Barbara, California 93117 EMail: fbaker@acc.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 Lutz expires in six months [Page 8] DRAFT Stacker LZS October 1993 Table of Contents 1. Introduction .......................................... 1 1.1 Licensing ....................................... 1 2. LZS Packets ........................................... 2 2.1 Packet Format ................................... 3 3. Configuration Option Format ........................... 5 SECURITY CONSIDERATIONS ...................................... 7 REFERENCES ................................................... 7 ACKNOWLEDGEMENTS ............................................. 7 CHAIR'S ADDRESS .............................................. 8 AUTHOR'S ADDRESS ............................................. 8 Bill.Simpson@um.cc.umich.edu