[Docs] [txt|pdf] [Tracker] [WG] [Email] [Diff1] [Diff2] [Nits] [IPR]

Versions: 02 03 04 05 06 07 08 09 10 RFC 1974

Network Working Group                                        Robert Lutz
Internet Draft                                          Stac Electronics
                                                             W A Simpson
                                                              Daydreamer
expires in six months                                     September 1994


                  PPP Stacker LZS Compression Protocol                    |
                    draft-ietf-pppext-stacker-02.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 ds.internic.net (US East Coast), nic.nordu.net          |
   (Europe), ftp.isi.edu (US West Coast), or 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.

   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



Lutz                     expires in six months                  [Page i]

DRAFT                         Stacker LZS                 September 1994


   algorithm, with single or multiple compression histories, for
   compressing PPP encapsulated packets.

















































Lutz                     expires in six months                 [Page ii]

DRAFT                         Stacker LZS                 September 1994


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                     expires in six months                  [Page 1]

DRAFT                         Stacker LZS                 September 1994


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 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 <End Marker>, 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
         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



Lutz                     expires in six months                  [Page 2]

DRAFT                         Stacker LZS                 September 1994


      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                     expires in six months                  [Page 3]

DRAFT                         Stacker LZS                 September 1994


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                     expires in six months                  [Page 4]

DRAFT                         Stacker LZS                 September 1994


         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                     expires in six months                  [Page 5]

DRAFT                         Stacker LZS                 September 1994


2.2.  Compressed Data                                                     |


   <Compressed Stream> := [<Compressed String>] <End Marker>
   <Compressed String> := 0 <Raw Byte> | 1 <Compressed Bytes>

   <Raw Byte> := <b><b><b><b><b><b><b><b>          (8-bit byte)
   <Compressed Bytes> := <Offset> <Length>

   <Offset> := 1 <b><b><b><b><b><b><b> |           (7-bit offset)
               0 <b><b><b><b><b><b><b><b><b><b><b> (11-bit offset)
   <End Marker> := 110000000
   <b> := 1 | 0

   <Length> :=
   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                     expires in six months                  [Page 6]

DRAFT                         Stacker LZS                 September 1994


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                     expires in six months                  [Page 7]

DRAFT                         Stacker LZS                 September 1994


   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                     expires in six months                  [Page 8]

DRAFT                         Stacker LZS                 September 1994


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

      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                     expires in six months                  [Page 9]
DRAFT                         Stacker LZS                 September 1994


                           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


Html markup produced by rfcmarkup 1.108, available from http://tools.ietf.org/tools/rfcmarkup/