One document matched: draft-ietf-pppext-stacker-03.txt
Differences from draft-ietf-pppext-stacker-02.txt
Network Working Group Robert Lutz
Internet Draft Stac Electronics
W A Simpson
Daydreamer
expires in six months March 1995
PPP Stacker LZS Compression Protocol |
draft-ietf-pppext-stacker-03.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 |
ftp.is.co.za (Africa)
nic.nordu.net (Europe)
ds.internic.net (US East Coast)
ftp.isi.edu (US West Coast)
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.
Lutz & Simpson expires in six months [Page i]
DRAFT Stacker LZS March 1995
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, with single or multiple compression histories, for
compressing PPP encapsulated packets.
Lutz & Simpson expires in six months [Page ii]
DRAFT Stacker LZS March 1995
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 & Simpson expires in six months [Page 1]
DRAFT Stacker LZS March 1995
2. LZS Packets
Before any LZS packets may be communicated, PPP must reach the
Network-Layer Protocol phase, and the Compression 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 4021 (Stacker |
LZS). |
When LZS is negotiated as the primary compression algorithm, the PPP |
Protocol field indicates type hex 00FB (link compressed datagram), or
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
Lutz & Simpson expires in six months [Page 2]
DRAFT Stacker LZS March 1995
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 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 & Simpson expires in six months [Page 3]
DRAFT Stacker LZS March 1995
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 & Simpson expires in six months [Page 4]
DRAFT Stacker LZS March 1995
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 & Simpson expires in six months [Page 5]
DRAFT Stacker LZS March 1995
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 & Simpson expires in six months [Page 6]
DRAFT Stacker LZS March 1995
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 & Simpson expires in six months [Page 7]
DRAFT Stacker LZS March 1995
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 & Simpson expires in six months [Page 8]
DRAFT Stacker LZS March 1995
Chair's Address
The working group can be contacted via the current chair:
Fred Baker
Cisco Systems |
519 Lado Drive |
Santa Barbara, California 93111 |
EMail: fred@cisco.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
Email: 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 & Simpson expires in six months [Page 9]
DRAFT Stacker LZS March 1995
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:26:05 |