Network Working Group Richard Price, Siemens/Roke Manor
Internet-Draft Robert Finking, Siemens/Roke Manor
Expires: February 2004 Abigail Surtees, Siemens/Roke Manor
Mark A West, Siemens/Roke Manor
October 20, 2003
Formal Notation for Robust Header Compression (ROHC-FN)
<draft-price-rohc-formal-notation-00.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 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 document is a submission of the IETF ROHC WG. Comments should
be directed to its mailing list, rohc@ietf.org.
Abstract
This document defines a proposal for the ROHC-FN: a formal notation
for specifying how to compress and decompress fields from an
arbitrary protocol stack. ROHC-FN is proposed with the intention of
simplifing the creation of new compression profiles to fit within the
ROHC [RFC-3095] framework.
Price et al. [Page 1]
Internet-Draft ROHC-FN October 20, 2003
Table of contents
1. Introduction..................................................2
2. Terminology...................................................3
3. Overview of ROHC-FN...........................................3
4. Normative definition of ROHC-FN...............................7
5. Encoding Methods..............................................12
6. Prolog definitions of encoding methods........................25
7. Bit level worked example......................................34
8. Security considerations.......................................40
9. Acknowledgements..............................................40
10. Authors' addresses............................................40
11. References....................................................40
Appendix A. Supporting Prolog Code................................42
1. Introduction
This draft is the new proposal for the formal notation. The
intention is to update draft-ietf-rohc-formal-notation-01.txt with
this notation if the members of the RoHC working group agree with
this proposal.
ROHC-FN is a simple notation designed to help with the creation of
new ROHC [RFC-3095] header compression profiles. ROHC-FN offers a
library of "encoding methods" that are often used in ROHC profiles,
so new profiles can be defined without needing to redefine this
library from scratch.
Informally, an encoding method is just a function that converts
uncompressed data into compressed data. The simplest encoding
methods only have one input and output: the input is an uncompressed
field and the output is the compressed version of the field. More
complex encoding methods can compress multiple fields at the same
time, e.g. "list" encoding from [RFC-3095], which is designed to
compress an ordered list of fields.
The features required for defining ROHC-FN are offered by the
programming language Prolog. As such ROHC-FN is defined both in
English and also in Prolog. The English definition is more
digestible but less formal. The Prolog definition is less digestible
but totally precise in that it allows any profile defined using ROHC-
FN to be compiled and executed, allowing the profile's behaviour to
be observed on real data. Hence where any ambiguity appears in the
English definition, the Prolog definition will clarify the issue.
There should however, be no conflicts between the English and Prolog
definitions. Any such conflicts should be reported to the authors.
Price et al. [Page 2]
Internet-Draft ROHC-FN October 20, 2003
Note that this draft contains a standalone definition of ROHC-FN
(i.e. there is no need to understand Prolog in order to understand
ROHC-FN).
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 [RFC-2119].
Control field
Control fields are transmitted from a ROHC compressor to a ROHC
decompressor, but are not part of the uncompressed protocol header
itself. An example is a checksum field over the header to ensure
robustness against bit errors and dropped packets.
Encoding method
Encoding methods are functions that can be applied to compress
fields in a protocol header.
Field
ROHC-FN divides the protocol to be compressed into a set of
contiguous bit patterns known as fields.
Library of encoding methods
The library of encoding methods contains a number of commonly used
encoding methods for compressing header fields.
Profile
A ROHC [RFC-3095] profile is a description of how to compress a
certain protocol stack over a certain type of link. Each profile
includes packet formats to compress the headers and a state machine
to control the actions of each endpoint.
3. Overview of ROHC-FN
This section gives an overview of ROHC-FN and explains how it can be
used to compress header fields as part of a ROHC profile.
3.1. Scope of ROHC-FN
The following section describes the scope of ROHC-FN, and explains
how it relates to the overall ROHC framework and also how it relates
to specific ROHC profiles.
Price et al. [Page 3]
Internet-Draft ROHC-FN October 20, 2003
The ROHC framework is common to all profiles: it defines the general
principles for doing ROHC compression. It defines the profile
concept, which makes ROHC a general platform for compression schemes.
It sets link layer requirements, and in particular negotiation
requirements for all ROHC profiles. It defines a set of common
functions such as Context Identifiers (CIDs) and padding and
segmentation (useful if the link layer can only handle a limited
range of packet sizes). It also defines common packet formats (IR,
IR-DYN, Feedback, Short-CID expander, etc.), and it defines a
generic, profile independent, handling of feedback.
A ROHC profile is a description of how to compress a certain protocol
stack over a certain type of link. For example, ROHC profiles are
available for RTP/UDP/IP and many other protocol stacks.
Each ROHC profile can be further subdivided into the following two
components:
a) Packet formats for compressing and decompressing headers
b) State machine
The job of the packet formats is to define how to compress and
decompress headers. The packet formats must define the compressed
version of each uncompressed header (and vice versa).
The packet formats will typically compress headers relative to a
"context" of field values from previous headers in a flow. This
improves the overall compression ratio, due to taking into account
redundancies between successive headers.
The job of the state machine is to ensure that the profile is robust
against bit errors and dropped packets. The state machine manages
the context, providing feedback and other mechanisms to ensure that
the compressor and decompressor contexts are kept in sync.
ROHC-FN is designed to help provide the packet formats for use in new
ROHC profiles. It offers a library of encoding methods for
compressing fields, and a mechanism for combining these encoding
methods to create new packet formats tailored to a specific protocol
stack. Note however that the state machine for the new profiles is
beyond the scope of ROHC-FN, and must be provided separately.
3.2. Example using IPv4
Rather than immediately diving in with a formal definition of ROHC-
FN, the following section will give an overview of how the notation
is used by means of an example. The example will develop the formal
notation for an encoding method capable of compressing a single,
well-known header: the IPv4 header.
Price et al. [Page 4]
Internet-Draft ROHC-FN October 20, 2003
The first step is to specify the overall encoding method for the IPv4
header. In this case we will use the single_packet_format encoding
method. This encoding method compresses a header by dividing it into
fields, compressing each field in turn, and then sending a single
packet containing the compressed version of each field. We define
this by writing the following in ROHC-FN:
ipv4_header ::= single_packet_format,
{
The symbol "::=" means "is encoded as", so the above expression
defines that the IPv4 header is encoded by sending a single packet
format (containing the compressed version of each field in the IPv4
header).
Note the opening curly brace, which indicates that subsequent
definitions are local to the ipv4_header. This scoping mechanism
helps to clarify which fields belong to which headers: it becomes
especially useful when compressing complex protocol stacks with
several headers and fields, often sharing the same names.
The next step is to specify the fields contained in the uncompressed
IPv4 header, which is accomplished in ROHC-FN as follows:
uncompressed_data ::= version, % 4 bits
header_length, % 4 bits
tos, % 6 bits
ecn, % 2 bits
length, % 16 bits
id, % 16 bits
reserved, % 1 bits
dont_frag, % 1 bits
more_fragments, % 1 bits
offset, % 13 bits
ttl, % 8 bits
protocol, % 8 bits
checksum, % 16 bits
src_addr, % 32 bits
dest_addr, % 32 bits
After this, we specify the fields contained in the compressed header.
Exactly what appears in this list of fields depends on the encoding
methods used to encode the uncompressed fields - we may be able to
compress certain fields down to 0 bits, in which case they do not
need to be sent in the compressed header at all as explained below.
Note that the order of the fields in the compressed header is
independent of the order of the fields in the uncompressed header.
Price et al. [Page 5]
Internet-Draft ROHC-FN October 20, 2003
compressed_data ::= src_addr, % 32 bits
dest_addr, % 32 bits
length, % 16 bits
id, % 16 bits
ttl, % 8 bits
protocol, % 8 bits
tos, % 6 bits
ecn, % 2 bits
dont_frag, % 1 bits
The next step is to specify the encoding methods for each field in
the IPv4 header. These will be taken from well-known encoding
methods in the ROHC-FN library. Note that the intention here is to
illustrate the use of the notation, rather than to describe the
optimum method of compressing IPv4 headers, therefore for the purpose
of the example we will use just three encoding methods from the ROHC-
FN library.
The "value" encoding method can compress any field whose length and
value is fixed. No compressed bits need to be sent because the field
can be reconstructed using its known size and value. The "value"
encoding method is used to compress five fields in the IPv4 header as
described below:
version ::= value(4, 4),
header_length ::= value(4, 5),
reserved ::= value(1, 0),
more_fragments ::= value(1, 0),
offset ::= value(13, 0),
Note that the first parameter indicates the length of the
uncompressed field in bits, and the second parameter gives its
integer value.
The "irregular" encoding method can be used to encode any field whose
length is fixed. It is a very general encoding method that can be
used for fields to which no other encoding method applies. All of
the bits in the uncompressed field need to be sent; hence this
encoding does not give any compression.
tos ::= irregular(6),
ecn ::= irregular(2),
length ::= irregular(16),
id ::= irregular(16),
dont_frag ::= irregular(1),
ttl ::= irregular(8),
protocol ::= irregular(8),
src_addr ::= irregular(32),
dest_addr ::= irregular(32),
Price et al. [Page 6]
Internet-Draft ROHC-FN October 20, 2003
The final encoding method is at the opposite extreme of generality:
"inferred_ip_checksum" is a specific encoding method for calculating
the IP checksum from the rest of the header values. Like the "value"
encoding method, no compressed bits need to be sent, since the field
value can be entirely reconstructed using the values in the other
fields of the IP header.
checksum ::= inferred_ip_checksum
}
We have now defined the format of the compressed IPv4 header, and
provided enough information to allow an implementation to construct
the compressed header from an uncompressed header and vice versa.
This completes the example.
3.3. Adding robustness
ROHC profiles are designed to be "robust" against packet loss and
residual bit errors on the link over which header compression takes
place. A well-designed profile can cope with these errors without
losing additional packets or introducing additional bit errors in the
decompressed headers.
ROHC-FN offers two techniques to help ensure that a ROHC profile is
robust. Firstly, the encoding methods in the ROHC-FN library are
designed to tolerate a certain number of dropped or misordered
packets between the compressor and decompressor. For example, Least-
Significant Bit (LSB) encoding can robustly compress fields that
change by a small value between successive headers.
Secondly, the "CRC" encoding method can be used to provide a CRC over
the original uncompressed header, to detect faulty decompressed
headers and prevent them from mistakenly being used to update the
context. This situation is illustrated in Figure 1:
CRC failure
+--------------+ +--------------+ ================ +--------------+
-| Valid header |-| Valid header |-|Invalid header|-| Valid header |-
+--------------+ +--------------+ ================ +--------------+
| | | | | |
>------+ +------>------+ +--------------->--------------+ +------>
context context
Figure 1: Preventing accidental corruption of the context
4. Normative definition of ROHC-FN
This section gives the normative definition of ROHC-FN, including its
syntax and any data structures that it requires.
4.1. ROHC-FN syntax
Price et al. [Page 7]
Internet-Draft ROHC-FN October 20, 2003
Defining how to compress a field or header using ROHC-FN is extremely
simple. All that needs to be provided is the following:
a) A name for the field or header to be compressed.
b) An encoding method, together with any parameters it needs,
including subfield parameters.
For example:
field_name ::= encoding_method(param1, param2, ...),
{
sub_field_1 ::= ...
sub_field_2 ::= ...
etc.
}
All formal notation is represented using this simple construct.
Because the construct can be nested, complex relationships can be
notated.
4.2. Comments
Comments do not affect the formal meaning of what is notated, but can
be used to improve readability. The use of them is entirely
optional.
It should be noted that profiles will be read, by many readers, in
terms of their intuitive English meaning. Such readers will not
necessarily differentiate between the formal and commentary parts of
a profile. It is essential therefore that any comments written are
correct. They should not be considered of lesser importance than the
rest of the notation in a profile, and should be strictly consistent
with it.
If the profile author does wish to insert free English text into the
profile, in order to explain why something has been done a particular
way, to clarify the intended meaning of the notation, or to elaborate
on some point, they can do so by use of one of the two commenting
styles described below.
4.2.1. End Of Line Comments
The end of line comment style makes use of the % comment character.
Any text between the % character and the end of the line has no
formal meaning. For example:
%-----------------------------------------------------------------
% IR-REPLICATE packet formats
%-----------------------------------------------------------------
Price et al. [Page 8]
Internet-Draft ROHC-FN October 20, 2003
% The following fields are included in all of the IR-REPLICATE
% packet formats:
%
replicate_common ::= discriminator, % 8 bits
tcp.seq_number, % 32 bits
tcp.flags.ecn, % 2 bits
4.2.2. Block Comments
The block comment style makes use of the /* and */ delimiters. Any
text between the /* and the */ has no formal meaning. For example:
/******************************************************************
* IR-REPLICATE packet formats
*****************************************************************/
/* The following fields are included in all of the IR-REPLICATE
* packet formats:
*/
replicate_common ::= discriminator, /* 8 bits */
tcp.seq_number, /* 32 bits */
tcp.flags.ecn, /* 2 bits */
The block comment style allows comments to be nested (i.e. comments
inside comments are allowed). For example:
/* Old version temporarily kept as a comment; delete when finalised
*
*replicate_common ::= discriminator, /* 8 bits */
* tcp.scaled_seq_number, /* 22 bits */
* tcp.seq_number_residue, /* 10 bits */
* tcp.flags.ecn, /* 2 bits */
*/
Readers familiar with the C, C++ or Java programming languages,
should take careful note of this fact!
Price et al. [Page 9]
Internet-Draft ROHC-FN October 20, 2003
4.3. Implementation structures
The following section gives some information about the data that must
be stored by an implementation of a ROHC profile. ROHC-FN assumes
that the data is available as a single structure, indexed by the name
of the relevant field. Note, however, that provided the relevant
data is available, the exact way in which the data structure is
stored is up to the implementation itself.
ROHC-FN assumes that for each field to be compressed, the following
eight attributes are available:
uncomp, uncomp_start, uncomp_length, comp, comp_start, comp_length,
context, updated_context
The notation to access any of the attributes for a particular field,
is the name of the attribute, followed by the field name in brackets.
For example;
uncomp(tcp_ip.options.list_length)
Gives the uncompressed value of the tcp_ip.options.list_length field.
Each of the attributes is explained in more detail below.
4.3.1. The uncomp attribute
The uncomp attribute contains the uncompressed value of the field.
This can either be the value of a field from the uncompressed header,
or the uncompressed value of a control field, but all fields have an
uncomp value attribute.
4.3.2. The uncomp_start attribute
The uncomp_start attribute contains the position in the header that
the uncompressed field starts at, specified in bits. Control fields
do not make use of this attribute.
4.3.3. The uncomp_length attribute
The uncomp_length attribute contains the length of the uncompressed
field, specified in bits. All fields have an uncomp_length
attribute.
4.3.4. The comp attribute
The comp attribute contains the compressed value of the field, i.e.
the value of the field as it appears in the compressed header. Note
that this will not be used for fields which are not encoded; some
don't appear in the compressed header at all.
Price et al. [Page 10]
Internet-Draft ROHC-FN October 20, 2003
4.3.5. The comp_start attribute
The comp_start attribute contains the position in the compressed
header that the field starts at, specified in bits. All attributes
which appear in the compressed header make use of this attribute.
4.3.6. The comp_length attribute
The comp_length attribute contains the length of the compressed
field, specified in bits. All attributes which appear in the
compressed header make use of this attribute.
4.3.7. The context attribute
The purpose of the context attribute is to allow inter-packet
compression. An analogy can be found in MPEG video compression.
Reasonable video compression can be achieved simply by treating each
frame as a still image and compressing it e.g. using JPEG. However
MPEG compression takes advantage of the fact that successive frames
of video can be compressed more efficiently by taking into account
the similarities between them. Similarly, the context attribute
contains information about the previous value of the field. Note
that there will be no context for the first packet in a stream.
The context attribute is actually key to efficient compression, since
the behaviour of one header is very often related to the behaviour of
previous headers in a flow. For example, the RTP Sequence Number
field increases by 1 for each consecutive header in an RTP stream.
ROHC profiles take into account the dependency between successive
headers by storing and referencing the context attribute. However,
whilst it is possible to do this explicitly, most of the time the
context is referenced implicitly by the encoding methods.
An implementation of ROHC-FN should allow encoding methods to read
values from the context, and should be able to update the context
with the new field values from the current header (or some other
value if that is appropriate).
All fields make use of the context attribute.
4.3.8. The updated_context attribute
The updated_context attribute contains the value that the context
attribute will take for the next header. The state machine for a
ROHC profile defines a specific point at which the context is
updated: at this point the updated_context attribute should be copied
into the context attribute.
All fields make use of the updated_context attribute.
Price et al. [Page 11]
Internet-Draft ROHC-FN October 20, 2003
5. Encoding methods
The ROHC [RFC-3095] standard contains a number of different
techniques for compressing header fields (LSB encoding, value
encoding, list-based compression etc.). Each of these techniques can
be added to the ROHC-FN library so that they can be reused when
creating new ROHC profiles.
The following encoding methods are all defined in English; a formal
Prolog definition for each is given in the next section. The sub-
section numbers are the same as those in the next section to make it
straightforward to refer from English to Prolog and vice versa,
without cluttering up the English definitions with Prolog.
5.1. Basic encoding methods
This section defines the simplest set of encoding methods. All these
encoding methods are self-contained in that they do not need to refer
to other fields.
5.1.1. Value
The value encoding method is used to encode header fields which
always have a fixed size and value. E.g. the IPv6 header version
number is a four bit field that always has the value 6:
version ::= value(4, 6)
Since the value is fixed, it is omitted from the compressed header.
As with all omitted fields the author of a profile has the option of
notating a value encoded field as a zero bit field in the compressed
header field order list, if they so wish.
5.1.2. Irregular
The "irregular" encoding method leaves the field untouched. The
field in the compressed packet will have an identical bit pattern to
the original field in the uncompressed packet. E.g.
age_in_years ::= irregular(16)
Note that since the field divisions specified in the profile are
completely arbitrary, there is no reason not to take what is
specified as a single field in a header specification and break it
down into smaller fields.
Using this technique, fields which are only irregular in part can be
better compressed. E.g. if the above field was the age in years of
the human who originated the packet, and if we knew from the protocol
definition that the field would never have a value greater than 123,
Price et al. [Page 12]
Internet-Draft ROHC-FN October 20, 2003
we would know that the most significant bits would always be zero, so
we might encode it as follows:
age_in_years_part_1 ::= value(9,0),
age_in_years_part_2 ::= irregular(7)
5.1.3. Static
The "static" encoding method compresses a field whose length and
value is the same as for the previous header in the flow. E.g.
src_port ::= static
Since the field value is the same as the previous field value, the
entire field can be reconstructed from the context, so it is
compressed to zero bits and does not appear in the compressed header.
5.1.4. LSB
The "lsb" encoding method compresses a field whose value differs by a
small amount from the value stored in the context. E.g.
msn ::= lsb(2,0),
The "lsb(k, p)" encoding method can compress a field f whose value
lies between (context(f) - p) and (context(f) - p + 2^k - 1)
inclusive. In particular, if p = 0 then the field value can only
stay the same or increase relative to the previous header in the
flow. If p = -1 then it can only increase, whereas if p = 2^k then
it can only decrease.
The compressed field takes up the specified number of bits in the
compressed header. See the ROHC [RFC-3095] standard for a full
definition of LSB encoding.
5.1.5. Index
The "index" encoding method compresses a field whose value is one of
a list of possible values. E.g.
id_flags ::= index(1, ['11111000':'10001111'])
The index encoding method takes two parameters. The first is the
number of bits to use to encode the index. The second is the list of
possible values the field can take. For "index(n, the_list)", the
length of the_list can be anything up to 2^n items long.
The compressed packet contains the index of the value to be
compressed. The leftmost item in the list has an index of 0, the
next item an index of 1 and so on.
Price et al. [Page 13]
Internet-Draft ROHC-FN October 20, 2003
The compressed field takes up the specified number of bits in the
compressed header.
5.2. Relative Field Encoding Methods
The encoding methods in this section are all able to encode a field
whose value can be inferred from the value of another field or
fields.
Fields can be referred to outside of the scope they are defined in,
by using the '.' scoping notation. So for example, to refer to
field_1 from outside the scope of the test_single_format header
(where it is defined), use 'test_single_format.field_1'. The same
scoping mechanism can be used for subfields within fields.
5.2.1. Same As
The "same_as" encoding method is used for fields that are always
identical to another field. Whilst having two identical fields in a
header is not normal, "same_as" is also useful for encoding fields
that are needed by encoding techniques that need to refer to other
fields. For example:
count ::= inferred_offset(4),
{
base_field ::= same_as(test_offset.id),
offset ::= value(4,3)
}
Since the same_as encoding method gets the entire value of the field
from another field, it takes up zero bits in the compressed header.
5.2.2. Group
The "group" encoding method is used to group two or more
noncontiguous uncompressed fields together, so that they can be
treated as a single field for compression. This encoding method
takes a single argument, which is the list of fields to be joined
together. This argument is specified as a subfield. For example:
ecn_and_reserved ::= group,
{
field_list ::= ip.ecn,
tcp.ecn,
tcp.reserved
}
Price et al. [Page 14]
Internet-Draft ROHC-FN October 20, 2003
Since the group encoding method gets the entire value of the field
from the fields that it is composed of, it takes up zero bits in the
compressed header.
5.2.3. Expression
This encoding method is used to when the uncompressed value of the
field is defined by a mathematical expression. The expression can be
made up of any of the following components:
Integers Integers can be expressed as decimal values,
binary values (prefixed by 0b), or hex values
(prefixed by 0x). Negative integers are
prefixed by a "-" sign.
Operators The operators +, -, *, / and ^ are available,
along with ( and ) for grouping. Note that
k / v is undefined if k is not an integer
multiple of v (i.e. if it does not evaluate to
an integer).
The precedence for each of the operators, along
with parentheses is given below (higher
precedence first):
(, )
^
*, /
+, -
floor (k, v) Returns k / v rounded down to the nearest
integer (undefined for v == 0).
mod (k, v) Returns k - v * floor(k, v).
log2 (v) Returns the smallest integer k where v <= 2^k,
i.e. it returns the smallest number of bits in
which value v can be stored.
The expression may refer to any of the attributes in the data
structure stored for each field (see above), but the following
attributes are most likely to be useful:
uncomp - the uncompressed value of the field,
uncomp_length - the length of the uncompressed field in bits,
comp - the compressed value of the field,
comp_length - the length of the compressed field in bits,
To access any of the attributes for a particular field, write the
name of the attribute, followed by the field name in brackets. E.g.
uncomp(tcp_ip.options.list_length)
Price et al. [Page 15]
Internet-Draft ROHC-FN October 20, 2003
This will get the uncompressed value of the list length of the tcp
options list. Note that if any of the attributes used in the
expression are undefined, the value of the expression is undefined.
Here is a complete example of expression encoding, which employs the
above attribute:
data_offset ::= expression((uncomp(tcp_ip.options.list_length)
+ 160) / 32)
Since the value of an expression encoded field is constructed
entirely from the expression, it takes up zero bits in the compressed
header.
5.2.4. Constant
"Constant" encoding works in the same manner as expression, but the
expression must yield a value that is constant for all headers.
5.2.5. Derived value
The "derived_value" encoding method is similar to the value encoding
method, except that the length and field value do not have to be
constant, since they are specified as subfields, rather than as in
line parameters. For example:
tcp.seq_number ::= derived_value,
{
field_length ::= constant(8),
field_value ::= expression(uncomp(tcp.seq_number.residue) +
(uncomp(tcp.seq_number.scaled) *
uncomp(tcp.payload_size)))
}
If constant encoding is used for both fields, the encoding method is
identical to value encoding. For example,
field_1 ::= value(4, 11)
Has identical meaning to:
field_1 ::= derived_value,
{
field_length ::= constant(4),
field_value ::= constant(11)
}
Price et al. [Page 16]
Internet-Draft ROHC-FN October 20, 2003
The number of bits that derived_value encoding takes up in the
compressed header depends on the encoding methods used for the length
and value. The above examples would both take up zero bits in the
header since the constant and expression encoding methods both take
up zero bits in the compressed header. If both length and value
encoding methods take up bits in the compressed header, the length
encoding is done first, followed by the value encoding.
5.2.6. Inferred_translate
TBD.
5.2.7. Inferred_size
The "inferred_size" encoding method infers the value of a field from
the total amount of remaining data in the header.
The first parameter specifies the length of the uncompressed field in
bits, and the second parameter specifies an offset that will be
subtracted from the total data length when deriving the value of the
field. E.g.
size_field ::= inferred_size(4, -8)
Since the value of the field is only dependent on the size of the
data, which is known, the encoded field is zero bits long.
5.2.8. Inferred_offset
The "inferred_offset" encoding method compresses a field that takes a
known offset relative to a certain base value. In typical usage the
base value will be specified as the value of another field, although
any value can be specified.
The method has three parameters. The first parameter, length,
defines the length of the field in bits. An offset of up to
(2^length - 1) can be specified from the base value. The length
parameter is specified in parentheses in the normal way. Offset
addition is done modulo 2^length, so negative offsets are possible.
The second parameter specifies the base value, along with how to
encode that value in the compressed header. The third parameter
specifies the offset from the base value, along with the encoding
method for that. Because these two parameters allow for the
specification of encoding methods, they are specified using
subfields, rather than as regular parameters. E.g.
id ::= inferred_offset(16),
{
base_field ::= same_as(msn),
offset ::= static
Price et al. [Page 17]
Internet-Draft ROHC-FN October 20, 2003
}
This says that the id field is 16 bits long, and has a static offset
from the value of the MSN. The exact number of bits it takes to
encode an inferred offset field depends on the encoding methods used
for the base_field and offset. The above examples both take zero
bits, since both the same_as and static encoding methods compress
down to zero bits.
5.2.9. Inferred_sequence
TBD
5.2.10. Inferred_ip_checksum
The "inferred_ip_checksum" encoding method is a very specific
encoding method used to compress the IP checksum field. It should
only be used for that purpose:
checksum ::= inferred_ip_checksum
Since the checksum can be constructed solely from the other fields in
the header, zero bytes are sent for this encoding.
5.3. Control field encoding methods
This section provides a selection of encoding method for handling
control fields, i.e. fields which appear in the compressed header to
control the compression in some way and do not appear in the
uncompressed header at all.
5.3.1. Literal Discriminator
The literal_discriminator encoding method writes a literal bit string
into the compressed header. It is one of two discriminator encoding
methods intended to be used in conjunction with the
multiple_packet_formats encoding method, which allows for more than
one method of compression for a given header. The
literal_discriminator encoding method allows the unique bit pattern
to be specified, in binary, which identifies the particular method of
compression that has been used. The syntax for the
literal_discriminator encoding method is unusual - the discriminator
is simply specified in between two single quote marks. For example
discriminator ::= '011'
The discriminator is added into the compressed header as is, so it
takes up however many bits are in the given literal bit pattern.
5.3.2. Control field
Price et al. [Page 18]
Internet-Draft ROHC-FN October 20, 2003
This encoding method is used for fields that need to be sent in the
compressed header, but which don't appear in the uncompressed header
at all. It takes two parameters, the base field, which is the field
it is based on and the compressed_method, which specifies the method
to use to encode the given field. E.g.
order_data ::= control_field,
{
base_field ::= same_as(test_list.list_of_fields.order),
compressed_method ::= irregular(1)
}.
The exact encoding of a control field, and the number of bits it
takes up are determined by the encoding method used by
compressed_method.
5.3.3. Self-describing values
TBD
5.3.4. Network Byte Order
TBD
5.3.5. Scale
TBD
5.3.6. CRC
The "CRC" encoding method provides a CRC calculated across the
original uncompressed header. The size of the CRC can be altered
depending on the characteristics of the link over which the protocol
is to be transmitted. A sufficiently long CRC should be provided to
ensure the probability that an unexpected error will be missed is
negligible. E.g. A 3 bit CRC,
crc_field ::= crc (3)
CRC algorithm to be described here in a later version of this
document.
5.3.7. Optional field
The "optional_field" encoding method allows for fields that may or
may not be present in the header. This encoding method takes two
arguments, condition, which controls whether the field is present,
and field_val, which describes how to encode the value of the field
when it is present. E.g.
Price et al. [Page 19]
Internet-Draft ROHC-FN October 20, 2003
extension_bits ::= optional_field
{
condition ::= same_as(message_extended),
field_val ::= lsb(4, 0)
}
The condition is considered to be "false" if it evaluates to zero,
and "true" otherwise.
Note that the condition must not depend on a field which occurs later
in the packet than the optional field, otherwise the decompressor
will not be able check the condition at the point when it needs to
know whether to include the optional field or not.
The exact length of the field in the compressed header depends on the
encoding methods used for "condition" and "field_val", and for a
particular packet of course it depends on whether the condition is
true or not.
5.4. Packet format encoding methods
This section details encoding methods used to encode whole headers.
All the encoding methods described above are designed to encode
single fields within headers; the packet format encoding methods
allow the individual fields to be built up into packets. The
encoding methods described in this section are intended for that
purpose, to contain a list of fields and corresponding encoding
methods, by which the whole packet can be encoded.
5.4.1. Single packet format
The "single_packet_format" encoding method specifies a single fixed
encoding for a given kind of header. This is the simplest packet
encoding method. E.g.
Price et al. [Page 20]
Internet-Draft ROHC-FN October 20, 2003
test_single_format ::= single_packet_format,
{
uncompressed_data ::= field_1 : 4 bits
field 2 : 4 bits
compressed_data ::= field_2 : 0 bits
field 1 : 4 bits
field_1 ::= irregular(4),
field 2 ::= value(4, 9)
}
This specifies the order (and length) of the fields in the
uncompressed header, followed by the order (and length) of the fields
in the compressed header, followed by a list of encoding techniques
for each field.
The compressed data will appear in the order specified by the field
order list "compressed_data", with each individual field being
encoded in the manner given for that field. Consequently the length
of the compressed data will be the total of the lengths of all the
individual fields. The above example would encode field_2 first
(zero bits long), followed by field_1 (four bits long), giving a
total length of four bits.
Note that the order of the fields specified in compressed_data does
not have to match the order they appear in the uncompressed_data.
Fields of zero bits length may be omitted from the field order list,
since their position in the list is not significant. So, without
changing the meaning, we could have written the above as:
test_single_format ::= single_packet_format,
{
uncompressed_data ::= field_1, % 4 bits
field 2, % 4 bits
compressed_data ::= field 1, % 4 bits
field_1 ::= irregular(4),
field 2 ::= value(4, 9)
}
5.4.2. Multiple packet formats
This encoding method allows multiple encodings for a given header.
This allows different compression techniques to be used at different
times, depending on what is the most efficient way of compressing a
particular header.
Price et al. [Page 21]
Internet-Draft ROHC-FN October 20, 2003
For example a field may have a fixed value most of the time, but very
occasionally the fixed value may change. Using single_packet_format,
this field would have to be encoded as irregular, even though the
value only changes rarely. Using multiple_packet_formats however we
can provide two alternative encodings, one for when the value remains
fixed and another for when the value changes.
The encoding method is notated in a similar way to the
single_packet_format encoding method; there are however a number of
differences. Firstly, it is necessary to specify the number of
alternative packet formats that are defined, which is done via the
co_format_count field. This is a control field in that it doesn't
appear in the uncompressed header. Typically it will be encoded as a
constant and so won't take up any bits in the compressed header
either, for example:
co_format_count ::= constant(2),
Secondly the field names are different. "uncompressed_data", becomes
"uncompressed_format", and "compressed_data" is split into several
fields, since whilst there is still only a single definition of the
uncompressed packet format, there are obviously several alternative
compressed packet formats. These are defined via fields named
co_format_0, co_format_1, co_format_2 etc., each of which has a
separate set of field encodings associated with it. In particular
each co_format must include a discriminator which uniquely identifies
that particular co_format.
The third difference is that the field encodings appear as subfields
of each compressed packet format. This is necessary to make it
explicit which encoding methods are to be used for which compressed
packet format, for example:
co_format_0 ::= discriminator,
field_1,
{
discriminator ::= '0',
field_1 ::= static
}
Note that the discriminator must always appear first in the field
order list, since the decompressor needs to know what packet format
it is dealing with before it can do anything else with the rest of
the packet.
Finally, default encoding methods can be specified for each field.
The default encoding methods specify the encoding method to use for a
field if a given co_format does not give an encoding method for that
field. This prevents the same encoding method from having to be
spelt out for every co_format. There is no need to specify a field
order list for the default encoding methods, since the field order is
Price et al. [Page 22]
Internet-Draft ROHC-FN October 20, 2003
specified individually for each co_format, so "..." can be given
instead. For example:
default_methods ::= ... ,
{
field_1 ::= value(4,1),
field_2 ::= value(4,2)
}
Note that the normal case will be for all default encodings to be
compressed to zero bits, in which case they are irrelevant to
compressed field order. However if any default encodings are used
which compress to greater than zero bits, their position in the field
order list must be specified explicitly for each packet format.
Putting this altogether, here is a complete example of multiple
packet formats:
test_packet_formats ::= multiple_packet_formats,
{
co_format_count ::= constant(2),
co_format_0 ::= discriminator,
field_1,
{
discriminator ::= '0',
field_1 ::= static
},
co_format_1 ::= discriminator,
field_1,
{
discriminator ::= '11',
field_1 ::= irregular(4)
},
uncompressed_format ::= field_1,
field_2,
default_methods ::= ... ,
{
field_2 ::= value(4,2)
}
}
5.4.3. List of known length
The "list_of_known_length" encoding method compresses a list of items
that do not necessarily occur in the same order for every header.
Example applications for "list" encoding include TCP options and TCP
SACK blocks.
Price et al. [Page 23]
Internet-Draft ROHC-FN October 20, 2003
The encoding method requires two subfields to be supplied: the
overall length of the list (in bits), and the items that can occur in
the list. Each list item is a single field, which must also be
compressed by supplying a suitable encoding method.
The list_of_known_length encoding method allows the list items to
occur in any order in the uncompressed header. Moreover, it is not
necessary for all of the list items to be present in every header.
Once the total list size (in bits) is reached, the
list_of_known_length encoding method stops compressing list items,
even if some of the items have not yet occurred in the list.
If there is more than one valid way of ordering the list items, then
the choice of which way to use is left to the compressor.
The set of list items that are present, and the order in which they
occur can change between successive headers. When they change this
information must be sent to the decompressor, so that it knows which
fields to reconstruct and which order to place them in the
uncompressed header. The list_of_known_length encoding method sends
the order and presence information to the decompressor by creating
two new control fields called "order" and "presence".
The order information starts with a 6 bit field, which specifies how
many entries there are in the order list. The rest of the order list
is a string of n entries, indicating the order of possible options,
where n is specified by the 6 bit field at the start of the order
information. For a list which can contain N different types of list
item, the length of each entry in the list will be the minimum number
of bits required to represent the N different types of entry. For
example if there were between 5 and 8 different types of entry then 3
bits.
The order list contains the indices in the order in which they
occurred. The presence data is a list a 1-bit flags, one per entry
in the list, which are set to "1" to indicate that the list item is
present or "0" if not. These flags occur in the order in which the
entries appear in the list encoding.
The complete description of list encoding, along with at least one
example, will be included in later versions of this document.
5.5. Miscellaneous encoding methods
This section introduces some miscellaneous encoding methods that can
be used to compress fields in a protocol header.
5.5.1. Uncompressible
Price et al. [Page 24]
Internet-Draft ROHC-FN October 20, 2003
TBD
5.5.2. No update
TBD
6. Prolog Definitions of Encoding Methods
This section contains the prolog definitions of the encoding methods
described in English in the previous section. The sub-section
numbers are the same as those in the previous section to make it
straightforward to refer from Prolog to English and vice versa.
Note that if the prolog definitions given below are used in
conjunction with a profile to compress real data, all possible
encodings of each packet will be given by Prolog (if asked for). If
more than one possible encoding is available for a given packet, a
particular implementation of a compressor is free to choose any
suitable encoding (not necessarily the most efficient). Therefore, a
correct implementation of the decompressor needs to be able to handle
all the alternative encodings given.
The Prolog definitions given in this section rely on underpinning
Prolog routines, which are included in Appendix A.
6.1. Basic encoding methods
6.1.1. Value
value(NUM_BITS, V) :-
get_current_comp(NAME),
evaluate(NUM_BITS, V, PROPOSED_VALUE),
(
doing(compression) ->
extract_bits(NAME, NUM_BITS, 0),
uncomp(NAME, VALUE),
PROPOSED_VALUE = VALUE,
comp(NAME, '')
;
doing(decompression) ->
comp(NAME, ''),
uncomp(NAME, PROPOSED_VALUE)
),
updated_context(NAME, PROPOSED_VALUE).
Price et al. [Page 25]
Internet-Draft ROHC-FN October 20, 2003
6.1.2. Irregular
irregular(NUM_BITS) :-
get_current_comp(NAME),
(
doing(compression) ->
extract_bits(NAME, NUM_BITS, 0),
uncomp(NAME, VALUE),
comp(NAME, VALUE)
;
doing(decompression) ->
extract_bits(NAME, NUM_BITS, 1),
comp(NAME, VALUE),
uncomp(NAME, VALUE)
),
updated_context(NAME, VALUE).
6.1.3. Static
static :-
get_current_comp(NAME),
context(NAME, VALUE),
defined(VALUE),
atom_length(VALUE, N),
(
doing(compression) ->
extract_bits(NAME, N, 0),
uncomp(NAME, V), VALUE = V,
comp(NAME, '')
;
doing(decompression) ->
comp(NAME, ''),
uncomp(NAME, VALUE)
),
updated_context(NAME, VALUE).
Price et al. [Page 26]
Internet-Draft ROHC-FN October 20, 2003
6.1.4. LSB
lsb(K, P) :-
get_current_comp(NAME),
context(NAME, CONTEXT_VALUE),
defined(CONTEXT_VALUE),
atom_length(CONTEXT_VALUE, N),
evaluate(N, P - CONTEXT_VALUE, BASE),
(
doing(compression) ->
extract_bits(NAME, N, 0),
uncomp(NAME, U_VALUE),
evaluate(N, (U_VALUE + BASE) mod 2^K, X),
evaluate(N, U_VALUE + BASE, Y),
X = Y,
evaluate(K, U_VALUE, C_VALUE),
comp(NAME, C_VALUE)
;
doing(decompression) ->
extract_bits(NAME, K, 1),
comp(NAME, C_VALUE),
evaluate(N, (C_VALUE + BASE) mod 2^K, X),
evaluate(N, X - BASE, U_VALUE),
uncomp(NAME, U_VALUE)
),
updated_context(NAME, U_VALUE).
6.1.5. Index
TBD
6.2. Relative Field Encoding Methods
6.2.1. Same As
same_as(QFIELD_NAME) :-
get_current_field(CURRENT_NAME),
term_to_atom(QFIELD_NAME, ATOMISED_FIELD_NAME),
(
doing(compression) ->
uncomp(ATOMISED_FIELD_NAME, UNCOMPRESSED_FIELD_VALUE),
uncomp(CURRENT_NAME, UNCOMPRESSED_FIELD_VALUE)
;
doing(decompression) ->
uncomp(CURRENT_NAME, UNCOMPRESSED_FIELD_VALUE),
uncomp(ATOMISED_FIELD_NAME, UNCOMPRESSED_FIELD_VALUE)
).
Price et al. [Page 27]
Internet-Draft ROHC-FN October 20, 2003
6.2.2. Expression
expression(EXPRESSION) :-
get_current_field(NAME),
precision(NUM_BITS),
evaluate(NUM_BITS, EXPRESSION, VALUE),
uncomp(NAME, VALUE).
6.2.3. Constant
constant(VALUE) :-
expression(VALUE).
6.2.4. Choice
TBD
6.2.5. Inferred_translate
TBD.
6.2.6. Inferred_size
inferred_size(LENGTH, OFFSET) :-
get_current_field(NAME),
(
uncomp('', WHOLE_HEADER),
atom_length(WHOLE_HEADER, HEADER_LENGTH),
precision(P),
evaluate(P, (HEADER_LENGTH - OFFSET) / 8, TEMP_FIELD_VALUE),
evaluate(LENGTH, TEMP_FIELD_VALUE, PROPOSED_FIELD_VALUE),
(
doing(compression) ->
extract_bits(NAME, LENGTH, 0),
uncomp(NAME, FIELD_VALUE),
PROPOSED_FIELD_VALUE = FIELD_VALUE,
comp(NAME, '')
;
doing(decompression) ->
comp(NAME, ''),
uncomp(NAME, PROPOSED_FIELD_VALUE)
) ->
true
;
doing(decompression) ->
comp(NAME, ''),
evaluate(LENGTH, 0, PROPOSED_FIELD_VALUE),
uncomp(NAME, PROPOSED_FIELD_VALUE)
).
6.2.7. Inferred_offset
Price et al. [Page 28]
Internet-Draft ROHC-FN October 20, 2003
inferred_offset(LENGTH) :-
get_current_field(NAME),
qualify_name('base_field', NAME, BASE_FIELD),
qualify_name('offset', NAME, OFFSET),
BASE_FIELD,
uncomp(BASE_FIELD, BASE_FIELD_VALUE),
(
doing(compression) ->
extract_bits(NAME, LENGTH, 0),
uncomp(NAME, FIELD_VALUE),
evaluate(LENGTH, FIELD_VALUE - BASE_FIELD_VALUE, PADDED_OFFSET),
uncomp(NAME, PADDED_OFFSET),
uncomp_start(OFFSET, 0),
OFFSET,
uncomp(NAME, FIELD_VALUE)
;
doing(decompression) ->
OFFSET,
uncomp_start(OFFSET, 0),
uncomp(OFFSET, OFFSET),
evaluate(LENGTH, OFFSET + BASE_FIELD_VALUE, PADDED_FIELD_VALUE),
uncomp(NAME, PADDED_FIELD_VALUE)
).
6.2.8. Inferred_sequence
TBD
Price et al. [Page 29]
Internet-Draft ROHC-FN October 20, 2003
6.2.9. Inferred_ip_checksum
inferred_ip_checksum :-
get_current_field(NAME),
(
qualify_name(_, HEADER, NAME),
uncomp(HEADER, HDR_BITS),
sub_atom(HDR_BITS, 0, 80, _, PRE),
sub_atom(HDR_BITS, 96, 64, _, POST) ->
eval16(PRE, VALUE1),
eval16(POST, VALUE2),
sum16(VALUE1, VALUE2, TEMP),
evaluate(16, 65535 - TEMP, CHECKSUM),
(
doing(compression) ->
sub_atom(HDR_BITS, 80, 16, _, CHECKSUM),
uncomp(NAME, CHECKSUM),
comp(NAME, '')
;
doing(decompression) ->
comp(NAME, ''),
uncomp(NAME, CHECKSUM)
)
;
doing(decompression) ->
comp(NAME, ''),
evaluate(16, 0, CHECKSUM),
uncomp(NAME, CHECKSUM)
).
6.3. Control field encoding methods
6.3.1. Discriminator
discriminator(DISCRIMINATOR) :-
get_current_field(NAME),
atom_length(DISCRIMINATOR, NUM_BITS),
(
doing(compression) ->
uncomp(NAME, ''),
comp(NAME, DISCRIMINATOR)
;
doing(decompression) ->
extract_bits(NAME, NUM_BITS, 1),
comp(NAME, D1), DISCRIMINATOR = D1,
uncomp(NAME, '')
).
Price et al. [Page 30]
Internet-Draft ROHC-FN October 20, 2003
6.3.2. Control field
control_field :-
get_current_field(NAME),
qualify_name(base_field, NAME, BASE_NAME),
qualify_name(compressed_method, NAME, Q_NAME),
qualify_name(_, QUALIFIER, NAME),
(
doing(compression) ->
BASE_NAME,
uncomp(BASE_NAME, VALUE),
uncomp(NAME, VALUE),
uncomp_start(Q_NAME, 0),
Q_NAME,
uncomp(Q_NAME, UNCOMP_VALUE),
VALUE = UNCOMP_VALUE,
comp(Q_NAME, COMP_VALUE),
comp(NAME, COMP_VALUE)
;
doing(decompression) ->
comp(QUALIFIER, VALUE),
comp(NAME, VALUE),
comp_start(NAME, START),
comp_start(Q_NAME, START),
Q_NAME,
comp(Q_NAME, COMP_VALUE),
comp(NAME, COMP_VALUE),
uncomp(Q_NAME, UNCOMP_VALUE),
uncomp(NAME, UNCOMP_VALUE),
uncomp(BASE_NAME, UNCOMP_VALUE),
BASE_NAME
).
6.3.3. Self-describing values
TBD
6.3.4. Network Byte Order
TBD
6.3.5. Scale
TBD
Price et al. [Page 31]
Internet-Draft ROHC-FN October 20, 2003
6.3.6. CRC
crc(N) :-
evaluate(N, 0, V),
discriminator(V).
% Place holder, correct definition to follow in a later version
6.3.7. Optional field
TBD
6.4. Packet format encoding methods
6.4.1. Single packet format
single_packet_format :-
get_current_field(NAME),
qualify_name('uncompressed_data', NAME, U_NAME),
qualify_name('compressed_data', NAME, C_NAME),
chosen_packet_format(NAME, U_NAME, C_NAME, no_common_format).
6.4.2. Compressed packet formats
multiple_packet_formats :-
get_current_field(NAME),
(
PREFIX = co ->
true
;
PREFIX = replicate
),
qualify_name('uncompressed_format', NAME, U_NAME),
qualify_name('chosen_format', NAME, CHOSEN_FORMAT),
qualify_name('chosen_common', NAME, CHOSEN_COMMON),
atom_concat(PREFIX, '_formats', FORMATS),
qualify_name(FORMATS, NAME, Q_FORMATS),
Q_FORMATS,
uncomp(Q_FORMATS, NUM_FORMATS),
format_name(NUM_FORMATS, FORMAT_NUM_ATOM),
concat_atom([PREFIX, '_format_', FORMAT_NUM_ATOM],
UNQUALIFIED_C_NAME),
atom_concat(PREFIX, '_common', UNQUALIFIED_COMMON_NAME),
qualify_name(UNQUALIFIED_C_NAME, NAME, C_NAME),
qualify_name(UNQUALIFIED_COMMON_NAME, NAME, COMMON_NAME),
comp(CHOSEN_FORMAT, C_NAME),
comp(CHOSEN_COMMON, COMMON_NAME),
chosen_packet_format(NAME, U_NAME, C_NAME, COMMON_NAME).
Price et al. [Page 32]
Internet-Draft ROHC-FN October 20, 2003
6.4.3. List of known length
list_of_known_length :-
get_current_field(NAME),
qualify_name('list_length', NAME, LIST_LENGTH),
qualify_name('list_items', NAME, LIST_ITEMS),
qualify_name(_, QUALIFIER, NAME),
(
doing(compression) ->
uncomp(QUALIFIER, HEADER),
uncomp_start(NAME, START),
sub_atom(HEADER, START, _, 0, SUB_HEADER),
uncomp(NAME, SUB_HEADER),
LIST_LENGTH,
LIST_ITEMS,
uncomp(LIST_ITEMS, UNCOMP_HEADER),
atom_prefix(SUB_HEADER, UNCOMP_HEADER),
uncomp(NAME, UNCOMP_HEADER),
comp(LIST_ITEMS, COMP_HEADER),
comp(NAME, COMP_HEADER)
;
doing(decompression) ->
comp(QUALIFIER, HEADER),
comp_start(NAME, START),
sub_atom(HEADER, START, _, 0, SUB_HEADER),
comp(NAME, SUB_HEADER),
LIST_LENGTH,
LIST_ITEMS,
comp(LIST_ITEMS, COMP_HEADER),
atom_prefix(SUB_HEADER, COMP_HEADER),
comp(NAME, COMP_HEADER),
uncomp(LIST_ITEMS, UNCOMP_HEADER),
uncomp(NAME, UNCOMP_HEADER)
).
6.4.4. List_n
TBD
6.5. Miscellaneous encoding methods
6.5.1. Uncompressible
TBD
6.5.2. No update
TBD
Price et al. [Page 33]
Internet-Draft ROHC-FN October 20, 2003
7. Bit level worked example
This section gives a worked example at the bit level, showing how a
simple profile describes the compression of real data from an
imaginary packet format. The example used has been kept fairly
simple, whilst still aiming to illustrate some of the intricacies
that arise in use of the notation.
All the formal notation in this section has been tested using the
Prolog definitions of the encoding methods given in section 6.
7.1. Example Packet Format
Our imaginary header contains information about a packet of
sandwiches. It is just 8 bits long, consisting of two four bit
fields:
1. number of sandwiches
2. number of extras (including cake, fruit, etc.)
So for example 10010010 would indicate a packet with 5 sandwiches and
two extras.
7.2. Initial Encoding
An initial definition based solely on the above information is:
sandwich_header ::= single_packet_format,
{
uncompressed_data ::= num_sandwiches : 4 bits
num_extras : 4 bits
compressed_data ::= num_sandwiches : 4 bits
num_extras : 4 bits
num_sandwiches ::= irregular(4),
num_extras ::= irregular(4)
}
This defines the packet nicely, but doesn't actually offer any
compression. If we use it to encode the above header, we get:
Uncompressed header: 10010010
Compressed header: 10010010
This is because we have stated that both fields are irregular - i.e.
we don't know anything about their behaviour.
Price et al. [Page 34]
Internet-Draft ROHC-FN October 20, 2003
7.3. Basic Compression
If packets of sandwiches were standardized to always contain two
extras, regardless of the number of sandwiches, then the second field
would always be 0010. The second field however remains in the header
for backward compatibility reasons. We now have:
sandwich_header ::= single_packet_format,
{
uncompressed_data ::= num_sandwiches : 4 bits
num_extras : 4 bits
compressed_data ::= num_sandwiches : 4 bits
num_extras : 0 bits
num_sandwiches ::= irregular(4),
num_extras ::= value(4, 2)
}
Using this simple scheme, we have successfully encoded the fact that
one of the fields has a permanently fixed value of two, and therefore
contains no useful information. Note that we could just as well have
omitted "num_extras : 0 bits" from the definition of the compressed
data if we so wished.
Using this new encoding on the above header, we get:
Uncompressed header: 10010010
Compressed header: 1001
Which halves the amount of data we need to transmit. However, this
encoding fails to take any advantage of a stream of identical
packets:
Uncompressed header: 10010010
Compressed header: 1001
Uncompressed header: 10010010
Compressed header: 1001
Uncompressed header: 10010010
Compressed header: 1001
7.4. Inter-packet compression
The profile we have defined so far has not compressed the
num_sandwiches field at all. This field can take any value, and so
there is no better single method of encoding this field than the
irregular encoding already used. However using the
Price et al. [Page 35]
Internet-Draft ROHC-FN October 20, 2003
multiple_packet_formats encoding we can avoid having to stick to a
single encoding method.
What would be ideal is to avoid encoding the field on the occasions
when its value is the same as the same field in the preceding header.
This is exactly what static encoding does:
sandwich_header ::= multiple_packet_formats,
{
uncompressed_format ::= num_sandwiches, % 4 bits
num_extras, % 4 bits
co_format_count ::= constant(2),
co_format_0 ::= discriminator, % 1 bits
num_sandwiches, % 0 bits
num_extras, % 0 bits
{
discriminator ::= '0',
num_sandwiches ::= static,
num_extras ::= value(4, 2)
},
co_format_1 ::= discriminator, % 1 bits
num_sandwiches, % 4 bits
num_extras, % 0 bits
{
discriminator ::= '1',
num_sandwiches ::= irregular(4),
num_extras ::= value(4, 2)
}
}
Note that we have had to add a discriminator field, in order that the
decompressor knows which packet format we have used. The format with
a static number of sandwiches is now just 1 bit long. However, the
original packet format (with an irregular number of sandwiches) has
also grown by one bit. An important consideration when creating
multiple packet formats is whether the extra format occurs frequently
enough that the average compressed header length is shorter as a
result. For example if no two packets of sandwiches, with the same
number of sandwiches in, were ever transmitted consecutively, then
the static format packet would never be used and all we have just
achieved is to lengthen our packet by one bit. However it turns out
that it is quite common to send out consecutive packets of sandwiches
which have the same number of sandwiches in, so we achieve a
significant saving by being able to encode the headers of such
packets in a single bit.
Price et al. [Page 36]
Internet-Draft ROHC-FN October 20, 2003
Using the above header, we now get:
Uncompressed header: 10010010
Compressed header: 11001
Uncompressed header: 10010010
Compressed header: 0 ; 11001
Uncompressed header: 10010010
Compressed header: 0 ; 11001
The first header in the stream is compressed the same way as before,
except that it now has the extra 1 bit discriminator at the start.
When a second header arrives, with the same number of sandwiches as
the first, it can now be compressed in two possible ways, either as a
single bit (0), or in the same way as previously.
Prolog execution of a profile will show all possible encodings of a
packet as defined by a given profile, separated by semi-colons.
Either of the above encodings for the packet could be produced by a
valid implementation, although of course a good implementation would
always pick the encoding which led to the best compression of the
packet stream (which is not necessarily the smallest encoding for a
particular packet).
7.5. Variable Length Discriminators
Suppose we do some analysis on sandwich flows and discover that
whilst it is usual for successive packets to have the same number of
sandwiches in them, on the occasions when they don't, the packet is
almost always a "diet" packet. The number of sandwiches in a diet
packet is always one. To encode the flow more efficiently a packet
format needs to be written to reflect this.
This now gives a total of three packet formats, which means we need
three discriminators to differentiate between them. The obvious
solution here is to increase the number of bits in the discriminator
from 1 to two and for example use discriminators 00, 01, and 10.
However we can do slightly better than this.
Any uniquely identifiable discriminator will suffice, so we can use
0, 10 and 11. If the discriminator starts with 0, that's the whole
thing. If it starts with 1 the decompressor knows it has to check
one more bit to determine the packet kind.
It would be erroneous to use 0, 01 and 10 as discriminators since
after reading an initial 0, the decompressor would have no way of
knowing if the next bit was a second bit of discriminator, or the
first bit of the next field in the packet stream.
This gives us the following:
Price et al. [Page 37]
Internet-Draft ROHC-FN October 20, 2003
sandwich_header ::= multiple_packet_formats,
{
uncompressed_format ::= num_sandwiches, % 4 bits
num_extras, % 4 bits
co_format_count ::= constant(3),
co_format_0 ::= discriminator, % 1 bits
num_sandwiches, % 0 bits
num_extras, % 0 bits
{
discriminator ::= '0',
num_sandwiches ::= static,
num_extras ::= value(4, 2)
},
co_format_1 ::= discriminator, % 2 bits
num_sandwiches, % 0 bits
num_extras, % 0 bits
{
discriminator ::= '10',
num_sandwiches ::= value(4, 1),
num_extras ::= value(4, 2)
},
co_format_2 ::= discriminator, % 2 bits
num_sandwiches, % 4 bits
num_extras, % 0 bits
{
discriminator ::= '11',
num_sandwiches ::= irregular(4),
num_extras ::= value(4, 2)
}
}
Here is some example output:
Uncompressed header: 10010010
Compressed header: 111001
Uncompressed header: 10010010
Compressed header: 0 ; 111001
Uncompressed header: 10010010
Compressed header: 0 ; 111001
Uncompressed header: 00010010
Compressed header: 10 ; 110001
Price et al. [Page 38]
Internet-Draft ROHC-FN October 20, 2003
7.6. Default encoding
There is some redundancy in the notation used to define the profile
so far. The num_extras field is the same in every packet format, and
time in the future (e.g. suppose the number of extras is no longer
fixed to 2), the num_extras field would have to be changed in every
packet.
This problem can be avoided by specifying a default encoding for this
field, which also leads to a more concisely notated profile:
sandwich_header_5 ::= multiple_packet_formats,
{
uncompressed_format ::= num_sandwiches, % 4 bits
num_extras, % 4 bits
co_format_count ::= constant(3),
is redefined each time. If the sandwich protocol was changed at some
co_format_0 ::= discriminator, % 1 bits
num_sandwiches, % 0 bits
{
discriminator ::= '0',
num_sandwiches ::= static
},
co_format_1 ::= discriminator, % 2 bits
num_sandwiches, % 0 bits
{
discriminator ::= '10',
num_sandwiches ::= value(4, 1)
},
co_format_2 ::= discriminator, % 2 bits
num_sandwiches, % 4 bits
{
discriminator ::= '11',
num_sandwiches ::= irregular(4)
},
default_methods ::= ... ,
{
num_extras ::= value(4,2)
}
}
The above profile behaves in exactly the same way as the one notated
previously.
Price et al. [Page 39]
Internet-Draft ROHC-FN October 20, 2003
8. Security considerations
This draft describes a formal notation similar to ABNF [RFC-2234],
and hence is not believed to raise any security issues.
9. Acknowledgements
A number of important concepts and ideas have been borrowed from ROHC
[RFC-3095]. Updates to the LIST encoding methods owe much to
discussions with Qian Zhang and Hongbin Liao.
Thanks to Paul Ollis for field labeling; and to Rob Hancock and
Stephen McCann for putting up with the authors' arguments and making
helpful suggestions, frequently against the tide!
The authors would also like to thank Carsten Bormann, Ghyslain
Pelletier, Christian Schmidt, Max Riegel and Lars-Erik Jonsson for
their comments and encouragement. We haven't always agreed, but the
arguments have been fun!
10. Authors' addresses
Richard Price Tel: +44 1794 833681
Email: richard.price@roke.co.uk
Robert Finking Tel: +44 1794 833189
Email: robert.finking@roke.co.uk
Abigail Surtees Tel: +44 1794 833131
Email: abigail.surtees@roke.co.uk
Mark A West Tel: +44 1794 833311
Email: mark.a.west@roke.co.uk
Roke Manor Research Ltd
Romsey, Hants, SO51 0ZN
United Kingdom
http://www.roke.co.uk
11. References
[RFC-2026] "The Internet Standards Process - Revision 3", Scott
Bradner, RFC 2026, Internet Engineering Task Force,
October 1996
[RFC-2119] "Key words for use in RFCs to Indicate Requirement
Levels", Scott Bradner, RFC 2119, Internet Engineering
Task Force, March 1997
Price et al. [Page 40]
Internet-Draft ROHC-FN October 20, 2003
[RFC-2234] "Augmented BNF for Syntax Specifications: ABNF",
D. Crocker and P. Overell, RFC 2234, Internet Engineering
Task Force, November 1997
[RFC-3095] "RObust Header Compression (ROHC)", Carsten Bormann et
al, RFC3095, Internet Engineering Task Force, July 2001
Price et al. [Page 41]
Internet-Draft ROHC-FN October 20, 2003
Appendix A. Supporting Prolog Code
This appendix will, in a later version of the document, contain the
supporting Prolog code that is needed in order to execute a profile
written in ROHC-FN.
Price et al. [Page 42]