Debian Codegraph @

rfc2118.html

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