One document matched: draft-ietf-pppext-stacker-02.txt
Differences from draft-ietf-pppext-stacker-01.txt
Network Working Group Robert Lutz
Internet Draft Stac Electronics
W A Simpson
Daydreamer
expires in six months September 1994
PPP Stacker LZS Compression Protocol |
draft-ietf-pppext-stacker-02.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, and 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.''
To learn the current status of any Internet-Draft, please check the |
``1id-abstracts.txt'' listing contained in the internet-drafts Shadow |
Directories on ds.internic.net (US East Coast), nic.nordu.net |
(Europe), ftp.isi.edu (US West Coast), or munnari.oz.au (Pacific |
Rim).
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
Lutz expires in six months [Page i]
DRAFT Stacker LZS September 1994
algorithm, with single or multiple compression histories, for
compressing PPP encapsulated packets.
Lutz expires in six months [Page ii]
DRAFT Stacker LZS September 1994
1. Introduction
Starting with a sliding window compression history, similar to LZ1
[3], Stac Electronics developed a new, enhanced compression algorithm
identified as Stacker 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 Stacker LZS 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 at the address and phone number listed with the author's
address for further information.
Lutz expires in six months [Page 1]
DRAFT Stacker LZS September 1994
2. LZS Packets
Before any LZS packets may be communicated, PPP must reach the
Network-Layer Protocol phase, and the CCP Control Protocol must reach
the Opened state.
Exactly one LZS 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 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 MUST be compressed, in the same fashion
as when Protocol-Field-Compression is negotiated.
The PPP Protocol number is followed by the original Information
field. The length of the Information field before compression MUST
NOT exceed the link Maximum Receive Unit (MRU).
PPP Link Control Protocol packets MUST NOT be sent within compressed
data.
Padding
The LZS Information field alway ends with the <End Marker>, which
is used to disambiguate padding. This allows trailing bits as
well as octets to be considered padding.
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:
- 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
Lutz expires in six months [Page 2]
DRAFT Stacker LZS September 1994
sequence requirement between different History Numbers.
To enable this feature, the implementation MAY rely on the Reset-
Request and Reset-Ack messages of the Compression Control
Protocol. The Data field of the CCP Reset-Request and Reset-Reply
contains the two octet History Number to be reset, most
significant octet first.
Alternatively, the implementation MAY utilize a reliable link, as
described in "PPP Reliable Transmission" [4].
The transmitter MAY reset a Compression History at any time. The
receiver is implicitly notified of this event, and the
decompression history will automatically be affected.
The transmitter MUST reset a history after a CCP Reset-Request for
a given History Number.
Data Expansion
The maximum expansion of Stacker LZS 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.
When the expansion plus compression header exceeds the size of the
peer's MRU for the link, the PPP packet MUST be sent without
compression, in the original PPP packet form. If history
checkpointing is not used, the transmitter resets the altered
history.
If it is detected that most packets are expanding (probably due to
the use of already compressed data), then the transmitter SHOULD
stop sending compressed packets, and reset its history on its next
compressed data packet.
Lutz expires in six months [Page 3]
DRAFT Stacker LZS September 1994
2.1. Packet Format
A summary of the Stacker LZS packet 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| PPP Protocol | (History Number) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| (Check Value) | Compressed Data ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
PPP Protocol
The PPP Protocol field is described in the Point-to-Point Protocol
Encapsulation [1].
When the Stacker LZS 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.
History Number
The number of the compression history which was used, ranging from |
2 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.
Check Value
By default, no check is added to the packet.
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.
A two octet Cyclic Redundancy Check (CRC) MAY be used, instead of
the LCB, after successful negotiation of the CRC option. The CRC
MUST be initialized to FFFF(hex) at the beginning of each packet,
and is based on the HDLC FCS-16 polynomial:
Lutz expires in six months [Page 4]
DRAFT Stacker LZS September 1994
x^16 + x^12 + x^5 + 1
The ones compliment of the CRC is transmitted least significant
octet first, which contains the coefficient of the highest term.
A one octet Sequence Number MAY be used, instead of a LCB or CRC,
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, or the LCB or CRC
is invalid, a CCP Reset-Request is sent, containing the full two
octet History Number (which is one (1) when no History Number is
present).
Future valid compressed packets are ignored, for that history
only, until a CCP Reset-Ack packet is received.
The Sequence Number is not reset by the transmitter when the
Reset-Ack is sent. Therefore, each new received detection of an
out of sequence packet MUST increment the Identifier of the CCP
Reset-Request. The receiver MUST continue ignoring valid
compressed packets for a particular history, until the correct
Reset-Ack Identifier for that History Number is received.
Compressed Data
The compressed PPP encapsulated packet.
When the sender does not add Padding [1], any trailing zero octets
are removed prior to transmission. A single trailing zero octet
is appended upon receipt, after removal of any framing FCS.
Lutz expires in six months [Page 5]
DRAFT Stacker LZS September 1994
2.2. Compressed Data |
<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 ...
Lutz expires in six months [Page 6]
DRAFT Stacker LZS September 1994
3. Configuration Option Format
Description
The CCP Stacker-LZS Configuration Option negotiates the use of
Stacker LZS on the link. By default or ultimate disagreement, no
compression is used.
A summary of the Stacker-LZS 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length | History Count |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Check Mode |
+-+-+-+-+-+-+-+-+
Type
17 |
Length
5
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.
The value 1 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.
Lutz expires in six months [Page 7]
DRAFT Stacker LZS September 1994
Check Mode |
The Check Mode indicates support of LCB, CRC or Sequence checking.
0 None (default)
1 LCB
2 CRC
3 Sequence Number
Security Considerations
Security issues are not discussed in this memo.
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.
Lutz expires in six months [Page 8]
DRAFT Stacker LZS September 1994
Chair's Address
The working group can be contacted via the current chair:
Fred Baker
Advanced Computer Communications
315 Bollay Drive
Santa Barbara, California 93117
EMail: fbaker@acc.com
Author's Address
Questions about this memo can also be directed to:
Robert Lutz
Stac Electronics
5993 Avenida Encinas
Carlsbad, CA 92008
(619)431-7474
stac/stac/bobl%stac_electronics@mcimail.com
William Allen Simpson |
Daydreamer |
Computer Systems Consulting Services |
1384 Fontaine |
Madison Heights, Michigan 48071 |
Bill.Simpson@um.cc.umich.edu |
bsimpson@MorningStar.com |
Lutz expires in six months [Page 9]
DRAFT Stacker LZS September 1994
Table of Contents
1. Introduction .......................................... 1
1.1 Licensing ....................................... 1
2. LZS Packets ........................................... 2
2.1 Packet Format ................................... 4
2.2 Compressed Data ................................. 6
3. Configuration Option Format ........................... 7
SECURITY CONSIDERATIONS ...................................... 8
REFERENCES ................................................... 8
CHAIR'S ADDRESS .............................................. 9 |
AUTHOR'S ADDRESS ............................................. 9
| PAFTECH AB 2003-2026 | 2026-04-22 14:25:48 |