Network Working Group R. Price
Internet-Draft R. Hancock
Expires: August 2, 2002 S. McCann
A. Surtees
P. Ollis
M. West
Siemens/Roke Manor
February 2002
Framework for EPIC-LITE
draft-ietf-rohc-epic-lite-01.txt
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026.
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."
The list of current Internet-Drafts can be accessed at http://
www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on August 2, 2002.
Copyright Notice
Copyright (C) The Internet Society (2002). All Rights Reserved.
Abstract
This draft describes the framework of the Efficient Protocol
Independent Compression (EPIC-LITE) scheme.
The RObust Header Compression ROHC [1] scheme is designed to compress
packet headers over error prone channels. It is built around an
extensible core framework that can be tailored to compress new
protocol stacks by adding additional ROHC profiles.
Price, et al. Expires August 2, 2002 [Page 1]
Internet-Draft Framework for EPIC-LITE February 2002
EPIC-LITE extends the basic ROHC framework by introducing a BNF-based
input language that simplifies the creation of new ROHC [1] profiles.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . 8
2. Terminology . . . . . . . . . . . . . . . . . . . . . . 8
3. The EPIC-LITE framework for generating new ROHC profiles 10
3.1 Structure of the EPIC-LITE compressed headers . . . . . 10
3.2 Compression and decompression procedures . . . . . . . . 11
3.3 BNF input language for creating new ROHC profiles . . . 14
3.4 Huffman compression . . . . . . . . . . . . . . . . . . 15
4. Overview of the BNF input language for EPIC-LITE . . . . 16
4.1 Information stored at compressor and decompressor . . . 18
4.2 Generated data . . . . . . . . . . . . . . . . . . . . . 19
5. Library of EPIC-LITE encoding methods . . . . . . . . . 20
5.1 STATIC . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.2 IRREGULAR . . . . . . . . . . . . . . . . . . . . . . . 21
5.2.1 IRREGULAR-PADDED . . . . . . . . . . . . . . . . . . . . 21
5.3 VALUE . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.4 LSB . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.5 UNCOMPRESSED . . . . . . . . . . . . . . . . . . . . . . 22
5.6 STACK encoding methods . . . . . . . . . . . . . . . . . 23
5.6.1 STACK-TO-CONTROL . . . . . . . . . . . . . . . . . . . . 23
5.6.2 STACK-FROM-CONTROL . . . . . . . . . . . . . . . . . . . 23
5.6.3 STACK-PUSH-MSN . . . . . . . . . . . . . . . . . . . . . 23
5.6.4 STACK-POP-MSN . . . . . . . . . . . . . . . . . . . . . 24
5.6.5 STACK-ROTATE . . . . . . . . . . . . . . . . . . . . . . 24
5.7 INFERRED encoding methods . . . . . . . . . . . . . . . 24
5.7.1 INFERRED-TRANSLATE . . . . . . . . . . . . . . . . . . . 24
5.7.2 INFERRED-SIZE . . . . . . . . . . . . . . . . . . . . . 25
5.7.3 INFERRED-OFFSET . . . . . . . . . . . . . . . . . . . . 25
5.7.4 INFERRED-IP-CHECKSUM . . . . . . . . . . . . . . . . . . 26
5.8 NBO . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5.9 SCALE . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.10 OPTIONAL . . . . . . . . . . . . . . . . . . . . . . . . 27
5.11 MANDATORY . . . . . . . . . . . . . . . . . . . . . . . 28
5.12 CONTEXT . . . . . . . . . . . . . . . . . . . . . . . . 28
5.13 LIST . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.13.1 LIST-NEXT . . . . . . . . . . . . . . . . . . . . . . . 30
5.14 FLAG encoding methods . . . . . . . . . . . . . . . . . 31
5.14.1 N flag . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.14.2 U flag . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.15 FORMAT . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.16 CRC . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.17 MSN encoding methods . . . . . . . . . . . . . . . . . . 34
5.17.1 MSN-LSB . . . . . . . . . . . . . . . . . . . . . . . . 34
5.17.2 MSN-IRREGULAR . . . . . . . . . . . . . . . . . . . . . 34
Price, et al. Expires August 2, 2002 [Page 2]
Internet-Draft Framework for EPIC-LITE February 2002
5.17.3 SET-MSN . . . . . . . . . . . . . . . . . . . . . . . . 34
6. Creating a new ROHC profile . . . . . . . . . . . . . . 35
6.1 Profile identifier . . . . . . . . . . . . . . . . . . . 35
6.2 Maximum number of header formats . . . . . . . . . . . . 35
6.3 Control of header alignment . . . . . . . . . . . . . . 36
6.4 Compressed header formats . . . . . . . . . . . . . . . 36
7. Security considerations . . . . . . . . . . . . . . . . 37
8. Acknowledgements . . . . . . . . . . . . . . . . . . . . 37
References . . . . . . . . . . . . . . . . . . . . . . . 37
Authors' Addresses . . . . . . . . . . . . . . . . . . . 38
A. EPIC-LITE compressor and decompressor . . . . . . . . . 39
A.1 Compressor . . . . . . . . . . . . . . . . . . . . . . . 49
A.1.1 Step 1: Packet classification . . . . . . . . . . . . . 49
A.1.2 Step 2: Using the state machine . . . . . . . . . . . . 50
A.1.3 Step 3: Compressing the header . . . . . . . . . . . . . 50
A.1.4 Step 4: Determining the indicator flags . . . . . . . . 53
A.1.5 Step 5: Encapsulating in ROHC packet . . . . . . . . . . 56
A.2 Decompressor . . . . . . . . . . . . . . . . . . . . . . 56
A.2.1 Step 1: Decapsulating from ROHC packet . . . . . . . . . 56
A.2.2 Step 2: Running the state machine . . . . . . . . . . . 56
A.2.3 Step 3: Reading the indicator flags . . . . . . . . . . 56
A.2.4 Step 4: Decompressing the fields . . . . . . . . . . . . 59
A.2.5 Step 5: Verifying correct decompression . . . . . . . . 60
A.3 Offline processing . . . . . . . . . . . . . . . . . . . 61
A.3.1 Step 1: Building the header formats . . . . . . . . . . 61
A.3.2 Step 2: Generating the indicator flags . . . . . . . . . 66
A.4 Library of methods . . . . . . . . . . . . . . . . . . . 73
A.4.1 STATIC . . . . . . . . . . . . . . . . . . . . . . . . . 73
A.4.2 IRREGULAR . . . . . . . . . . . . . . . . . . . . . . . 74
A.4.2.1 IRREGULAR-PADDED . . . . . . . . . . . . . . . . . . . . 75
A.4.3 VALUE . . . . . . . . . . . . . . . . . . . . . . . . . 76
A.4.4 LSB . . . . . . . . . . . . . . . . . . . . . . . . . . 77
A.4.5 UNCOMPRESSED . . . . . . . . . . . . . . . . . . . . . . 79
A.4.6 STACK encoding methods . . . . . . . . . . . . . . . . . 80
A.4.6.1 STACK-TO-CONTROL . . . . . . . . . . . . . . . . . . . . 80
A.4.6.2 STACK-FROM-CONTROL . . . . . . . . . . . . . . . . . . . 81
A.4.6.3 STACK-PUSH-MSN . . . . . . . . . . . . . . . . . . . . . 82
A.4.6.4 STACK-POP-MSN . . . . . . . . . . . . . . . . . . . . . 83
A.4.6.5 STACK-ROTATE . . . . . . . . . . . . . . . . . . . . . . 84
A.4.7 INFERRED encoding methods . . . . . . . . . . . . . . . 84
A.4.7.1 INFERRED-TRANSLATE . . . . . . . . . . . . . . . . . . . 84
A.4.7.2 INFERRED-SIZE . . . . . . . . . . . . . . . . . . . . . 86
A.4.7.3 INFERRED-OFFSET . . . . . . . . . . . . . . . . . . . . 86
A.4.7.4 INFERRED-IP-CHECKSUM . . . . . . . . . . . . . . . . . . 87
A.4.8 NBO . . . . . . . . . . . . . . . . . . . . . . . . . . 88
A.4.9 SCALE . . . . . . . . . . . . . . . . . . . . . . . . . 90
A.4.10 OPTIONAL . . . . . . . . . . . . . . . . . . . . . . . . 91
A.4.11 MANDATORY . . . . . . . . . . . . . . . . . . . . . . . 92
Price, et al. Expires August 2, 2002 [Page 3]
Internet-Draft Framework for EPIC-LITE February 2002
A.4.12 CONTEXT . . . . . . . . . . . . . . . . . . . . . . . . 93
A.4.13 LIST . . . . . . . . . . . . . . . . . . . . . . . . . . 94
A.4.13.1 LIST-NEXT . . . . . . . . . . . . . . . . . . . . . . . 98
A.4.14 FLAG encoding methods . . . . . . . . . . . . . . . . . 101
A.4.14.1 N . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
A.4.14.2 U . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
A.4.15 FORMAT . . . . . . . . . . . . . . . . . . . . . . . . . 103
A.4.16 CRC . . . . . . . . . . . . . . . . . . . . . . . . . . 106
A.4.16.1 MSN-LSB . . . . . . . . . . . . . . . . . . . . . . . . 106
A.4.16.2 MSN-IRREGULAR . . . . . . . . . . . . . . . . . . . . . 109
A.4.16.3 SET-MSN . . . . . . . . . . . . . . . . . . . . . . . . 110
A.5 ABNF description of the input language . . . . . . . . . 110
Full Copyright Statement . . . . . . . . . . . . . . . . 113
Price, et al. Expires August 2, 2002 [Page 4]
Internet-Draft Framework for EPIC-LITE February 2002
1. Introduction
This document describes a plug-in extension for the ROHC [1]
framework which simplifies the creation of new compression profiles.
The Efficient Protocol Independent Compression (EPIC-LITE) scheme for
generating new ROHC profiles takes as its input a choice of one or
more compression techniques for each field in the protocol stack to
be compressed. Using this input EPIC-LITE derives a set of
compressed header formats that can be used to quickly and efficiently
compress and decompress headers.
Chapter 2 explains some of the terminology used in the draft.
Chapter 3 gives an overview of the EPIC-LITE scheme.
Chapter 4 describes the language used by EPIC-LITE to create new
profiles.
Chapter 5 considers the basic techniques available in the EPIC-
LITE library of compression routines.
Chapter 6 specifies the parameters used to define a ROHC [1]
profile.
Appendix A gives a normative description of EPIC-LITE in
pseudocode.
2. Terminology
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 RFC-2119 [5].
Profile
A ROHC [1] profile is a description of how to compress a certain
protocol stack over a certain type of link. Each profile includes
one or more sets of compressed header formats and a state machine
to control the compressor and the decompressor.
Context
The context is memory which stores one or more previous values of
fields in the uncompressed header. The compressor and
decompressor both maintain a copy of the context, and fields can
be compressed relative to their stored values for better
Price, et al. Expires August 2, 2002 [Page 5]
Internet-Draft Framework for EPIC-LITE February 2002
compression efficiency.
Compressed header format
A compressed header format describes how to compress each field in
the chosen protocol stack. It consists of two parts: a bit
pattern to indicate to the decompressor which format is being
used, followed by a list of the compressed versions of each field.
Encoding method
An encoding method is a procedure for compressing fields.
Examples include STATIC encoding (field is the same as the
context), INFERRED-OFFSET encoding (field is calculated at the
decompressor) and IRREGULAR encoding (field must be transmitted in
full).
Indicator flags
Each EPIC-LITE compressed packet contains a set of indicator
flags. The flags are placed at the front of the packet as a
single bit pattern, and indicate to the decompressor exactly which
encoding method has been applied to which field.
Set of compressed header formats
A complete set of compressed header formats uses up all of the
indicator bit patterns available at the start of the compressed
header. A profile may have several sets of compressed header
formats available, but only one set can be in use at a given time.
Library of encoding methods
The library of encoding methods contains a number of commonly used
procedures that can be called to compress fields in the chosen
protocol stack. More encoding methods can be added to the library
if they are needed.
BNF (Backus Naur Form)
BNF is a "metasyntax" commonly used to describe the syntax of
protocols and languages.
BNF input language
EPIC-LITE describes a new ROHC profile using a simple BNF-based
input language. The BNF description of the ROHC profile assigns
one or more encoding methods to each field in the chosen stack.
Price, et al. Expires August 2, 2002 [Page 6]
Internet-Draft Framework for EPIC-LITE February 2002
Control data
The term 'control data' refers to any data passed between the
compressor and decompressor, that is not part of the uncompressed
header. An example of control data is the header checksum
calculated by EPIC-LITE over the uncompressed header to ensure
robustness against bit errors and dropped packets.
3. The EPIC-LITE framework for generating new ROHC profiles
This chapter outlines the EPIC-LITE framework for the creation of new
ROHC profiles.
3.1 Structure of the EPIC-LITE compressed headers
Each compressed header is divided into two distinct parts: the
indicator flags and the compressed fields as illustrated below:
+---+---+---+---+--------------------+--------------------+---
| 0 | 1 | 1 | 0 | Compressed Field 1 | Compressed Field 2 |...
+---+---+---+---+--------------------+--------------------+---
\ \ / / \ /
\ \ / / \ /
Indicator Flags Compressed Fields
Figure 1 : Structure of an EPIC-LITE compressed header
The indicator flags specify how every field in the uncompressed
header has been compressed, whilst the compressed fields contain
enough information to transmit each field from the compressor to the
decompressor. This information might be the entire uncompressed
field, it might be LSBs (Least Significant Bits) of the uncompressed
field etc.
Note that for simplicity EPIC-LITE always places the indicator flags
at the front of the compressed header followed by each complete
compressed field in turn. As for RFC-1144 [3] the compressed fields
are in reverse order compared to the uncompressed header (this is a
useful trick to speed up parsing at the decompressor).
Unlike other compression schemes, the header formats used by EPIC-
LITE are not designed by hand but instead are generated automatically
using a special algorithm. This means that EPIC-LITE can be applied
to any protocol stack provided that it has been correctly programmed
using the BNF-based input language described in Section 3.3.
Price, et al. Expires August 2, 2002 [Page 7]
Internet-Draft Framework for EPIC-LITE February 2002
3.2 Compression and decompression procedures
Figure 2 illustrates the processing which is done by EPIC-LITE for
each header to be compressed and decompressed. Note that references
are given to pseudocode in Appendix A which describes each of the
stages explicitly.
---------------------------------------------------------------------
Price, et al. Expires August 2, 2002 [Page 8]
Internet-Draft Framework for EPIC-LITE February 2002
| Uncompressed packet Uncompressed packet ^
v |
+-------------------+ +-------------------+
| Selecting the | | Verifying correct |
| context | | decompression |
| (Section A.1.1) | | (Section A.2.5) |
+-------------------+ +-------------------+
| ^
| Uncompressed packet Uncompressed packet |
v Context |
+-------------------+ +-------------------+
| Running the | | Decompressing |
| state machine | | the fields |
| (Section A.1.2) | | (Section A.2.4) |
+-------------------+ +-------------------+
| Set of header formats Chosen format ^
| Uncompressed packet Compressed fields |
v Context Context |
+-------------------+ +-------------------+
| Compressing | | Reading the |
| the fields | | indicator flags |
| (Section A.1.3) | | (Section A.2.3) |
+-------------------+ +-------------------+
| ^
| Chosen format Compressed header |
v Compressed fields Context |
+-------------------+ +-------------------+
| Determining the | | Running the |
| indicator flags | | state machine |
| (Section A.1.4) | | (Section A.2.2) |
+-------------------+ +-------------------+
| ^
| Compressed header Compressed header |
v Context |
+-------------------+ +-------------------+
| Encapsulating in | |Decapsulating from |
| ROHC packet | ---------------> | ROHC packet |
| (Section A.1.5) | ROHC | (Section A.2.1) |
+-------------------+ packet +-------------------+
Figure 2: EPIC-LITE compression/decompression
---------------------------------------------------------------------
Each of these steps is described in more detail below.
At the compressor:
Price, et al. Expires August 2, 2002 [Page 9]
Internet-Draft Framework for EPIC-LITE February 2002
Step 1: The input to the compressor is simply an uncompressed packet
(with known length). In order to compress the packet it is first
necessary to classify it and choose the context relative to which the
packet will be compressed. If no suitable context is available then
an existing context must be overwritten.
Step 2: Once the context has been chosen the compressor knows which
ROHC [1] profile will be used to compress the packet. In particular
it can run the state machine that determines which set of header
formats will be used to compress the packet (IR, IR-DYN or CO).
Step 3: Given the uncompressed packet and a set of compressed header
formats, the compressor can choose a header format to robustly carry
this information to the decompressor using as few bits as possible.
Note that EPIC-LITE chooses the header format simultaneously with
compressing the header to improve the overall speed of compression.
Step 4: Each compressed header format has a unique set of indicator
flags that communicate to the decompressor which format is in use.
The compressor determines these indicator flags and appends them to
the front of the compressed fields to create a compressed header.
Step 5: Once the compressed header has been calculated, the
compressor encapsulates it within a ROHC packet by adding 0 or more
octets of context identifier together with any padding and
segmentation that is required.
At the decompressor:
Step 1: The input to the decompressor is a ROHC packet. From this
packet the decompressor can determine the attached context
identifier, which in turn specifies the context relative to which the
packet should be decompressed.
Step 2: Once the context has been identified, the decompressor can
run the state machine to determine if the packet may be decompressed.
Step 3: The decompressor then reads the indicator flags in the header
to determine which compressed header format has been used. This
allows the compressed value of each field to be extracted.
Step 4: Using the compressed value of each field and the context, the
decompressor can apply the encoding methods to reconstruct the
uncompressed packet. Note that fields are decompressed in reverse
order to compression (this ensures that fields which are inferred
from other field values are reconstructed correctly).
Step 5: Finally, the decompressor verifies that correct decompression
Price, et al. Expires August 2, 2002 [Page 10]
Internet-Draft Framework for EPIC-LITE February 2002
has occurred by applying the header checksum. If the packet is
successfully verified then it can be forwarded.
3.3 BNF input language for creating new ROHC profiles
EPIC-LITE is a protocol-independent compression scheme because it can
generate new compressed header formats automatically using a special
algorithm. In order for EPIC-LITE to compress a new protocol stack
however, it must be given a description of how the stack behaves.
EPIC-LITE uses a simple BNF-based input language for the fast
creation of new compression schemes. The language is designed to be
easy to use without detailed knowledge of the mathematics underlying
EPIC-LITE. The only information required to create a new ROHC [1]
profile using EPIC-LITE is a description of how the chosen protocol
stack behaves.
EPIC-LITE converts the input into one or more sets of compressed
header formats that can be used by a ROHC [1] compressor and
decompressor. As with all version of BNF the input language has a
rule-based structure, which makes it easy to build new profiles out
of existing ones (e.g. when adding new layers to a protocol stack).
Figure 3 describes the process of building a set of compressed header
formats from the BNF input, which is done once only and the results
stored at the compressor and decompressor. References are given to
pseudocode in Appendix A which describes the various stages
explicitly.
Price, et al. Expires August 2, 2002 [Page 11]
Internet-Draft Framework for EPIC-LITE February 2002
---------------------------------------------------------------------
+-----------------------+
| Input Stage 1: |
| Resolve input |
| into set of compressed|
| header formats |
| (Section A.3.1) |
+-----------------------+
|
v
+-----------------------+
| Input Stage 2: |
| Run Huffman algorithm |
| to generate flags |
| (Section A.3.2) |
+-----------------------+
Figure 3: Building EPIC-LITE compressed header formats
---------------------------------------------------------------------
Note that since the EPIC-LITE compressed header formats can be
generated offline, the fact that profiles are specified using an
input language does not affect the processing requirements of
compression and decompression.
3.4 Huffman compression
Huffman compression [2] is a well known technique used in many
popular compression schemes. EPIC-LITE uses ordinary Huffman
compression to generate a new set of compressed header formats.
The basic Huffman algorithm is designed to compress an arbitrary
stream of characters from a character set such as ASCII. The idea is
to create a new set of compressed characters, where each normal
character maps onto a compressed character and vice versa. Common
characters are given shorter compressed equivalents than rarely used
characters, reducing the average size of the data stream.
EPIC-LITE uses Huffman compression to generate the indicator flags
for each compressed header format. Each format is treated as one
character in the Huffman character set, so more common compressed
header formats are indicated using fewer bits than rare header
formats. The most commonly used header format is often indicated by
the presence of a single "0" flag at the front of the compressed
header.
Price, et al. Expires August 2, 2002 [Page 12]
Internet-Draft Framework for EPIC-LITE February 2002
The following chapters describe the mechanisms of EPIC-LITE in
greater detail.
4. Overview of the BNF input language for EPIC-LITE
This chapter describes the BNF-based input language provided by EPIC-
LITE for the creation of new ROHC [1] profiles.
The language is designed to be flexible but at the same time easy to
use without detailed knowledge of the mathematics underlying EPIC-
LITE. The only requirement for writing an efficient EPIC-LITE
profile is a description of how the relevant protocol stack behaves.
As with all versions of BNF, the description of the protocol is built
up using the following two constructs:
New BNF rule A new encoding method is created from existing
ones by writing a new BNF rule for the encoding
method
Set of choices One or more encoding methods can be assigned to
a given field by using the choice ("|") operator
EPIC-LITE also contains a library of fundamental encoding methods
(STATIC compression, LSB compression etc.) as described in Chapter 5.
The BNF description of how to compress a new protocol stack always
resolves into a selection of these fundamental encoding methods.
The exact syntax of the BNF-based input language can itself be
described using an existing version of BNF. A suitable variant is
"Augmented BNF" (ABNF) as described in RFC-2234 [6]. For example, in
ABNF the syntax for defining a new encoding method in terms of
existing ones is as follows:
<encoding_method> = <encoding_name> <ws> "="
1*(<ws> <field_encoding>)
<field_encoding> = <encoding_name>
*(<ws> "|" <ws> <encoding_name>)
Each instance of <encoding_name> calls an encoding method that
converts a certain number of uncompressed bits into a certain number
of compressed bits. Note also that <ws> is white space, used to
delimit the various encoding methods.
A complete description of the BNF-based input language can be found
Price, et al. Expires August 2, 2002 [Page 13]
Internet-Draft Framework for EPIC-LITE February 2002
in Appendix A.5.
An example of how to create a new encoding method is given below. An
encoding method known as IPv6_Header is constructed from the basic
encoding methods available in the library. This new method is
designed to compress an entire IPv6 header.
IPv6_Header_co = Version
Traffic_Class_co
ECT_Flag_co
CE_Flag
Flow_Label_co
Payload_Length
Next_Header
Hop_Limit_co
Source_Address_co
Destination_Address_co
Version = VALUE(4,6,100%)
Traffic_Class = STATIC(100%)
ECT_Flag = STATIC(100%)
CE_Flag = VALUE(1,0,99%) | VALUE(1,1,1%)
Flow_Label = STATIC(100%)
Payload_Length = INFERRED-SIZE(16,288)
Next_Header = STACK-TO-CONTROL(8)
Hop_Limit = STATIC(100%)
Source_Address = STATIC(100%)
Destination_Address = STATIC(100%)
Each field in the IPv6 header is given a choice of possible encoding
methods. If an encoding method is not implicitly used 100% of the
time for that field (e.g. INFERRED-SIZE) then one of the parameters
is the probability that it will be used to encode the field in
question. This is very important since EPIC-LITE ensures that common
encoding methods require fewer bits to carry the compressed data than
rarely used encoding methods.
For optimal compression, the probability should equal the percentage
Price, et al. Expires August 2, 2002 [Page 14]
Internet-Draft Framework for EPIC-LITE February 2002
of time for which the encoding method is selected to compress the
field. Note that there is no requirement for probabilities to add up
to exactly 100%, as EPIC-LITE will automatically scale the
probabilities by a constant factor if they do not.
Note also that the BNF input language is designed to be both human-
readable and machine-readable. If only one protocol stack needs to
be compressed, the input language can simply be converted by hand
directly to an implementation. However, since the input language
provides a complete description of the protocol stack to be
compressed, it is possible to compress headers using only the
information contained in the BNF description and without any
additional knowledge of the protocol stack. This means that it is
possible to implement a protocol-independent compressor that can
download a new ROHC [1] profile described in the BNF input language
and immediately use it to compress headers.
4.1 Information stored at compressor and decompressor
Any ROHC compressor maintains a number of contexts as described in
Section 5.1.3 of ROHC [1]. Each context at the compressor and
decompressor includes the following:
Compression profile: Compressed header formats
State machine
Field values: One or more previously processed headers
The compression profile describes how to compress a certain protocol
stack over a certain type of link. It includes the profile
parameters that describe the set of compressed header formats (as
discussed in Chapter 6) and additionally records the current state of
the state machine.
The compressor also stores one or more sets of field values from
previously processed headers. Each new header can be compressed
relative to these field values to improve the compression ratio.
For the profiles generated using EPIC-LITE, the compressor and
decompressor maintain a context value for some or all of the "field
encodings" specified in the BNF description (recall that a field
encoding is a set of one or more encoding methods that can be used to
compress a given field). This context value is taken from the last
header to be successfully compressed or decompressed.
Furthermore, in order to provide robustness the compressor can
maintain more than one context value for each field. These values
represent the r most likely candidates values for the context at the
Price, et al. Expires August 2, 2002 [Page 15]
Internet-Draft Framework for EPIC-LITE February 2002
decompressor, given that bit errors and dropped packets may prevent
the compressor from being 100% certain exactly which values are
contained in the decompressor context.
EPIC-LITE ensures that the compressed header contains enough
information so that the uncompressed header can be extracted no
matter which one of the compressor context values is actually stored
at the decompressor. The only problem arises if the decompressor has
a context value that does not belong to the set of values stored at
the compressor; this situation is detected by a checksum over the
uncompressed header and the packet is discarded at the decompressor.
If more than one value for a field is stored in the compressor
context, some of the library encoding methods will automatically fail
or only succeed under certain conditions. For example, STATIC
encoding will fail and LSB encoding will only succeed if sufficient
LSBs are sent to infer correct value of the field regardless of the
precise value stored in the decompressor context.
Note that the rules for extracting fields from the uncompressed
header and updating the context values are given in Appendix A.
The number of context values per field to be stored at the compressor
is implementation-specific. Storing more values reduces the chance
that the decompressor will have a context value different from any of
the values stored at the compressor (which could cause the packet to
be decompressed incorrectly). The trade-off is that the compressed
header will be larger because it must contain enough information to
decompress relative to any of the candidate context values.
As an example, an implementation may choose to store the last r
values of each field in the compressor context. In this case
robustness is guaranteed against up to r - 1 consecutive dropped
packets between the compressor and the decompressor.
4.2 Generated data
There is some data that is passed from the compressor to the
decompressor, but which is not present in the uncompressed header.
This data communicates additional information that might be useful to
the decompressor: for example a checksum over the uncompressed header
to ensure correct decompression has occurred.
This data may be generated by certain encoding methods and then added
either to the uncompressed header to be compressed immediately or to
the control data stack to be compressed later.
Price, et al. Expires August 2, 2002 [Page 16]
Internet-Draft Framework for EPIC-LITE February 2002
5. Library of EPIC-LITE encoding methods
The ROHC [1] standard contains a number of different encoding methods
(LSB encoding, scaled timestamp encoding, list-based compression
etc.) for compressing header fields. EPIC-LITE treats these encoding
methods as library functions to be called by the BNF input language
when they are needed.
The following library contains a wide range of basic encoding
methods. Moreover new encoding methods can be added to the library
as and when they are needed.
Note that this chapter contains an informative description only. The
normative pseudocode description of every encoding method can be
found in Appendix A.4.
The syntax of each encoding method is given using ABNF as defined in
RFC-2234 [6]. Note that each of the encoding methods may have one or
more parameters of the following type:
<value> A non-negative integer (specified as decimal,
binary or hex). Binary values are prefixed by 0b
and hex values are preceded by 0x.
<offset> An integer (positive or negative)
<length> A non-negative integer used to indicate the
length of the field being compressed
<probability> A probability expressed as a percentage with at
most 2 decimal places
<encoding_name> The name of another encoding method including
all parameters
The ABNF description of these parameters is found in Appendix A.5.
5.1 STATIC
ABNF notation: "STATIC(" <probability> ")"
The STATIC encoding method can be used when the header field does not
change relative to the context. If a field is STATIC then no
information concerning the field need be transmitted in the
compressed header.
Price, et al. Expires August 2, 2002 [Page 17]
Internet-Draft Framework for EPIC-LITE February 2002
The only parameter for the STATIC encoding method is a probability
that indicates how often the method will be used. Encoding methods
with high probability values require fewer bits in the compressed
header than encoding methods that are allocated low probability
values. In general the probability should reflect as accurately as
possible the chance that the field will be encoded as STATIC.
5.2 IRREGULAR
ABNF notation: "IRREGULAR(" <length> "," <probability> ")"
The IRREGULAR encoding method is used when the field cannot be
compressed relative to the context, and hence must be transmitted in
full in the compressed header.
The IRREGULAR encoding method has a length parameter to indicate the
length of the field in bits and a probability that indicates how
often it will be used.
A modified version of IRREGULAR encoding is given below:
5.2.1 IRREGULAR-PADDED
ABNF notation: "IRREGULAR-PADDED(" <length> "," <value> ","
<probability> ")"
The IRREGULAR-PADDED encoding method compresses any field that is
large in terms of number of bits but has a small actual value (and
hence the most significant bits are zero).
The encoding method transmits a certain number of LSBs (Least
Significant Bits) of the field. The first parameter gives the
overall length of the field, whilst the next parameter specifies the
number of LSBs to be transmitted in the compressed header. The bits
not transmitted are all taken to be 0 by the decompressor. The
probability gives an indication of how often IRREGULAR-PADDED will be
used.
The IRREGULAR-PADDED encoding method is useful for compressing fields
that take small integer values with a high probability.
5.3 VALUE
ABNF notation: "VALUE(" <length> "," <value> "," <probability> ")"
Price, et al. Expires August 2, 2002 [Page 18]
Internet-Draft Framework for EPIC-LITE February 2002
The VALUE encoding method can be used to transmit one particular
value for a field. It is followed by parameters to indicate the
length and integer value of the field as well as the probability of
the field taking this value.
5.4 LSB
ABNF notation: "LSB(" <value> "," <offset> "," <probability> ")"
The LSB encoding method compresses the field by transmitting only its
LSBs (Least Significant Bits).
The first parameter indicates the number of LSBs to transmit in the
compressed header. The second parameter is the offset of the LSBs:
it describes whether the decompressor should interpret the LSBs as
increasing or decreasing the field value contained in its context.
Again the probability indicates how often LSB encoding will be used.
To illustrate how the second parameter works, suppose that k LSBs are
transmitted with offset p. The decompressor uses these LSBs to
replace the k LSBs of the value of this field stored in the context
(val), and then adds or subtracts multiples of 2^k so that the new
field value lies between (val - p) and (val - p + 2^k - 1).
In particular, if p = 0 then the field value can only stay the same
or increase. If p = -1 then it can only increase, whereas if p = 2^k
then it can only decrease.
Recall that for robustness the compressor can store r values for each
field in its context. If this is the case then enough LSBs are
transmitted so that the decompressor can reconstruct the correct
field value, no matter which of the r values it has stored in its
context. This is equivalent to Window-based LSB encoding as
described in ROHC [1].
5.5 UNCOMPRESSED
ABNF notation: "UNCOMPRESSED(" <value> "," <value> "," <value> ","
<value> ")"
The UNCOMPRESSED encoding method transmits a field uncompressed
without alteration. All uncompressed fields are transmitted as-is at
the end of the compressed header.
The UNCOMPRESSED encoding method differs from the IRREGULAR encoding
method in that the size of the field is not fixed, but instead is
Price, et al. Expires August 2, 2002 [Page 19]
Internet-Draft Framework for EPIC-LITE February 2002
specified by a control field. The first parameter gives the length n
of the control field: UNCOMPRESSED encoding obtains this control
field simply by removing the first value (which should be n bits)
from the control data stack.
The next three parameters specify a divisor, multiplier and offset
for the control field. These parameters scale the value of the
control field so that it specifies the exact size of the UNCOMPRESSED
field in bits. If the parameters are d, m and p respectively then:
size of UNCOMPRESSED field = floor(control field value / d) * m + p
UNCOMPRESSED encoding is usually used in conjunction with one of the
STACK encoding methods, which write to the control data stack as
explained below:
5.6 STACK encoding methods
These methods are used to move values around for use by future
encoding methods. They take as a parameter the number of bits to be
transferred and always have 100% probability of being used.
5.6.1 STACK-TO-CONTROL
ABNF notation: "STACK-TO-CONTROL(" <length> ")"
This encoding method takes the specified number of bits from the
uncompressed header and transfers them to the control data stack. It
does the reverse at the decompressor.
5.6.2 STACK-FROM-CONTROL
ABNF notation: "STACK-FROM-CONTROL(" <length> ")"
This encoding method takes an item with the specified number of bits
from the control data stack and transfers it to the uncompressed
header. It does the reverse at the decompressor.
5.6.3 STACK-PUSH-MSN
ABNF notation: "STACK-PUSH-MSN(" <length> ")"
The MSN (Master Sequence Number) is a width defined value that
increases by one for each packet received at the compressor.
Price, et al. Expires August 2, 2002 [Page 20]
Internet-Draft Framework for EPIC-LITE February 2002
This encoding method copies the least significant specified number of
bits of the MSN to the top of the control data stack. Conversely, it
removes these bits at the decompressor.
5.6.4 STACK-POP-MSN
ABNF notation: "STACK-POP-MSN(" <length> ")"
This encoding method removes the specified number of bits of the MSN
from the uncompressed data or adds it at the decompressor.
5.6.5 STACK-ROTATE
ABNF notation: "STACK-ROTATE(" <value> "," <value> ")"
This encoding method rotates the top n items on the top control stack
m times where n is the first parameter and m the second. A rotation
of n items by 1 moves the nth element on the control stack to the top
of the stack (and the top n-1 items down one place).
5.7 INFERRED encoding methods
The following versions of INFERRED encoding are available:
5.7.1 INFERRED-TRANSLATE
ABNF notation: "INFERRED-TRANSLATE(" <length> "," <length> *(","
<value> "," <value>) ")"
The INFERRED-TRANSLATE encoding method translates a field value under
a certain mapping. The first pair of parameters specifies the length
of the field before and after the translation. This is followed by
additional pairs of integers, representing the field value before and
after it is translated. Note that the final field value at the
compressor (or equivalently, the original field value at the
decompressor) appears first in each pair. For example:
INFERRED-TRANSLATE(8,16,41,0x86DD,4,0x0800) ; GRE Protocol
The GRE Protocol field behaves in the same manner as the Next Header
field in other extension headers, except that it indicates that the
subsequent header is IPv6 or IPv4 using the values 0x86DD and 0x0800
instead of 41 and 4. The INFERRED-TRANSLATE encoding method can
convert the standard values (as provided by LIST compression defined
Price, et al. Expires August 2, 2002 [Page 21]
Internet-Draft Framework for EPIC-LITE February 2002
in Section 5.11) into the values required by the GRE Protocol field.
At the compressor, once the translation is complete the field is
copied to the control data stack. At the decompressor the field is
removed from the control data stack, translated and then added to the
uncompressed data.
5.7.2 INFERRED-SIZE
ABNF notation: "INFERRED-SIZE(" <length> "," <offset> ")"
The INFERRED-SIZE encoding method infers the value of a field from
the size of the uncompressed packet.
The first parameter specifies the uncompressed field length in bits,
and the second parameter specifies the offset of the uncompressed
packet size (i.e. the amount of packet which has already been
compressed). If the INFERRED-SIZE field value is v, the offset is p
and the total packet length after (but not including) the INFERRED-
SIZE field is L then the following equation applies (assuming 8 bits
in a byte):
L = 8 * v + p
5.7.3 INFERRED-OFFSET
ABNF notation: "INFERRED-OFFSET(" <length> ")"
The INFERRED-OFFSET encoding method compresses a field that usually
has a constant offset relative to a certain base field.
The parameter describes the length of the field to be compressed.
The base field will already be on the control data stack - put there
using one of the STACK methods.
The encoding subtracts the base field from the field to be compressed
and replaces the field value by these "offset" bits in the
uncompressed header. The offset bits are then compressed by the next
encoding method in the input code.
For example, a typical sequence number can be compressed as follows:
Price, et al. Expires August 2, 2002 [Page 22]
Internet-Draft Framework for EPIC-LITE February 2002
STACK-PUSH-MSN(32) ; Put MSN on control stack
INFERRED-OFFSET(32) ; Sequence Number
STACK-POP-MSN(32) ; Remove MSN
STATIC(99%) | ; Sequence Number offset
LSB(8,-1,0.7%) |
LSB(16,-1,0.2%) |
IRREGULAR(32,0.1%)
In this case the offset field is expected to change rarely and only
by small amounts, and hence it is compressed using mainly STATIC and
LSB encodings.
5.7.4 INFERRED-IP-CHECKSUM
ABNF notation: "INFERRED-IP-CHECKSUM(" <encoding_name> ")"
This method is used for calculating the IP checksum. At the
compressor it replaces the bits representing the IP checksum with "0"
bits (these are a known distance from the beginning of this method).
It then continues to compress using encoding_name. At the
decompressor it decompresses encoding_name as usual. A 16-bit one's
complement sum is then computed over the length of data which has
been decompressed in this method and the result copied into the
appropiate bits (at a fixed offset) in the header.
5.8 NBO
ABNF notation: "NBO(" <length> ")"
The NBO encoding method may be used if there is a possibility that
the following field will be in reverse byte order from the rest of
the header, as is sometimes seen with the IP ID, for example. The
method looks at the specified number of bits (typically 16 or 32)
and, using a history, decides whether or not they are in network byte
order. If they are it removes them from the stack, puts a 1-bit flag
with the value "1" on the stack and replaces the original value. If
the value is not in NBO it removes the bits, puts a flag with the
value "0" on the stack and replaces the byte-swapped value. This
method can be used prior to other methods, for example:
Price, et al. Expires August 2, 2002 [Page 23]
Internet-Draft Framework for EPIC-LITE February 2002
NBO (16) ; Check for network byte order
STACK-PUSH-MSN(16) ; Put MSN on control stack
INFERRED-OFFSET(16) ; IP ID
STACK-POP-MSN(16) ; Remove MSN
STATIC(80%) | ; IP ID offset
LSB(5,-1,15%) |
IRREGULAR(16,5%)
STATIC(99%) | ; NBO flag
IRREGULAR(1,1%)
5.9 SCALE
ABNF notation: "SCALE(" <length> ")"
The SCALE encoding method is used for fields which change by a
regular (usually large) amount every packet. The number of bits
specified are removed and a suitable scale factor chosen. Three
values each with the specified length are then replaced on the stack.
If the original field has value v and the chosen scale is s then
these values are:
v / s = the scaled value of v when v is divided by s using integer
arithmetic
v mod s = the remainder when v is divided by s
s = the scale value
They are placed on the stack in the order above so that the next
value to be compressed is the scale value.
5.10 OPTIONAL
ABNF notation: "OPTIONAL(" <encoding_name> ")"
The OPTIONAL encoding method is used to compress fields that are
optionally present in the uncompressed header.
OPTIONAL encoding requires a 1 bit indicator flag to specify whether
or not the optional field is present in the uncompressed header.
Price, et al. Expires August 2, 2002 [Page 24]
Internet-Draft Framework for EPIC-LITE February 2002
This flag is extracted from the control data stack. The value of the
flag is added to the stack by another encoding method (such as STACK-
TO-CONTROL or LIST). For example:
STACK-TO-CONTROL(1) ; GRE Key flag
OPTIONAL(KEY-ENCODING) ; GRE Key
In this case the encoding method KEY-ENCODING is called to compress
the GRE Key field, but only if the Key Flag is set to 1. If the Key
Flag is set to 0 (indicating that the GRE Key is not present) then
some padding bits of 0 may be added to the compressed header (the
number of bits added is determined by the compressor - the compressor
chooses a format for KEY-ENCODING, which though not used provides the
number of bits with which to pad). If there is a U method
encompassing the OPTIONAL method then the number of bits with which
to pad is automatically zero.
5.11 MANDATORY
ABNF notation: "MANDATORY(" <encoding_name> ")"
This encoding method may be used where another encoding method has
appended a flag indicating the presence of a field in the
uncompressed header. If the field is optionally present then the
OPTIONAL encoding (above) may be used. If the field is always
present then the MANDATORY encoding can be used. This checks that
the value of the flag on the stack is 1 (indicating that the field is
present). If the value of the flag is 0 then the MANDATORY encoding
method will fail.
5.12 CONTEXT
ABNF notation: "CONTEXT(" <encoding_name> "," <value> ")"
The CONTEXT encoding method is used to store multiple copies of the
same field in the context. This encoding method is useful when
compressing fields that take a small number of values with high
probability, but when these values are not known a-priori.
CONTEXT encoding can also be applied to larger fields: even an entire
TCP header. This can be very useful when multiple TCP flows are sent
to the same IP address, as a single ROHC [1] context can be used to
compress the packets in all of the TCP flows.
Price, et al. Expires August 2, 2002 [Page 25]
Internet-Draft Framework for EPIC-LITE February 2002
The first parameter specifies the encoding method that should be used
to compress the field. The second parameter specifies how many
copies of the field should be stored in the context.
CONTEXT encoding applies the specified encoding method to the
uncompressed header, compressing relative to any of the copies of the
field stored in its context. It then appends an "index" value to the
uncompressed header to indicate to the decompressor which context
value should be used for decompression. Consider the following
example using the TCP Window field:
CONTEXT(TCP-WINDOW,4) ; Window
VALUE(2,0,89%) | ; Window context index
VALUE(2,1,10%) |
VALUE(2,2,0.5%) |
VALUE(2,3,0.5%)
At most 4 copies of the Window field can be stored in the context.
The Window field can be compressed relative to any of these values:
the value chosen by the compressor is transmitted to the decompressor
using the "index".
5.13 LIST
ABNF notation: "LIST(" <value> "," <value> "," <value> "," <value>
"," <value> "," <encoding_name> *(","
<encoding_name>) *("," <value>) ")"
The LIST encoding method compresses a list of items that do not
necessarily occur in the same order for every uncompressed header.
Example applications for the LIST encoding method include TCP options
and TCP SACK blocks.
The size of the list is determined by a control field in exactly the
same manner as for UNCOMPRESSED encoding. The first four integer
parameters are defined as in UNCOMPRESSED.
The fifth parameter gives the number of bits which should be read
from the uncompressed_data stack to decide which of the encoding
methods in the list to use to compress the next list item.
These parameters are followed by a set of encoding methods that can
be used to compress individual items in the list and a set of
integers to identify which method to use. If the integer obtained
using the fifth parameter matches the nth integer then use the nth
Price, et al. Expires August 2, 2002 [Page 26]
Internet-Draft Framework for EPIC-LITE February 2002
encoding method.
This continues until data amounting to the size of the list has been
compressed.
Once the list size is reached, LIST encoding appends the order in
which the encoding methods were applied to the uncompressed data and
the presence of data for the methods. The profile defines whether
the order and presence can change in a compressed packet or not. For
example:
LIST(4,1,32,0,8,
OPTIONAL(TCP-SACK),
OPTIONAL(TCP-TIMESTAMP),
OPTIONAL(TCP-END),
OPTIONAL(TCP-GENERIC),
5,8,0) ; TCP Options
STATIC(99.9%) | ; TCP Options order
IRREGULAR(8, 0.1%)
STATIC(75%) | ; TCP Options presence
IRREGULAR(4,25%)
The order in which the methods are applied is irrelevant in the
mapping between methods chosen and the indicator flags. They are
always considered to be compressed in the order in which they appear
in the profile and the order and presence fields deal with the actual
order in which they were processed.
5.13.1 LIST-NEXT
ABNF notation: "LIST-NEXT(" <value> "," <encoding_name> *(","
<encoding_name>) *("," <value>) ")"
LIST-NEXT encoding is similar to basic LIST encoding, except that the
next list item to compress is known a-priori from a control field.
IP extension headers can be compressed using LIST-NEXT.
The first parameter specifies the number of bits to extract from the
control data stack before each list item is compressed. This is
followed by the set of encoding methods available to LIST-NEXT and a
set of 0 or more integers. The nth encoding method can only be
called when the nth integer value is obtained from the control data
stack.
Price, et al. Expires August 2, 2002 [Page 27]
Internet-Draft Framework for EPIC-LITE February 2002
For example:
LIST-NEXT(8, OPTIONAL(AH-ENCODING),
OPTIONAL(ESP-ENCODING),
OPTIONAL(GRE-ENCODING),
OPTIONAL(GENERIC-ENCODING),
51,50,47) ; Header Chain
STATIC(99.9%) | ; Header Chain order
IRREGULAR(8,0.01%)
STATIC(75%) | ; Header Chain presence
IRREGULAR(4,25%)
The IP extension header chain can have a number of specific encoding
methods designed for one type of extension header (AH, ESP or GRE) as
well as a "generic" encoding method that can cope with arbitrary
extension headers but at reduced compression efficiency.
Just as with basic LIST encoding, LIST-NEXT also adds the order in
which the encoding methods are applied and their presence or absence
to the uncompressed header, so that the decompressor can reconstruct
the list in the correct order.
5.14 FLAG encoding methods
The flag encoding methods are used to modify the behavior of another
encoding method. Each flag encoding has a single parameter, which is
the name of another encoding method. The flag encoding method calls
this encoding method, but additionally modifies the input or output
in some manner.
Note that flag encoding methods do not require the original encoding
method to be rewritten (as they only modify its input or output).
5.14.1 N flag
ABNF notation: "N(" <encoding_name> ")"
The N flag runs the encoding method specified by its parameter, with
the exception that it does not update the context. This is useful
when a field takes an unexpected value for one header and then
reverts back to its original behavior in subsequent headers.
An example of the N flag in use is given below:
Price, et al. Expires August 2, 2002 [Page 28]
Internet-Draft Framework for EPIC-LITE February 2002
STATIC(99%) | ; Window
N(LSB(11,2048,0.9%)) |
IRREGULAR(16,0.1%)
In the above example the N flag is applied to the TCP Window field.
The field is compressed by transmitting only the last few LSBs, which
are always interpreted at the decompressor as a decrease in the field
value. However, because the context is not updated the field reverts
back to its original value following the decrease.
5.14.2 U flag
ABNF notation: "U(" <encoding_name> ")"
The U flag changes the destination of any compressed bits produced by
the encoding method specified as its parameter. Instead of putting
them on the compressed_data stack it puts them on the unc_fields
stack. They no longer contribute to the length of the compressed
header so this is taken account of in the build method. This means
that if an OPTIONAL method is surrounded by a U flag and the optional
part is not actually present then no padding bits are required.
An example of the U flag in use is given below:
U(OPTIONAL(crsc_entry)) ; CSRC-list entry
where
csrc_entry = IRREGULAR(32)
This means that if the CSRC entry is present then it will be
compressed as IRREGULAR (i.e. the full 32 bits will be sent) and
these bits will be pushed on the uncompressed stack. However, if it
is not present then no padding bits will need to be sent.
5.15 FORMAT
ABNF notation: "FORMAT(" <encoding_name> "," *(<encoding_name>) ")"
The FORMAT encoding method is used to create more than one set of
compressed header formats.
Recall that each set of compressed header formats uses up all of the
indicator bit patterns available at the start of the compressed
Price, et al. Expires August 2, 2002 [Page 29]
Internet-Draft Framework for EPIC-LITE February 2002
header. Thus a profile can have several sets of compressed header
formats, but only one set can be in use at a given time.
FORMAT encoding is followed by a list of k encoding methods. Each
encoding method is given its own set of compressed header formats in
the CO packets. Note however that all encoding methods are present
in the IR(-DYN) packets, so an IR(-DYN) packet may be sent to change
to a new set of compressed header formats.
An index flag is appended to the uncompressed header to indicate
which set of formats is currently in use, as illustrated by the
following example of an IR(-DYN) format (for CO the index flag would
be STATIC(100%)):
FORMAT(SEQUENTIAL-IP-ID,RANDOM-IP-ID) ; IP ID
IRREGULAR(1,100%) ; IP_ID Index
Two sets of compressed header formats are provided: one for an IP ID
that increases sequentially, and one for a randomly behaving IP ID.
Note that the Index flag is only sent in the IR(-DYN) packets.
5.16 CRC
ABNF notation: "CRC(" <value> "," <probability> ")"
The CRC encoding method generates a CRC checksum calculated across
the entire uncompressed header. At the decompressor this CRC is used
to validate that correct decompression has occurred.
Note that it is possible for different header formats to have
different amounts of CRC protection, so extra CRC bits can be
allocated to protect important context-updating information. This is
illustrated in the example below:
CRC(3,99%) | ; Checksum Coverage
CRC(7,1%)
The uncompressed header is recorded in the crc_static and crc_dynamic
variables. Note that the fields that either never change or only
change in the IR packet are placed in crc_static, and the remaining
fields are placed in crc_dynamic. The CRC is calculated over
crc_static + crc_dynamic, with the static fields placed first to
speed up computation.
Price, et al. Expires August 2, 2002 [Page 30]
Internet-Draft Framework for EPIC-LITE February 2002
In general an EPIC-LITE profile can use any CRC length for which a
CRC polynomial has been explicitly defined. The following CRC
lengths are currently supported:
3-bit: C(x) = 1 + x + x^3
6-bit: C(x) = 1 + x + x^3 + x^4 + x^6
7-bit: C(x) = 1 + x + x^2 + x^3 + x^6 + x^7
8-bit: C(x) = 1 + x + x^2 + x^8
10-bit: C(x) = 1 + x + x^4 + x^5 + x^9 + x^10
12-bit: C(x) = 1 + x + x^2 + x^3 + x^11 + x^12
16-bit: C(x) = 1 + x^2 + x^15 + x^16
5.17 MSN encoding methods
These methods are used to send the MSN (Master Sequence Number) to
the decompressor. Separate encoding methods are required because the
MNS does not appear in the uncompressed data itself.
There are two encoding methods which compress the MSN and one which
can be used to assign a particular field to be the MSN (for example,
RTP sequence number):
5.17.1 MSN-LSB
ABNF notation: "MSN-LSB(" <value> "," <offset> "," <probability> ")"
This method uses ordinary LSB encoding on the value in MSN rather
than on the uncompressed_data stack. It also stores some information
for use if extra bits of MSN are to be sent to pad the compressed
header to a specific bit alignment.
5.17.2 MSN-IRREGULAR
ABNF notation: "MSN-IRREGULAR(" <length> "," <probability> ")"
As with MSN-LSB this method uses ordinary IRREGULAR encoding and
stores the extra information described above.
5.17.3 SET-MSN
ABNF notation: "SET-MSN(" <length> ")"
The parameter of this method specifies the number of bits to assign
Price, et al. Expires August 2, 2002 [Page 31]
Internet-Draft Framework for EPIC-LITE February 2002
to be MSN. The bits are taken from the uncompressed stack. This
value can then be used for INFERRED-OFFSET methods and compressed
using MSN-LSB or MSN-IRREGULAR when no more fields need it.
6. Creating a new ROHC profile
This chapter describes how to generate new ROHC [1] profiles using
EPIC-LITE. It is important that the profiles are specified in an
unambiguous manner so that any compressor and decompressor using the
profiles will be able to interoperate.
The following eight variables are required by EPIC-LITE to create a
new ROHC [1] profile:
profile_identifier
max_formats
max_sets
bit_alignment
npatterns
CO_packet
IR_DYN_packet
IR_packet
Once a value has been assigned to each variable the profile is well-
defined. A compressor and decompressor using the same values for
each variable should be able to successfully interoperate.
Each of the variables is described in more detail below:
6.1 Profile identifier
The profile_identifier is a 16-bit integer that is used when
negotiating a common set of profiles between the compressor and
decompressor. Official profile identifiers are assigned by IANA to
ensure that two distinct profiles do not receive the same profile
identifier. Note that the 8 MSBs of the profile identifier are used
to specify the version of the profile (so that old profiles can be
obsoleted by new profiles).
6.2 Maximum number of header formats
The max_formats parameter controls the number of compressed header
formats to be stored at the compressor and decompressor.
If more compressed header formats are generated than can be stored
then EPIC-LITE discards all but the max_formats most probable formats
to be used. Note that the max_formats parameter affects the EPIC-
LITE compressed header formats, and so for interoperability it MUST
Price, et al. Expires August 2, 2002 [Page 32]
Internet-Draft Framework for EPIC-LITE February 2002
be specified as part of the profile.
If more than max_formats header formats are generated for the IR
packet then this means that there are headers which it may be
impossible to compress using this profile (resulting in a switch to a
different profile). Hence it is RECOMMENDED that no more than
max_formats distinct header formats are generated for the IR packet
of any profile.
In a similar manner the max_sets parameter controls the total number
of sets of compressed header formats to be stored. Recall that a
profile can have several sets of compressed header formats, but only
one set may be in use at a given time. It is important to note that
the maximum size specified by max_formats applies to each individual
set of header formats, so the total overall number of formats that
need to be stored is equal to max_formats * (max_sets + 2) including
the 2 sets of formats for the IR and IR-DYN packets.
6.3 Control of header alignment
The alignment of the compressed headers is controlled using the
bit_alignment parameter. The output of the EPIC-LITE compressor is
guaranteed to be an integer multiple of bit_alignment bits long.
Additionally, the parameter npatterns can be used to reserve bit
patterns in the compressed header. The parameter specifies the
number of bit patterns in the first word (i.e. the first
bit_alignment bits) of the compressed header that are available for
use by EPIC-LITE. Consequently npatterns takes a value between 1 and
2^bit_alignment.
For compatibility with ROHC [1], it is important for EPIC-LITE not to
use the bit patterns 111XXXXX in the first octet of each compressed
header because they are reserved by the ROHC framework. So to
produce a set of header formats compatible with ROHC [1] the
bit_alignment parameter MUST be set to 8 and npatterns MUST be set to
224.
6.4 Compressed header formats
The profile parameter CO_packet specifies an encoding method that is
used to generate the EPIC-LITE CO packets. This encoding method may
be described using the BNF-based input language provided in Chapter 4
(or in fact can be described in any manner provided that it is
unambiguous).
The distinction between the eight variables required to define a new
ROHC [1] profile and the input language defined in Chapter 4 is
Price, et al. Expires August 2, 2002 [Page 33]
Internet-Draft Framework for EPIC-LITE February 2002
important. The only requirement for compatibility with the profile
is that the correct compressed header formats are used: the fact that
they are specified in the input language is not important, and they
can be implemented in any manner.
The profile parameters IR_packet and IR_DYN_packet specify an
encoding method which is used to generate the EPIC-LITE IR and IR-DYN
packets respectively.
Note that the IR_DYN_packet parameter is optional. If it is not
given then EPIC-LITE generates the IR-DYN packet using the same
encoding method as specified by the CO_packet parameter. The
IR_packet parameter is also optional. If it is not given then EPIC-
LITE generates the IR packet using the same encoding method as
specified by the IR_DYN_packet parameter (or CO_packet if
IR_DYN_packet is also not given).
7. Security considerations
EPIC-LITE generates compressed header formats for direct use in ROHC
profiles. Consequently the security considerations for EPIC-LITE
inherit those of ROHC [1].
EPIC-LITE profiles also describe how to compress and decompress
headers. As such they are interpreted or compiled by the compressor
and decompressor. An error in the profile description may cause
undefined behaviour. In a situation where profiles could be
dynamically updated consideration MUST be given to authenticating and
verifying the integrity of the profile.
8. Acknowledgements
Header compression schemes from ROHC [1] have been important sources
of ideas and knowledge. Basic Huffman encoding [2] was enhanced for
the specific tasks of robust, efficient header compression.
Thanks to
Carsten Bormann (cabo@tzi.org)
Christian Schmidt (christian.schmidt@icn.siemens.de)
Max Riegel (maximilian.riegel@icn.siemens.de)
for valuable input and review.
References
[1] Bormann, C., Burmeister, C., Degermark, M., Fukushima, H.,
Price, et al. Expires August 2, 2002 [Page 34]
Internet-Draft Framework for EPIC-LITE February 2002
Hannu, H., Jonsson, L-E., Hakenberg, R., Koren, T., Le, K., Liu,
Z., Martensson, A., Miyazaki, A., Svanbro, K., Wiebke, T.,
Yoshimura, T. and H. Zheng, "RObust Header Compression (ROHC):
Framework and four profiles: RTP, UDP, ESP, and uncompressed",
RFC 3095, July 2001.
[2] Nelson, M. and J-L. Gailly, "The Data Compression Book", M&T
Books , 1995.
[3] Jacobson, V., "Compressing TCP/IP headers for low-speed serial
links", RFC 1144, February 1990.
[4] Bradner, S., "The Internet Standards Process -- Revision 3", BCP
9, RFC 2026, October 1996.
[5] Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", BCP 14, RFC 2119, March 1997.
[6] Crocker, D. and P. Overell, "Augmented BNF for Syntax
Specifications: ABNF", RFC 2234, November 1997.
Authors' Addresses
Richard Price
Siemens/Roke Manor
Roke Manor Research Ltd.
Romsey, Hants SO51 0ZN
UK
Phone: +44 (0)1794 833681
EMail: richard.price@roke.co.uk
URI: http://www.roke.co.uk
Robert Hancock
Siemens/Roke Manor
Roke Manor Research Ltd.
Romsey, Hants SO51 0ZN
UK
Phone: +44 (0)1794 833601
EMail: robert.hancock@roke.co.uk
URI: http://www.roke.co.uk
Price, et al. Expires August 2, 2002 [Page 35]
Internet-Draft Framework for EPIC-LITE February 2002
Stephen McCann
Siemens/Roke Manor
Roke Manor Research Ltd.
Romsey, Hants SO51 0ZN
UK
Phone: +44 (0)1794 833341
EMail: stephen.mccann@roke.co.uk
URI: http://www.roke.co.uk
Abigail Surtees
Siemens/Roke Manor
Roke Manor Research Ltd.
Romsey, Hants SO51 0ZN
UK
Phone: +44 (0)1794 833131
EMail: abigail.surtees@roke.co.uk
URI: http://www.roke.co.uk
Paul Ollis
Siemens/Roke Manor
Roke Manor Research Ltd.
Romsey, Hants SO51 0ZN
UK
Phone: +44 (0)1794 833168
EMail: paul.ollis@roke.co.uk
URI: http://www.roke.co.uk
Mark A. West
Siemens/Roke Manor
Roke Manor Research Ltd.
Romsey, Hants SO51 0ZN
UK
Phone: +44 (0)1794 833311
EMail: mark.a.west@roke.co.uk
URI: http://www.roke.co.uk
Appendix A. EPIC-LITE compressor and decompressor
This appendix gives a complete pseudocode description of the EPIC-
LITE compressor and decompressor.
Price, et al. Expires August 2, 2002 [Page 36]
Internet-Draft Framework for EPIC-LITE February 2002
The appendix contains the following sections:
Compressor operation (Section A.1)
Decompressor operation (Section A.2)
Offline processing (Section A.3)
Library of methods (Section A.4)
BNF description of input language (Section A.5)
Recall that each EPIC-LITE profile for ROHC [1] is described by the
following eight variables:
profile_identifier 16-bit integer uniquely identifying the
ROHC profile generated by EPIC-LITE
max_formats Maximum number of header formats per set
max_sets Total number of sets of header formats
bit_alignment Number of bits for alignment (all
compressed headers will be multiples of
bit_alignment bits). (Set to 8 for
compatibility with ROHC [1].)
npatterns Number of bit patterns available for
EPIC-LITE in the first word of the
compressed header (set to 224 for
compatibility with ROHC [1].)
CO_packet Name of the method that generates the CO
packet formats
IR_DYN_packet Name of the method that generates the
IR-DYN packet formats
IR_packet Name of the method that generates the IR
packet formats
Additionally, the following general functions are used in the
pseudocode description of EPIC-LITE:
The functions used for list manipulation are given below:
Price, et al. Expires August 2, 2002 [Page 37]
Internet-Draft Framework for EPIC-LITE February 2002
empty (list) Empties the list
sort-natural (list, compare) Sorts the list as defined by the compare
function (which compares 2 elements).
Sort is 'natural' in that original
ordering of elements is preserved in the
event of 2 elements being equal
append (list, item) Appends an item to a list
prepend (list, item) Prepend an item to head of list
concatenate (list, list) Appends all the entries from the second
list to the first one
copy (list, list) Replaces the first list with a copy of
the second list
head-of (list) Finds first item in list
tail-of (list) Finds last item in list
next-item (curr_item) Finds the next item in the list from
curr_item
previous-item (curr_item) Finds the previous item in the list
from curr_item
at-end (list) Checks whether at the end of the list
size-of (list) Returns the number of elements in list
The following functions are used to traverse the BNF input language
describing the new ROHC profile. Note that the relevant information
can be extracted from the input language by hand or automatically via
a suitable BNF parser:
Price, et al. Expires August 2, 2002 [Page 38]
Internet-Draft Framework for EPIC-LITE February 2002
first-field (method_name)
finds the first instance of <field_encoding> referenced
in the encoding method (applies to a non-library
encoding method only)
next-field (method_name)
finds the next instance of <field_encoding> in the
method (if none can be found then NULL-ENCODING is
returned)
prev-field (method_name)
finds the previous instance of <field_encoding> in the
method
last-field (method_name)
finds the last instance of <field_encoding> in the
method (these functions allow iteration over the
different field encodings in a method. This must be in
the order defined in the profile)
first-method (field_encoding)
find the first encoding method listed within the field
encoding
next-method (field_encoding)
find the next encoding method listed within the field
encoding (this and the previous function allow iteration
over the encoding methods for a given field. This must
be in the order defined in the profile. If none can be
found then NULL-METHOD is returned)
extract-name (method)
finds the name of the encoding method
extract-probability (method)
finds the probability of the method being invoked
Method function handling:
Price, et al. Expires August 2, 2002 [Page 39]
Internet-Draft Framework for EPIC-LITE February 2002
lookup-build-function (method)
finds the 'BUILD' function that relates to the
method. If this is a library method, then the
function returns a reference to the 'BUILD'
subfunction for that method. Otherwise it
returns a reference to the main 'BUILD' function
which is then called recursively
lookup-compress-function (method)
as above but for the 'COMPRESS' function
lookup-decompress-function (method)
as above but for the 'DECOMPRESS' function
context-size (method)
looks up the number of context entries that will be
needed to compress using this method. This can be
worked out off line as part of the 'BUILD' function and
stored for reference during compression and
decompression.
count-bits (method, enc)
counts the number of bits that would be present in a
compressed header for data compressed with format enc
for this method (This can be worked out off line as part
of the 'BUILD' function and stored for use during
compression and decompression).
Data handling:
Value based functions:
Price, et al. Expires August 2, 2002 [Page 40]
Internet-Draft Framework for EPIC-LITE February 2002
length (var) Returns the length in bits of var
value (var) Returns the value of var
str (len, val) Returns a variable with length len and
containing the value val
lsb (var, k) Returns the least significant k bits of
a (width defined or not) value (var) in
a width defined value
msb (var, k) Returns the most significant k bits of a
width defined value (var) in a width
defined value
concat (var_1, var_2) Returns a width defined value with most
significant bits being var_1 and least
being var_2 - ie concatenates the two
strings
Addition, subtraction and multiplication can be done on width defined
values as long as the two values have the same length (i.e. this
translates into modular arithmetic) but must be done carefully.
Stack functions:
In the functions below an item has a length and value associated with
it which can be found using the functions above.
push (stack_name, n, var) For a bit-overlay stack, this function
adds n bits with value var to the top of
the stack (stack_name). For an item
stack, this function pushes an item with
length n and value var to the top of the
stack (stack_name)
push (stack_name, item) For a bit-overlay stack, this function
adds n bits with value var to the top of
the stack (stack_name) where n is the
length of item and it has value var.
For an item stack, this function pushes
item on var to the top of the stack
(stack_name)
pop (stack_name, n, item) Pop n bits of data off a bit based stack
(stack_name) and put into item
Price, et al. Expires August 2, 2002 [Page 41]
Internet-Draft Framework for EPIC-LITE February 2002
pop (stack_name, item) Pop item off an item based stack
(stack_name)
top (stack_name, n) Returns the item made up of the top n
bits on a bit based stack (stack_name)
top (stack_name) Returns the top item from an item based
stack (stack_name)
stack-size (stack) Returns the size in bits of a bit based
stack
add (stack_1, stack_2) Pushes stack_1 onto stack_2 but leaves
the outcome in stack_1
rotate (stack_name, n, m) Rotate the top n items on an item based
stack (stack_name) m times. Take the
nth item from the stack and put it on
the top.
stack-pointer (stack_name) Returns the position of the top of a
stack (stack_name) NB this is never used
for accessing the stack and can be of
arbitrary form
Context based functions:
The enc_index counter is used to access information stored in the
context for each field encoding. It is initially 1 and is
incremented throughout compression and decompression. Some encoding
methods do not have any context associated with them, for example,
INFERRED-SIZE. This incremental way of accessing context information
means that if a choice of two or more encoding methods is available
for a given field, each in turn should contain the same number of
subfields as each other, otherwise the alignment of the context will
be lost.
NB leaving a value in the context empty is NOT the same as storing
something which zero-bits wide.
Price, et al. Expires August 2, 2002 [Page 42]
Internet-Draft Framework for EPIC-LITE February 2002
context (enc_index, i, var)
Put the value stored at the ith position
in the context associated with enc_index
into var. If there isn't a value in the
ith position then return empty
save (enc_index, var, storage)
Store the value in var in storage
associated with enc_index (to be
transferred to the context if
(de)compression is successful
clear (enc_index, storage) Remove the value in storage associated
with enc_index and leave it empty (for
use if non-context-updating method)
transfer (storage, context) Transfer the information in storage into
the context
Miscellaneous:
convert-percentage (pc) Converts the percentage (in floating
point) to the fixed point representation
used
store (list, method, field_encoding)
Add method associated with
field_encoding to list
get-method (list, field_encoding)
Return the method associated with
field_encoding from list
get-method-list (main_list_elt, method_chosen)
Finds method_chosen such that
method_chosen <=>
main_list_item.id
format-get-method-list (main_list_elt, method_chosen, method)
Finds method_chosen such that
method_chosen <=>
main_list_item.id assuming that a
specific method has been chosen using
the FORMAT method (this is used to
ensure correct decompression of an
IR(-DYN) packet)
Price, et al. Expires August 2, 2002 [Page 43]
Internet-Draft Framework for EPIC-LITE February 2002
get-format (main_list_elt, method_chosen)
Finds the main_list_item such that
method_chosen <=> main_list_item.id
get-header-length (method_chosen)
Returns the length in bits of the
compressed header format (excluding
flags) for this list element
(sum of number of bits in each
compressed field)
lookup-crc-function (n) Finds the function for computing an
n-bit crc over a specified amount of
data and putting the value into a given
width defined variable
byte-swap (item) Returns another item the same as item
but stored in the opposite byte ordering
compute-16-checksum (data, length)
Compute a 16-bit one's complement sum
over data of length
Other constructs:
foreach item in [reverse] list
:
end loop
provides for iteration over all the elements of a list [in
reverse order]
call function (...)
indicates a reference to a function is being invoked
choose (...)
the choice of whatever is specified is implementation specific
- it may affect efficiency but whatever choice is made will not
affect interoperability, for example, choose (j < k) - pick
an arbitrary value j which is less than k.
Some global variables:
Price, et al. Expires August 2, 2002 [Page 44]
Internet-Draft Framework for EPIC-LITE February 2002
uncompressed_data Bit based stack
Compression - initially header and payload,
finally empty
Decompression - initially empty,
finally original header and
payload
compressed_data Bit based stack
Compression - initially empty,
finally compressed header and
payload
Decompression - initially compressed header,
finally empty
unc_fields Bit based stack
Compression - initially empty,
used to store fields to be sent
uncompressed for transfer to
compressed_data
Decompression - initially data which has been
sent uncompressed,
finally only payload for
transfer to uncompressed_data
received_data Bit based stack
Decompression - initially packet received,
splits into compressed_data and
unc_fields
control_data Item based stack
Compression and
Decompression - initially and finally empty -
storage for control fields if
not used immediately after
generation
u_flag A flag which starts with value zero. It keeps
track of which stack (compressed_data or
unc_fields) has the compressed data added to/
removed from it.
compression_stack Pointer to either compressed_data or
unc_fields, whichever is the one that is
currently having data put onto it according
to the value of u_flag.
Initially at both compression and decompression
compression_stack = compressed_data.
Price, et al. Expires August 2, 2002 [Page 45]
Internet-Draft Framework for EPIC-LITE February 2002
context Storage of data as reference for
compression and decompression -
referenced by 'enc_index'
storage Storage of data during (de)compression
to be transferred to context if
successful - referenced by 'enc_index'
enc_index A counter to keep track of the field encodings
and context data associated with them
method_chosen List of methods used to compress a given
header - lists the encoding method
chosen for each 'enc_index'
compressor_state The current state at the compressor (can be set
to "IR", "IR-DYN" or "CO")
current_set The set of compressed header formats
currently in use
crc_static The static part of the header
crc_dynamic The dynamic part of the header
crc The decompressed crc for checking against one
calculated over full header (a width defined
value)
MSN The Master Sequence Number - a width defined
value (its value increases by one for each
packet received at the compressor or it is set
to be a specific value using the SET-MSN method
if the header contains a suitable field)
msn_bits The number of bits chosen to encode the MSN
msn_lsbs The LSBs of MSN used for padding (a width
defined value)
A.1 Compressor
This section describes the EPIC-LITE header compressor.
A.1.1 Step 1: Packet classification
The input to the EPIC-LITE compressor is simply an uncompressed
Price, et al. Expires August 2, 2002 [Page 46]
Internet-Draft Framework for EPIC-LITE February 2002
packet. The compressor does not know whether the packet contains an
RTP header, TCP header or other type of header, and hence the first
step is to determine which (if any) ROHC context can be used to
compress the packet.
With any profile generated by EPIC-LITE the packet classification is
performed automatically, since the profile will reject any packet
that it cannot successfully compress relative to the chosen context.
Note however that additional packet classification MAY be performed
before the packet is passed to the EPIC-LITE compressor. For example
the compressor MAY wish to check that the values that are initialised
in the IR packet, or fixed for all states take the values specified
in the prospective context before compression is attempted, as if
they do not then compression will not succeed.
A.1.2 Step 2: Using the state machine
The job of the state machine is to choose whether to send IR, IR-DYN
or compressed (CO) packets. Since EPIC-LITE currently operates in a
unidirectional mode of compression only there is no need to
synchronize the decision with the decompressor, and hence the choice
can be left as an implementation decision.
A.1.3 Step 3: Compressing the header
The next step is to choose the compressed header format that will be
used to transmit the header from the compressor to the decompressor.
Given the selected profile the compressor has exactly max_sets + 2
possible sets of header formats available: a total of max_sets
different sets of CO packets, as well as a set of IR-DYN packets and
a set of IR packets. The choice of which header formats to use
depends on the current state of the state machine.
The compressor calls the function COMPRESS to compress the header.
The function takes one parameter - the name of the method that is
currently being used. The global variable enc_index is initially 1.
Note that is not necessary to provide EPIC-LITE with a description of
where the fields occur in the uncompressed header, as this
information is provided automatically as part of each method (written
in the BNF input language). Each encoding method has a specific
number of bits associated with it which is the number of bits that
encoding method can compress - this splits the header into fields.
The function has a single output: a Boolean value indicating whether
or not compression has successfully occurred. Additionally, if
compression succeeds then the stack compressed_data will contain the
Price, et al. Expires August 2, 2002 [Page 47]
Internet-Draft Framework for EPIC-LITE February 2002
compressed value of every field in the uncompressed header.
The function also modifies the value of the global variable,
method_chosen. If compression is successful then for each field in
the profile, method_chosen will contain an indicator of which
encoding method has been selected for the field. This is mapped onto
a set of indicator flags in Section A.1.4.
The compression commences with a call to the COMPRESS function for
the method specified in CO_packet (or IR_DYN_packet or IR_packet
depending on the compressor state).
The function may call itself recursively with a different input.
For one particular aspect of profile complexity there are two
distinct categories. For a profile in the first category, if a
header is compressible, then compression is guaranteed to complete
successfully in a single pass. The second category of profiles
cannot make this guarantee. This is due either to a change of packet
format (as indicated through the FORMAT encoding method) or to the
failure of a non-library encoding method. A change of format
requires IR-DYN packets to be sent indicating the change. Multiple
formats may need to be tried in order to find one that can
successfully compress the packet, and the compressor should implement
such a mechanism. Where a non-library encoding method fails,
alternative encoding methods may be available. However, some
encoding methods may have been applied, altering the contents of the
stacks used to store state information for compression. The
compressor should implement a mechanism, such as rolling back the
compression state information, to allow alternative encoding methods
to be tried. This ensures that all possible combinations of encoding
methods can be tried to find one which will successfully compress the
packet.
If the method is specified as part of the EPIC-LITE library, the
pseudocode for the COMPRESS procedure is specified separately (in
Appendix A.4.).
function COMPRESS (method_name)
var enc, method
var compress_function
enc = first-field (method_name)
while (enc <> NULL_ENCODING)
Price, et al. Expires August 2, 2002 [Page 48]
Internet-Draft Framework for EPIC-LITE February 2002
method = first-method (enc)
do
# compress_function will be for the method if it is a
# library method or a recursive call to this function for
# a composite method...
compress_function = lookup-compress-function
(extract-name (method))
can_compress = call compress_function
(extract-name (method))
if can_compress = true then
# store the method selected from this field_encoding in
# method_chosen
store (method_chosen, method, enc)
else
# otherwise try another method in the field_encoding
method = next-method (enc)
endif
loop until (can_compress = true) or (method = NULL_METHOD)
if can_compress = true then
enc = next-field (method_name)
else
return false
endif
end while
return true
end COMPRESS
Price, et al. Expires August 2, 2002 [Page 49]
Internet-Draft Framework for EPIC-LITE February 2002
N.B. This procedure shows the encoding methods for a field being
checked in the order in which they appear in the profile. The order
in which they are checked is actually implementation specific but is
shown in the form above for simplicity of the pseudocode. But, for
interoperability the "store" function must have a unique mapping
dictated by the order of the encoding methods in the profile between
the field and the encoding method.
Note that once the header has been compressed, the variable "storage"
should contain the uncompressed value of each field which has context
associated with it. This information is then transferred to the
context in the compressor (possibly overwriting one of the copies of
information already stored).
A.1.4 Step 4: Determining the indicator flags
The next step is to determine the correct indicator flags for the
chosen compressed header format.
Once the indicator flags have been added the header should be padded
to be a multiple of bit_alignment bits and the uncompressed fields
and payload added.
The compressor must run the following procedures:
function get-indicator-flags (method_chosen, flags_list_elt, Mvalue)
var main_list_item, old_item, ml
var last_N_before_item, w, length, length_item, next_length, num
var last_N_of_smaller_length
var found_length, n_diff
var fl
# How this mapping is done is implementation dependent at the
# compressor
get-format (main_list_item, method_chosen)
old_item = next-item (main_list_item)
last_N_before_item = tail-of (old_item.cum_N_list)
w = head-of (main_list_item.cum_N_list)
length = head-of (main_list_item.length_list)
found_length = 0
# If length_list only has one item then this loop will only
# be done once (as in EPIC-LITE), otherwise loop until the
# cumulative_N which covers Mvalue is found. This gives the
Price, et al. Expires August 2, 2002 [Page 50]
Internet-Draft Framework for EPIC-LITE February 2002
# length of the flags
while (found_length = 0)
n_diff = w - last_N_before_item
if (n_diff < Mvalue) then
w = next-item (w)
length = next-item (length)
else
found_length = 1
endif
end loop
# Find first flags of this length from the flag list
found_length = 0
fl = head-of (flag_list)
while (found_length = 0)
if length = fl.length then
found_length = 1
else
fl = next-item (fl)
endif
end loop
# Find the last cumulative N which has flags of smaller length
# than fl
found_length = 0
ml = tail-of (main_list)
while (found_length = 0)
if (head-of (ml.length_list) < length) then
ml = previous-item (ml)
else
found_length = 1
ml = next-item (ml)
endif
end loop
length_item = head-of (ml.length_list)
num = head-of (cum_N_list)
next_length = next-item (length_item)
found_length = 0
while (next_length <> NULL and found_length = 0)
if next_length <> length then
length_item = next-item (length_item)
Price, et al. Expires August 2, 2002 [Page 51]
Internet-Draft Framework for EPIC-LITE February 2002
next_length = next-item (next_length)
num = next-item (num)
else
found_length = 1
endif
end loop
last_N_of_smaller_length = num
# Work out what the indicator flags will be for this Mvalue
flags = Mvalue + fl.flags + last_N_before_item -
last_N_of_smaller_length
return length
end get-indicator-flags
procedure INDICATOR-FLAGS
var n, bit, temp, length
var extra_bits
# Take account of the currently selected FORMAT set
choose (main_list or formats and associated flag_list according
to the value of current_set)
length = get-indicator-flags (method_chosen, flags, 0)
push (compressed_data, length, flags)
# pad the compressed header to bit_alignment with extra bits of
# MSN - use zeros if more space than bits of MSN
bit = bit_alignment
n = (bit - (stack-size (compressed_data) mod bit)) mod bit
temp = value (MSN) - value (lsb (MSN, msn_bits))
temp = temp / (2^msn_bits)
extra_bits = lsb (temp, n)
push (unc_fields, extra_bits)
# add the uncompressed fields after the compressed header
add (compressed_data, unc_fields)
# add the payload after the uncompressed fields
Price, et al. Expires August 2, 2002 [Page 52]
Internet-Draft Framework for EPIC-LITE February 2002
add (compressed_data, uncompressed_data)
end INDICATOR-FLAGS
A.1.5 Step 5: Encapsulating in ROHC packet
The last step is to encapsulate the EPIC-LITE compressed packet
within a ROHC packet.
Note that this includes adding the CID and any other ROHC framework
headers (segmentation, padding etc.) as described in ROHC [1]. The
ROHC packet is then ready to be transmitted.
A.2 Decompressor
This section describes the EPIC-LITE header decompressor.
A.2.1 Step 1: Decapsulating from ROHC packet
The input to the EPIC-LITE decompressor is a compressed ROHC packet.
The first step is to read the CID of the packet and to extract the
EPIC-LITE packet for parsing by the appropriate profile.
If the ROHC packet is identified as containing an EPIC-LITE
compressed packet then the decompression process continues as
indicated below.
A.2.2 Step 2: Running the state machine
The decompressor state machine determines whether the received packet
should be decompressed or discarded (based on whether the
decompressor believes its stored context to be valid or invalid).
Since the compressor and decompressor state machines do not have to
be synchronized, this is left as an implementation decision.
A.2.3 Step 3: Reading the indicator flags
The input to Step 3 is an EPIC-LITE compressed packet. Note that the
overall length of the packet is known from the link layer, but the
length of the compressed header itself is NOT known.
The first step is to determine the compressed header format and split
the packet into compressed header and uncompressed data. This is
accomplished by reading the indicator flags as per the following
procedure:
Price, et al. Expires August 2, 2002 [Page 53]
Internet-Draft Framework for EPIC-LITE February 2002
procedure decode-indicator-flags (received_data, method_chosen,
flags, bit_chunks, Mvalue)
var main_list_item, ml
var last_N_before_item, length, length_item, next_length, num
var last_N_of_smaller_length
var found_length
var fl
found_length = 0
fl = head-of (flag_list)
while (found_length = 0 and fl <> NULL)
if (top (received_data, fl.length*bit_chunks)
<= fl.flags) then
found_length = 1
else
fl = next-item (fl)
endif
end loop
if fl <> NULL then
fl = previous=item (fl)
else
fl = tail-of (flag_list)
endif
length = fl.length
flags = top (received_data, length*bit_chunks)
# Find the last cumulative N which has flags of smaller length
# than fl
found_length = 0
ml = tail-of (main_list)
while (found_length = 0)
if (head-of (ml.length_list) < length) then
ml = previous-item (ml)
else
found_length = 1
ml = next-item (ml)
endif
end loop
length_item = head-of (ml.length_list)
num = head-of (ml.cum_N_list)
next_length = next-item (length_item)
Price, et al. Expires August 2, 2002 [Page 54]
Internet-Draft Framework for EPIC-LITE February 2002
found_length = 0
while (next_length <> NULL and found_length = 0)
if next_length <> length then
length_item = next-item (length_item)
next_length = next-item (next_length)
num = next-item (num)
else
found_length = 1
endif
end loop
last_N_of_smaller_length = num
Mvalue = flags - fl.flags
num = tail-of (ml.cum_N_list)
while ((num - last_N_of_smaller_length) < Mvalue)
ml = previous-item (ml)
num = tail-of (ml.cum_N_list)
end loop
main_list_elt = ml
ml = next-item (ml)
last_N_before_item = tail-of (ml.cum_N_list)
Mvalue = Mvalue + last_N_of_smaller_length - last_N_before_item
# How this mapping is done is decompressor specific
get-method-list (main_list_item, method_chosen)
end decode-indicator-flags
procedure READ-FLAGS
var found, n, size, bit, k, len, Mvalue
var temp, flags, flags_temp
# Take account of the currently selected FORMAT set
choose (main_list or formats and associated flag_list according
to the value of current_set)
decode-indicator-flags (received_data, method_chosen,
flags, 1, Mvalue)
len = length (flags)
Price, et al. Expires August 2, 2002 [Page 55]
Internet-Draft Framework for EPIC-LITE February 2002
pop (received_data, len, flags_temp)
n = get-header-length (method_chosen)
# put the compressed header on the compressed data stack
pop (received_data, n, temp)
push (compressed_data, temp)
# store any extra lsbs of MSN sent
bit = bit_alignment
k = (bit - (n + len) mod bit) mod bit
pop (received_data, k, msn_lsbs)
# put the rest of the received packet on the unc_fields stack
size = stack-size (received_data)
pop (received_data, size, temp)
push (unc_fields, temp)
end READ-FLAGS
A.2.4 Step 4: Decompressing the fields
Now that the format of the compressed header has been determined, the
next step is to decompress each field in turn.
The decompressor calls the procedure DECOMPRESS to calculate the
uncompressed value of the fields. The only input to the procedure is
the name of a method. Unlike the COMPRESS function there are no
outputs since decompression always succeeds (although if the packet
is corrupted, the correct answer may not be obtained).
Initially, the DECOMPRESS procedure is called for the method
specified in CO_packet (or IR_DYN_packet or IR_packet depending on
the ROHC packet type received). Note that as for COMPRESS the
procedure may call itself recursively with different inputs. The
global variable enc_index is initially 1.
Price, et al. Expires August 2, 2002 [Page 56]
Internet-Draft Framework for EPIC-LITE February 2002
procedure DECOMPRESS (method_name)
var enc, method
var decompress_function
enc = last-field (method_name)
while (enc <> NULL_ENCODING)
method = get-method (method_chosen, enc)
# decompress_function will be for the method if it is a
# library method or a recursive call to this function for
# composite method...
decompress_function = lookup-decompress-function
(extract-name (method))
call decompress_function (extract-name (method))
enc = prev-field (method_name)
end while
end DECOMPRESS
Observe that the DECOMPRESS procedure reads the input code in the
opposite order to the COMPRESS procedure. This is because
decompression is the exact mirror-image of compression: if fields are
parsed in reverse order then it will never be the case that a field
can only be decompressed relative to a field that has not yet been
reached.
When the entire header has been decompressed it is on the stack
uncompressed data and the payload is still on the stack unc_fields.
These should be combined to make the original packet.
A.2.5 Step 5: Verifying correct decompression
By this stage the decompressor has calculated the value
uncompressed_data that contains the entire uncompressed header as
well as the payload.
The final step is to verify that successful decompression has
occurred by applying the checksum to the uncompressed header. The
CRC method makes available the variables checksum_value (containing
the checksum from the compressed header) and crc_static + crc_dynamic
Price, et al. Expires August 2, 2002 [Page 57]
Internet-Draft Framework for EPIC-LITE February 2002
(containing all of the fields in the uncompressed header). The CRC
should be evaluated over crc_static + crc_dynamic and compared with
the CRC stored in checksum_value.
If the uncompressed header fails the checksum then it should be
discarded. If it passes then it can be forwarded by the
decompressor.
Furthermore, if decompression is successful then the values contained
within context can be replaced by the values contained in storage.
A.3 Offline processing
This section describes how the profile is converted into one or more
sets of compressed header formats. Note that the following
algorithms are run once offline and the results stored at the
compressor and decompressor.
A.3.1 Step 1: Building the header formats
The first step is to build up a list of the max_formats different
compressed header formats that occur with the highest probability
(based on the probability values given in the input code).
To generate the max_sets + 2 different sets of compressed header
formats, the BUILD procedure is called max_sets times with the global
variable compressor_state set to "CO" and current_set taking values
from 0 to max_sets - 1 inclusive. Additionally it is called once
with compressor_state = "IR" and once with compressor_state = "IR-
DYN". The output in each case is a list describing the top
max_formats different compressed header formats. The list has the
following attributes:
The output from the BUILD procedure is a list describing the top
max_formats different compressed header formats in the following way.
Each list_item has several parts:
Price, et al. Expires August 2, 2002 [Page 58]
Internet-Draft Framework for EPIC-LITE February 2002
list_item.P Overall percentage probability that the header
format identified in this list item will be used
list_item.N Total size of the header format identified in
this list item in bits, excluding indicator
flags
list_item.id A list of integers uniquely identifying the
header format associated with this list item (id
is itself a list on which the list functions
defined earlier can be performed)
Note that all percentages are stored to exactly 2 decimal places (or
by scaling they can be stored as a 2-octet integer from 0 to 10000
inclusive). When two percentages are multiplied, the result MUST be
calculated exactly (i.e. to 4 decimal places, or equivalently a 4-
octet integer) and then truncated to 2 decimal places.
For example, 15.8% is represented as 1580, 89.2% is represented as
8920. The result of multiplying these two values together is:
1580 x 8920 = 14093600 (interim result, accurate to 4 DP)
14093600 / 10000 = 1409 (any remainder is discarded)
1409 = 14.09%
For interoperability the top max_formats entries MUST NOT be
reordered when the discarding process is carried out. In the event
of a tie, the list entries with the lowest indices are kept.
Note that the procedure may call itself recursively using a different
input.
Some functions used in the BUILD procedure are defined first:
#
# compare two items by probability
#
function COMPARE (a, b)
if a.P > b.P then
return 1
else if a.P < b.P then
return -1
else
return 0
endif
end COMPARE
Price, et al. Expires August 2, 2002 [Page 59]
Internet-Draft Framework for EPIC-LITE February 2002
#
# discard items from list such that:
# list is sorted
# if list contains less than max_formats entries then
# the sorted list is returned
# else if list contains more than max_formats then
# keep the max_formats most probably entries
# if any other entries have the same probability as
# the least probable entry, keep those
# discard the rest
#
procedure DISCARD (list, max_formats)
var result_list
var count
var last_item
empty (result_list)
sort-natural (list, COMPARE)
count = 0
last_item = tail-of (list)
foreach item in reverse list
if ((count >= max_formats) and ((last_item.P <> item.P) or
(item.P = 0)) then
break
endif
prepend (result_list, item)
last_item = item
count = count + 1
end loop
copy (list, result_list)
end DISCARD
Price, et al. Expires August 2, 2002 [Page 60]
Internet-Draft Framework for EPIC-LITE February 2002
#
# combine two lists by creating their
# product. This sums the N values and
# multiplies the P values
#
procedure COMBINE (final, temp)
empty (new_list)
foreach dst in temp
foreach src in final
item.P = dst.P * src.P
item.P = dst.N + src.N
copy (item.id, dst.id)
concatenate (item.id, src.id)
append (new_list, item)
end loop
DISCARD (new_list, max_formats)
end loop
copy (final, new_list)
end COMBINE
#
# build the list for the method given
#
procedure BUILD (method_name, probability, build_list)
var enc, method
var item
var final_list, build_output, temp_list
var build_function
enc = first-field (method_name)
item.P = convert-percentage (100%)
item.N = 0
Price, et al. Expires August 2, 2002 [Page 61]
Internet-Draft Framework for EPIC-LITE February 2002
empty (item.id)
empty (final_list)
append (final_list, item)
while (enc <> NULL_ENCODING)
empty (temp_list)
method = first-method (enc)
do
# build_function will be for the method if it is a library
# method or a recursive call to this function for a composite
# method...
empty (build_output)
build_function = lookup-build-function (method)
call build_function (extract-name (method),
extract-probability (method),
build_output)
foreach item in build_output
append (item.id, method)
append (temp_list, item)
end loop
DISCARD (temp_list)
method = next-method (enc)
loop until method = NULL_METHOD
# combine lists - result in final_list
COMBINE (final_list, temp_list)
enc = next-field (method_name)
end while
foreach item in final_list
item.P *= probability
Price, et al. Expires August 2, 2002 [Page 62]
Internet-Draft Framework for EPIC-LITE February 2002
end loop
copy (build_list, final_list)
end BUILD
procedure BUILD-TABLE (base_method, result)
BUILD (base_method, convert-percentage (100%), result)
end BUILD-TABLE
The final output of BUILD is a list describing max_formats different
compressed header formats.
A.3.2 Step 2: Generating the indicator flags
The final step of generating a new set of compressed header formats
is to convert the list of probabilities into a set of indicator
flags. Each header format begins with a unique pattern of indicator
flags that serve to distinguish it from all other header formats in
the set.
EPIC-LITE generates the indicator flags using ordinary Huffman
compression. For each of the cases in Section A.3.1 where the BUILD
algorithm is run the following algorithm should be applied to the
output of BUILD:
#
# build the flags associated with the list given, reserving the
# bit pattern '111' if do_reserve is set
#
procedure BUILD-FLAGS (main_list, do_reserve)
var work_list, reserve
var u, v, w, z
var i, flag, value, prev_length, num_formats
sort-natural (main_list, COMPARE)
DISCARD (main_list, max_formats)
empty (work_list)
Price, et al. Expires August 2, 2002 [Page 63]
Internet-Draft Framework for EPIC-LITE February 2002
u = head-of (main_list)
v = head-of (work_list) # which will be null
# the work_list starts empty, so v is 'null'. However, as soon as
# the first item is added to the work list, v references this item,
# which is why there is a condition & re-initialisation of v at the
# bottom of the loop
item.P = u.P
u.parent = item
num_formats = size-of (main_list)
for i = 0 to (num_formats - 2)
if (i = (num_formats - 4) and do_reserve) then
RESERVE (u, v, reserve, flag)
endif
u_next = next-item (u)
v_next = next-item (v)
if (at-end (v) or (
not at-end (u_next) and (u_next.P <= v.P)) then
item.P = u.P + u_next.P
append (work_list, item)
u.parent = item
u_next.parent = item
u = next-item (u_next)
else if (at-end (u) or (
not at-end (v_next) and v_next.P <= u.P)) then
item.P = v.P + v_next.P
append (work_list, item)
v.parent = item
v_next.parent = item
v = next-item (v_next)
else
item.P = u.P + v.P
append (work_list, item)
u.parent = item
v.parent = item
u = u_next
Price, et al. Expires August 2, 2002 [Page 64]
Internet-Draft Framework for EPIC-LITE February 2002
v = next-item (v)
endif
if (i = 0) then
v = head-of (work_list)
endif
end loop
item.parent = NULL_ITEM
cumulative_N = 0
empty (flag_list)
w = tail-of (main_list)
for i = 0 to (num_formats - 1)
z = w
length = 0
do
if do_reserve then
if (type = 0 and (z = reserve [0])) then
length = length + 1
else if (type = 1 and (z = reserve [0] or z = reserve [1])) then
length = length + 1
else if (type = 2 and z = reserve [3]) then
length = length + 1
else if (type = 2 and z = reserve [1]) then
length = length - 1
else if (type = 3 and z = reserve [2]) then
length = length + 1
endif
endif
length = length + 1
z = z.parent
loop until z.parent = NULL_ITEM
cumulative_N = cumulative_N + 1
Price, et al. Expires August 2, 2002 [Page 65]
Internet-Draft Framework for EPIC-LITE February 2002
append (w.length_list, length)
append (w.cum_N_list, cumulative_N)
# Add this length into the flag_list - either by adding
# 1 to the element with correct length or by adding a
# new element. Flag_list should be in ascending order of
# lengths.
found_same_length = 0
fl_elt = head-of (flag_list)
while (fl_elt <> NULL and found_same_length = 0)
if fl_elt.length = length then
found_same_length = 1
endif
end while
if found_same_length = 0 then
fl_elt.N = cumulative_N
fl_elt.length = length
append (flag_list, fl_elt)
else
fl_elt.N = fl_elt.N + 1
endif
w = previous-item (w)
end loop
# Generate the Huffman flags
flag_item.N = 0
flag_item.length = 0
flag_item.flags = 0
prepend(flag_list,flag_item)
fl_3 = head-of (flag_list)
fl_2 = next-item (fl_3)
fl_2.flags = str(fl_2.length,0)
fl_1 = next-item(fl_2)
while (fl_1 <> NULL)
fl_1.flags = str(fl_1.length,(fl_2.flags + (fl_2.N - fl_3.N))
* 2 ^ (fl_1.length - fl_2.length))
fl_1 = next-item (fl_1)
Price, et al. Expires August 2, 2002 [Page 66]
Internet-Draft Framework for EPIC-LITE February 2002
fl_2 = next-item (fl_2)
fl_3 = next-item (fl_3)
end while
end BUILD_FLAGS
#
# procedure to work out whether to use one or two list
# items to reserve the bits '111'
#
procedure RESERVE (u, v, reserve, flag)
var temp_u, temp_v
var t
var prob
temp_u = u
temp_v = v
flag = 0
# This section works out which order the 4 remaining nodes
# will be formed into tree
for t = 0 to 3
if (at-end (temp_v) or (
not at-end (temp_u) and temp_u.P <= temp_v.P) then
reserve [t] = temp_u
prob [t] = temp_u.P
temp_u = next-item (temp_u)
else
reserve [t] = temp_v
prob [t] = temp_v.P
temp_v = next-item (temp_v)
endif
end loop
# prob[0] = A ... prob [3] = D
Price, et al. Expires August 2, 2002 [Page 67]
Internet-Draft Framework for EPIC-LITE February 2002
# This function is pretending to create a node which will
# have the same probability as B and will take up the bit
# pattern '111'. If the new node were to be created then
# check whether a + 2*B >= D to decide whether or not the
# node comes before or after B. This part looks at the
# probabilities to work out which nodes would have their
# lengths changed by inserting this node so they can be
# changed accordingly in the length counting (rather than
# actually trying to add the new node)
if ((prob [0] + prob [1]) >= prob [3]) then
flag = 0
else
if ((prob [0] + prob [1]) < prob [2]) then
if ((prob [0] + (2 * prob [1])) < prob [3]) then
flag = 1
else
flag = 2
endif
else
if ((prob [1] + prob[2] < prob [3])) then
flag = 3
else
flag = 2
endif
endif
endif
end RESERVE
The procedure RESERVE is called at most once by BUILD-FLAGS to
reserve the bit pattern "111" in the first octet of each compressed
header (for compatibility with the ROHC framework).
The output of BUILD-FLAGS is the main_list each item of which has
three key parts:
Price, et al. Expires August 2, 2002 [Page 68]
Internet-Draft Framework for EPIC-LITE February 2002
list_item.length_list List of lengths of numbers of flags (for
EPIC-LITE this will only have one
element). The lengths should
(automatically) be in ascending order.
list_item.cum_N_list A list of numbers - corresponding to the
number of headers with each flag length
in the length_list (again for EPIC-LITE
there will only be one element). The
numbers should (automatically) be in
ascending order.
list_item.identifier Some unique identifier which can be used
to perform mapping between these flags
and the header format used to generate a
compressed header requiring these flags.
and a flag_list each item of which has the following elements:
flag_list_item.length The length of the Huffman flags.
flag_list_item.N The cumulative number of headers with
Huffman flags up to this length.
flag_list_item.flags The flags for the first header with
flags of this length (the rest can be
worked out from this information).
Note that the compressor assigns bit patterns to the indicator flags
using the following rules:
1. The most probable headers have all "0" indicator flags
2. The indicator flags for the next header format are calculated by
adding 1 to the previous flags (treated as an integer) and
padding with enough 0s to reach the correct length
As an example, the indicator flags for a set of compressed header
formats are given below:
Price, et al. Expires August 2, 2002 [Page 69]
Internet-Draft Framework for EPIC-LITE February 2002
main_list
Compressed header format No. of flags Cumulative_N
1 2 1
2 2 2
3 3 3
4 4 4
5 4 5
6 4 6
7 5 7
8 6 8
9 6 9
flag_list
No. of flags N Bit pattern of flags
2 1 00
3 3 100
4 4 1010
5 7 11010
6 8 110110
Note that the most probable compressed header format will have all
"0" indicator flags, whilst the least probable header format will
have all "1" indicator flags (except for the bit pattern "111" if
this is reserved for the ROHC [1] framework).
A.4 Library of methods
This section gives pseudocode for each of the methods in the library.
Note that for each method three pieces of pseudocode are given:
corresponding to the function COMPRESS, and procedures DECOMPRESS and
BUILD described previously.
Note that all of the global variables required for these procedures
are defined at the beginning of Appendix A.
It is assumed that as soon as the 'return' command is encountered,
the procedure stops.
For COMPRESS functions which check through the r values stored in the
context, the value of r is implementation-specific. Note that if any
of the r context values is empty, any method attempting to compress
relative to the context will automatically fail.
A.4.1 STATIC
STATIC (P%)
Price, et al. Expires August 2, 2002 [Page 70]
Internet-Draft Framework for EPIC-LITE February 2002
COMPRESS (STATIC)
var context_val, item
var n, i
context (enc_index, 1, context_val)
n = length (context_val)
# check that the value to be compressed matches each of the r
# values stored in context for this encoding - if not then
# STATIC can't be used to compress this encoding
for i = 1 to r
context (enc_index, i, context_val)
if (context_val <> top (uncompressed_data, n)) then
return false
endif
end loop
pop (uncompressed_data, n, item)
save (enc_index, item, storage)
enc_index = enc_index + 1
return true
end COMPRESS
DECOMPRESS (STATIC)
var context_val
context (enc_index, 1, context_val)
push (uncompressed_data, context_val)
save (enc_index, context_val, storage)
enc_index = enc_index + 1
end DECOMPRESS
BUILD (STATIC, P, format)
var item
item.P = P
item.N = 0
empty (item.id)
append (format, item)
end BUILD
A.4.2 IRREGULAR
Price, et al. Expires August 2, 2002 [Page 71]
Internet-Draft Framework for EPIC-LITE February 2002
IRREGULAR(n,P%)
COMPRESS (IRREGULAR)
var item
pop (uncompressed_data, n, item)
push (compression_stack, item)
save (enc_index, item, storage)
enc_index = enc_index + 1
return true
end COMPRESS
DECOMPRESS (IRREGULAR)
var item
pop (compression_stack, n, item)
push (uncompressed_data, item)
save (enc_index, item, storage)
enc_index = enc_index + 1
end DECOMPRESS
BUILD (IRREGULAR, P, format)
var item
item.P = P
item.N = n
empty (item.id)
append (format, item)
end BUILD
A.4.2.1 IRREGULAR-PADDED
IRREGULAR-PADDED(n,k,P%)
COMPRESS (IRREGULAR-PADDED)
var item, temp
if (value (top (uncompressed_data, n - k)) <> 0) then
return false
else
pop (uncompressed_data, n, item)
temp = lsb (item, k)
push (compression_stack, temp)
Price, et al. Expires August 2, 2002 [Page 72]
Internet-Draft Framework for EPIC-LITE February 2002
save (enc_index, item, storage)
enc_index = enc_index + 1
return true
endif
end COMPRESS
DECOMPRESS (IRREGULAR-PADDED)
var item, temp
var full
full = 0
pop (compression_stack, k, temp)
full = full + value (temp)
item = str (n, full)
push (uncompressed_data, item)
save (enc_index, item, storage)
enc_index = enc_index + 1
end DECOMPRESS
BUILD (IRREGULAR-PADDED, P, format)
var item
item.P = P
item.N = k
empty (item.id)
append (format, item)
end BUILD
A.4.3 VALUE
Price, et al. Expires August 2, 2002 [Page 73]
Internet-Draft Framework for EPIC-LITE February 2002
VALUE(n,v,P%)
COMPRESS (VALUE)
var value
if (top (uncompressed_data, n) <> v) then
return false
else
pop (uncompressed_data, n, value)
save (enc_index, value, storage)
enc_index = enc_index + 1
return true
endif
end COMPRESS
DECOMPRESS (VALUE)
var item
item = str (n, v)
push (uncompressed_data, n, v)
save (enc_index, item, storage)
enc_index = enc_index + 1
end DECOMPRESS
BUILD (VALUE, P, format)
var item
item.P = P
item.N = 0
empty (item.id)
append (format, item)
end BUILD
A.4.4 LSB
LSB(k,p,P%)
COMPRESS (LSB)
var context_val, item, temp, new_item, lsb_val, p_item
var n, i
context (enc_index, 1, context_val)
n = length (context_val)
Price, et al. Expires August 2, 2002 [Page 74]
Internet-Draft Framework for EPIC-LITE February 2002
p_item = str (n, p)
new_item = top (uncompressed_data, n)
for i = 1 to r
context (enc_index, i, context_val)
# check new_item in interval
# [value (context_val)-p, value (context_val)-p+2^k]
temp = (new_item - context_val + p_item)
if (value (temp) < 0) or (value (temp) >= 2^k) then
return false
endif
end loop
pop (uncompressed_data, n, item)
lsb_val = lsb (item, k)
push (compression_stack, lsb_val)
save (enc_index, item, storage)
enc_index = enc_index + 1
return true
end COMPRESS
DECOMPRESS (LSB)
var context_val, interval_start, interval_end, recd, p_item
var new_item, twok_item
var n, new, start, end
context (enc_index, 1, context_val)
n = length (context_val)
p_item = str (n, p)
twok_item = str (n, 2^k)
pop (compression_stack, k, recd)
interval_start = context_val - p
interval_end = interval_start + twok_item
new_item = concat (msb (interval_start, (n-k)), recd)
# check whether value (new_item) is in interval
# [value (interval_start), value (interval_end)]
# allowing for the interval to wrap over zero. If not then
# recalculate new_item
start = value (interval_start)
end = value (interval_end)
new = value (new_item)
if (((start < end) and ((new < start) or (new > end))) or
Price, et al. Expires August 2, 2002 [Page 75]
Internet-Draft Framework for EPIC-LITE February 2002
((start > end) and ((new > start) or (new < end)))) then
new_item = concat (msb (interval_end, (n-k)), recd)
endif
push (uncompressed_data, new_item)
save (enc_index, new_item, storage)
enc_index = enc_index + 1
end DECOMPRESS
BUILD (LSB, P, format)
var item
item.P = P
item.N = k
empty (item.id)
append (format, item)
end BUILD
A.4.5 UNCOMPRESSED
UNCOMPRESSED(n,d,m,p)
COMPRESS (UNCOMPRESSED)
var scale_len
var unc, len_item
scale_len = floor( value((top(control_data)) / d) * m + p)
if (stack-size (uncompressed_data) < scale_len) then
return false
else
pop (uncompressed_data, scale_len, unc)
push (unc_fields, unc)
pop (control_data, len_item)
if (length (len_item) <> n) then
return false
endif
push (uncompressed_data, len_item)
return true
endif
end COMPRESS
Price, et al. Expires August 2, 2002 [Page 76]
Internet-Draft Framework for EPIC-LITE February 2002
DECOMPRESS (UNCOMPRESSED)
var scale_len
var unc, len_item
pop (uncompressed_data, n, len_item)
scale_len = floor( (value (len_item) / d) * m + p)
push (control_data, len_item)
pop (unc_fields, scale_len, unc)
push (uncompressed_data, unc)
end DECOMPRESS
BUILD
end BUILD
A.4.6 STACK encoding methods
A.4.6.1 STACK-TO-CONTROL
STACK-TO-CONTROL(n)
COMPRESS (STACK-TO-CONTROL)
var item
pop (uncompressed_data, n, item)
push (control_data, item)
return true
end COMPRESS
DECOMPRESS (STACK-TO-CONTROL)
var item
pop (control_data, item)
push (uncompressed_data, item)
end DECOMPRESS
BUILD (STACK-TO-CONTROL, 100%, format)
end BUILD
Price, et al. Expires August 2, 2002 [Page 77]
Internet-Draft Framework for EPIC-LITE February 2002
A.4.6.2 STACK-FROM-CONTROL
STACK-FROM-CONTROL(n)
COMPRESS (STACK-FROM-CONTROL)
var item
pop (control_data, item)
if (length (item) <> n) then
return false
endif
push (uncompressed_data, item)
return true
end COMPRESS
DECOMPRESS (STACK-TO-CONTROL)
var item
pop (uncompressed_data, n, item)
push (control_data, item)
end DECOMPRESS
BUILD (STACK-TO-CONTROL, 100%, format)
end BUILD
Price, et al. Expires August 2, 2002 [Page 78]
Internet-Draft Framework for EPIC-LITE February 2002
A.4.6.3 STACK-PUSH-MSN
STACK-PUSH-MSN(n)
COMPRESS (STACK-PUSH-MSN)
var temp
temp = str (n, value (MSN) mod 2^n)
push (control_data, temp)
return true
end COMPRESS
DECOMPRESS (STACK-PUSH-MSN)
var item
pop (control_data, item)
end DECOMPRESS
BUILD (STACK-PUSH-MSN, 100%, format)
end BUILD
Price, et al. Expires August 2, 2002 [Page 79]
Internet-Draft Framework for EPIC-LITE February 2002
A.4.6.4 STACK-POP-MSN
STACK-POP-MSN(n)
COMPRESS (STACK-POP-MSN)
var item, temp
pop (uncompressed_data, n, item)
temp = str (n, value (MSN) mod 2^n)
if (item <> temp)
#value on stack wasn't MSN
return false
endif
return true
end COMPRESS
DECOMPRESS (STACK-POP-MSN)
var temp
temp = str (n, value (MSN) mod 2^n)
push (uncompressed_data, temp)
end DECOMPRESS
BUILD (STACK-POP-MSN, 100%, format)
end BUILD
Price, et al. Expires August 2, 2002 [Page 80]
Internet-Draft Framework for EPIC-LITE February 2002
A.4.6.5 STACK-ROTATE
STACK-ROTATE(n,m)
COMPRESS (STACK-ROTATE)
rotate (control_data, n, m)
return true
end COMPRESS
DECOMPRESS (STACK-ROTATE)
rotate (control_data, n, (n - m))
end DECOMPRESS
BUILD (STACK-ROTATE, 100%, format)
end BUILD
A.4.7 INFERRED encoding methods
A.4.7.1 INFERRED-TRANSLATE
INFERRED-TRANSLATE(n,m,a(0),b(0),a(1),b(1)...,a(k-1),b(k-1))
COMPRESS (INFERRED-TRANSLATE)
var item, trans_item
var found, i
found = 0
i = 0
while ((i < k) and (found = 0))
if (value (top (uncompressed_data, m)) = b(i))
pop (uncompressed_data, m, item)
trans_item = str (n, a(i))
push (control_data, trans_item)
found = 1
else
i = i + 1
endif
end while
return found
end COMPRESS
Price, et al. Expires August 2, 2002 [Page 81]
Internet-Draft Framework for EPIC-LITE February 2002
DECOMPRESS (INFERRED-TRANSLATE)
var trans_item
var i, found
found = 0
i = 0
pop (control_data, trans_item)
while ((i < k) and (found = 0))
if (value (trans_item) = a(i))
push (uncompressed_data, m, b(i))
found = 1
else
i = i + 1
endif
end while
end DECOMPRESS
BUILD (INFERRED-TRANSLATE, 100%, format)
end BUILD
Price, et al. Expires August 2, 2002 [Page 82]
Internet-Draft Framework for EPIC-LITE February 2002
A.4.7.2 INFERRED-SIZE
INFERRED-SIZE(n,p)
COMPRESS (INFERRED-SIZE)
var item
var bits_in_byte # usually 8!
if ((bits_in_byte * value (top (uncompressed_data, n))) + p) <>
stack-size (uncompressed_data) then
return false
else
pop (uncompressed_data, n, item)
return true
endif
end COMPRESS
DECOMPRESS (INFERRED-SIZE)
var size
var bits_in_byte # usually 8!
size = (stack-size (uncompressed_data) + n - p) / bits_in_byte)
push (uncompressed_data, n, size)
end DECOMPRESS
BUILD (INFERRED-SIZE, 100%, format)
end BUILD
A.4.7.3 INFERRED-OFFSET
Price, et al. Expires August 2, 2002 [Page 83]
Internet-Draft Framework for EPIC-LITE February 2002
INFERRED-OFFSET(n)
COMPRESS (INFERRED-OFFSET)
var item, base, offset
pop (uncompressed_data, n, item)
pop (control_data, base)
if (length (base) <> n) then
return false
endif
offset = item - base
push (uncompressed_data, offset)
push (uncompressed_data, base)
return true
end COMPRESS
DECOMPRESS (INFERRED-OFFSET)
var item, base, offset
pop (uncompressed_data, n, base)
push (control_data, base)
pop (uncompressed_data, n, offset)
item = offset + base
push (uncompressed_data, item)
end DECOMPRESS
BUILD (INFERRED-OFFSET, 100%, format)
end BUILD
A.4.7.4 INFERRED-IP-CHECKSUM
INFERRED-IP-CHECKSUM(new_method)
COMPRESS (INFERRED-IP-CHECKSUM)
var compress_function
var can_compress
var item, ip_sum
# zero the ip checksum bits in the header
pop (uncompressed_data, 80, item)
pop (uncompressed_data, 16, ip_sum)
push (uncompressed_data, 16, 0)
Price, et al. Expires August 2, 2002 [Page 84]
Internet-Draft Framework for EPIC-LITE February 2002
push (uncompressed_data, item)
compress_function = lookup-compress-function
(extract-name (new_method))
can_compress = call compress_function
(extract-name (new_method))
return can_compress
end COMPRESS
DECOMPRESS (INFERRED-IP-CHECKSUM)
var decompress_function
var item, temp
var init_len, final_len, decomp_len, ip_sum
init_len = stack-size (uncompressed_data)
decompress_function = lookup-decompress-function
(extract-name (new_method))
call decompress_function (extract-name (new_method))
final_len = stack-size (uncompressed_data)
decomp_len = final_len - init_len
ip_sum = compute-16-checksum (uncompressed_data, decomp_len)
pop (uncompressed_data, 80, item)
pop (uncompressed_data, 16, temp)
push (uncompressed_data, 16, ip_sum)
push (uncompressed_data, item)
end DECOMPRESS
BUILD (INFERRED-IP-CHECKSUM, 100%, format)
var build_function
build_function = lookup-build-function
(extract-name (new_method))
call build_function (extract-name (new_method), 100%, format)
end BUILD
A.4.8 NBO
Price, et al. Expires August 2, 2002 [Page 85]
Internet-Draft Framework for EPIC-LITE February 2002
NBO(n)
COMPRESS (NBO)
var original, swapped
var nbo_flag
pop (uncompressed_data, n, original)
choose (nbo_flag of zero or one)
# according to whether original is in network byte order or not
# (1 implies it is, 0 implies it isn't)
# this decision can be made based on the context history
push (uncompressed_data, 1, nbo_flag)
if (nbo_flag = 0) then
swapped = byte-swap (original)
push (uncompressed_data, swapped)
else
push (uncompressed_data, original)
endif
# store the original value or other implementation specific
# information for making decision about flag value
save (enc_index, original, storage)
enc_index = enc_index + 1
return true
end COMPRESS
DECOMPRESS (NBO)
var original, decomped, nbo_flag
pop (uncompressed_data, n, decomped)
pop (uncompressed_data, 1, nbo_flag)
if (value (nbo_flag) = 1 then
original = decomped
else
original = byte-swap (decomped)
endif
push (uncompressed_data, original)
enc_index = enc_index + 1
end DECOMPRESS
BUILD (NBO, 100%, format)
end BUILD
Price, et al. Expires August 2, 2002 [Page 86]
Internet-Draft Framework for EPIC-LITE February 2002
A.4.9 SCALE
SCALE(n)
COMPRESS (SCALE)
var original
var scale_f, scaled_val, remainder
pop (uncompressed_data, n, original)
choose (scale_f) # such that original is changing by a multile
# of scale_f each header. This decision can
# be based on context history
scaled_val = value (original) / scale_f
remainder = value (original) mod scale_f
push (uncompressed_data, n, scaled_val)
push (uncompressed_data, n, remainder)
push (uncompressed_data, n, scale_f)
# store the original value or other implementation specific
# information for making decision about scale_f
save (enc_index, original, storage)
enc_index = enc_index + 1
return true
end COMPRESS
DECOMPRESS (SCALE)
var scaled_val, scale_f, remainder
var original
pop (uncompressed_data, n, scale_f)
pop (uncompressed_data, n, remainder)
pop (uncompressed_data, n, scaled_val)
original = ((scaled_val * scale_f) + remainder) mod 2^n
push (uncompressed_data, n, original)
enc_index = enc_index + 1
end DECOMPRESS
BUILD (SCALE, 100%, format)
end BUILD
Price, et al. Expires August 2, 2002 [Page 87]
Internet-Draft Framework for EPIC-LITE February 2002
A.4.10 OPTIONAL
OPTIONAL(new_method)
COMPRESS (OPTIONAL)
var flag
var compress_function
var can_compress, n
var enc
pop (control_data, flag)
if (value (flag) = 1) then
compress_function = lookup-compress-function
(extract-name (new_method))
can_compress = call compress_function
(extract-name (new_method))
else
choose (format to encode new_method)
# compressor choice of format for new_method, where enc is the
# format chosen
if u_flag = 0 then
# not under U method then pad with bits of zero
n = count-bits (new_method, enc)
push (compression_stack, n, 0)
else
# don't need to pad as under U method
endif
store (method_chosen, OPTIONAL, enc)
can_compress = 1
endif
push (control_data, flag)
return can_compress
end COMPRESS
DECOMPRESS (OPTIONAL)
var flag, item
var decompress_function
var n
var enc
pop (control_data, flag)
if (value (flag = 1)) then
Price, et al. Expires August 2, 2002 [Page 88]
Internet-Draft Framework for EPIC-LITE February 2002
decompress_function = lookup-decompress-function
(extract-name (new_method))
call decompress_function (extract-name (new_method))
else
# enc is the format sent for new_method (obtained from the
# indicator flags)
if u_flag = 0 then
# not under U method so need to remove bits of padding
n = count-bits (new_method, enc)
pop (compression_stack, n, item)
else
# don't need to remove padding as under U method
endif
endif
push (control_data, flag)
end DECOMPRESS
BUILD (OPTIONAL, 100%, format)
var build_function
build_function = lookup-build-function
(extract-name (new_method))
call build_function (extract-name (new_method), P, format)
end BUILD
A.4.11 MANDATORY
MANDATORY(new_method)
COMPRESS (MANDATORY)
var flag
var compress_function
var can_compress
pop (control_data, flag)
if (value (flag) <> 1) then
return false
else
compress_function = lookup-compress-function
Price, et al. Expires August 2, 2002 [Page 89]
Internet-Draft Framework for EPIC-LITE February 2002
(extract-name (new_method))
can_compress = call compress_function
(extract-name (new_method))
endif
push (control_data, flag)
return can_compress
end COMPRESS
DECOMPRESS (MANDATORY)
var decompress_function
var flag
pop (control_data, flag)
decompress_function = lookup-decompress-function
(extract-name (new_method))
call decompress_function (extract-name (new_method))
push (control_data, flag)
end DECOMPRESS
BUILD (MANDATORY, 100%, format)
var build_function
build_function = lookup-build-function
(extract-name (new_method))
call build_function (extract-name (new_method), 100%, format)
end BUILD
A.4.12 CONTEXT
CONTEXT(new_method,k)
COMPRESS (CONTEXT)
var n, j, m
var compress_function
var can_compress
n = ceiling (log2(k-1))
choose (j < k) # compressor choice
m = context-size (new_method)
Price, et al. Expires August 2, 2002 [Page 90]
Internet-Draft Framework for EPIC-LITE February 2002
enc_index = enc_index + j * m
compress_function = lookup-compress-function
(extract-name (new_method))
can_compress = call compress_function
(extract-name (new_method))
push (uncompressed_data, n, j)
enc_index = enc_index + (k - j - 1) * m
return can_compress
end COMPRESS
DECOMPRESS (CONTEXT)
var n, j, m
var decompress_function
var index
n = ceiling (log2(k-1))
pop (uncompressed_data, n, index)
j = value (index)
m = context-size (new_method)
enc_index = enc_index + j * m
decompress_function = lookup-decompress-function
(extract-name (new_method))
call decompress_function (extract-name (new_method))
enc_index = enc_index + (k - j - 1) * m
end DECOMPRESS
BUILD (CONTEXT, 100%, format)
var build_function
build_function = lookup-build-function (new_method)
call build_function (extract-name (new_method), 100%, format)
end BUILD
A.4.13 LIST
LIST(n,d,m,p,z,new_method(0),new_method(1),...,
new_method(k-1),v(0),v(1),...,v(j))
COMPRESS (LIST)
Price, et al. Expires August 2, 2002 [Page 91]
Internet-Draft Framework for EPIC-LITE February 2002
var scale_len, i, can_compress, stack_len, bits
var comp_len, order, presence
var present [0..(k-1)], unc_length
var compress_function
top(control_data, unc_length)
scale_len = floor( value(unc_length) / d) * m + p)
for i = 0 to (k - 1)
present [i] = str (1,0)
end loop
order = 0
bits = ceiling (log2(k-1))
i = 0
list_start_enc_index = enc_index
while (scale_len > 0)
# basically loop through the methods until all scale_len bits
# are compressed and any of the methods which aren't used are
# marked as not used. The order in which methods are checked
# is implementation specific but some ways will require
# changing the order more frequently (reducing efficiency) than
# others.
stack_len = stack-size (uncompressed_data)
can_compress = false
i = 0
while (i < k) and (can_compress = false)
if (value (present [i]) = 0) and
((i >= j) or ((i < j) and
(value (top (uncompressed_data, z)) = v(i)))) then
present [i] = str (1,1)
order = order * 2^bits + i
push (control_data, present [i])
for x = 0 to i
enc_index = enc_index + context-size (new_methods(x))
compress_function = lookup-compress-function
(extract-name (new_method(i)))
can_compress = call compress_function
(extract-name (new_method(i)))
if can_compress = false then
return false
endif
Price, et al. Expires August 2, 2002 [Page 92]
Internet-Draft Framework for EPIC-LITE February 2002
comp_len = stack_len - stack-size (uncompressed_data)
scale_len = scale_len - comp_len
pop (control_data, present [i])
enc_index = list_start_enc_index
if (length (present[i]) <> 1) then
return false
endif
else
i = i + 1
endif
end while
end while
# process remaining LIST entries that have not been used
# (i.e. are not present in the header)
for i = 0 to (k - 1)
if (value (present [i]) = 0) then
push (control_data, present [i])
for x = 0 to i
enc_index = enc_index + context-size (new_methods(x))
order = order * 2^bits + i
compress_function = lookup-compress-function
(extract-name (new_method(i)))
can_compress = call compress_function
(extract-name (new_method(i)))
if can_compress = false then
return false
endif
pop (control_data, present [i])
enc_index = list_start_enc_index
if (length (present[i]) <> 1) then
return false
endif
endif
end loop
presence = 0
for i = 0 to (k - 1)
presence = presence * 2 + value (present[i])
end loop
push (uncompressed_data, k, presence)
push (uncompressed_data, bits*k, order)
Price, et al. Expires August 2, 2002 [Page 93]
Internet-Draft Framework for EPIC-LITE February 2002
return true
end COMPRESS
DECOMPRESS (LIST)
var decompress_function
var presence, order, i, j, bits, uncomp_len, old_len,
var original_len
var present [0..(k - 1)]
var presence_item, order_item
bits = ceiling (log2(k-1))
list_start_enc_index = enc_index
pop (uncompressed_data, bits*k, order_item)
pop (uncompressed_data, k, presence_item)
presence = value (presence_item)
order = value (order_item)
for i = 0 to (k - 1)
present [(k - 1) - i] = lsb (presence, 1)
presence = (presence - value (present [(k - 1) - i])) / 2
end loop
for j = 0 to (k - 1)
i = value (lsb (order, bits))
order = (order รป i )/ 2^bits
push (control_data, present [i])
old_len = stack-size (uncompressed_data)
for x = 0 to i
enc_index = enc_index + context-size (new_methods(x))
decompress_function = lookup-decompress-function
(extract-name (new_method(i)))
call decompress_function (extract-name (new_method(i)))
enc_index = list_start_enc_index
uncomp_len = uncomp_len +
(stack-size (uncompressed_data) - old_len)
pop (control_data, present[i])
original_len = ((uncomp_len - p) * d) / m
push (control_data, n, original_len)
end loop
end DECOMPRESS
Price, et al. Expires August 2, 2002 [Page 94]
Internet-Draft Framework for EPIC-LITE February 2002
BUILD (LIST, 100%, format)
var i
var build_function
var temp_format
item.P = convert-percentage (100%)
item.N = 0
empty (item.id)
append (format, item)
for i = 0 to (k - 1)
empty (temp_format)
build_function = lookup-build-function (
extract-name (new_method(i)))
call build_function (extract-name (new_method(i),
100%, temp_format))
DISCARD (temp_format)
COMBINE (format, temp_format)
end loop
end BUILD
A.4.13.1 LIST-NEXT
LIST-NEXT (n,new_method(0),new_method(1),...,
new_method(k-1),v(0),v(1),...,v(j))
# This pseudocode is very similar to LIST, the differences being
# from where the information about which method to use next comes
# from and how to tell when there is no more data to compress using
# this method
COMPRESS (LIST)
var i, can_compress, bits, order, presence, p
var present [0..(k-1)], v, null
var compress_function
for i = 0 to (k - 1)
present [i] = str (1,0)
end loop
order = 0
bits = ceiling (log2(k-1))
i = 0
Price, et al. Expires August 2, 2002 [Page 95]
Internet-Draft Framework for EPIC-LITE February 2002
pop (control_data, v)
if (length (v) <> n) then
return false
endif
null = str (0, 0)
while (v <> null)
# basically loop through the methods until no more information
# has been put on the control_data stack by the previous method
# (i.e. the end of the list has been reached). The order in
# which methods are checked is implementation specific but some
# ways will require changing the order more frequently
# (reducing efficiency) than others.
can_compress = false
i = 0
while (i < k) and (can_compress = false)
if (value (present [i]) = 0) and
((i >= j) or ((i < j) and (v = v(i)))) then
present [i] = str (1,1)
order = order * 2^bits + i
push (control_data, present [i])
p = stack-pointer (control_data)
compress_function = lookup-compress-function
(extract-name (new_method(i)))
can_compress = call compress_function
(extract-name (new_method(i)))
if can_compress = false then
return false
endif
# find out whether there is more to compress by checking
# the position of the stack pointer
if (p <> stack-pointer (control_data)) then
pop (control_data, v)
if (length (v) <> n) then
return false
endif
pop (control_data, present [i])
else
pop (control_data, present [i])
v = null
endif
Price, et al. Expires August 2, 2002 [Page 96]
Internet-Draft Framework for EPIC-LITE February 2002
if (length (present[i]) <> 1) then
return false
endif
else
i = i + 1
endif
end while
end while
# process remaining LIST-NEXT entries that have not been used
# (i.e. are not present in the header)
for i = 0 to (k - 1)
if (value (present [i]) = 0) then
push (control_data, present [i])
order = order * 2^bits + i
compress_function = lookup-compress-function
(extract-name (new_method(i)))
can_compress = call compress_function
(extract-name (new_method(i)))
if can_compress = false then
return false
endif
pop (control_data, present [i])
if (length (present[i]) <> 1) then
return false
endif
endif
end loop
presence = 0
for i = 0 to (k - 1)
presence = presence * 2 + value (present[i])
end loop
push (uncompressed_data, k, presence)
push (uncompressed_data, bits*k, order)
return true
end COMPRESS
DECOMPRESS is almost the same as for LIST - the only difference being
that there is no need to keep track of length and push it onto the
Price, et al. Expires August 2, 2002 [Page 97]
Internet-Draft Framework for EPIC-LITE February 2002
control stack at the end as this is implicit in the choice of
methods. BUILD is the same as for LIST
A.4.14 FLAG encoding methods
A.4.14.1 N
N(new_method)
COMPRESS (N)
var compress_function
var can_compress, temp
temp = enc_index
compress_function = lookup-compress-function
(extract-name (new_method))
can_compress = call compress_function
(extract-name (new_method))
if (enc_index <> temp) then
clear (temp, storage)
endif
return can_compress
end COMPRESS
DECOMPRESS (N)
var decompress_function
var temp
temp = enc_index
decompress_function = lookup-decompress-function
(extract-name (new_method))
call decompress_function (extract-name (new_method))
if (enc_index <> temp) then
clear (temp, storage)
endif
end DECOMPRESS
BUILD (N, (P = extract-probability (new_method)), format)
var build_function
Price, et al. Expires August 2, 2002 [Page 98]
Internet-Draft Framework for EPIC-LITE February 2002
build_function = lookup-build-function (method)
call build_function (extract-name (new_method), P, format)
end BUILD
A.4.14.2 U
U(new_method)
COMPRESS (U)
var compress_function
var can_compress
if u_flag = 0 then
compression_stack = unc_fields
endif
u_flag = u_flag + 1
compress_function = lookup-compress-function
(extract-name (new_method))
can_compress = call compress_function
(extract-name (new_method))
u_flag = u_flag - 1
if u_flag = 0 then
compression_stack = compressed_data
endif
return can_compress
end COMPRESS
DECOMPRESS (U)
var decompress_function
if u_flag = 0 then
compression_stack = unc_fields
endif
u_flag = u_flag + 1
decompress_function = lookup-decompress-function
(extract-name (new_method))
call decompress_function (extract-name (new_method))
u_flag = u_flag - 1
Price, et al. Expires August 2, 2002 [Page 99]
Internet-Draft Framework for EPIC-LITE February 2002
if u_flag = 0 then
compression_stack = compressed_data
endif
end DECOMPRESS
BUILD (U, (P = extract-probability (new_method)), format)
var build_function
build_function = lookup-build-function (method)
call build_function (extract-name (new_method), P, format)
foreach el in format
el.N = 0
end loop
end BUILD
A.4.15 FORMAT
FORMAT(new_method(0), ..., new_method(k - 1))
COMPRESS (FORMAT)
var n, can_compress, index_val
var compress_function
n = ceiling(log2(k-1))
choose (index_val < k)
# The compressor needs to make a choice on which FORMAT
# to use. The algorithm for making this choice is entirely
# up to the compressor. It may wish to take into account
# compression performance (of compressed packets) and
# flexibility of compression. The selection processing
# should allow a successful match to be made (if possible),
# but must also terminate in the case where the packet is
# incompressible. It may be that a choice is made based on
# "CO" state processing, which should be carried forward
# into IR(-DYN) state packet generation.
compress_function = lookup-compress-function (
extract-name(new_method(index_val)))
can_compress = call compress_function (
extract-name (new_method(index_val)))
Price, et al. Expires August 2, 2002 [Page 100]
Internet-Draft Framework for EPIC-LITE February 2002
if (can_compress <> false) then
current_set = current_set * k + index_val
endif
if can_compress = false then
return false
else
push (uncompressed_data, n, index_val)
endif
return true
end COMPRESS
DECOMPRESS (FORMAT)
var decompress_function
var n, index
n = ceiling(log2(k-1))
pop (uncompressed_data, n, index)
if (compressor_state <> "CO") then
# get-method-list in decode-indicator-flags has to assume
# one of the methods from FORMAT to get a list of methods
# used. This may not be the one actually used according to
# the index so the list of methods (ie method_chosen) must
# be reparsed from the original main_list_elt in light of
# the updated information.
format-get-method-list (main_list_elt, method_chosen,
new_method (value (index)))
current_set = current_set * k + value (index)
endif
decompress_function = lookup-decompress-function (
extract-name (new_method(value (index))))
call decompress_function (
extract-name (new_method(value (index))))
end DECOMPRESS
BUILD (FORMAT, 100%, format)
var j, i
var build_function
var temp_format
Price, et al. Expires August 2, 2002 [Page 101]
Internet-Draft Framework for EPIC-LITE February 2002
if (compressor_state = "CO") then
j = current_set mod k
current_set = current_set / k
build_function = lookup-build-function (
extract-name (new_method(j)))
call build_function (extract-name (new_method(j)),
100%, format)
else
for i = 0 to (k - 1)
empty (temp_format)
build_function = lookup-build-function (
extract-name (new_method(i)))
call build_function (extract-name (new_method(i),
100%, temp_format)
foreach item in temp_format
append (item.id, new_method(i))
append (format, item)
end loop
end loop
DISCARD (format)
endif
end BUILD
Price, et al. Expires August 2, 2002 [Page 102]
Internet-Draft Framework for EPIC-LITE February 2002
A.4.16 CRC
CRC(n,P%)
COMPRESS (CRC)
var crc_function
crc_function = lookup-crc-function (n)
call crc_function (n, crc_static + crc_dynamic, crc)
push (compression_stack, crc)
return true
end COMPRESS
DECOMPRESS (CRC)
pop (compression_stack, n, crc)
end DECOMPRESS
BUILD (CRC, P%, format)
var item
item.P = P
item.N = n
empty (item.id)
append (format, item)
end BUILD
A.4.16.1 MSN-LSB
MSN-LSB(k,p,P%)
COMPRESS (MSN-LSB)
var context_val, item, temp, lsb_val, p_item
var n, i
context (enc_index, 1, context_val)
n = length (context_val)
p_item = str (n, p)
for i = 1 to r
context (enc_index, i, context_val)
Price, et al. Expires August 2, 2002 [Page 103]
Internet-Draft Framework for EPIC-LITE February 2002
# check MSN in interval
# [value (context_val)-p, value (context_val)-p+2^k]
temp = MSN - context_val + p_item
if ((value (temp) < 0) or (value (temp) >= 2^k)) then
return false
endif
end loop
lsb_val = lsb (MSN, k)
push (compression_stack, lsb_val)
save (enc_index, MSN, storage)
enc_index = enc_index + 1
msn_bits = k
return true
end COMPRESS
DECOMPRESS (MSN-LSB)
var context_val, interval_start, interval_end, recd, p_item
var new_item, twok_item, temp, lsbs, twok_extra
var n, m, new, start, end
context (enc_index, 1, context_val)
n = length (context_val)
p_item = str (n, p)
twok_item = str (n, 2^k)
twok_extra = str (n, 2^(k + length (msn_lsbs)))
pop (compression_stack, k, temp)
recd = concat (msn_lsbs, temp)
interval_start = context_val - p_item
interval_end = interval_start + twok_extra
new_item = concat (msb (interval_start, (n-k-length (msn_lsbs))),
recd)
# check whether value (new_item) is in interval
# [value (interval_start), value (interval_end)]
# allowing for the interval to wrap over zero. If not then
# recalculate new_item
start = value (interval_start)
end = value (interval_end)
new = value (new_item)
if (((start < end) and ((new < start) or (new > end))) or
Price, et al. Expires August 2, 2002 [Page 104]
Internet-Draft Framework for EPIC-LITE February 2002
((start > end) and ((new > start) or (new < end)))) then
new_item = concat (msb (interval_end, (n-k-length (msn_lsbs))),
recd)
endif
MSN = new_item
save (enc_index, new_item, storage)
enc_index = enc_index + 1
end DECOMPRESS
BUILD (MSN-LSB, P, format)
var item
item.P = P
item.N = k
empty (item.id)
append (format, item)
end BUILD
Price, et al. Expires August 2, 2002 [Page 105]
Internet-Draft Framework for EPIC-LITE February 2002
A.4.16.2 MSN-IRREGULAR
MSN-IRREGULAR(n,P%)
COMPRESS (MSN-IRREGULAR)
push (compression_stack, MSN)
save (enc_index, MSN, storage)
enc_index = enc_index + 1
msn_bits = n
return true
end COMPRESS
DECOMPRESS (MSN-IRREGULAR)
pop (compression_stack, n, MSN)
save (enc_index, MSN, storage)
enc_index = enc_index + 1
end DECOMPRESS
BUILD (MSN-IRREGULAR, P, format)
var item
item.P = P
item.N = n
empty (item.id)
append (format, item)
end BUILD
Price, et al. Expires August 2, 2002 [Page 106]
Internet-Draft Framework for EPIC-LITE February 2002
A.4.16.3 SET-MSN
SET-MSN(n)
COMPRESS (SET-MSN)
var item
pop (uncompressed_data, n, item)
MSN = item
return true
end COMPRESS
DECOMPRESS (SET-MSN)
push (uncompressed_data, MSN)
end DECOMPRESS
BUILD (SET-MSN, 100%, format)
end BUILD
A.5 ABNF description of the input language
The following is an ABNF description of a ROHC [1] profile generated
using EPIC-LITE:
<profile> = <profile_identifier> <ws>
<max_formats> <ws>
<max_sets> <ws>
<bit_alignment> <ws>
<npatterns> <ws>
<CO_packet>
[<ws> <IR_DYN_packet>]
[<ws> <IR_packet>]
<ws> = 1*(%x09 | %x0A | %x0D | %x20)
; white space used as
; delimiters
<profile_identifier> = "profile_identifier" <ws>
<hex_integer>
Price, et al. Expires August 2, 2002 [Page 107]
Internet-Draft Framework for EPIC-LITE February 2002
<max_formats> = "max_formats" <ws> <integer>
<max_sets> = "max_sets" <ws> <integer>
<bit_alignment> = "bit_alignment" <ws> <integer>
<npatterns> = "npatterns" <ws> <integer>
<CO_packet> = "CO packet" <ws> <encoding_name>
<IR_DYN_packet> = "IR-DYN packet" <ws>
<encoding_name>
<IR_packet> = "IR packet" <ws> <encoding_name>
<integer> = 1*(<digit>)
<digit> = "0" | "1" | "2" | "3" | "4" |
"5" | "6" | "7" | "8" | "9"
<hex_integer> = "0x" <hex_digit> *(<hex_digit>)
<hex_digit> = <digit> | "a" | "b" | "c" | "d"
| "e" | "f" | "A" | "B" | "C" |
"D" | "E" | "F"
The following is an ABNF description of a new encoding method written
using the input language (note that the previous ABNF rules still
apply). Comments are contained between a ";" symbol and the end of
the line, and are ignored in the input language.
<encoding_method> = <encoding_name> <ws> "="
1*(<ws> <field_encoding>)
Price, et al. Expires August 2, 2002 [Page 108]
Internet-Draft Framework for EPIC-LITE February 2002
<field_encoding> = <encoding_name> <ws>
*(<ws> "|" <ws> <encoding_name>)
<encoding_name> = <name> ["(" <parameter> *(","
<parameter>) ")"]
<name> = <letter> *(<letter> | <digit> |
"_" | "-" | "/" | ".")
<letter> = "A" | "B" | "C" | ... | "X" |
"Y" | "Z" | "a" | ... | "z"
<parameter> = <value> | <length> | <offset> |
<probability> | <encoding_name>
<probability> = <digit> [<digit>] [<digit>]
["." <digit> [<digit>]] "%"
<value> = <integer> | <hex_integer> |
<binary_integer>
<binary_integer> = "0b" <bit> *(<bit>)
<bit> = "0" | "1"
<length> = <integer>
<offset> = ["-"] <integer>
Price, et al. Expires August 2, 2002 [Page 109]
Internet-Draft Framework for EPIC-LITE February 2002
Full Copyright Statement
Copyright (C) The Internet Society (2002). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Acknowledgement
Funding for the RFC Editor function is currently provided by the
Internet Society.
Price, et al. Expires August 2, 2002 [Page 110]
