home *** CD-ROM | disk | FTP | other *** search
/ The Hacker's Encyclopedia 1998 / hackers_encyclopedia.iso / rfc / 3 / rfc1979.txt < prev    next >
Encoding:
Text File  |  2003-06-11  |  18.4 KB  |  564 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7. Network Working Group                                           J. Woods
  8. Request for Comments: 1979                                 Proteon, Inc.
  9. Category: Informational                                      August 1996
  10.  
  11.  
  12.                           PPP Deflate Protocol
  13.  
  14. Status of This Memo
  15.  
  16.    This memo provides information for the Internet community.  This memo
  17.    does not specify an Internet standard of any kind.  Distribution of
  18.    this memo is unlimited.
  19.  
  20. Abstract
  21.  
  22.    The Point-to-Point Protocol (PPP) [1] provides a standard method for
  23.    transporting multi-protocol datagrams over point-to-point links.
  24.  
  25.    The PPP Compression Control Protocol [2] provides a method to
  26.    negotiate and utilize compression protocols over PPP encapsulated
  27.    links.
  28.  
  29.    This document describes the use of the PPP Deflate compression
  30.    protocol for compressing PPP encapsulated packets.
  31.  
  32. Table of Contents
  33.  
  34.      1.     Introduction ......................................    2
  35.         1.1       Licensing ...................................    2
  36.      2.     PPP Deflate Packets ...............................    3
  37.         2.1       Packet Format ...............................    6
  38.      3.     Configuration Option Format .......................    8
  39.      SECURITY CONSIDERATIONS ..................................    9
  40.      REFERENCES ...............................................    9
  41.      ACKNOWLEDGEMENTS .........................................    9
  42.      CHAIR'S ADDRESS ..........................................   10
  43.      AUTHOR'S ADDRESS .........................................   10
  44.  
  45.  
  46.  
  47.  
  48.  
  49.  
  50.  
  51.  
  52.  
  53.  
  54.  
  55.  
  56.  
  57.  
  58. Woods                        Informational                      [Page 1]
  59.  
  60. RFC 1979                      PPP Deflate                    August 1996
  61.  
  62.  
  63. 1.  Introduction
  64.  
  65. The 'deflate' compression format[3], as used by the PKZIP and gzip
  66. compressors and as embodied in the freely and widely distributed
  67. zlib[4] library source code, has the following features:
  68.  
  69.        - an apparently unencumbered encoding and compression
  70.          algorithm, with an open and publically-available
  71.          specification.
  72.  
  73.        - low-overhead escape mechanism for incompressible data.  The
  74.          PPP Deflate specification offers options to reduce that
  75.          overhead further.
  76.  
  77.        - heavily used for many years in networks, on modem and other
  78.          point-to-point links to transfer files for personal computers
  79.          and workstations.
  80.  
  81.        - easily achieves 2:1 compression on the Calgary corpus[5]
  82.          using less than 64KBytes of memory on both sender and
  83.          receive.
  84.  
  85. 1.1.  Licensing
  86.  
  87.    The zlib source is widely and freely available, subject to the
  88.    following copyright:
  89.  
  90.       (C) 1995 Jean-Loup Gailly and Mark Adler
  91.  
  92.        This software is provided 'as-is', without any express or implied
  93.        warranty.  In no event will the authors be held liable for any
  94.        damages arising from the use of this software.
  95.  
  96.        Permission is granted to anyone to use this software for any
  97.        purpose, including commercial applications, and to alter it and
  98.        redistribute it freely, subject to the following restrictions:
  99.  
  100.        1. The origin of this software must not be misrepresented; you
  101.           must not claim that you wrote the original software. If you
  102.           use this software in a product, an acknowledgment in the
  103.           product documentation would be appreciated but is not
  104.           required.
  105.  
  106.        2. Altered source versions must be plainly marked as such, and
  107.           must not be misrepresented as being the original software.
  108.  
  109.  
  110.  
  111.  
  112.  
  113.  
  114. Woods                        Informational                      [Page 2]
  115.  
  116. RFC 1979                      PPP Deflate                    August 1996
  117.  
  118.  
  119.        3. This notice may not be removed or altered from any source
  120.           distribution.
  121.  
  122.        Jean-Loup Gailly        Mark Adler
  123.        gzip@prep.ai.mit.edu    madler@alumni.caltech.edu
  124.  
  125.       If you use the zlib library in a product, we would appreciate
  126.       *not* receiving lengthy legal documents to sign. The sources are
  127.       provided for free but without warranty of any kind.  The library
  128.       has been entirely written by Jean-Loup Gailly and Mark Adler; it
  129.       does not include third-party code.
  130.  
  131.    The deflate format and compression algorithm are based on Lempel-Ziv
  132.    LZ77 compression; extensive research has been done by the GNU Project
  133.    and the Portable Network Graphics working group supporting its patent
  134.    free status.
  135.  
  136. 2.  PPP Deflate Packets
  137.  
  138.    Before any PPP Deflate packets may be communicated, PPP must reach
  139.    the Network-Layer Protocol phase, and the CCP Control Protocol must
  140.    reach the Opened state.
  141.  
  142.    Exactly one PPP Deflate datagram is encapsulated in the PPP
  143.    Information field, where the PPP Protocol field contains 0xFD or
  144.    0xFB.  0xFD is used when the PPP multilink protocol is not used or
  145.    "above" multilink.  0xFB is used "below" multilink, to compress
  146.    independently on individual links of a multilink bundle.
  147.  
  148.    The maximum length of the PPP Deflate datagram transmitted over a PPP
  149.    link is the same as the maximum length of the Information field of a
  150.    PPP encapsulated packet.
  151.  
  152.    Only packets with PPP Protocol numbers in the range 0x0000 to 0x3FFF
  153.    and neither 0xFD nor 0xFB are compressed.  Other PPP packets are
  154.    always sent uncompressed.  Control packets are infrequent and should
  155.    not be compressed for robustness.
  156.  
  157.    Padding
  158.  
  159.       PPP Deflate packets require the previous negotiation of the Self-
  160.       Describing-Padding Configuration Option [6] if padding is added to
  161.       packets.  If no padding is added, than Self-Describing-Padding is
  162.       not required.
  163.  
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170. Woods                        Informational                      [Page 3]
  171.  
  172. RFC 1979                      PPP Deflate                    August 1996
  173.  
  174.  
  175.    Reliability and Sequencing
  176.  
  177.       PPP Deflate requires the packets to be delivered in sequence.  It
  178.       relies on Reset-Request and Reset-Ack LCP packets or on
  179.       renegotiation of the Compression Control Protocol [2] to indicate
  180.       loss of synchronization between the transmitter and receiver.  The
  181.       LCP FCS detects corrupted packets and the normal mechanisms
  182.       discard them.  Missing or out of order packets are detected by the
  183.       sequence number in each packet.  The packet sequence number ought
  184.       to be checked before decoding the packet.
  185.  
  186.       Instead of transmitting a Reset-Request packet when detecting a
  187.       sequence error, the receiver MAY momentarily force CCP to drop out
  188.       of the Opened state by transmitting a new CCP Configure-Request.
  189.       This method is more expensive than using Reset-Requests.
  190.  
  191.       When the receiver first encounters an unexpected sequence number
  192.       it SHOULD send a Reset-Request LCP packet as defined in the
  193.       Compression Control Protocol.  When the transmitter sends the
  194.       Reset-Ack or when the receiver receives a Reset-ACK, they must
  195.       reset the sequence number to zero, clear the compression
  196.       dictionary, and resume sending and receiving compressed packets.
  197.       The receiver MUST discard all compressed packets after detecting
  198.       an error and until it receives a Reset-Ack.  This strategy can be
  199.       thought of as abandoning the transmission of one "file" and
  200.       starting the transmission of a new "file."
  201.  
  202.       The transmitter must clear its compression history and respond
  203.       with a Reset-Ack each time it receives a Reset-Request, because it
  204.       cannot know if previous Reset-Acks reached the receiver.  The
  205.       receiver need not do anything to its history when it receives a
  206.       Reset-Ack, because the transmitter will simply not refer to any
  207.       prior history ('deflate' is a sliding-window compressor).
  208.  
  209.       When the link is busy, one decompression error is usually followed
  210.       by several more before the Reset-Ack can be received.  It is
  211.       undesirable to transmit Reset-Requests more frequently than the
  212.       round-trip-time of the link, because redundant Reset-Requests
  213.       cause unnecessary compression dictionary clearing.  The receiver
  214.       MAY transmit an additional Reset-Request each time it receives a
  215.       compressed or uncompressed packet until it finally receives a
  216.       Reset-Ack, but the receiver ought not transmit another Reset-
  217.       Request until the Reset-Ack for the previous one is late.  The
  218.       receiver MUST transmit enough Reset-Request packets to ensure that
  219.       the transmitter receives at least one.  For example, the receiver
  220.       might choose to not transmit another Reset-Request until after one
  221.       second (or, of course, a Reset-Ack has been received and
  222.       decompression resumed).
  223.  
  224.  
  225.  
  226. Woods                        Informational                      [Page 4]
  227.  
  228. RFC 1979                      PPP Deflate                    August 1996
  229.  
  230.  
  231.    Data Expansion
  232.  
  233.       'Deflate', as used in this standard, expands incompressible data
  234.       by approximately 14-18 bytes (8 bytes worst-case at the 'deflate'
  235.       level, two further bytes for the 'deflate' end-of-block and the
  236.       zero-length synchronization block header, two bytes of sequence
  237.       number, and two bytes to account for adding the PPP Protocol Field
  238.       to the transmitted data unit).
  239.  
  240.       The BSD Compress draft proposal[7] describes an escape mechanism
  241.       for incompressible data that trades off a layering violation for
  242.       the irritating complications of variable and potentially
  243.       unpredictable effective MRU lengths.  That direct escape mechanism
  244.       (and much of the text of its description) is used here as well.
  245.  
  246.       If an incompressible data packet does not fit within the MRU of
  247.       the link, the packet MUST be sent in its original form without CCP
  248.       encapsulation; PPP packets with significant data expansion that do
  249.       not exceed the MRU of the link SHOULD be sent in their original
  250.       form without CCP encapsulation.  In both of these cases, the
  251.       transmitter must increment the sequence number, as future
  252.       encapsulated packets will depend on the correct reception of some
  253.       number of unencapsulated packets.
  254.  
  255.       When a PPP packet is received with PPP Protocol numbers in the
  256.       range 0x0000 to 0x3FFF, (except, of course, 0xFD and 0xFB) it is
  257.       assumed that the packet would have caused expansion.  The packet
  258.       is locally added to the compression history.  (Given the
  259.       definition of the 'deflate' format, a convenient method of doing
  260.       this is to locally "decompress" a stored-block header of the
  261.       appropriate length, followed by the actual data block; or the data
  262.       can simply be appended to the receiver's history, depending on
  263.       implementation details.)
  264.  
  265.       Sending incompressible packets in their native encapsulation
  266.       avoids maximum transmission unit complications.  If uncompressed
  267.       packets could be larger than their native form, then it would be
  268.       necessary for the upper layers of an implementation to treat the
  269.       PPP link as if it had a smaller MTU, to ensure that compressed
  270.       incompressible packets are never larger than the negotiated PPP
  271.       MTU.
  272.  
  273.       Using native encapsulation for incompressible packets complicates
  274.       the implementation.  The transmitter and the receiver must start
  275.       putting information into the compression dictionary starting with
  276.       the same packets, without relying upon seeing a compressed packet
  277.       for synchronization.  The first few packets after clearing the
  278.       dictionary are usually incompressible, and so are likely to sent
  279.  
  280.  
  281.  
  282. Woods                        Informational                      [Page 5]
  283.  
  284. RFC 1979                      PPP Deflate                    August 1996
  285.  
  286.  
  287.       in their native encapsulation, just like packets before
  288.       compression is turned on.  If CCP or LCP packets are handled
  289.       separately from Network-Layer packets (e.g. a "daemon" for control
  290.       packets and "kernel code" for data packets), care must be taken to
  291.       ensure that the transmitter synchronizes clearing the dictionary
  292.       with the transmission of the configure-ACK or Reset-Ack that
  293.       starts compression, and the receiver must similarly ensure that
  294.       its dictionary is cleared before it processes the next packet.
  295.  
  296. 2.1.  Packet Format
  297.  
  298.    A summary of the PPP Deflate packet format is shown below.
  299.  
  300.    The fields are transmitted from left to right.
  301.  
  302.     0                   1                   2                   3
  303.     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
  304.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  305.    |         PPP Protocol          |           Sequence            |
  306.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  307.    |   Data ...
  308.    +-+-+-+-+-+-+-+-+
  309.  
  310.  
  311.    PPP Protocol
  312.  
  313.       The PPP Protocol field is described in the Point-to-Point Protocol
  314.       Encapsulation [1].
  315.  
  316.       When the PPP Deflate compression protocol is successfully
  317.       negotiated by the PPP Compression Control Protocol [2], the value
  318.       of the protocol field is 0xFD or 0xFB.  This value MAY be
  319.       compressed when Protocol-Field-Compression is negotiated.
  320.  
  321.    Sequence
  322.  
  323.       The sequence number is sent most significant octet first.  It
  324.       starts at 0 when the dictionary is cleared, and is incremented by
  325.       1 for each packet, including uncompressed packets.  The sequence
  326.       number after 65535 is zero.  In other words, the sequence number
  327.       "wraps" in the usual way.
  328.  
  329.       The sequence number ensures that lost or out of order packets do
  330.       not cause the compression databases of the peers to become
  331.       unsynchronized.  When an unexpected sequence number is
  332.       encountered, the dictionaries must be resynchronized with a CCP
  333.       Reset-Request or Configure-Request.  The packet sequence number
  334.       can be checked before a compressed packet is decoded.
  335.  
  336.  
  337.  
  338. Woods                        Informational                      [Page 6]
  339.  
  340. RFC 1979                      PPP Deflate                    August 1996
  341.  
  342.  
  343.    Data
  344.  
  345.       The compressed PPP encapsulated packet, consisting of the Protocol
  346.       and Data fields of the original, uncompressed packet follows.
  347.  
  348.       The Protocol field compression MUST be applied to the protocol
  349.       field in the original packet before the sequence number is
  350.       computed or the entire packet is compressed, regardless of whether
  351.       the PPP protocol field compression has been negotiated.  Thus, if
  352.       the original protocol number was less than 0x100, it must be
  353.       compressed to a single byte.
  354.  
  355.       The basic format of the compressed data is precisely described by
  356.       the 'Deflate' Compressed Data Format Specification[3].  Each
  357.       transmitted packet must begin at a 'deflate' block boundary, to
  358.       ensure synchronization when incompressible data resets the
  359.       transmitter's state; to ensure this, each transmitted packet must
  360.       be terminated with a zero-length 'deflate' non-compressed block
  361.       (BTYPE of 00).  This means that the last four bytes of the
  362.       compressed format must be 0x00 0x00 0xFF 0xFF.  These bytes MUST
  363.       be removed before transmission; the receiver can reinsert them if
  364.       required by the implementation.
  365.  
  366.  
  367.  
  368.  
  369.  
  370.  
  371.  
  372.  
  373.  
  374.  
  375.  
  376.  
  377.  
  378.  
  379.  
  380.  
  381.  
  382.  
  383.  
  384.  
  385.  
  386.  
  387.  
  388.  
  389.  
  390.  
  391.  
  392.  
  393.  
  394. Woods                        Informational                      [Page 7]
  395.  
  396. RFC 1979                      PPP Deflate                    August 1996
  397.  
  398.  
  399. 3.  Configuration Option Format
  400.  
  401.  
  402.    Description
  403.  
  404.       The CCP PPP Deflate Configuration Option negotiates the use of PPP
  405.       Deflate on the link.  By default or ultimate disagreement, no
  406.       compression is used.
  407.  
  408.    A summary of the PPP Deflate Configuration Option format is shown
  409.    below.  The fields are transmitted from left to right.
  410.  
  411.     0                   1                   2                   3
  412.     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
  413.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  414.    |     Type      |    Length     |Window | Method|    MBZ    |Chk|
  415.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  416.  
  417.  
  418.    Type
  419.  
  420.       26 for PPP Deflate.
  421.  
  422.    Length
  423.  
  424.       3
  425.  
  426.    Window
  427.  
  428.       Represents the maximum window size the decompressor is willing to
  429.       allocate; expressed as the base-2 logarithm of the LZ77 window
  430.       size, minus 8.  'Deflate' compliant decompressors must be willing
  431.       to accept the maximum 32KB window size, represented by a value of
  432.       7.  A 'deflate' compliant compressor is at liberty to use a
  433.       reduced window size, so a PPP Deflate compressor MUST either honor
  434.       the restriction requested or reject the option.
  435.  
  436.    Method
  437.  
  438.       Must be the binary number 1000.  Represents the 'zlib' Compression
  439.       Method identifier of '8' for 'deflate' compression with up to 32K
  440.       window size.
  441.  
  442.    MBZ
  443.  
  444.       Must be all 0 bits.
  445.  
  446.  
  447.  
  448.  
  449.  
  450. Woods                        Informational                      [Page 8]
  451.  
  452. RFC 1979                      PPP Deflate                    August 1996
  453.  
  454.  
  455.    Chk
  456.  
  457.       Must be 00 to specify sequence number check method.
  458.  
  459. Security Considerations
  460.  
  461.    Security issues are not discussed in this memo.
  462.  
  463. References
  464.  
  465.    [1]   Simpson, W., "The Point-to-Point Protocol (PPP)", STD 51,
  466.          RFC 1661, July 1994.
  467.  
  468.    [2]   Rand, D., "The PPP Compression Control Protocol (CCP)",
  469.          RFC 1962, June 1996.
  470.  
  471.    [3]   Deutsch, L.P., "'Deflate' Compressed Data Format
  472.          Specification", draft available in
  473.          ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc.
  474.  
  475.    [4]   Gailly, J.-L., "Zlib 0.95 beta".
  476.  
  477.    [5]   Bell, T.C., Cleary, G. G. and Witten, I.H., "Text Compression",
  478.          Prentice_Hall, Englewood Cliffs NJ, 1990.  The compression
  479.          corpus itself can be found in ftp.uu.net:/pub/archiving/zip/.
  480.  
  481.    [6]   Simpson, W., "PPP LCP Extensions", RFC 1570, January 1994.
  482.  
  483.    [7]   Schryver, V., "PPP BSD Compression Protocol", RFC 1977,
  484.          August 1996.
  485.  
  486. Acknowledgments
  487.  
  488.    William Simpson provided the very valuable idea of not using any
  489.    additional header bytes for incompressible packets.
  490.  
  491.  
  492.  
  493.  
  494.  
  495.  
  496.  
  497.  
  498.  
  499.  
  500.  
  501.  
  502.  
  503.  
  504.  
  505.  
  506. Woods                        Informational                      [Page 9]
  507.  
  508. RFC 1979                      PPP Deflate                    August 1996
  509.  
  510.  
  511. Chair's Address
  512.  
  513.    The working group can be contacted via the current chair:
  514.  
  515.    Karl Fox
  516.    Ascend Communications
  517.    3518 Riverside Drive, Suite 101
  518.    Columbus, Ohio 43221
  519.  
  520.    EMail: karl@ascend.com
  521.  
  522. Author's Address
  523.  
  524.    Questions about this memo can also be directed to:
  525.  
  526.    John Woods
  527.    Proteon, Inc.
  528.    9 Technology Drive
  529.    Westborough MA 01581-1799
  530.  
  531.    (508) 898-2800 ext. 2651
  532.    EMail: jfw@funhouse.com
  533.  
  534.  
  535.  
  536.  
  537.  
  538.  
  539.  
  540.  
  541.  
  542.  
  543.  
  544.  
  545.  
  546.  
  547.  
  548.  
  549.  
  550.  
  551.  
  552.  
  553.  
  554.  
  555.  
  556.  
  557.  
  558.  
  559.  
  560.  
  561.  
  562. Woods                        Informational                     [Page 10]
  563.  
  564.