Internet Draft November 1996 (Expires May 1997)
M. Sabin, Consultant
R. Monsour, Hi/fn Inc.
LZS Payload Compression Transform for ESP
<draft-sabin-lzs-payload-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 are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted 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).
It is intended that a future version of this draft be submitted to
the IESG for publication as an Informational RFC. Comments about
this draft should be submitted to the authors or to the IPSEC mailing
list (ipsec@tis.com).
Abstract
This memo proposes a "payload compression transform" based on the LZS
compression algorithm. The transform can be used to compress the
payload field of an IP datagram that uses the Encapsulating Security
Payload (ESP) format. The compression transform proposed here is
stateless, meaning that a datagram can be decompressed independently
of any other datagram. Compression is performed prior to the
encryption operation of ESP, which has the side benefit of reducing
the amount of data that must be encrypted.
This memo anticipates a forthcoming draft of ESP that will supercede
[Atkins96]. The forthcoming draft will allow for ESP payloads to be
compressed via transforms such as the one described in this memo.
Sabin, et al [Page 1]
INTERNET DRAFT LZS Compression for ESP November 1996
Acknowledgments
The LZS details presented here are similar to those in "PPP Stac LZS
Compression Protocol," by R. Friend and W. A. Simpson [RFC-1974].
The authors wish to thank the many participants of the IPSEC mailing
list whose discussion made possible the architecture for integrating
compression with ESP.
Table of Contents
1. Introduction
2. Format of Transformed Payload
3. Compression Procedure
4. Decompression Procedure
5. Security Considerations
6. References
7. Author's Addresses
8. Appendix: Compression Efficiency versus Datagram Size
1. Introduction
Encrypted data is random in nature and not compressible. When an IP
datagram is encrypted, compression methods used at lower protocol
layers -- e.g., PPP compression [RFC-1962] -- no longer work. If
both compression and encryption are desired, compression must be
performed first.
A side benefit of compressing the data first is that the amount of
data which must be encrypted is reduced. In some implementations,
compression is done in hardware and encryption is done in software,
and this can represent a significant reduction in software overhead.
The Encapsulating Security Payload (ESP) format is well suited to
combining compression with encryption, for a variety of reasons:
- ESP is the place were encryption is applied to an IP datagram.
It is straightforward to precede the encryption step by an
optional compression step. The compression step transforms an
uncompressed ESP payload into a compressed ESP payload. This
"payload compression transform" can be independently defined and
used with any ESP transform.
- ESP provides a security parameters index (SPI) that links a
datagram to security parameters negotiated elsewhere. A
destination uses the SPI to look up the ESP transform needed to
decode an incoming datagram. If compression details are included
among the negotiated parameters, a destination can also use the
SPI to look up the compression transform needed to decode the ESP
Sabin, et al [Page 2]
INTERNET DRAFT LZS Compression for ESP November 1996
payload.
This memo proposes a payload compression transform based on the LZS
compression algorithm. The transform can be used to compress any ESP
payload. The transform is stateless, meaning that the payload of a
datagram can be decompressed independently of any other datagram.
This is important in IP, where the delivery of individual datagrams
is not guaranteed.
1.1 Background of LZS Compression
The LZS algorithm is a lossless compression method that 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 schemes, such as
those often used for video compression, that do not exactly
reproduce the original data.
Details of LZS formatting 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.2 Licensing
Source and object licenses for LZS 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.3 Requirements Terminology
In this document, the words that are used to define the
significance of each particular requirement are usually
capitalized. These words are:
- MUST: This word, or the adjective "REQUIRED," means that the
item is an absolute requirement of the specification.
- SHOULD: This word, or the adjective "RECOMMENDED," means
that there might exist valid reasons in particular
circumstances to ignore this item, but the full implications
should be understood and the case carefully weighed before
taking a different course.
Sabin, et al [Page 3]
INTERNET DRAFT LZS Compression for ESP November 1996
- MAY: This word, or the adjective "OPTIONAL," means that the
item is truly optional. One vendor might choose to include the
item because of a particular marketplace requirement or because
it enhances the product, while another vendor might omit the
item.
2. Format of Transformed Payload
The input to the payload compression transform is a payload to be
encapsulated by ESP. The output of the transform is a new payload of
following format:
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| CC | |
+-+-+-+-+-+-+-+-+ |
| |
| Payload Data (compressed or uncompressed) |
| |
| +-+-+-+-+-+-+-+-|
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
2.1 Compression Control
The Compression Control (CC) field is a single, bit-mapped byte.
The bits are numbered 7 (most significant) to 0 (least
significant). The following bits are defined:
- COMPRESSED (bit 7)
This bit is set to 1 to indicate the payload is compressed. It
is cleared to 0 to indicate the payload is not compressed.
- HIST_RESET (bit 6)
This bit is set to 1 to indicate that the compression history
associated with this datagram's SPI was reset prior to
processing this datagram's payload. It is cleared to 0 to
indicate the compression history was not reset.
In order to make the transform stateless between datagrams, the
sender MUST reset the compression history prior to processing
each datagram's payload. Thus, the HIST_RESET bit MUST be set
to 1 in every datagram. (The HIST_RESET bit is defined here
for upwards compatibility with future transforms that may allow
Sabin, et al [Page 4]
INTERNET DRAFT LZS Compression for ESP November 1996
statefulness.)
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 Payload Data
The Payload Data is either compressed or uncompressed. The value
of the COMPRESSED bit of the CC field is set accordingly. The
Payload Data field is an integral number of bytes in length.
3. Compression Procedure
The compression procedure consists of the following steps:
i) The sender resets the compression history and sets the
HIST_RESET bit of the CC field to 1.
ii) The sender decides whether or not to compress the payload.
- If the sender chooses to compress the payload, the LZS
algorithm is applied. The resulting compressed data is
formatted according to [ANSI94]. The COMPRESSED bit of the CC
field is set to 1.
- If the sender chooses not to compress the payload, the
COMPRESSED bit of the CC field is set to 0.
An implementation SHOULD monitor the results of the payload
compression operation and reject the operation if it results in
expansion. In such a case, the uncompressed payload SHOULD be
transmitted with the COMPRESSED bit set to 1.
After the payload has been transformed by these steps, the
transformed payload is submitted to the encode procedure of the
selected ESP transform.
4. Decompression Procedure
Prior to applying the decompression procedure, the decode procedure
of the selected ESP transform is applied to extract the payload.
The decompression procedure consists of the following steps:
Sabin, et al [Page 5]
INTERNET DRAFT LZS Compression for ESP November 1996
i) The receiver checks the HIST_RESET bit of the CC field. If
HIST_RESET = 1, the decompression history is reset. If HIST_RESET
= 0, the datagram is discarded.
ii) The receiver checks the COMPRESSED bit of the CC field. If
COMPRESSED = 1, the LZS decompression algorithm is applied to the
payload data. If COMPRESSED = 0, decompression is not applied.
5. Security Considerations
Security issues are not discussed in this memo.
6. References
[ANSI94] American National Standards Institute, Inc., "Data
Compression Method for Information Systems," ANSI X3.241-1994,
August 1994.
[Atkins96] Atkinson, R., "IP Encapsulating Security Protocol,"
RFC-xxxx, June 1996.
[Calgary] Text Compression Corpus, University of Calgary, available
at
ftp://ftp.cpsc.ucalgary.ca/pub/projects/text.compression.corpus.
[RFC-1962] Rand, D., "The PPP Compression Control Protocol (CCP),"
RFC-1962, June 1996.
[RFC-1974] Friend, R., and Simpson, W.A., "PPP Stac LZS Compression
Protocol," RFC-1974, August 1996.
7. Authors' Addresses
Michael Sabin
883 Mango Avenue
Sunnyvale, CA 94087
Email: mike.sabin@worldnet.att.net
Robert Monsour
Hi/fn Inc.
12636 High Bluff Drive
San Diego, CA 92130
Email: rmonsour@earthlink.net
8. Appendix: Compression Efficiency versus Datagram Size
The following table offers some guidance on the compression
Sabin, et al [Page 6]
INTERNET DRAFT LZS Compression for ESP November 1996
efficiency that can be achieved as a function of datagram size. Each
entry in the table shows the compression ratio that was achieved when
the proposed transform 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,| 64 128 256 512 1024 2048 4096 8192 16384
bytes |
--------------|----------------------------------------------------
Compression |1.18 1.28 1.43 1.58 1.74 1.91 2.04 2.11 2.14
ratio |
Sabin, et al [Page 7]