Network Working Group Kevin Schneider
Internet Draft ADTRAN, Inc.
expires May 1995
PPP LZS-DCP Compression Protocol (LZS-DCP)
draft-ietf-pppext-lzs-dcp-00.txt
Status of this Memo
This document is a submission to the Point-to-Point Protocol Working
Group of the Internet Engineering Task Force (IETF). Comments should
be submitted to the ietf-ppp@merit.edu mailing list.
Distribution of this memo is unlimited.
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. Internet Drafts may be updated, replaced, or obsoleted by
other documents at any time. It is not appropriate to use Internet
Drafts as reference material, or to cite them other than as a
``working draft'' or ``work in progress.''
Please check the 1id-abstracts.txt listing contained in the
internet-drafts Shadow Directories on nic.ddn.mil, ds.internic.net,
vernera.isi.edu, nic.nordu.net, or munnari.oz.au to learn the current
status of any Internet Draft.
Abstract
The Point-to-Point Protocol (PPP) [1] provides a standard method for
transporting multi-protocol datagrams over point-to-point links.
The PPP Compression Control Protocol [2] provides a method to
negotiate and utilize compression protocols over PPP encapsulated
links.
This document describes the use of the Stacker LZS data compression
algorithm for compressing PPP encapsulated packets, using a DCP
header [6]. To distinguish this protocol from the Standard PPP
Stacker LZS compression protocol [5], it will be referred to as the
LZS-DCP Compression Protocol.
Schneider expires May 1995 [Page i]
DRAFT LZS-DCP November 1994
1. Introduction
Starting with a sliding window compression history, similar to LZ1
[3], Stac Electronics developed a compression algorithm identified as
Stacker LZS. Motorola has proposed a packet format for a portable
data compression protocol known as DCP [6]. This document specifies
a technique for using both the Stacker-LZS algorithm and the DCP
within the context of PPP.
A TR30.1 ad hoc committee is currently working on a standard for data
compression for DSUs. The ad hoc committee has decided to use PPP
for this purpose, but along with a compression protocol that
incorporates the compressor synchronization mechanism proposed in
[6]. This document is a result of that effort. It defines a new
compression protocol, LZS-DCP, to be used under CCP. This
compression protocol defines a DCP compatible data format for the
Stacker-LZS data compression algorithm. A notable difference between
LZS-DCP and other non-DCP compression protocols is that LZS-DCP uses
the Reset-Request and Reset-Ack bits in the DCP header instead of the
CCP Reset-Request and Reset-Ack packets to keep the compressor and
decompressor synchronized.
The Stacker LZS-DCP compression algorithm supports both single
compression history communication and multiple compression history
communication.
A single compression history will require the minimum amount of
memory to implement, but may not provide as much compression as a
multiple history implementation.
Often, many streams of information are interleaved over the same
link. Each virtual link will transmit data that is independent of
other virtual links. Using multiple compression histories can
improve the compression ratio of a communication link by associating
separate compression histories with separate virtual links of
communication.
1.1. Licensing
Source and object licenses are available on a non-discriminatory
basis. Hardware implementations are also available. Contact Stac
Electronics for further information.
1.2. Specification of Requirements
In this document, several words are used to signify the requirements
Schneider expires May 1995 [Page 1]
DRAFT LZS-DCP November 1994
of the specification. These words are often capitalized.
MUST This word, or the adjective "required", means that the
definition is an absolute requirement of the specification.
MUST NOT This phrase means that the definition is an absolute
prohibition of the specification.
SHOULD This word, or the adjective "recommended", means that there
may exist valid reasons in particular circumstances to
ignore this item, but the full implications must be
understood and carefully weighed before choosing a
different course.
MAY This word, or the adjective "optional", means that this
item is one of an allowed set of alternatives. An
implementation which does not include this option MUST be
prepared to interoperate with another implementation which
does include the option.
1.3. Terminology
This document frequently uses the following terms:
datagram The unit of transmission in the network layer (such as IP).
A datagram may be encapsulated in one or more packets
passed to the data link layer.
frame The unit of transmission at the data link layer. A frame
may include a header and/or a trailer, along with some
number of units of data.
packet The basic unit of encapsulation, which is passed across the
interface between the network layer and the data link
layer. A packet is usually mapped to a frame; the
exceptions are when data link layer fragmentation is being
performed, or when multiple packets are incorporated into a
single frame.
peer The other end of the point-to-point link.
silently discard
This means the implementation discards the packet without
further processing. The implementation SHOULD provide the
capability of logging the error, including the contents of
the silently discarded packet, and SHOULD record the event
Schneider expires May 1995 [Page 2]
DRAFT LZS-DCP November 1994
in a statistics counter.
2. LZS-DCP Packets
Before any LZS-DCP packets are communicated, PPP must reach the
Network-Layer Protocol phase, and the CCP Control Protocol must reach
the Opened state.
Exactly one LZS-DCP datagram is encapsulated in the PPP Information
field, where the PPP Protocol field indicates type hex 00FD
(compressed datagram).
The maximum length of the LZS-DCP 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 ID Field. Protocol-Field-Compression MAY be used on this
value, if has been sucessfully negotiated for the link.
The PPP Protocol ID Field is followed by the original Information
field. The length of the uncompressed data field is limited only by
the allowed size of the compressed data field and the higher protocol
layers.
PPP Link Control Protocol packets MUST NOT be sent within LZS-DCP
packets. PPP Network Control Protocol packets MUST NOT be sent
within LZS-DCP packets.
Padding
PPP padding is not allowed in a LZS-DCP packet. However, on
compressed packets, padding may be accomplished by extending the
data field with zeros following the <End Marker> (see Section
2.1.1). This is referred to as LZS Padding. The LCB, if present,
is always the octet preceding the frame CRC.
Reliability and Sequencing
When no Compression History is kept, the algorithm does not depend
on a reliable link, and does not require that packets be delivered
in sequence. However, per packet compression results in a lower
compression ratio than it could be on a stream.
Some reasons for resetting the history on a per packet basis
include:
Schneider expires May 1995 [Page 3]
DRAFT LZS-DCP November 1994
- The link has a high error rate.
- The resources of the transmitter or receiver limit the ability
to maintain a compression history between packets.
When Compression Histories are negotiated, the packet sequence
MUST be preserved within specific History Numbers. There is no
sequence requirement between different History Numbers.
To enable this feature, the implementation MUST rely on the Reset-
Request and Reset-Ack bits of this protocol. These signalling
bits apply to the history number of the packet containing them.
This requires that the history number field be the same size in
both directions of a link. Any data in the packet is processed
after the signalling bits are processed.
The transmitter MAY reset a Compression History at any time.
Because the Stacker-LZS algorithm is a sliding window algorithm,
the decompressor does not require an explicit notification of the
reset event.
The transmitter MUST reset a history after a Reset-Request for a
given History Number.
Data Expansion
The maximum expansion of Stacker LZS-DCP is 12.5%.
A Maximum Receive Unit (MRU) MAY be negotiated that is 12.5%
larger than the size of a normal packet. Then, packets can always
be sent compressed regardless of expansion.
The transmitter MAY send an uncompressed LZS-DCP packet at any
time, although the typical use of uncompressed LZS-DCP packets is
as an anti-expansion mechanism.
When the expansion plus compression header exceeds the size of the
peer's MRU for the link, the data MUST be sent as an uncompressed
LZS-DCP packet.
An uncompressed LZS-DCP packet is transmitted according to the
format shown in Section 2.1, with the C/U bit set to 0
(Uncompressed-Data). If the Configuration Option Field 'Process
Mode', is set to a value of 1 (Process-Uncompressed), uncompressed
LZS-DCP packets are processed by both the compressor and the
decompressor, updating the histories of each. If the Process Mode
Field is set to a value of 0 (None), AND the compressor has
modified its history before sending the uncompressed packet, the
Schneider expires May 1995 [Page 4]
DRAFT LZS-DCP November 1994
compressor history must be reset. (Reset is not required if the
compressor history can be restored to its previous state.)
2.1. Packet Format
A summary of the LZS-DCP packet format is shown below. The fields
are transmitted from left to right.
0 1 2
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| PPP Protocol | DCP-Header |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| (History Number) | (Seq Num) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Data ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| (LCB) |
+-+-+-+-+-+-+-+-+
PPP Protocol
The PPP Protocol field is described in the Point-to-Point Protocol
Encapsulation [1].
When the LZS-DCP compression protocol is successfully negotiated
by the PPP Compression Control Protocol [2], the value is 00FD
hex. This value MAY be compressed when Protocol-Field-
Compression is negotiated.
DCP-Header
The DCP-Header is nominally one octet in length, but may be
extended through the use of the extension bit.
The format of the DCP-Header is as follows:
0 1 2 3 4 5 6 7
+-----+-----+-----+-----+-----+-----+-----+-----+
| E | C/U | R-A | R-R | Res | Res | Res | C/D |
+-----+-----+-----+-----+-----+-----+-----+-----+
E - Extension Bit
The E bit is the extension bit. If set to 0, it indicates that
another octet of the DCP-Header is present. Currently, this
Schneider expires May 1995 [Page 5]
DRAFT LZS-DCP November 1994
bit is always set to 1, since the DCP-Header field is only one
octet long.
C/U - Compressed/Uncompressed Bit
The C/U indicates whether the data field contains compressed or
uncompressed data. A value of 1 indicates compressed data
(often referred to as a compressed packet), and a value of 0
indicates uncompressed data (or an uncompressed packet).
R-A - Reset-Ack R-R - Reset-Request
The DCP-Header includes Reset-Request and Reset-Ack Bits in
order to provide a mechanism for indicating a decompression
failure in one direction of a compressed link without affecting
traffic in the other direction. A decompression failure MAY be
determined using the sequence number and/or LCB mechanism.
To indicate a decompression failure, an implementation MUST
transmit a packet with the Reset-Request Bit set to 1. The
Data field MAY be filled with data, compressed or uncompressed,
or be left empty. Once a Reset-Request has been sent, the data
in any compressed packets received is discarded until a packet
containing a Reset-Ack is received. It is the responsibility
of the receiver to ensure the reliability of the reset
request-acknowledge mechanism. This may require the
transmission of an additional Reset-Request before a Reset-Ack
will be received.
Upon reception of a packet containing a Reset-Request, the
transmitting compressor MUST be reset to an initial state,
which includes resetting or clearing the history buffer. If
the data field of the packet containing the Reset-Request
contains data, it is delivered to the local receiver as a
normal data packet. In addition to the reset of the
compressor, a packet MUST be transmitted with Reset-Ack bit set
to 1. The data field of this packet MUST be filled with data.
If no data is ready for transmission, the transmitter MUST wait
until data is ready before sending the Reset-Ack.
On receipt of a Reset-Ack, the receiving decompressor MAY be
reset to an initial state. (A reset is not required since the
incoming data packets will not reference the old history
buffer). After reset, any compressed or uncompressed data
contained in the packet is processed.
Reset-Requests and Reset-Acks are specific to the history
number of the packet containing them.
Schneider expires May 1995 [Page 6]
DRAFT LZS-DCP November 1994
Res - Reserved
These bits are reserved and MUST be set to 0
C/D - Control/Data
This bit is used by DCP to provide in-band negotiation in
applications where out-of-band negotiation methods are not
provided. Since CCP provides an out of band negotiating
mechanism, this feature is not used in this application. All
packets MUST set this bit to a value of 0, which signifies that
the packet is a data packet. (Packets containing only Reset-
Requests are classified as data packets.)
History Number
The number of the compression history which was used, ranging from
1 to the negotiated History Count.
If the negotiated History Count is less than 2, this field is
removed. If the negotiated History Count is 2 or more, but less
than 256, this field is 1 octet. If 256 or more histories are
negotiated, this field is 2 octets, most significant octet first.
If multiple histories are used in one direction on a link, the
history number field MUST be present on all packets in both
directions, and sized according to the largest number of histories
in either direction.
If multiple histories are used, this field MUST be present in
uncompressed as well as compressed packets.
Sequence Number
A one octet Sequence Number MAY be used, after successful
negotiation of the Sequence Number option. The Sequence Number
begins with one (1), and wraps to zero (0). This number is
relative to the History Number used.
On receipt, if Sequence Number one (1) follows any other number
than zero (0), or is otherwise out of sequence, a Reset-Request is
sent, in a packet containing the same History Number as that which
detected a packet out of sequence.
Future valid compressed packets are ignored, for that history
only, until a packet containing a Reset-Ack is received.
Schneider expires May 1995 [Page 7]
DRAFT LZS-DCP November 1994
The Sequence Number is not reset by the transmitter when a packet
containing a Reset-Ack is sent. The decompressor should
resynchronize (reset) its local sequence number counter when a
packet containing a Reset-Ack is received.
Sequence numbers are used on all packets, compressed or
uncompressed. Therefore, the receiver increments its counter upon
receiving an LZS-DCP packet, whether it contains compressed or
uncompressed data.
Data
This field contains uncompressed or compressed data, depending on
the state of the C/U bit in the Header. This length of this field
is always an integer number of octets.
For compressed packets, the data field MUST begin with a complete
codeword and end with the <End Marker> (see Section 2.1.1), which
may be followed with additional octets containing only zeros.
There MUST be only one <End Marker> per packet. To save on
bandwidth, any trailing zero octets may be removed prior to
transmission. A single trailing zero octet is appended upon
receipt, after removal of any framing FCS and the LCB, if present.
Longitudinal Check Byte
A simple one octet Longitudinal Check Byte (LCB) MAY be used,
after successful negotiation of the LCB option. The LCB MUST be
initialized to FF(hex) at the beginning of each packet, and is the
Exclusive-OR of each octet of the original uncompressed data.
The LCB is only included on compressed packets, and is always
located in the octet immediately prior to the frame CRC.
On receipt, if the LCB is invalid, a Reset-Request is sent, in a
packet containing the same History Number as that which was
detected with the invalid LCB.
Schneider expires May 1995 [Page 8]
DRAFT LZS-DCP November 1994
2.1.1. Compressed Data
The Stacker-LZS compression algorithm is Defined in ANSI X3.241 [7].
The format of the compressed data is repeated here for informational
purposes.
<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 ...
3. Configuration Option Format
The LZS-DCP Configuration Option negotiates the use of LZS-DCP on the
link. By default or ultimate disagreement, no compression is used.
This Configuration Option is used in CCP, and can be used in other
negotiation mechanisms.
The default values listed below were chosen by the TR30.1 ad hoc
committee on compression of synchronous data. All implementations
must support the default values.
A summary of the LZS-DCP Configuration Option format is shown below.
The fields are transmitted from left to right.
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
Schneider expires May 1995 [Page 9]
DRAFT LZS-DCP November 1994
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length | History Count |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Check Mode | Process Mode |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type
23
Length
6
History Count
The History Count field is two octets, most significant octet
first, and specifies the maximum number of Compression Histories.
The value 0 indicates that the implementation expects the peer to
reset the Compression History at the beginning of every packet.
If this value is seleted, the transmitter MUST set the Reset-Ack
bit of every packet that contains compressed data.
The value 1 is the default value and is used to indicate that only
one history is maintained.
Other valid values range from 2 to 65535. The peer is not
required to send as many histories as the implementation indicates
that it can accept.
Check Mode
The Check Mode indicates support of LCB and/or Sequence checking.
The use of check mode None (0) is discouraged for history counts
greater than zero.
0 None
1 LCB
2 Sequence Number
3 Sequence Number + LCB (default)
Process Mode
The Process Mode specifies how uncompressed packets are handled.
A value of None (0) indicates that uncompressed packets are not
processed by the decompressor. A value of Process-Uncompressed
Schneider expires May 1995 [Page 10]
DRAFT LZS-DCP November 1994
(1) indicates that uncompressed packets are processed by the
decompressor to update the history.
0 None (default)
1 Process-Uncompressed
Security Considerations
Security issues are not discussed in this memo.
Acknowledgements
This document is based on, and uses much of the text of [5].
References
[1] Simpson, W., Editor, "The Point-to-Point Protocol (PPP)", STD
51, RFC 1661, Daydreamer, July 1994.
[2] Rand, D., "The PPP Compression Control Protocol (CCP)", work
in progress.
[3] Lempel, A. and Ziv, J., "A Universal Algorithm for Sequential
Data Compression", IEEE Transactions On Information Theory,
Vol. IT-23, No. 3, May 1977.
[4] Rand, D., "PPP Reliable Transmission", RFC 1663, Novell, July
1994.
[5] Lutz, B., Simpson, B. "PPP Stacker LZS Compression Protocol",
work in progress.
[6] Motorola Information Systems Group, "Data Compression Protocol
(DCP) Proposal", TR-30.1 ad hoc contribution (email
reflector), September 21, 1994.
[7] ANSI X3.241, "American National Standard Data Compression
Method, Adaptive Coding with Sliding Window fo Information
Interchange", currently unpublished.
Schneider expires May 1995 [Page 11]
DRAFT LZS-DCP November 1994
Chair's Address
The working group can be contacted via the current chair:
Fred Baker
Senior Software Engineer
Cisco Systems
519 Lado Drive
Santa Barbara, California 93111
(805) 681-0115
EMail: fred@cisco.com
Author's Address
Questions about this memo can also be directed to:
Kevin Schneider
Adtran, Inc.
901 Explorer Blvd.
Huntsville, AL 25806
(205) 971-8024
Email: kevin@adtran.com
Schneider expires May 1995 [Page 12]
DRAFT LZS-DCP November 1994
Table of Contents
1. Introduction .......................................... 1
1.1 Licensing ....................................... 1
1.2 Specification of Requirements ................... 1
1.3 Terminology ..................................... 2
2. LZS-DCP Packets ....................................... 3
2.1 Packet Format ................................... 5
2.1.1 Compressed Data ................................. 9
3. Configuration Option Format ........................... 9
SECURITY CONSIDERATIONS ...................................... 11
REFERENCES ................................................... 11
CHAIR'S ADDRESS ........................................... 12
AUTHOR'S ADDRESS ............................................. 12
