HTTP/1.1 200 OK Date: Tue, 09 Apr 2002 06:45:49 GMT Server: Apache/1.3.20 (Unix) Last-Modified: Thu, 23 Nov 1995 23:00:00 GMT ETag: "304e54-47b5-30b4fcf0" Accept-Ranges: bytes Content-Length: 18357 Connection: close Content-Type: text/plain Network Working Group Robert Lutz Internet Draft Stac Electronics W A Simpson DayDreamer expires in six months November 1995 PPP Stacker LZS Compression Protocol draft-ietf-pppext-stacker-04.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) Lutz & Simpson expires in six months [Page i] DRAFT Stacker LZS November 1995 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 & Simpson expires in six months [Page ii] DRAFT Stacker LZS November 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 November 1995 2. LZS Packets | Before any LZS packets may be communicated, PPP must reach the | Network-Layer Protocol phase. When the Compression Control Protocol (CCP) has reached the Opened | state, and 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). When CCP has not successfully reached the Opened state, or LZS is not | the primary compression algorithm, exactly one LZS datagram is | encapsulated in the PPP Information field, where the PPP Protocol field indicates type hex 4021 (Stacker LZS). Note that in the latter case, use of LZS is terminated by the PPP | LCP Protocol-Reject. The default format is used: a single history | with no History Number field and no Check Value field. | 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 Lutz & Simpson expires in six months [Page 2] DRAFT Stacker LZS November 1995 include: - 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 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. 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 the appropriate | history. Lutz & Simpson expires in six months [Page 3] DRAFT Stacker LZS November 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. There is no need for the field when no history is kept, | or only a single history is kept. | 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 (the field is not | present). 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 Lutz & Simpson expires in six months [Page 4] DRAFT Stacker LZS November 1995 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: x**16 + x**12 + x**5 + 1 | The ones complement 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). Upon receipt of the Reset-Request, the affected history is reset | by the transmitter, and a Reset-Ack is sent. However, the | Sequence Number is not reset. 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 CCP 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 November 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 November 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. Every implementation MUST support at least one | history. 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 November 1995 Check Mode The Check Mode indicates support of LCB, CRC or Sequence checking. | The values supported may be XOR'd, and an appropriate single value | indicated by Configure-Nak. 0 None (default) 1 LCB 2 CRC 4 Sequence Number (recommended) | Some early implementations indicate Sequence Number support by a | value of 3 (LCB and CRC), due to a typographical error in early | drafts. This use is deprecated, but SHOULD be accepted by later | implementations when a Configure-Ack or Configure-Nak contains | this illegal value. 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 November 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 (prefered) | Lutz & Simpson expires in six months [Page 9] DRAFT Stacker LZS November 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