Subject: RE: [rohc] Some reflections on the notation discussions in Yokoha ma

From: "Price, Richard" <[email-masked]>
Date: Fri, 2 Aug 2002 15:08:26 +0100

Lars-Erik,

Thanks for the excellent summary of the split between the notation
draft and the algorithms for generating bits-on-the-wire.

I'd like to discuss how the notation draft should be structured in
some more detail. In particular we need to standardise the "interface"
between the notation draft and the algorithms that generate the actual
compressed headers.

The method we are proposing to compress a TCP/IP header breaks the
compression process into two steps:

A.   The uncompressed header is decomposed into fields and mapped to
     a "compressed" version of each field.

B.   The compressed versions of each field are mapped to a single
     compressed header.

The idea of compressing data in two steps is used by many well-known
compression algorithms such as DEFLATE. This algorithm first searches
the uncompressed message for repeated strings, which it then replaces
with "compressed" versions of the strings (i.e. pointers to previous
occurrences of the same string). DEFLATE then uses Huffman encoding
to map the compressed versions of each string onto a single compressed
message. Since both steps involve mapping from one type of data to
another we can legitimately refer to them both as "encodings". However
we should take care to distinguish between the two steps to prevent
confusion - defining the steps in separate drafts should go a long way
to resolving this issue.

For the first step of the TCP/IP compression process we match the
uncompressed data to a set of BNF rules, and for each successfully
matched BNF rule we generate a compressed version of the field. More
specifically, for each BNF rule it is necessary to define the following
information:

1.   How to determine whether the BNF rule matches the uncompressed data.

2.   Probability P specifying the likelihood that the BNF rule will match
     the uncompressed data.
    
3.   Integer N specifying the number of bits needed by the compressed
     version of the field (so 2^N is the total number of field values
     that match the BNF rule).

4.   Compression mapping that converts an uncompressed field value into
     an N-bit compressed field value, and optionally some control fields
     (recall that control fields are new uncompressed data that is
     generated by the BNF rule, and not present in the original header).

5.   Decompression mapping that reverses the compression mapping.

The EPIC-LITE framework draft describes this information using three
subroutines: a "COMPRESS" subroutine describing 1 and 4, a "DECOMPRESS"
subroutine describing 5, and a "BUILD" subroutine describing 2 and 3.
This split reflects how EPIC-LITE generates the final compressed headers.
However it is possible to envisage other algorithms for generating
compressed headers that use the information differently (e.g. we
could have an algorithm that compresses and decompresses the headers
directly from the BNF description, without using an offline step to
first build a set of compressed header formats).

So in the interests of decoupling the notation draft from the
generation of the compressed headers, we should replace the EPIC-LITE
pseudocode with a set of simpler functions that each describe one
of the pieces of information mentioned above. Different algorithms can 
then use whatever information they need when generating the compressed
headers.

Regarding how the drafts should be structured, I'm in favour of keeping
the two encoding steps separated because they can be defined
independently. We already have two algorithms for generating compressed
headers from the same BNF notation (EPIC and EPIC-LITE) and more may be
provided in the future. Conversely it is possible to modify and extend
the notation draft (e.g. by adding new BNF rules) without affecting the
operation of EPIC or EPIC-LITE.

However I don't think that we need to split up the notation draft any
further because it doesn't define the bits-on-the-wire: the algorithms
that build compressed headers can use any of the information generated
by each BNF rule, but they can also discard the information that they
don't require. So splitting the notation draft doesn't buy us anything
from a technical perspective.

Comments on any of the above would be much appreciated!

Regards,

Richard

> -----Original Message-----
> From: Lars-Erik Jonsson (EAB) 
> [mailto:[email-masked]]
> Sent: Friday, August 02, 2002 11:34 AM
> To: [email-masked]'
> Subject: [rohc] Some reflections on the notation discussions 
> in Yokohama
> 
> 
> Hi all,
> 
> At the Yokohama meeting, we seemed to have some disagreements whether
> we should have a unified or modulated approach with the notation. I was
> in favor of the latter, but afterwards I started to wonder whether we 
> really had that different opinions. Maybe I was not really clear with
> what I meant, especially not considering the material we had on the 
> table with two different notation documents. I do think we should have
> one uniform notation, and this is where I think there might have been
> some misunderstanding. However, I think it is important to build that
> notation in such a way that it can be applied in several steps, i.e.
> the input side is a mapping from the original header while the output
> only covers what is needed for the bits-on-the-wire-encoding.
> 
> Another thing that I think has caused some confusion is what we mean
> when we say encoding. There are two kind of encodings involved in
> this and we should try to come up with a terminology that clearly
> shows the difference. We have agreed that the final encoding of the
> compressed header bits is not part of the notation work, but the
> notation obviously do include lots of encoding stuff. The notation
> defines various encoding methods on a per-field level, and this is
> the core content of the notation. As an example, LSB encoding could
> be applied to an original header field, and the notation provides
> formal ways of describing the encoding. What is not part of the
> notation is how to take all encoded fields and turn these into a
> bitstring for transmission as an identifiable compressed header over
> the wire. That could be done in many ways, with certain intelligent
> encoding methods or by hand, and each new notation-based profile
> would have to choose which such encoding to use and with that produce
> the actual compressed header formats. 
> 
> Cheers,
> /L-E
> 
> 
> -----------------------------------
> Lars-Erik Jonsson, M.Sc
> Wireless IP Optimizations
> AWARE - Advanced Wireless Algorithm Research and Experiments
> Ericsson Research, Corporate Unit
> Ericsson AB
> Box 920, S-971 28 Luleå, Sweden
> E-mail: [email-masked]
> Phone: +46 920 20 21 07
> Fax: +46 920 20 20 99
> Home: +46 920 999 57
> 
> My opinions are my personal opinions and should not be considered
> as the opinions of my employer, if not explicitly stated. 
> 
> _______________________________________________
> Rohc mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/rohc
>

---

From: "Lars-Erik Jonsson (EAB)" <[email-masked]>
Date: Wed, 14 Aug 2002 13:33:33 +0200

Richard,

> some more detail. In particular we need to standardize the "interface"

I do not think we need to standardize that. A new profile using the
notation to describe how compression is performed would of course have
to cover also the last step of combining all fields into a single
compressed header, possibly referring to an external encoding algorithm. However, it is up to each new profile to define the compressed formats,
might be with a previously defined encoding principle or as "hand made"
formats, and the formats must of course in some way be clearly described
in the profile specification. The notation helps us to specify 
compressed headers in a much more structured way, potentially by 
using automated tools when writing profiles.

> from a technical perspective.

I think we have some kind of agreement here, things will hopefully be
sorted out when we start to discuss the details of the notation. The
simplified next version of the notation draft will hopefully help to get
discussions going and generate more ideas/opinions.

BR
/L-E