IPComp LZS: IP Payload Compression Using LZS
How the LZS compression algorithm carries a smaller IP payload, and the rules that keep each datagram readable on its own.
Friend, R. and R. Monsour, "IP Payload Compression Using LZS", RFC 2395, DOI 10.17487/RFC2395, December 1998, <https://www.rfc-editor.org/info/rfc2395>.
@misc{rfc2395,
series = {Request for Comments},
number = 2395,
howpublished = {RFC 2395},
publisher = {RFC Editor},
doi = {10.17487/RFC2395},
url = {https://www.rfc-editor.org/info/rfc2395},
author = {R. Friend and R. Monsour},
title = {{IP Payload Compression Using LZS}},
pagetotal = 9,
year = 1998,
month = dec,
} RFC text
Contents
Network Working Group R. Friend
Request for Comments: 2395 R. Monsour
Category: Informational Hi/fn, Inc.
December 1998
IP Payload Compression Using LZS
Status of this Memo
This memo provides information for the Internet community. It does
not specify an Internet standard of any kind. Distribution of this
memo is unlimited.
Copyright Notice
Copyright (C) The Internet Society (1998). All Rights Reserved.
Abstract
This document describes a compression method based on the LZS
compression algorithm. This document defines the application of the
LZS algorithm to the IP Payload Compression Protocol [IPCOMP].
[IPCOMP] defines a method for applying lossless compression to the
payloads of Internet Protocol datagrams.
Table of Contents
1. Introduction...................................................2
1.1 General....................................................2
1.2 Background of LZS Compression..............................2
1.3 Licensing..................................................3
1.4 Specification of Requirements..............................3
2. Compression Process............................................3
2.1 Compression History........................................3
2.2 Compression Encoding Format................................3
2.3 Padding....................................................4
3. Decompression Process..........................................4
4. IPComp Association (IPCA) Parameters...........................4
4.1 ISAKMP Transform ID........................................5
4.2 ISAKMP Security Association Attributes.....................5
4.3 Manual configuration.......................................5
4.4 Minimum packet size threshold..............................5
4.5 Compressibility test.......................................5
5. Security Considerations........................................5
6. Acknowledgements...............................................5
7. References.....................................................6
8. Authors' Addresses.............................................7
9. Appendix: Compression Efficiency versus Datagram Size..........8
10. Full Copyright Statement......................................9
1. Introduction
1.1 General
This document specifies the application of LZS compression, a
lossless compression algorithm, to IP datagram payloads. This
document is to be used in conjunction with the IP Payload Compression
Protocol [IPCOMP]. This specification assumes a thorough
understanding of the IPComp protocol.
1.2 Background of LZS Compression
Starting with a sliding window compression history, similar to [LZ1],
Hi/fn developed a new, enhanced compression algorithm identified as
LZS. The LZS algorithm is a general purpose lossless compression
algorithm for use with a wide variety of data types. Its encoding
method is very efficient, providing compression for strings as short
as two octets in length.
The LZS algorithm uses a sliding window of 2,048 bytes. During
compression, redundant sequences of data are replaced with tokens
that represent those sequences. During decompression, the original
sequences are substituted for the tokens in such a way that the
original data is exactly recovered. LZS differs from lossy
compression algorithms, such as those often used for video
compression, that do not exactly reproduce the original data.
The details of LZS compression can be found in [ANSI94].
The efficiency of the LZS algorithm depends on the degree of
redundancy in the original data. A table of compression ratios for
the [Calgary] Corpus file set is provided in the appendix in Section
7.
1.3 Licensing
Hi/fn, Inc. holds patents on the LZS algorithm. Licenses for a
reference implementation are available for use in IPPCP, IPSec, TLS
and PPP applications at no cost. Source and object licenses are
available on a non-discriminatory basis. Hardware implementations are
also available. For more information, contact Hi/fn at the address
listed with the authors' addresses.
1.4 Specification of Requirements
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC-2119].
2. Compression Process
2.1 Compression History
The sender MUST reset the compression history prior to processing
each datagram's payload. This ensures that each datagram's payload
can be decompressed independently of any other, as is needed when
datagrams are received out of order.
The sender MUST flush the compressor each time it transmits a
compressed datagram. Flushing means that all data going into the
compressor is included in the output, i.e., no data is held back in
the hope of achieving better compression. Flushing is necessary to
prevent a datagram's data from spilling over into a later datagram.
2.2 Compression Encoding Format
The input to the payload compression algorithm is an IP datagram
payload. The output of the algorithm is a new (and hopefully smaller)
payload. The output payload contains the input payload's data in
either compressed or uncompressed format. The input and output
payloads are each an integral number of bytes in length.
If the uncompressed form is used, the output payload is identical to
the input payload and the IPComp header is omitted. If the
compressed form is used, the output payload is prepended with the
IPComp header and encoded as defined in [ANSI94], which is repeated
here for informational purposes ONLY.
<Compressed Stream> := [<Compressed String>] <End Marker>
<Compressed String> := 0 <Raw Byte> | 1 <Compressed Bytes>
<Raw Byte> := <b><b><b><b><b><b><b><b> (8-bit byte)
<Compressed Bytes> := <Offset> <Length>
<Offset> := 1 <b><b><b><b><b><b><b> | (7-bit offset)
0 <b><b><b><b><b><b><b><b><b><b><b> (11-bit offset)
<End Marker> := 110000000
<b> := 1 | 0
<Length> :=
00 = 2 1111 0110 = 14
01 = 3 1111 0111 = 15
10 = 4 1111 1000 = 16
1100 = 5 1111 1001 = 17
1101 = 6 1111 1010 = 18
1110 = 7 1111 1011 = 19
1111 0000 = 8 1111 1100 = 20
1111 0001 = 9 1111 1101 = 21
1111 0010 = 10 1111 1110 = 22
1111 0011 = 11 1111 1111 0000 = 23
1111 0100 = 12 1111 1111 0001 = 24
1111 0101 = 13 ...
2.3 Padding
A datagram payload compressed using LZS always ends with the last
compressed data byte (also known as the <end marker>), which is used
to disambiguate padding. This allows trailing bits as well as bytes
to be considered padding.
The size of a compressed payload MUST be in whole octet units.
3. Decompression Process
If the received datagram is compressed, the receiver MUST reset the
decompression history prior to processing the datagram. This ensures
that each datagram can be decompressed independently of any other, as
is needed when datagrams are received out of order. Following the
reset of the decompression history, the receiver decompresses the
Payload Data field according to the encoding specified in section 3.2
of [ANSI94].
If the received datagram is not compressed, the receiver needs to
perform no decompression processing and the Payload Data field of the
datagram is ready for processing by the next protocol layer.
4. IPComp Association (IPCA) Parameters
ISAKMP MAY be used to negotiate the use of the LZS compression method
to establish an IPCA, as defined in [IPCOMP].
4.1 ISAKMP Transform ID
The LZS Transform ID as IPCOMP_LZS, as specified in The Internet IP
Security Domain of Interpretation [SECDOI]. This value is used to
negotiate the LZS compression algorithm under the ISAKMP protocol.
4.2 ISAKMP Security Association Attributes
There are no other parameters required for LZS compression negotiated
under ISAKMP.
4.3 Manual configuration
The CPI value IPCOMP_LZS is used for a manually configured IPComp
Compression Associations.
4.4 Minimum packet size threshold
As stated in [IPCOMP], small packets may not compress well. Informal
tests using the LZS algorithm over the Calgary Corpus data set show
that the average payload size that may produce expanded data is
approximately 90 bytes. Thus implementations may not want to attempt
to compress payloads smaller than 90 bytes.
4.5 Compressibility test
There is no adaptive algorithm embodied in the LZS algorithm, for
compressibility testing, as referenced in [IPCOMP].
5. Security Considerations
This document does not add any further security considerations that
[IPCOMP] and [Deutsch96] have already declared.
6. Acknowledgments
The LZS details presented here are similar to those in PPP LZS-DCP
Compression Protocol (LZS-DCP), [RFC-1967].
The author wishes to thank the participants of the IPPCP working
group mailing list whose discussion is currently active and is
working to generate the protocol specification for integrating
compression with IP.
7. References
[AH] Kent, S., and R., Atkinson, "IP Authentication Header",
RFC 2402, November 1998.
[ANSI94] American National Standards Institute, Inc., "Data
Compression Method for Information Systems," ANSI X3.241-
1994, August 1994.
[Calgary] Text Compression Corpus, University of Calgary, available
at ftp://ftp.cpsc.ucalgary.ca/pub/projects/text.
compression.corpus.
[IPCOMP] Shacham, A., "IP Payload Compression Protocol (IPComp)",
RFC 2393, December 1998.
[LZ1] Lempel, A., and Ziv, J., "A Universal Algorithm for
Sequential Data Compression", IEEE Transactions On
Information Theory, Vol. IT-23, No. 3, May 1977.
[RFC-1962] Rand, D., "The PPP Compression Control Protocol (CCP)",
RFC 1962, June 1996.
[RFC-1967] Schneider, K., and R. Friend, "PPP LZS-DCP Compression
Protocol (LZS-DCP)", RFC 1967, August 1996.
[RFC-2003] Perkins, C., "IP Encapsulation within IP", RFC 2003,
October 1996.
[RFC-2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[SECDOI] Piper, D., "The Internet IP Security Domain of
Interpretation for ISAKMP", RFC 2407, November 1998.
8. Authors' Addresses
Robert Friend
Hi/fn Inc.
5973 Avenida Encinas
Suite 110
Carlsbad, CA 92008
EMail: rfriend@hifn.com
Robert Monsour
Hi/fn Inc.
2105 Hamilton Avenue
Suite 230
San Jose, CA 95125
EMail: rmonsour@hifn.com
9. Appendix: Compression Efficiency versus Datagram Size
The following table offers some guidance on the compression
efficiency that can be achieved as a function of datagram size. Each
entry in the table shows the compression ratio that was achieved when
LZS was applied to a test file using datagrams of a specified size.
The test file was the University of Calgary Text Compression Corpus
[Calgary]. The Calgary Corpus consists of 18 files with a total size
(all files) of 3.278MB.
Datagram size,|
bytes | 64 128 256 512 1024 2048 4096 8192 16384
--------------|----------------------------------------------------
Compression |1.18 1.28 1.43 1.58 1.74 1.91 2.04 2.11 2.14
ratio |
10. Full Copyright Statement
Copyright (C) The Internet Society (1998). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
ISO Plain Language
On this page
§1What This Memo Adds to IPComp
RFC 2395 defines how the LZS compression algorithm is applied to the payloads of IP datagrams. It is a companion to the IP Payload Compression Protocol, RFC 2393, which defines how lossless compression is applied to IP payloads in the first place. This memo supplies the algorithm and the parameters used to negotiate it; it does not restate the protocol.
The algorithm comes from Hi/fn, which developed LZS from a sliding window compression history similar to Lempel and Ziv's 1977 algorithm. LZS is a general purpose lossless algorithm that works with a wide variety of data types, and its encoding is efficient enough to compress strings as short as two octets in length.
On licensing, the memo states that Hi/fn holds patents on the LZS algorithm. Licences for a reference implementation are available for use in IPPCP, IPSec, TLS and PPP applications at no cost. Source and object licences are available on a non-discriminatory basis, and hardware implementations are also available.
The IP Payload Compression Protocol says how to compress a packet's contents, but it needs a specific algorithm to do it with. This memo names that algorithm, LZS, and says how the two negotiate it. The algorithm's owner, Hi/fn, holds patents on it and offers licences for a reference implementation at no cost.
§1.2How LZS Compression Works
LZS is a general purpose lossless compression algorithm, developed by Hi/fn from a sliding window compression history similar to Lempel and Ziv's 1977 algorithm. Its encoding method is very efficient, providing compression for strings as short as two octets in length.
The algorithm uses a sliding window of 2,048 bytes. During compression, redundant sequences of data are replaced with tokens that represent those sequences. During decompression, the original sequences are substituted for the tokens in such a way that the original data is exactly recovered. That exact recovery is what separates LZS from lossy compression algorithms, such as those often used for video compression, which do not exactly reproduce the original data.
How much the data shrinks depends on the degree of redundancy in the original data. The memo's appendix measures this against the University of Calgary Text Compression Corpus, a set of 18 files with a total size of 3.278MB, and reports the compression ratio achieved at each datagram size. The measured ratio rises with the size of the datagram, from 1.18 at 64 bytes to 2.14 at 16384 bytes.
LZS looks back over the previous 2,048 bytes of data. When it meets a stretch it has already seen, it writes a short token pointing at that stretch instead of writing the bytes again. On the other side, the receiver uses the token to copy the bytes back, so the data comes out exactly as it went in. The more repetitive the data is, the more the algorithm saves.
| Datagram size in bytes | Compression ratio |
|---|---|
| 64 | 1.18 |
| 128 | 1.28 |
| 256 | 1.43 |
| 512 | 1.58 |
| 1024 | 1.74 |
| 2048 | 1.91 |
| 4096 | 2.04 |
| 8192 | 2.11 |
| 16384 | 2.14 |
§2Compressing and Decompressing a Datagram
Two rules govern what the sender does with each datagram, and both exist for the same reason: to keep datagrams independent of one another.
- The sender MUST reset the compression history before processing each datagram's payload. This ensures that each datagram's payload can be decompressed independently of any other, as is needed when datagrams are received out of order.
- The sender MUST flush the compressor each time it transmits a compressed datagram. Flushing means that all data going into the compressor is included in the output, so no data is held back in the hope of achieving better compression. Flushing is necessary to prevent a datagram's data from spilling over into a later datagram.
The input to the algorithm is an IP datagram payload, and the output is a new, and hopefully smaller, payload. The output payload holds the input payload's data in either compressed or uncompressed format, and the input and output payloads are each an integral number of bytes in length. If the uncompressed form is used, the output payload is identical to the input payload and the IPComp header is omitted. If the compressed form is used, the output payload is prepended with the IPComp header and encoded as the memo defines.
The receiver mirrors the sender. If the received datagram is compressed, the receiver MUST reset the decompression history before processing the datagram, and then decompresses the Payload Data field according to the encoding specified in section 3.2 of ANSI X3.241-1994. If the received datagram is not compressed, the receiver performs no decompression processing and the Payload Data field is ready for processing by the next protocol layer.
Each packet is compressed on its own. The sender empties its memory of earlier data before starting, and it sends everything it has compressed rather than holding some back for a better ratio later. That way the receiver can unpack a packet without needing the packets before it, so packets can arrive in any order.
§2.2The Encoded Stream Format
The compressed stream is a sequence of compressed strings followed by an end marker. Each compressed string starts with a single bit that says what follows: a zero means the next item is a raw byte, and a one means the next item is a compressed reference. A compressed reference is an offset and a length. The offset is either 7 bits long or 11 bits long, told apart by a leading bit: a one gives a 7-bit offset, and a zero gives an 11-bit offset. The length is coded in a variable number of bits and covers the values 2 through 24.
The end marker is the bit sequence 110000000. A datagram payload compressed using LZS always ends with the last compressed data byte, also known as the end marker, and that marker is used to disambiguate padding. This allows trailing bits as well as trailing bytes to be considered padding. The size of a compressed payload MUST be in whole octet units.
The compressed data is a run of items, each either a literal byte or a reference to an earlier stretch, and it ends with a fixed marker of nine bits. The marker tells the receiver where the compressed data stops and the padding starts, so padding can be counted in bits rather than only in whole bytes.
<Compressed Stream> := [<Compressed String>] <End Marker>
<Compressed String> := 0 <Raw Byte> | 1 <Compressed Bytes>
<Raw Byte> := <b><b><b><b><b><b><b><b> (8-bit byte)
<Compressed Bytes> := <Offset> <Length>
<Offset> := 1 <b><b><b><b><b><b><b> | (7-bit offset)
0 <b><b><b><b><b><b><b><b><b><b> (11-bit offset)
<End Marker> := 110000000
<b> := 1 | 0
<Length> :=
00 = 2 1111 0110 = 14
01 = 3 1111 0111 = 15
10 = 4 1111 1000 = 16
1100 = 5 1111 1001 = 17
1101 = 6 1111 1010 = 18
1110 = 7 1111 1011 = 19
1111 0000 = 8 1111 1100 = 20
1111 0001 = 9 1111 1101 = 21
1111 0010 = 10 1111 1110 = 22
1111 0011 = 11 1111 1111 0000 = 23
1111 0100 = 12 1111 1111 0001 = 24
1111 0101 = 13 ...§4IPComp Association Parameters and Thresholds
Several parameters decide how LZS is used with IPComp.
- Negotiation. ISAKMP MAY be used to negotiate the use of the LZS compression method to establish an IP Comp Association. The LZS Transform ID is
IPCOMP_LZS, as specified in the Internet IP Security Domain of Interpretation, and this value is what negotiates the LZS compression algorithm under the ISAKMP protocol. - Other ISAKMP attributes. There are no other parameters required for LZS compression negotiated under ISAKMP.
- Manual configuration. The CPI value
IPCOMP_LZSis used for a manually configured IPComp Compression Association. - Minimum packet size threshold. As IPComp states, small packets may not compress well. Informal tests using the LZS algorithm over the Calgary Corpus data set show that the average payload size that may produce expanded data is approximately 90 bytes. Implementations may therefore not want to attempt to compress payloads smaller than 90 bytes.
- Compressibility test. There is no adaptive algorithm embodied in the LZS algorithm for compressibility testing, as IPComp refers to.
Two ends can agree to use LZS: through ISAKMP, using the name IPCOMP_LZS, or by configuring it by hand with the same value. Beyond that, the memo gives one practical warning. A packet under about 90 bytes is likely to come out larger than it went in, so it is not worth compressing one.
§5Security Considerations
The memo's security section is one sentence long: it does not add any further security considerations beyond those that the IPComp specification has already declared. Everything about the security of compressed IP payloads is therefore left where IPComp put it.
The acknowledgements note that the LZS details presented here are similar to those in the PPP LZS-DCP Compression Protocol, so an implementation already handling that case has most of the work done. The authors also thank the participants of the IPPCP working group mailing list, whose discussion was working to generate the protocol specification for integrating compression with IP.
This memo adds nothing new about security. It leaves the question to the IP Payload Compression Protocol, which sets out the rules for compressed packets. It also notes that the format here is close to the one already used for compressing PPP links.