Internet Draft R. Monsour
Expires in six months Hi/fn, Inc.
July 29, 1997
IP Payload Compression Using LZS
<draft-ietf-ippcp-lzs-00.txt>
Status of this Memo
This document is an Internet-Draft. Internet Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas,
and its working Groups. Note that other groups may also distribute
working documents as Internet Drafts.
Internet-Drafts draft documents are valid for a maximum of six months
and may be updated, replaced, or obsolete by other documents at any
time. It is inappropriate to use Internet-Drafts as reference material
or to cite them other than as "work in progress."
To learn the current status of any Internet-Draft, please check the
"1id-abstracts.txt" listing contained in the Internet-Drafts Shadow
Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
ftp.isi.edu (US West Coast).
Distribution of this memo is unlimited.
It is intended that a future version of this draft be submitted to the
IESG for publication as an Informational RFC.
Abstract
This document describes a IP compression method based on the LZS
compression algorithm. This document defines the application of the
LZS algorithm to the IP Payload Compression Protocol [Thomas].
[Thomas] defines a method for applying lossless compression to the
payloads of Internet Protocol datagrams.
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.
Table of Contents
R. Monsour [Page 1]
Internet Draft draft-ietf-ippcp-lzs-00.txt July 29, 1997
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 Anti-expansion of Payload Data.............................3
2.3 Format of Compressed Datagram Payload......................4
2.4 Compression Encoding Format................................5
2.5 Padding....................................................6
3. Decompression Process..........................................6
4. Security Considerations........................................6
5. References.....................................................6
6. Authors Addresses..............................................8
7. Appendix: Compression Efficiency versus Datagram Size..........8
1. Introduction
1.1 General
This document is a submission to the IETF IP Payload Compression
Protocol (IPPCP) Working Group. Comments are solicited and should be
addressed to the working group mailing list (ippcp@external.cisco.com)
or to the editor.
This document specifies the application of LZS compression, a lossless
compression algorithm, to IP datagram payloads. It is to be used in
conjunction with the IP Payload Compression Protocol which, at this
writing, is under development by the IP Payload Compression Protocol
working group.
1.2 Background of LZS Compression
Starting with a sliding window compression history, similar to LZ1
[LZ1], Hi/fn developed a new, enhanced compression algorithm
identified as LZS. The LZS algorithm is optimized to compress all file
types as efficiently as possible. Even string matches as short as two
octets are effectively compressed.
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
R. Monsour [Page 2]
Internet Draft draft-ietf-ippcp-lzs-00.txt July 29, 1997
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 typical compression ratio is 2:1.
LZS achieves a compression ratio of 2.34:1 on the University of
Calgary Text Compression Corpus [Calgary].
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 author's address.
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 RFC2119 [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 Anti-expansion of Payload Data
The maximum expansion produced by the LZS algorithm is 12.5%.
R. Monsour [Page 3]
Internet Draft draft-ietf-ippcp-lzs-00.txt July 29, 1997
If the size of a compressed IP datagram, including whatever overhead
is included to define the compression protocol, is not smaller than
the size of the original IP datagram, the IP datagram MUST be sent in
the original non-compressed form. This policy ensures saving the
decompression processing cycles and avoiding incurring IP datagram
fragmentation when the expanded datagram is larger than the MTU.
Small IP datagrams are more likely to expand as a result of
compression. Therefore, a numeric threshold SHOULD be applied before
compression, where IP datagrams of size smaller than the threshold are
sent in the original form without attempting compression. The numeric
threshold is implementation dependent.
An IP datagram with payload, which has been previously compressed,
tends not to compress any further. Such previously compressed payload
may be the result of external processes, such as compression applied
by an upper layer in the communication stack, or by an off-line
compression utility. An adaptive algorithm SHOULD be implemented in
order to avoid the performance penalty of futile compression attempts.
Such as adaptive algorithm is implementation dependent and independent
of compression method.
2.3 Format of Compressed Datagram Payload
The following is an example datagram that results when using LZS as
the compression algorithm for the IP Payload Control Protocol. Note
that the IP header has been omitted for clarity.
0 1 2 3
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Compression Parameters Index (CPI) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|C| Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Payload Data (variable) ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Compression Parameters Index (CPI)
The Compression Parameters Index (CPI) is a 32-bit pseudo-random
value identifying the association for this datagram. The details of
its use can be found in [Thomas].
C
R. Monsour [Page 4]
Internet Draft draft-ietf-ippcp-lzs-00.txt July 29, 1997
This one-bit field, when one, indicates that the datagram payload is
compressed; a value of zero indicates that the datagram payload is
not compressed.
Reserved
This 31-bit field is reserved for future use and MUST be zeroed by
the sender. It SHOULD be ignored by the receiver.
Payload Data
This variable-length field contains the optionally compressed
datagram payload.
2.4 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. If the compressed form is used, the output payload
as defined in section 3.2 of [ANSI94], and 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
R. Monsour [Page 5]
Internet Draft draft-ietf-ippcp-lzs-00.txt July 29, 1997
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.5 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.
3. Decompression Process
If the C bit of the received datagram is a one (i.e., indicating the
datagram is compressed), the receiver MUST reset the compression
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
compression history, the receiver decompresses the Payload Data field
according to the encoding specified in section 3.2 of [ANSI94].
If the C bit of the received datagram is zero, 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. Security Considerations
This memo discusses the use of lossless compression technology in the
Internet Protocol. This can include use of IP Security. The proposed
use of compression within this protocol is not believed to have an
effect on the underlying security functionality provide by the
protocol; i.e., the use of compression is not known to degrade or
alter the nature of the underlying security architecture or the
encryption technologies used to implement it.
The use of compression does change the length of ESP payloads, in a
manner that depends on the data prior to encryption. Thus, the use of
compression may have an effect on the ability of an eavesdropper to
glean information by analyzing the length of transmitted packets.
5. References
[AH] Kent, S. and Atkinson, R., "IP Authentication Header", draft-
ietf-ipsec-auth-header-01.txt, Work in Progress, July 1997.
R. Monsour [Page 6]
Internet Draft draft-ietf-ippcp-lzs-00.txt July 29, 1997
[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.
[DOI] Piper, D., "The Internet IP Security Domain of Interpretation
for ISAKMP", draft-ietf-ipsec-ipsec-doi-02.txt, Work in Progress,
February 1997.
[ESP] Kent, S. and Atkinson, R., "IP Encapsulating Security Payload",
draft-ietf-ipsec-esp-v2-00.txt, Work in Progress, July 1997.
[ISAKMP] Maughan, D., Schertler, M., Schneider, M., and Turner, J.,
"Internet Security Association and Key Management Protocol (ISAKMP)",
draft-ietf-ipsec-isakmp-08.txt, Work in Progress, July 1997.
[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-1700] Reynolds, J., Postel, J., "Assigned Numbers", RFC 1700,
October 1994.
[RFC-1883] Deering, S., Hinden, R., "Internet Protocol, Version 6
(IPv6) Specification", RFC 1883, April 1996.
[RFC-1962] Rand, D., "The PPP Compression Control Protocol (CCP)",
RFC-1962, June 1996.
[RFC-1967] K. Schneider, 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", RFC 2119, March 1997.
[Shacham] Shacham, A., "IP Payload Compression Protocol (IPComp)",
draft-ietf-ippcp-protocol-00.txt, Work in Progress, July 1997.
[Thayer] Thayer, R., "Compression Payload for Use with IP Security",
draft-thayer-seccomp-01.txt, Work in Progress, March, 1997.
[Thomas] Thomas, M., "The Compressed Payload Header", draft-thomas-
R. Monsour [Page 7]
Internet Draft draft-ietf-ippcp-lzs-00.txt July 29, 1997
ippcp-compression-00.txt, Work in Progress, July 1997.
6. Authors Addresses
Robert Monsour
Hi/fn Inc.
5973 Avenida Encinas
Suite 110
Carlsbad, CA 92008
Email: rmonsour@hifn.com
7. 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 length of the file prior to compression was 3,278,000
bytes. When the entire file was compressed as a single payload, a
compression ratio of 2.34 resulted.
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 |
R. Monsour [Page 8]
