[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                                      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 <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



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


   <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 & 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


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