home *** CD-ROM | disk | FTP | other *** search
/ Unix System Administration Handbook 1997 October / usah_oct97.iso / rfc / 1900s / rfc1967.txt < prev    next >
Text File  |  1996-08-08  |  40KB  |  1,012 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7. Network Working Group                                       K. Schneider
  8. Request for Comments: 1967                                  ADTRAN, Inc.
  9. Category: Informational                                        R. Friend
  10.                                                          Stac Technology
  11.                                                              August 1996
  12.  
  13.  
  14.                PPP LZS-DCP Compression Protocol (LZS-DCP)
  15.  
  16. Status of This Memo
  17.  
  18.    This memo provides information for the Internet community.  This memo
  19.    does not specify an Internet standard of any kind.  Distribution of
  20.    this memo is unlimited.
  21.  
  22. Abstract
  23.  
  24.    The Point-to-Point Protocol (PPP) [1] provides a standard method for
  25.    transporting multi-protocol datagrams over point-to-point links.
  26.  
  27.    The PPP Compression Control Protocol [2] provides a method to
  28.    negotiate and utilize compression protocols over PPP encapsulated
  29.    links.
  30.  
  31.    This document describes the use of the Stac LZS data compression
  32.    algorithm for compressing PPP encapsulated packets, using a DCP
  33.    header [6].  This protocol is an enhanced version of the non-DCP
  34.    (Option 17) PPP Stac LZS compression protocol [5], and will be
  35.    referred to as the LZS-DCP Compression Protocol.
  36.  
  37. Table of Contents
  38.  
  39.      1.     Introduction ..........................................    2
  40.         1.1       Licensing .......................................    3
  41.         1.2       Specification of Requirements ...................    3
  42.         1.3       Terminology .....................................    3
  43.      2.     LZS-DCP Packets .......................................    4
  44.         2.1       Example LZS-DCP Packets .........................    5
  45.         2.2       Padding .........................................    6
  46.         2.3       Reliabliity and Squencing .......................    6
  47.         2.4       Data Expansion ..................................    6
  48.         2.5       Packet Format ...................................    7
  49.            2.5.1  PPP Protocol ....................................    7
  50.            2.5.2  DCP-Header ......................................    8
  51.            2.5.3  History Number ..................................    9
  52.            2.5.4  Sequence Number .................................    9
  53.            2.5.5  Data ............................................   10
  54.            2.5.6  Longitudinal Check Byte .........................   10
  55.  
  56.  
  57.  
  58. Schneider & Friend           Informational                      [Page 1]
  59.  
  60. RFC 1967                        LZS-DCP                      August 1996
  61.  
  62.  
  63.            2.5.7  Compressed Data .................................   11
  64.      3.     Sending Compressed Datagrams     .....................    11
  65.         3.1       Transmitter Process .............................   11
  66.         3.2       Receiver Process ................................   12
  67.         3.3       History Maintenance .............................   13
  68.         3.4       Anti-Expansion Mechanism ........................   14
  69.         3.5       History Resynchronization Mechanism .............   14
  70.      4.     Configuration Option Format ...........................   15
  71.      SECURITY CONSIDERATIONS ......................................   16
  72.      REFERENCES ...................................................   17
  73.      CHAIR'S ADDRESS ..............................................   17
  74.      AUTHORS' ADDRESSES ...........................................   18
  75.  
  76. 1.  Introduction
  77.  
  78.    Starting with a sliding window compression history, similar to LZ1
  79.    [3], Stac Electronics developed a compression algorithm identified as
  80.    Stac LZS.  A PPP Compression Protocol for this compression algorithm
  81.    was developed and published [5].  That protocol was taken as a basis
  82.    for data compression work done in TIA for DSU/CSUs.  As a part of
  83.    that standardization process, the concept of a portable Data
  84.    Compression Protocol (DCP) was introduced [6].  The resulting
  85.    (pending) TIA/EIA-655 standard uses this LZS-DCP protocol, which
  86.    ncorporates DCP into a PPP compression protocol for Stac LZS.  A very
  87.    similar protocol is currently out for ballot in the Frame Relay
  88.    Forum.  (It is identical except for the size of the history number
  89.    field.)
  90.  
  91.    This publication of the LZS-DCP compression protocol is in the
  92.    interest of providing a common compression protocol for Stac-LZS, and
  93.    to provide features that are not available with the LZS compression
  94.    protocol [5].  Some of the differences between the LZS-DCP and LZS
  95.    (compression type 17) protocols are as follows:
  96.  
  97.         1) LZS-DCP provides an option which allows packets containing
  98.            uncompressible data to be transferred without requiring the
  99.            compression history to be cleared, potentially allowing a
  100.            higher compression ratio.  A bit is included in the DCP
  101.            header to indicate whether the packet contains compressed or
  102.            uncompressed data.
  103.  
  104.         2) LZS-DCP uses reset request and acknowledgment bits in the DCP
  105.            header that is included on each packet rather than using
  106.            CCP's reset request and acknowledge packets, which may result
  107.            in fewer discarded data packets during the REQ/ACK handshake.
  108.  
  109.         3) LZS-DCP allows simultaneous use of both sequence numbers and
  110.            the LCB for compression error detection.
  111.  
  112.  
  113.  
  114. Schneider & Friend           Informational                      [Page 2]
  115.  
  116. RFC 1967                        LZS-DCP                      August 1996
  117.  
  118.  
  119.    The Stac LZS compression algorithm supports both single and multiple
  120.    compression histories.  A single compression history will require the
  121.    minimum amount of memory to implement, but may not provide as much
  122.    compression as a multiple history implementation.
  123.  
  124.    Often, many streams of information are interleaved over the same
  125.    physical link.  Each virtual connection will transmit data that is
  126.    independent of other virtual connections.  Using multiple compression
  127.    histories can improve the compression ratio of a communication link
  128.    by associating separate compression histories with separate virtual
  129.    links of communication.
  130.  
  131. 1.1.  Licensing
  132.  
  133.    Source and object licenses are available on a non-discriminatory
  134.    basis.  Hardware implementations are also available.  Contact Stac
  135.    Electronics (hardware.sales@stac.com) for further information.
  136.  
  137. 1.2.  Specification of Requirements
  138.  
  139.    In this document, several words are used to signify the requirements
  140.    of the specification.  These words are often capitalized.
  141.  
  142.    MUST      This word, or the adjective "required", means that the
  143.              definition is an absolute requirement of the specification.
  144.  
  145.    MUST NOT  This phrase means that the definition is an absolute
  146.              prohibition of the specification.
  147.  
  148.    SHOULD    This word, or the adjective "recommended", means that there
  149.              may exist valid reasons in particular circumstances to
  150.              ignore this item, but the full implications MUST be
  151.              understood and carefully weighed before choosing a
  152.              different course.
  153.  
  154.    MAY       This word, or the adjective "optional", means that this
  155.              item is one of an allowed set of alternatives.  An
  156.              implementation which does not include this option MUST be
  157.              prepared to interoperate with another implementation which
  158.              does include the option.
  159.  
  160. 1.3.  Terminology
  161.  
  162.    This document frequently uses the following terms:
  163.  
  164.    datagram  The unit of transmission in the network layer (such as IP).
  165.              A datagram may be encapsulated in one or more packets
  166.              passed to the data link layer.
  167.  
  168.  
  169.  
  170. Schneider & Friend           Informational                      [Page 3]
  171.  
  172. RFC 1967                        LZS-DCP                      August 1996
  173.  
  174.  
  175.    frame     The unit of transmission at the data link layer.  A frame
  176.              may include a header and/or a trailer, along with some
  177.              number of units of data.
  178.  
  179.    packet    The basic unit of encapsulation, which is passed across the
  180.              interface between the network layer and the data link
  181.              layer.  A packet is usually mapped to a frame; the
  182.              exceptions are when data link layer fragmentation is being
  183.              performed, or when multiple packets are incorporated into a
  184.              single frame.
  185.  
  186.    peer      The other end of the point-to-point link.
  187.  
  188.    silently discard
  189.  
  190.              This means the implementation discards the packet without
  191.              further processing.  The implementation SHOULD provide the
  192.              capability of logging the error, including the contents of
  193.              the silently discarded packet, and SHOULD record the event
  194.              in a statistics counter.
  195.  
  196. 2.  LZS-DCP Packets
  197.  
  198.    Before any LZS-DCP packets are communicated, PPP MUST reach the
  199.    Network-Layer Protocol phase, and the CCP Control Protocol MUST reach
  200.    the Opened state.
  201.  
  202.    Exactly one LZS-DCP datagram is encapsulated in the PPP Information
  203.    field, where the PPP Protocol field indicates type hex 00FD
  204.    (compressed datagram) or type hex 00FB (Individual link compressed
  205.    datagram).  Type hex 00FD is used when compression is negotiated over
  206.    a single physical link or when compression is negotiated over a
  207.    single bundle consisting of multiple physical links.  Type hex 00FB
  208.    is used when compression is negotiated separately over individual
  209.    physical links to the same destination.  For more information, please
  210.    refer to PPP Compression Control Protocol.
  211.  
  212.    The maximum length of the LZS-DCP datagram transmitted over a PPP
  213.    link is the same as the maximum length of the Information field of a
  214.    PPP encapsulated packet.
  215.  
  216.    Prior to compression, the uncompressed data begins with the PPP
  217.    Protocol ID Field.  Protocol-Field-Compression MAY be used on this
  218.    value, if has been successfully negotiated for the link.
  219.  
  220.    The PPP Protocol ID Field is followed by the original Information
  221.    field. The length of the uncompressed data field is limited only by
  222.    the allowed size of the compressed data field and the higher protocol
  223.  
  224.  
  225.  
  226. Schneider & Friend           Informational                      [Page 4]
  227.  
  228. RFC 1967                        LZS-DCP                      August 1996
  229.  
  230.  
  231.    layers.
  232.  
  233.    PPP Link Control Protocol packets MUST NOT be sent within LZS-DCP
  234.    packets.  PPP Network Control Protocol packets MUST NOT be sent
  235.    within LZS-DCP packets.
  236.  
  237. 2.1.  Example LZS-DCP packets (shown using PPP in HDLC-like framing,
  238.       using Address-and-Control-Field-Compression and Protocol-Field-
  239.       Compression. - RFC 1662 )
  240.  
  241.    Compressed Packet:
  242.  
  243.         PPP |                                        | PPP
  244.         PID | HDR   SEQ           DATA           LCB | FCS
  245.       +-----+-----+-----+---................---+-----+-----+
  246.       | F D | C 0 | n n |   Compressed Data    | y y | z z |
  247.       +-----+-----+-----+---................---+-----+-----+
  248.                         /                      \
  249.                        /      Compression       \
  250.                       /      Transformation      \
  251.                      /                            \
  252.                     /PPP                           \
  253.                    / PID   PPP Information Field    \
  254.                   +-----+----....................----+
  255.                   | x x | upper layer protocol data  |
  256.                   +-----+----....................----+
  257.  
  258.  
  259.    Uncompressed Packet
  260.  
  261.         PPP |                                  | PPP
  262.         PID | HDR   SEQ           DATA         | FCS
  263.       +-----+-----+-----+---................---+-----+
  264.       | F D | 8 0 | n n |   Un-compressed Data | z z |
  265.       +-----+-----+-----+---................---+-----+
  266.                         /                      \
  267.                        /                        \
  268.                       /                          \
  269.                      /                            \
  270.                     /PPP                           \
  271.                    / PID   PPP Information Field    \
  272.                   +-----+----....................----+
  273.                   | x x | upper layer protocol data  |
  274.                   +-----+----....................----+
  275.  
  276.       where:  C0 and 80 are representative LZS-DCP headers; nn, xx, yy,
  277.               and zz are values determined by the packet's context.
  278.  
  279.  
  280.  
  281.  
  282. Schneider & Friend           Informational                      [Page 5]
  283.  
  284. RFC 1967                        LZS-DCP                      August 1996
  285.  
  286.  
  287. 2.2.  Padding
  288.  
  289.       PPP padding is not allowed in a LZS-DCP packet.  However, on
  290.       compressed packets, padding may be accomplished by extending the
  291.       data field with zeros following the last compressed data octet
  292.       (see Section 2.1.1).  This is referred to as LZS Padding.  The
  293.       LCB, if present, MUST be the octet preceding the frame CRC.
  294.  
  295. 2.3.  Reliability and Sequencing
  296.  
  297.       When no Compression History is kept, the algorithm does not depend
  298.       on a reliable link, and does not require that packets be delivered
  299.       in sequence.  However, per packet compression results in a lower
  300.       compression ratio than it could be on a stream.
  301.  
  302.       Some reasons for clearing the history on a per packet basis
  303.       include:
  304.  
  305.       -  The link has a high error rate.
  306.       -  The resources of the transmitter or receiver limit the ability
  307.          to maintain a compression history between packets.
  308.  
  309.       When one or more compression Histories are negotiated, the packet
  310.       sequence MUST be preserved within specific History Numbers.  There
  311.       is no sequence requirement between different History Numbers.
  312.  
  313.       When using one or more compression histories, the implementation
  314.       MUST rely on either a lower layer reliable link protocol (RFC
  315.       1663), use a technique to keep the compressor and decompressor
  316.       histories in synchronization, or both.  The LZS-DCP protocol
  317.       provides the Request-Req and Request-Ack bits in the DCP header
  318.       for this purpose.  Since this synchronization is done on a per
  319.       history basis, the history number fields are required to be the
  320.       same size in both directions of the link.  Any data contained in
  321.       the packet is processed after the signaling bits are processed.
  322.  
  323.       The transmitter MAY clear a Compression History at any time.
  324.  
  325.       The transmitter MUST clear a history after a receiving a Reset-
  326.       Request for a given History Number.
  327.  
  328. 2.4.  Data Expansion
  329.  
  330.       The maximum expansion of Stac LZS is 12.5%.
  331.  
  332.       A Maximum Receive Unit (MRU) MAY be negotiated that is 12.5%
  333.       larger than the size of a normal packet.  Then, packets can always
  334.       be sent compressed regardless of expansion.
  335.  
  336.  
  337.  
  338. Schneider & Friend           Informational                      [Page 6]
  339.  
  340. RFC 1967                        LZS-DCP                      August 1996
  341.  
  342.  
  343.       The transmitter MAY send an uncompressed LZS-DCP packet at any
  344.       time, although the typical use of uncompressed LZS-DCP packets is
  345.       as an anti-expansion mechanism.
  346.  
  347.       When the expansion plus compression header exceeds the size of the
  348.       peer's MRU for the link, the data MUST be sent as an uncompressed
  349.       LZS-DCP packet.
  350.  
  351.       An uncompressed LZS-DCP packet is transmitted according to the
  352.       format shown in Section 2.1, with the C/U bit set to 0
  353.       (Uncompressed-Data).  If the Configuration Option Field 'Process
  354.       Mode', is set to a value of 1 (Process-Uncompressed), uncompressed
  355.       LZS-DCP packets are processed by both the compressor and the
  356.       decompressor, updating the histories of each. If the Process Mode
  357.       Field is set to a value of 0 (None), and the compressor has
  358.       modified its history before sending the uncompressed packet, the
  359.       compressor history MUST be clear.
  360.  
  361. 2.5.  Packet Format
  362.  
  363.    A summary of the LZS-DCP packet format is shown below.  The fields
  364.    are transmitted from left to right.
  365.  
  366.     0                   1                   2
  367.     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3
  368.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  369.    |          PPP Protocol         |   DCP-Header  |
  370.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  371.    |       (History Number)        |  (Seq Num)    |
  372.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  373.    |         Data ...
  374.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  375.    |     (LCB)     |
  376.    +-+-+-+-+-+-+-+-+
  377.  
  378. 2.5.1.  PPP Protocol
  379.  
  380.       The PPP Protocol field is described in the Point-to-Point Protocol
  381.       Encapsulation [1].
  382.  
  383.       When the LZS-DCP compression protocol is successfully negotiated
  384.       by the PPP Compression Control Protocol [2], the value is 00FD or
  385.       00FB hex.  This value MAY be compressed when Protocol-Field-
  386.       Compression is negotiated.
  387.  
  388.  
  389.  
  390.  
  391.  
  392.  
  393.  
  394. Schneider & Friend           Informational                      [Page 7]
  395.  
  396. RFC 1967                        LZS-DCP                      August 1996
  397.  
  398.  
  399. 2.5.2.  DCP-Header
  400.  
  401.       The DCP-Header is nominally one octet in length, but may be
  402.       extended through the use of the extension bit.
  403.  
  404.       The format of the DCP-Header is as follows:
  405.  
  406.          0     1     2     3     4     5     6     7
  407.       +-----+-----+-----+-----+-----+-----+-----+-----+
  408.       |  E  | C/U | R-A | R-R | Res | Res | Res | C/D |
  409.       +-----+-----+-----+-----+-----+-----+-----+-----+
  410.  
  411.       E - Extension Bit
  412.  
  413.          The E bit is the extension bit.  If set to 0, it indicates that
  414.          another octet of the DCP-Header is present.  Currently, this
  415.          bit is always set to 1, since the DCP-Header field is only one
  416.          octet long.
  417.  
  418.       C/U - Compressed/Uncompressed Bit
  419.  
  420.          The C/U indicates whether the data field contains compressed or
  421.          uncompressed data.  A value of 1 indicates compressed data
  422.          (often referred to as a compressed packet), and a value of 0
  423.          indicates uncompressed data (or an uncompressed packet).
  424.  
  425.       R-A - Reset-Ack
  426.  
  427.          The R-A bit is used to inform the decompressing peer that
  428.          the history buffer specified by the history number in the
  429.          packet was in the cleared state just before the data contained
  430.          in the packet was processed by the compression transformation
  431.          (see section 3., Sending Compressed Datagrams).  This bit MUST
  432.          be set to a value of "1" to indicate a Reset-Ack, and to
  433.          acknowledge a receive failure (R-R) (see section 3., Sending
  434.          Compressed Datagrams).  This bit is specific to the history
  435.          number of the packet containing it.
  436.  
  437.       R-R - Reset-Request
  438.  
  439.          The R-R bit is used to request that the compressing peer
  440.          clear the history buffer specified by the history number in the
  441.          packet.  This bit MUST be set to a value of "1" to indicate a
  442.          Reset-Request, and to respond to a receive failure (R-R) (see
  443.          section 3., Sending Compressed Datagrams).  This bit is
  444.          specific to the history number of the packet containing it.
  445.  
  446.  
  447.  
  448.  
  449.  
  450. Schneider & Friend           Informational                      [Page 8]
  451.  
  452. RFC 1967                        LZS-DCP                      August 1996
  453.  
  454.  
  455.       Res - Reserved
  456.  
  457.          These bits are reserved and MUST be set to 0
  458.  
  459.       C/D - Control/Data
  460.  
  461.          This bit is used by DCP to provide in-band negotiation in
  462.          applications where out-of-band negotiation methods are not
  463.          provided (i.e. Frame Relay).  Since CCP provides an out of band
  464.          negotiating mechanism, this feature is not used in this
  465.          application.  All packets MUST set this bit to a value of 0,
  466.          which signifies that the packet is a data packet.  (Packets
  467.          containing only Reset- Requests are classified as data
  468.          packets.)
  469.  
  470. 2.5.3.  History Number
  471.  
  472.       The number of the compression history which was used, ranging from
  473.       1 to the negotiated value in the History Count field.
  474.  
  475.       If the negotiated History Count is less than 2, this field is
  476.       removed.  If the negotiated History Count is 2 or more, but less
  477.       than 256, this field is 1 octet.  If 256 or more histories are
  478.       negotiated, this field is 2 octets, most significant octet first.
  479.  
  480.       If multiple histories are used in one direction on a link, the
  481.       history number field MUST be present on all packets in both
  482.       directions, and sized according to the largest number of histories
  483.       in either direction.
  484.  
  485.       If multiple histories are used, this field MUST be present in
  486.       uncompressed as well as compressed packets.
  487.  
  488. 2.5.4.  Sequence Number
  489.  
  490.       The sequence number field is one octet in length.  When the check
  491.       mode field is set to the "Sequence Number" or "Sequence Number +
  492.       LCB" options, the sequence number field MUST be present in all
  493.       data compression packets that contain a data field.
  494.  
  495.       The value of the sequence number field (the sequence number of the
  496.       packet) MUST begin with "1" and increment modulo 256 on successive
  497.       packets that contain data fields.  This number is relative to the
  498.       history number used.
  499.  
  500.       On receipt of a packet with the R-A bit set to "0", if the
  501.       sequence number of the packet is any number other than (N+1) mod
  502.       256, where N is the sequence number of the last packet received
  503.  
  504.  
  505.  
  506. Schneider & Friend           Informational                      [Page 9]
  507.  
  508. RFC 1967                        LZS-DCP                      August 1996
  509.  
  510.  
  511.       for the same history, or an initial value of "0", a receive
  512.       failure for that history has occurred.  The receive failure MUST
  513.       be handled according to the synchronization procedure in section
  514.       3.5.
  515.  
  516.       The sequence number MUST NOT be reset by the transmitter when a
  517.       packet containing a Reset-Ack is sent. The decompressor MUST
  518.       resynchronize its sequence number reference for the indicated
  519.       history when a packet containing a Reset-Ack is received.
  520.  
  521. 2.5.5.  Data
  522.  
  523.       The data field MUST contain a single datagram in either compressed
  524.       or uncompressed form, depending on the state of the C/U bit in the
  525.       Header.  This length of this field is always be an integer number
  526.       of octets.  This field is required in all packets that do not have
  527.       the R-R bit set to "1".
  528.  
  529.       If the C/U bit is set to "0", the data field contains the
  530.       uncompressed form of the datagram.
  531.  
  532.       If the C/U bit is set to "1", the form of the data field is one
  533.       block of compressed data as defined in 3.2 of X3.241-1994, with
  534.       the following exceptions:  1) the end marker may be followed with
  535.       additional octets containing only zeros;  2) if the final octet in
  536.       the block of compressed data has a value of "0", then it MAY be
  537.       removed from the data field.
  538.  
  539.       There is only one end marker per block of compressed data.
  540.  
  541. 2.5.6.  Longitudinal Check Byte
  542.  
  543.       The LCB field is one octet in length, and if present MUST be the
  544.       last octet in the data compression packet.  When the check-mode
  545.       field is set to "LCB" or "Sequence Number + LCB", this field MUST
  546.       be present in all packets where the data field contains compressed
  547.       data.  This field MUST NOT be present in data compression packets
  548.       where the data field contains uncompressed data.  This field
  549.       contains the result of the LCB calculation, in accordance with the
  550.       following paragraph.
  551.  
  552.       The LCB octet is the Exclusive-OR of FF(hex) and each octet of the
  553.       uncompressed datagram (prior to the compression transformation).
  554.       On receipt, the receiver computes the Exclusive-OR of FF(hex) and
  555.       each octet of the decompressed packet.  If this value does not
  556.       match the received LCB, then a receive failure for that history
  557.       has occurred.  The receive failure is handled according to the
  558.       history synchronization procedure in section 3.5.
  559.  
  560.  
  561.  
  562. Schneider & Friend           Informational                     [Page 10]
  563.  
  564. RFC 1967                        LZS-DCP                      August 1996
  565.  
  566.  
  567. 2.5.7.  Compressed Data
  568.  
  569.    The Stac LZS compression algorithm is Defined in ANSI X3.241-1994
  570.    [7]. The format of the compressed data is repeated here for
  571.    informational purposes ONLY.
  572.  
  573.    <Compressed Stream> := [<Compressed String>] <End Marker>
  574.    <Compressed String> := 0 <Raw Byte> | 1 <Compressed Bytes>
  575.  
  576.    <Raw Byte> := <b><b><b><b><b><b><b><b>          (8-bit byte)
  577.    <Compressed Bytes> := <Offset> <Length>
  578.  
  579.    <Offset> := 1 <b><b><b><b><b><b><b> |           (7-bit offset)
  580.                0 <b><b><b><b><b><b><b><b><b><b><b> (11-bit offset)
  581.    <End Marker> := 110000000
  582.    <b> := 1 | 0
  583.  
  584.    <Length> :=
  585.    00        = 2     1111 0110      = 14
  586.    01        = 3     1111 0111      = 15
  587.    10        = 4     1111 1000      = 16
  588.    1100      = 5     1111 1001      = 17
  589.    1101      = 6     1111 1010      = 18
  590.    1110      = 7     1111 1011      = 19
  591.    1111 0000 = 8     1111 1100      = 20
  592.    1111 0001 = 9     1111 1101      = 21
  593.    1111 0010 = 10    1111 1110      = 22
  594.    1111 0011 = 11    1111 1111 0000 = 23
  595.    1111 0100 = 12    1111 1111 0001 = 24
  596.    1111 0101 = 13     ...
  597.  
  598. 3.  Sending Compressed Datagrams
  599.  
  600.    The reliable and efficient transport of datagrams on the data link
  601.    depends on the following processes.
  602.  
  603. 3.1.  Transmitter Process
  604.  
  605.       The compression operation results in either compressed or
  606.       uncompressed data.  When a network datagram is received, it is
  607.       assigned to a particular history buffer and processed according to
  608.       ANSI X3.241-1994 to form compressed data or used as is to form
  609.       uncompressed data.  Prior to the compression operation, if a
  610.       Reset-Request is outstanding for the history buffer to be used,
  611.       the buffer is cleared.  In performing the compression operation,
  612.       if the process mode field is set to the value None ("0"), the
  613.       history MUST only be updated if the result is compressed data.  If
  614.       process mode field is set to the value Process-Uncompressed ("1"),
  615.  
  616.  
  617.  
  618. Schneider & Friend           Informational                     [Page 11]
  619.  
  620. RFC 1967                        LZS-DCP                      August 1996
  621.  
  622.  
  623.       the history MUST be updated when either compressed data or
  624.       uncompressed data is produced.  Uncompressed data MAY be sent at
  625.       any time.  Uncompressed data MUST be sent if compression causes
  626.       enough expansion to cause the data compression datagram size to
  627.       exceed the Information field's MRU.
  628.  
  629.       If the Process Mode field is set to the value None ("0") and the
  630.       compressor has modified the history buffer before sending an
  631.       uncompressed datagram, the history buffer MUST be cleared before
  632.       the next datagram is processed.
  633.  
  634.       The output of the compression operation is placed in the
  635.       information field of the datagram.  The C/U bit is set according
  636.       to whether the data field contains compressed or uncompressed
  637.       data.  If the sequence number field is present according the value
  638.       of the check mode field, the sequence number counter for the
  639.       applicable history number MUST be incremented and its value placed
  640.       in the sequence number field.  If the data field contains
  641.       compressed data, and Check Mode field is set accordingly, the LCB
  642.       field is present and its value is computed as specified in section
  643.       2.2.6.
  644.  
  645.       Upon reception of a packet containing a Reset-Request, the
  646.       transmitting compressor MUST be cleared to an initial state, which
  647.       includes clearing the history buffer.  If the data field of the
  648.       packet containing the Reset-Request contains data, it is delivered
  649.       to the local receiver as a normal data packet.  In addition to the
  650.       reset of the compressor, a packet MUST be transmitted with Reset-
  651.       Ack bit set to 1.  The data field of this packet MUST be filled
  652.       with data.  If no data is ready for transmission, the transmitter
  653.       MUST wait until data is ready before sending the Reset-Ack.
  654.  
  655.       If the history buffer is in the clear state (the history buffer
  656.       contains no data bytes) prior to performing the compression
  657.       operation, the resulting compressed or uncompressed packet MUST be
  658.       sent with the R-A bit set to "1".
  659.  
  660. 3.2.  Receiver Process
  661.  
  662.       When a data compression datagram is received from the peer, the
  663.       R-R and R-A bits MUST be checked.  If the R-R bit is set, the
  664.       local compression engine MUST be signaled that a Reset-Request has
  665.       been received for the history specified by the history number
  666.       field.  If the R-A bit is set, any outstanding receive failure for
  667.       the specified history MUST be cleared.  If no receive failure is
  668.       outstanding, and the sequence number field is present, its value
  669.       checked. If a receive failure has occurred, it MUST be handled
  670.       according to the history resynchronization mechanism described
  671.  
  672.  
  673.  
  674. Schneider & Friend           Informational                     [Page 12]
  675.  
  676. RFC 1967                        LZS-DCP                      August 1996
  677.  
  678.  
  679.       below, and the remainder of the datagram is discarded.  If no
  680.       receive failure is detected, the data is assigned to the indicated
  681.       decompression history buffer and processed according to process
  682.       mode field and C/U bit.
  683.  
  684.       If the C/U bit is set to "1", a single octet containing the value
  685.       0x00 MUST be appended to the data field and the resulting
  686.       compressed data block MUST be decompressed according to ANSI
  687.       X3.241-1994.  If the LCB field is present on the received
  688.       datagram, an LCB for the uncompressed data MUST be computed and
  689.       checked against the received LCB according to section 2.1.  If a
  690.       receive failure has occurred, it MUST be handled according to the
  691.       History Resynchronization Mechanism described below.
  692.  
  693.       If the C/U bit is set to "0" and the process mode field is set to
  694.       the value Process-Uncompressed ("1"), the specified decompression
  695.       history buffer MUST be updated with the received uncompressed
  696.       data.
  697.  
  698.       If the C/U bit is set to "0" and process mode field is set to the
  699.       value None ("0"), the specified decompression history buffer MUST
  700.       NOT be modified.
  701.  
  702.       If the R-A bit is set to "1", the receiving decompressor MAY be
  703.       reset to an initial state.  (However, due to the characteristics
  704.       of the Stac LZS algorithm, a decompressor reset is not required).
  705.       After reset, any compressed or uncompressed data contained in the
  706.       packet is processed.
  707.  
  708.       On the occurrence of a receive failure, an implementation MUST
  709.       transmit a packet with the R-R bit set to "1" (a Reset-Request)
  710.       and with the history number matching the history that had the
  711.       failure.  The data field may be present if data is waiting to be
  712.       transported for that history, or the R-R bit may be set in a
  713.       packet transmitted without sequence number, data, or LCB fields.
  714.       Once a receive failure has occurred, the data in any subsequent
  715.       packets received for that history MUST be discarded until a packet
  716.       containing a Reset-Ack is received.  It is the responsibility of
  717.       the receiver to ensure the reliability of the reset request-
  718.       acknowledge mechanism.  This may require the transmission of an
  719.       additional Reset-Request before a Reset-Ack will be received.
  720.  
  721. 3.3.  History Maintenance
  722.  
  723.       The History Count field determines the number of history buffers
  724.       to be maintained for the compression protocol.  For example, each
  725.       history buffer could represent a separate logical connection
  726.       between the data compression peers.  When maintaining a history,
  727.  
  728.  
  729.  
  730. Schneider & Friend           Informational                     [Page 13]
  731.  
  732. RFC 1967                        LZS-DCP                      August 1996
  733.  
  734.  
  735.       the peers MUST use link error detection and signaling to ensure
  736.       that both the compressor and decompressor copies of each history
  737.       buffer are always identical.
  738.  
  739.       Setting the History Count field to the value "0" indicates that
  740.       the compression is to be on a connectionless basis.  In this case,
  741.       a single history buffer is used and MUST be cleared at the
  742.       beginning of every datagram.  The compressing entity MUST set the
  743.       R-A bit on all outgoing datagrams.
  744.  
  745.       When the History Count field is set to the value "1", a single
  746.       history buffer is maintained by each of the data compression
  747.       peers. (A single logical connection.)
  748.  
  749.       When the History Count field is set to a value greater than "1",
  750.       separate history buffers, error detection states, and signaling
  751.       states are maintained by the decompressing entity for each
  752.       history.  The compressing peer may transmit data on any number of
  753.       separate histories, up to the value of the History Count field.
  754.  
  755. 3.4.  Anti-Expansion Mechanism
  756.  
  757.       When one or more histories are negotiated and the Process Mode
  758.       field is set to None ("0"), there are 2 options on how to handle
  759.       packets that expand:
  760.  
  761.          1) Send the expanded data and keep the history, thus allowing
  762.             loss of current bandwidth but preserving future bandwidth on
  763.             the link.
  764.          2) Send the uncompressed data and clear the history, thus
  765.             conserving current bandwidth, but allowing possible loss of
  766.             future bandwidth on the link.
  767.  
  768.       When 1 or more histories are negotiated and the Process Mode field
  769.       is set to Process-Uncompressed ("1"), there is an additional
  770.       option:
  771.  
  772.          3) Send the uncompressed data and do not clear the compression
  773.             history; the decompressor will update its history, thus
  774.             conserving the current bandwidth and future bandwidth on the
  775.             link.
  776.  
  777. 3.5.  History Resynchronization Mechanism
  778.  
  779.       The DCP-Header includes R-R (Reset-Request) and R-A (Reset-Ack)
  780.       bits in order to provide a mechanism for indicating a receiver
  781.       failure in one direction of a compressed link without affecting
  782.       traffic in the other direction.  A receive failure is determined
  783.  
  784.  
  785.  
  786. Schneider & Friend           Informational                     [Page 14]
  787.  
  788. RFC 1967                        LZS-DCP                      August 1996
  789.  
  790.  
  791.       using the sequence number and/or LCB mechanism, according to the
  792.       value of the check mode field.
  793.  
  794.       Reset-Requests and Reset-Acks are specific to the history number
  795.       of the packet containing them.
  796.  
  797.       Reset-Request/Reset-Ack history synchronization signaling is
  798.       provided to recover from a loss of synchronization between peers,
  799.       especially in unreliable transport layers.  As with all
  800.       compression algorithms, the decompressor can not recover from
  801.       dropped, erroneous, or mis-ordered datagrams, and will propagate
  802.       errors catastrophically until both peers are reset to an initial
  803.       state.
  804.  
  805.       The LZS-DCP protocol provides a means to detect these error
  806.       conditions: LCB for erroneous datagrams, and sequence number for
  807.       dropped or mis-ordered datagrams.  There is a means for correcting
  808.       a loss of synchronization: clear both the failing compression and
  809.       decompression histories, and follow the transmitter and receiver
  810.       processes in sections 3.1. and 3.2.
  811.  
  812. 4.  Configuration Option Format
  813.  
  814.    The LZS-DCP Configuration Option negotiates the use of LZS-DCP on the
  815.    link.  By default or ultimate disagreement, no compression is used.
  816.    This Configuration Option is used in CCP, and can be used in other
  817.    negotiation mechanisms [2].
  818.  
  819.    All implementations MUST support the default values.
  820.  
  821.    A summary of the LZS-DCP Configuration Option format is shown below.
  822.    The fields are transmitted from left to right.
  823.  
  824.     0                   1                   2                   3
  825.     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
  826.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  827.    |     Type      |    Length     |        History Count          |
  828.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  829.    |   Check Mode  | Process Mode  |
  830.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  831.  
  832.    Type
  833.  
  834.       23
  835.  
  836.    Length
  837.  
  838.       6
  839.  
  840.  
  841.  
  842. Schneider & Friend           Informational                     [Page 15]
  843.  
  844. RFC 1967                        LZS-DCP                      August 1996
  845.  
  846.  
  847.    History Count
  848.  
  849.       The History Count field is two octets, most significant octet
  850.       first, and specifies the maximum number of Compression Histories.
  851.  
  852.       The value 0 indicates that the implementation expects the peer to
  853.       clear the Compression History at the beginning of every packet.
  854.       If this value is selected, the transmitter MUST set the Reset-Ack
  855.       bit of every packet that contains compressed data.
  856.  
  857.       The value 1 is the default value and is used to indicate that only
  858.       one history is maintained.
  859.  
  860.       Other valid values range from 2 to 65535.  The peer is not
  861.       required to send as many histories as the implementation indicates
  862.       that it can accept.  However, it should be noted that resources
  863.       are allocated in each peer to support the number of negotiated
  864.       histories in this field.
  865.  
  866. Check Mode
  867.  
  868.       The Check Mode indicates support of LCB and/or Sequence checking.
  869.       The use of check mode None (0) MUST NOT be used for history counts
  870.       greater than zero.
  871.  
  872.          0    None
  873.          1    LCB
  874.          2    Sequence Number
  875.          3    Sequence Number + LCB (default)
  876.  
  877.    Process Mode
  878.  
  879.       The Process Mode specifies how uncompressed packets are handled.
  880.       A value of None (0) indicates that uncompressed packets are not
  881.       processed by the decompressor.  A value of Process-Uncompressed
  882.  
  883.       (1) indicates that uncompressed packets are processed by the
  884.       decompressor to update the history.
  885.  
  886.          0    None (default)
  887.          1    Process-Uncompressed
  888.  
  889. Security Considerations
  890.  
  891.    Security issues are not discussed in this memo.
  892.  
  893.  
  894.  
  895.  
  896.  
  897.  
  898. Schneider & Friend           Informational                     [Page 16]
  899.  
  900. RFC 1967                        LZS-DCP                      August 1996
  901.  
  902.  
  903. Acknowledgments
  904.  
  905.    This document is based on, and uses much of the text of [5].
  906.  
  907. References
  908.  
  909.    [1]    Simpson, W., Editor, "The Point-to-Point Protocol (PPP)", STD
  910.           51, RFC 1661, Daydreamer, July 1994.
  911.  
  912.    [2]    Rand, D., "The PPP Compression Control Protocol (CCP)", RFC
  913.           1962, June 1996.
  914.  
  915.    [3]    Lempel, A., and J. Ziv, "A Universal Algorithm for Sequential
  916.           Data Compression", IEEE Transactions On Information Theory,
  917.           Vol. IT-23, No. 3, May 1977.
  918.  
  919.    [4]    Rand, D., "PPP Reliable Transmission", RFC 1663, Novell, July
  920.           1994.
  921.  
  922.    [5]    Friend, R., and W. Simpson, "PPP Stac LZS Compression
  923.           Protocol", RFC 1974, August 1996.
  924.  
  925.    [6]    Motorola Information Systems Group, "Data Compression Protocol
  926.           (DCP) Proposal", TR-30.1 ad hoc contribution (email
  927.           reflector), September 21, 1995.
  928.  
  929.    [7]    ANSI X3.241-1994, "American National Standard Data Compression
  930.           Method, Adaptive Coding with Sliding Window of Information
  931.           Interchange".
  932.  
  933. Chair's Address
  934.  
  935.    The working group can be contacted via the current chair:
  936.  
  937.    Karl Fox
  938.    Ascend Communications
  939.    3518 Riverside Drive, Suite 101
  940.    Columbus, Ohio 43221
  941.  
  942.    EMail: karl@ascend.com
  943.  
  944.  
  945.  
  946.  
  947.  
  948.  
  949.  
  950.  
  951.  
  952.  
  953.  
  954. Schneider & Friend           Informational                     [Page 17]
  955.  
  956. RFC 1967                        LZS-DCP                      August 1996
  957.  
  958.  
  959. Authors' Addresses
  960.  
  961.    Questions about this memo can also be directed to:
  962.  
  963.    Kevin Schneider
  964.    Adtran, Inc.
  965.    901 Explorer Blvd.
  966.    Huntsville, AL 25806
  967.  
  968.    Phone: (205) 971-8024
  969.    EMail: kschneider@adtran.com
  970.  
  971.  
  972.    Robert Friend
  973.    Stac Technology
  974.    12636 High Bluff Drive
  975.    San Diego, CA 92130-2093
  976.  
  977.    Phone: (619) 794-4542
  978.    EMail: rfriend@stac.com
  979.  
  980.  
  981.  
  982.  
  983.  
  984.  
  985.  
  986.  
  987.  
  988.  
  989.  
  990.  
  991.  
  992.  
  993.  
  994.  
  995.  
  996.  
  997.  
  998.  
  999.  
  1000.  
  1001.  
  1002.  
  1003.  
  1004.  
  1005.  
  1006.  
  1007.  
  1008.  
  1009.  
  1010. Schneider & Friend           Informational                     [Page 18]
  1011.  
  1012.