Network Working Group D. Rand
Request for Comments: 1978 Novell
Category: Informational August 1996
PPP Predictor Compression Protocol
Status of This Memo
This memo provides information for the Internet community. This memo
does not specify an Internet standard of any kind. Distribution of
this memo is unlimited.
Abstract
The Point-to-Point Protocol (PPP) [1] provides a standard method of
encapsulating multiple protocol datagrams over point-to-point links.
The PPP Compression Control Protocol [2] provides a method for
transporting multi-protocol datagrams over PPP encapsulated links.
This document describes the use of the Predictor data compression
algorithm for compressing PPP encapsulated packets.
Table of Contents
1. Introduction ...................................... 1
2. Licensing ......................................... 2
3. Predictor Packets ................................. 2
3.1 Predictor theory ............................ 2
3.2 Encapsulation for Predictor type 1 .......... 7
3.3 Encapsulation for Predictor type 2 .......... 8
4. Configuration Option Format ....................... 9
SECURITY CONSIDERATIONS .................................. 9
REFERENCES ............................................... 9
ACKNOWLEDGEMENTS ......................................... 9
CHAIR'S ADDRESS .......................................... 9
AUTHOR'S ADDRESS ......................................... 9
1. Introduction
Predictor is a high speed compression algorithm, available without
license fees. The compression ratio obtained using predictor is not
as good as other compression algorithms, but it remains one of the
fastest algorithms available.
Note that although care has been taken to ensure that the following
code does not infringe any patents, there is no assurance that it is
Rand Informational [Page 1]
RFC 1978 Predictor Protocol August 1996
not covered by a patent.
2. Licensing
There are no license fees or costs associated with using the
Predictor algorithm.
Use the following code at your own risk.
3. Predictor Packets
Before any Predictor packets may be communicated, PPP must reach the
Network-Layer Protocol phase, and the Compression Control Protocol
must reach the Opened state.
Exactly one Predictor datagram is encapsulated in the PPP Information
field, where the PPP Protocol field indicates type hex 00FD
(compressed datagram).
The maximum length of the Predictor datagram transmitted over a PPP
link is the same as the maximum length of the Information field of a
PPP encapsulated packet.
Prior to compression, the uncompressed data begins with the PPP
Protocol number. This value MAY be compressed when Protocol-Field-
Compression is negotiated.
PPP Link Control Protocol packets MUST NOT be send within compressed
data.
3.1. Predictor theory
Predictor works by filling a guess table with values, based on the
hash of the previous characters seen. Since we are either emitting
the source data, or depending on the guess table, we add a flag bit
for every byte of input, telling the decompressor if it should
retrieve the byte from the compressed data stream, or the guess
table. Blocking the input into groups of 8 characters means that we
don't have to bit-insert the compressed output - a flag byte preceeds
every 8 bytes of compressed data. Each bit of the flag byte
corresponds to one byte of reconstructed data.
Take the source file:
000000 4141 4141 4141 410a 4141 4141 4141 410a AAAAAAA.AAAAAAA.
000010 4141 4141 4141 410a 4141 4141 4141 410a AAAAAAA.AAAAAAA.
000020 4142 4142 4142 410a 4241 4241 4241 420a ABABABA.BABABAB.
000030 7878 7878 7878 780a xxxxxxx.
Rand Informational [Page 2]
RFC 1978 Predictor Protocol August 1996
Compressing the above data yields the following:
000000 6041 4141 4141 0a60 4141 4141 410a 6f41 `AAAAA.`AAAAA.oA
000010 0a6f 410a 4142 4142 4142 0a60 4241 4241 .oA.ABABAB.`BABA
000020 420a 6078 7878 7878 0a B.`xxxxx.
Reading the above data says:
flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6.
Reconstructed data is: 0 1 2 3 4 5 6 7
datatracker.ietf.org