home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / rfc / rfc2118 < prev    next >
Text File  |  1997-03-20  |  17KB  |  508 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7. Network Working Group                                            G. Pall
  8. Request for Comments: 2118                         Microsoft Corporation
  9. Category: Informational                                       March 1997
  10.  
  11.  
  12.  
  13.           Microsoft Point-To-Point Compression (MPPC) Protocol
  14.  
  15. Status of this Memo
  16.  
  17.    This memo provides information for the Internet community.  This memo
  18.    does not specify an Internet standard of any kind.  Distribution of
  19.    this memo is unlimited.
  20.  
  21. Abstract
  22.  
  23.    The Point-to-Point Protocol (PPP) [1] provides a standard method for
  24.    transporting multi-protocol datagrams over point-to-point links.
  25.  
  26.    The PPP Compression Control Protocol [2] provides a method to
  27.    negotiate and utilize compression protocols over PPP encapsulated
  28.    links.
  29.  
  30.    This document describes the use of the Microsoft Point to Point
  31.    Compression protocol (also referred to as MPPC in this document) for
  32.    compressing PPP encapsulated packets.
  33.  
  34. Table of Contents
  35.  
  36.    1.     Introduction ..........................................    2
  37.       1.1       Licensing .......................................    2
  38.       1.2.      Specification of Requirements ...................    2
  39.    2.     Configuration Option Format ...........................    3
  40.    3.     MPPC Packets ..........................................    4
  41.       3.1       Packet Format....................................    5
  42.    4. Description of Compressor and Encoding ....................    6
  43.       4.1       Literal Encoding ................................    7
  44.       4.2       Copy Tuple Encoding .............................    7
  45.           4.2.1     Offset Encoding .............................    7
  46.           4.2.2     Length-of-Match Encoding ....................    7
  47.       4.3       Synchronization .................................    8
  48.    SECURITY CONSIDERATIONS ......................................    8
  49.    REFERENCES ...................................................    9
  50.    ACKNOWLEDGEMENTS .............................................    9
  51.    CHAIR'S ADDRESS    ...........................................    9
  52.    AUTHORS' ADDRESS .............................................    9
  53.  
  54.  
  55.  
  56.  
  57.  
  58. Pall                         Informational                      [Page 1]
  59.  
  60. RFC 2118                     MPPC Protocol                    March 1997
  61.  
  62.  
  63. 1.  Introduction
  64.  
  65.  
  66.    The Microsoft Point to Point Compression scheme is a means of
  67.    representing arbitrary Point to Point Protocol (PPP) packets in a
  68.    compressed form. The MPPC algorithm is designed to optimize processor
  69.    utilization and bandwidth utilization in order to support large
  70.    number of simultaneous connections. The MPPC algorithm is also
  71.    optimized to work efficiently in typical PPP scenarios
  72.    (1500 byte MTU, etc.).
  73.  
  74.    The MPPC algorithm uses an LZ [3] based algorithm with a sliding
  75.    window history buffer.
  76.  
  77.    The MPPC algorithm keeps a continous history so that after 8192 bytes
  78.    of data has been transmitted compressed there is always 8192 bytes of
  79.    history to use for compressing, except when the history is flushed.
  80.  
  81. 1.1.  Licensing
  82.  
  83.    MPPC can only be used in products that implement the Point to Point
  84.    Protocol AND for the sole purpose of interoperating with other MPPC
  85.    and Point to Point Protocol implementations.
  86.  
  87.    Source and object licenses are available on a non-discriminatory
  88.    basis from Stac Electronics. Please contact:
  89.  
  90.          Cheryl Poland
  91.          Stac Electronics
  92.          12636 High Bluff Drive,
  93.          San Deigo, CA 92130
  94.          Phone: (619)794-4534
  95.          Email: cherylp@stac.com
  96.  
  97. 1.2.  Specification of Requirements
  98.  
  99.    In this document, several words are used to signify the requirements
  100.    of the specification.  These words are often capitalized.
  101.  
  102.    MUST      This word, or the adjective "required", means that the
  103.              definition is an absolute requirement of the specification.
  104.  
  105.    MUST NOT  This phrase means that the definition is an absolute
  106.              prohibition of the specification.
  107.  
  108.  
  109.  
  110.  
  111.  
  112.  
  113.  
  114. Pall                         Informational                      [Page 2]
  115.  
  116. RFC 2118                     MPPC Protocol                    March 1997
  117.  
  118.  
  119.    SHOULD    This word, or the adjective "recommended", means that there
  120.              may exist valid reasons in particular circumstances to
  121.              ignore this item, but the full implications MUST be
  122.              understood and carefully weighed before choosing a
  123.              different course.
  124.  
  125.    MAY       This word, or the adjective "optional", means that this
  126.              item is one of an allowed set of alternatives.  An
  127.              implementation which does not include this option MUST be
  128.              prepared to interoperate with another implementation which
  129.              does include the option.
  130.  
  131. 2.  Configuration Option Format
  132.  
  133.    Description
  134.  
  135.       The CCP Configuration Option negotiates the use of MPPC on the
  136.       link.  By default or ultimate disagreement, no compression is
  137.       used.
  138.  
  139.    A summary of the CCP Configuration Option format is shown below.
  140.    The fields are transmitted from left to right.
  141.  
  142.     0                   1                   2                   3
  143.     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
  144.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  145.    |     Type      |    Length     |        Supported Bits         |
  146.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  147.    |       Supported Bits          |
  148.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  149.  
  150.    Type
  151.  
  152.       18
  153.  
  154.    Length
  155.  
  156.       6
  157.  
  158.    Supported Bits
  159.  
  160.       This field is 4 octets, most significant octet first. The least
  161.       significant bit in the least significant octet set to 1 indicates
  162.       desire to negotiate MPPC.
  163.  
  164.       All other bits MUST be set to 0.
  165.  
  166.  
  167.  
  168.  
  169.  
  170. Pall                         Informational                      [Page 3]
  171.  
  172. RFC 2118                     MPPC Protocol                    March 1997
  173.  
  174.  
  175. 3.  MPPC Packets
  176.  
  177.    Before any MPPC packets may be communicated, PPP must reach the
  178.    Network-Layer Protocol phase, and the CCP Control Protocol must reach
  179.    the Opened state.
  180.  
  181.    Exactly one MPPC datagram is encapsulated in the PPP Information
  182.    field. The PPP Protocol field indicates type hex 00FD for all
  183.    compressed datagrams.
  184.  
  185.    The maximum length of the MPPC datagram transmitted over a PPP link
  186.    is the same as the maximum length of the Information field of a PPP
  187.    encapsulated packet. Since the history buffer is limited to 8192
  188.    bytes, this length cannot be greater than 8192 bytes.
  189.  
  190.    Only packets with PPP Protocol numbers in the range hex 0021 to hex
  191.    00FA are compressed.  Other packets are not passed thru the MPPC
  192.    processor and are sent with their original PPP Protocol numbers.
  193.  
  194.    Padding
  195.  
  196.       It is recommended that padding not be used with MPPC since it
  197.       defeats the purpose of compression. If the sender must use padding
  198.       it MUST negotiate the Self-Describing-Padding Configuration option
  199.       during LCP phase and use self-describing pads.
  200.  
  201.    Reliability and Sequencing
  202.  
  203.       The MPPC scheme does not require a reliable link.  Instead, it
  204.       relies on a 12 bit coherency count in each packet to keep the
  205.       history buffers synchronized.  If the receiver recognizes that the
  206.       coherency count received in the packet does not match the count it
  207.       is expecting, it sends a CCP Reset-Request packet to resynchronize
  208.       its history buffer with the sender's history buffer.
  209.  
  210.       MPPC expects the packets to be delivered in sequence, otherwise
  211.       history buffer re-synchronization will not occur.
  212.  
  213.       MPPC MAY be used over a reliable link, as described in "PPP
  214.       Reliable Transmision" [5], but this typically just adds
  215.       unnecessary overhead since only the coherency count is required.
  216.  
  217.    Data Expansion
  218.  
  219.       If compressing the data results in data expansion, the original
  220.       data is sent as an uncompressed MPPC packet. The sender must flush
  221.       the history before compressing any more data and set the FLUSHED
  222.       bit on the next outgoing packet.
  223.  
  224.  
  225.  
  226. Pall                         Informational                      [Page 4]
  227.  
  228. RFC 2118                     MPPC Protocol                    March 1997
  229.  
  230.  
  231. 3.1.  Packet Format
  232.  
  233.     0                   1                   2                   3
  234.     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
  235.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  236.    |         PPP Protocol          |A|B|C|D| Coherency Count       |
  237.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  238.    |        Compressed Data...
  239.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  240.  
  241.    PPP Protocol
  242.  
  243.       The PPP Protocol field is described in the Point-to-Point Protocol
  244.       Encapsulation [1].
  245.  
  246.       When the MPPC compression protocol is successfully negotiated by
  247.       the PPP Compression Control Protocol, the value is hex 00FD. This
  248.       value MAY be compressed when Protocol-Field-Compression is
  249.       negotiated.
  250.  
  251.    Bit A
  252.  
  253.       This bit indicates that the history buffer has just been
  254.       initialized before this packet was generated.  This packet can
  255.       ALWAYS be decompressed because it is not based on any previous
  256.       history. This bit is typically sent to inform the peer that the
  257.       sender has initialized its history buffer before compressing the
  258.       packet and that the receiving peer must initialize its history
  259.       buffer before decompressing the packet. This bit is referred to as
  260.       FLUSHED bit in this document.
  261.  
  262.       Implementation Note: Compression and decompression histories are
  263.       always initialized with all zeroes.
  264.  
  265.    Bit B
  266.  
  267.       This bit indicates that the packet was moved to the front of the
  268.       history buffer typically because there was no room at the end of
  269.       the history buffer.  This bit is used to tell the decompressor to
  270.       set its history pointer to the beginning of the history buffer.
  271.  
  272.       Implementation Notes:
  273.       1. It is implied that this bit must be set at least once for every
  274.          8192 bytes of data that is sent compressed.
  275.       2. It is also implied that this bit can be set even if the
  276.          sender's history buffer is not full. Initialized history that
  277.          has not been used for compressing data must not be referred to
  278.          in the compressed packets.
  279.  
  280.  
  281.  
  282. Pall                         Informational                      [Page 5]
  283.  
  284. RFC 2118                     MPPC Protocol                    March 1997
  285.  
  286.  
  287.    Bit C
  288.  
  289.       This bit (if set) is used to indicate that the packet is
  290.       compressed.
  291.  
  292.    Bit D
  293.  
  294.       This bit must be set to 0.
  295.  
  296.    Coherency Count
  297.  
  298.       The coherency count is used to assure that the packets are sent in
  299.       proper order and that no packet has been dropped.  This count
  300.       starts at 0 and is always increased by 1 and NEVER decreases or
  301.       goes back. When all bits are 1, the count returns to 0.
  302.  
  303.    Compressed Data
  304.  
  305.       The compressed data begins with the protocol field.  For example,
  306.       in case of an IP packet (0021 followed by an IP header), the
  307.       compressor will first try to compress the 0021 protocol field and
  308.       then compress the IP header.
  309.  
  310.       If the packet contains header compression, the MPPC compressor is
  311.       applied AFTER header compression is preformed and MUST be applied
  312.       to the compressed header as well.  For example, if a packet
  313.       contained the protocol 002d for a compressed TCP/IP header, the
  314.       compressor would first attempt to compress 002d and then it
  315.       would attempt to compress the compressed Van-Jacobsen TCP/IP
  316.       header.
  317.  
  318. 4. Description of Compressor and Encoding
  319.  
  320.    The compressor runs through the length of the frame producing as
  321.    output a Literal (byte to be sent uncompressed) or a <Offset,
  322.    Length-of-Match> Copy tuple, where Offset is the number of bytes
  323.    before in the history where the match lies and Length-of-Match is the
  324.    number of bytes to copy from the location indicated by Offset.
  325.  
  326.    For example, comsider the following string:
  327.  
  328.    0         1         2         3         4
  329.    012345678901234567890123456789012345678901234567890
  330.    for whom the bell tolls, the bell tolls for thee.
  331.  
  332.    The compressor would produce:
  333.  
  334.    for whom the bell tolls,<16,15> <40,4><19,3>e.
  335.  
  336.  
  337.  
  338. Pall                         Informational                      [Page 6]
  339.  
  340. RFC 2118                     MPPC Protocol                    March 1997
  341.  
  342.  
  343.    The Literal and Copy tuple tokens are then encoded according to the
  344.    MPPC encoding scheme.
  345.  
  346. 4.1 Literal Encoding
  347.  
  348.    Literals are bytes sent uncompressed. If the value of the Literal is
  349.    below hex 80, it is encoded with its value itself. If the Literal has
  350.    value greater than hex 7F it is sent as bits 10 followed by the lower
  351.    7 bits of the Literal.
  352.  
  353.    Example: Literal hex 56 is transmitted as  01010110
  354.             Literal hex E7 is transmitted as 101100111
  355.  
  356. 4.2 Copy Tuple Encoding
  357.  
  358.    Copy tuples represent compressed data. A tuple has two elements: the
  359.    Offset and Length-of-Match. The Offset is encoded before the Length-
  360.    of-Match.
  361.  
  362. 4.2.1 Offset Encoding
  363.  
  364.    Offset values less than 64 are encoded as bits 1111 followed by the
  365.    lower 6 bits of the value.
  366.  
  367.    Offset values between 64 and 320 are encoded as bits 1110 followed by
  368.    the lower 8 bits of the computation (value - 64).
  369.  
  370.    Offset values between 320 and 8191 are encoded as bits 110 followed
  371.    by the lower 13 bits of the computation (value - 320).
  372.  
  373.    Examples: Offset value of 3 is encoded as:     1111 000011
  374.              Offset value of 128 is encoded as:   1110 01000000
  375.              Offset value of 1024 is encoded as:   110 0001011000000
  376.  
  377. 4.2.2 Length-of-Match Encoding
  378.  
  379.    Length of 3 is encoded with bit 0.
  380.  
  381.    Length values from 4 to 7 are encoded as 10 followed by lower 2 bits
  382.    of the value.
  383.  
  384.    Length values from 8 to 15 are encoded as 110 followed by lower 3
  385.    bits of the value.
  386.  
  387.    Length values from 16 to 31 are encoded as 1110 followed by lower 4
  388.    bits of the value.
  389.  
  390.  
  391.  
  392.  
  393.  
  394. Pall                         Informational                      [Page 7]
  395.  
  396. RFC 2118                     MPPC Protocol                    March 1997
  397.  
  398.  
  399.    Length values from 32 to 63 are encoded as 11110 followed by lower 5
  400.    bits of the value.
  401.  
  402.    Length values from 64 to 127 are encoded as 111110 followed by lower
  403.    6 bits of the value.
  404.  
  405.    Length values from 128 to 255 are encoded as 1111110 followed by
  406.    lower 7 bits of the value.
  407.  
  408.    Length values from 256 to 511 are encoded as 11111110 followed by
  409.    lower 8 bits of the value.
  410.  
  411.    Length values from 512 to 1023 are encoded as 111111110 followed by
  412.    lower 9 bits of the value.
  413.  
  414.    Length values from 1024 to 2047 are encoded as 1111111110 followed by
  415.    lower 10 bits of the value.
  416.  
  417.    Length values from 2048 to 4095 are encoded as 11111111110 followed
  418.    by lower 11 bits of the value.
  419.  
  420.    Length values from 4096 to 8191 are encoded as 111111111110 followed
  421.    by lower 12 bits of the value.
  422.  
  423.    Examples: Length of 15 is encoded as:           110 111
  424.              Length of 120 is encoded as:       111110 111000
  425.              Length of 4097 is encoded as:111111111110 000000000001
  426.  
  427.    The largest Length value that can be encoded is 8191.
  428.  
  429. 4.3  Synchronization
  430.  
  431.    Packets may be lost during transfer. If the decompressor maintained
  432.    coherency count does not match the coherency count received in the
  433.    compressed packet, the decompressor drops the packet and sends a CCP
  434.    Reset-Request packet. The compressor on receiving this packet flushes
  435.    the history buffer and sets the FLUSHED bit in the next packet it
  436.    sends. The decompressor on receiving a packet with its FLUSHED bit
  437.    set flushes its history buffer and sets its coherency count to the
  438.    one transmitted by the compressor in that packet. Thus
  439.    synchronization is achieved without a CCP Reset-Ack packet.
  440.  
  441. Security Considerations
  442.  
  443.    Security issues are not discussed in this memo.
  444.  
  445.  
  446.  
  447.  
  448.  
  449.  
  450. Pall                         Informational                      [Page 8]
  451.  
  452. RFC 2118                     MPPC Protocol                    March 1997
  453.  
  454.  
  455. References
  456.  
  457.    [1]   Simpson, W., Editor, "The Point-to-Point Protocol (PPP)", STD
  458.          51, RFC 1661, Daydreamer, July 1994.
  459.  
  460.    [2]   Rand, D., "The PPP Compression Control Protocol (CCP)", RFC
  461.          1962, Novell, June 1996.
  462.  
  463.    [3]   Lempel, A. and Ziv, J., "A Universal Algorithm for Sequential
  464.          Data Compression", IEEE Transactions On Information Theory,
  465.          Vol. IT-23, No. 3, May 1977.
  466.  
  467.    [4]   Rand, D., "PPP Reliable Transmission", RFC 1663, Novell, July
  468.          1994.
  469.  
  470. Acknowledgments
  471.  
  472.    Thomas Dimitri made significant contributions towards the design and
  473.    development of Microsoft Point-To-Point Compression Protocol. Robert
  474.    Friend of Stac Technology provided editoral input.
  475.  
  476. Chair's Address
  477.  
  478.    The working group can be contacted via the current chair:
  479.  
  480.          Karl F. Fox
  481.          Ascend Communications
  482.          3518 Riverside Dr., Suite 101
  483.          Columbus, Ohio  43221
  484.  
  485.          (614) 451-1883
  486.  
  487.          EMail: karl@ascend.Com
  488.  
  489. Author's Address
  490.  
  491.    Questions about this memo can also be directed to:
  492.  
  493.          Gurdeep Singh Pall
  494.          1, Microsoft Way,
  495.          Redmond, WA 98052
  496.  
  497.          (206) 882-8080
  498.  
  499.          Email: gurdeep@microsoft.com
  500.  
  501.  
  502.  
  503.  
  504.  
  505.  
  506. Pall                         Informational                      [Page 9]
  507.  
  508.