Subject: [rohc] Role and approach of the ROHC formal notation

From: Carsten Bormann <[email-masked]>
Date: Tue, 4 Mar 2003 15:09:54 +0100

ROHCers,

Lars-Erik (who plays chair on this issue) and I have had a little 
discussion on the side on the formal notation.
Actually, it seems to us that we need to have this discussion on the 
list.
We need to get a much better grasp of the role and basic approach of 
the ROHC formal notation before we meet in San Francisco, in order to 
be able to use the precious face time there for wrapping up the more 
sticky points.

So, I would like to invite comments on the views discussed below.
Please do comment even if you haven't been involved in the notation 
work so far, e.g., if you see an issue that is not currently explained 
very well in the document and/or seems to need further discussion.

Gruesse, Carsten

PS.: Looking at the message again, I'd like to point out that one thing 
we *don't* need to converge on at this point is what the basis of the 
formal notation should be, e.g. Haskell vs. Prolog.  I'm just citing 
these two "implementations" of the ROHC-FN approach to underscore the 
points I was trying to make.

Begin forwarded message:

> From: [email-masked] (Dr. Carsten Bormann)
> Date: Tue Mar 4, 2003  07:07:59 Europe/Berlin
> To: "Lars-Erik Jonsson (EAB)" <[email-masked]>
> Subject: Re: Notation questions
>
>     From [email-masked] Mon Mar  3 17:25:37 2003
>     Date: Mon, 3 Mar 2003 17:18:38 +0100
>     From: "Lars-Erik Jonsson (EAB)" <[email-masked]>
>     To: "Carsten Bormann (E-mail)" <[email-masked]>
>     Subject: Notation questions
>
>     Intro:
>
>        For me, notation is about having a well defined way of
>        describing what to send in compressed headers. That
>        description would be a result of the characteristics of
>        the original headers, and the "compression principles"
>        used for the profile.
>
> I think what we came up with is a little different -- it describes the
> meaning of compressed headers in terms of the uncompressed headers.
> Of course, you can leave the latter part out, it just becomes hard to
> have any kind of formal semantics then.  (I.e., you can still decide
> whether a compressed header is syntactically correct -- but for a good
> compression scheme this is true for almost any bit combination.  But
> it becomes hard to assign formal semantics to a parse tree if you
> don't have a formal notation for the uncompressed headers.)
>
>        The notated information could then be used to draw
>        compressed header formats by hand, or one could
>        potentially use some automated means to generate compressed
>        header formats in a more structured way. Whether such formats
>        would be humanly readable or not would depend on the
>        mechanism used, but must in either case be documented in
>        some way in profile specifications.
>
> This drawing mechanism might be a third operational mode of the
> compiled notation programs (the other ones are compression and
> decompression, but see below).
>
>        With EPIC, they had a notation, and two different automated
>        means to generate formats, called EPIC and EPIC-Lite, where
>        both generated a very large set of formats that could not
>        easily be documented. The header generation algorithms do
>        put limitations on how the formats are done, and imply a
>        number of specific ways of operating. An algorithm, such as
>        EPIC, thus constitutes a number of technical compression
>        decisions, things that are far from obvious how to do.
>
>        Which format to use when compressing a packet is further a
>        separate issue. I believe that header formats that are
>        generated by automatic means might provide simpler means
>        to create compressed headers, but these two issues (defining
>        compressed formats and actually compressing headers) are
>        still different parts of what we are discussing.
>
> In an implementation, yes.  In a formal notation, formally defining
> the structure of the compressed packets without defining their
> relationship to the uncompressed packets is not very useful (I'm
> repeating myself).  Once you describe this relationship formally, and
> find a way to compile the formal notation, you can build a compressor
> and a decompressor this way (modulo oracles, see below).
>
>     1) In Richards last e-mails, he seems to say that the notation
>        itself gives the compressed formats (bits on the wire), and
>        I do not buy that. How could that be possible?
>
> I believe Richard's/Mark's idea is that the notation defines all the
> bits in the compressed packet (its "body"), apart from an initial
> discriminator.  This discriminator is what differs between EPIC and
> EPIC-lite.  The discriminator carries all the information that is
> needed to parse the body.  The body carries information that is too
> big to carry in the discriminator; essentially orthogonally encodable
> information.  The discriminator can use interesting tricks like EPIC
> (Huffman on complete discriminators) or, if we want, arithmetic coding
> (I don't know when those patents run out, though).  The notation
> supplies everything that is needed to go into the discriminator
> computation (values, probabilities).
>
>     2) Richard is confusing compressing headers with defining the
>        candidate compressed header formats. Do you understand this?
>
> Well, the compressed header formats are in some way related to the
> uncompressed packet.  The notation captures this relationship.  The
> notation can use an oracle function to be able to derive more than one
> packet format based on the same uncompressed packet.
>
>     3) By using a functional language, exactly what do you mean
>        you would get by compiling the notated information?
>
> That was one question that Richard raised.  Right now, in his proposal
> you get a program that can either compress or decompress, depending on
> a switch thrown initially.  I don't know yet how his oracles work; I
> still have to read it up.
>
> In my proposal, the Prolog program defines a relation (in the
> mathematical sense) between uncompressed and compressed packets.
> Since the relation can have multiple compressed packets for one
> uncompressed packet, the oracle functionality is already built into
> the model.  (Obviously, it also can have multiple uncompressed packets
> for one compressed packet, so you can write incorrect instances of the
> notation.  One useful property of a notation would be to allow
> automatically catching this error -- this may be easier in Richard's
> variant than in mine.)
>
> In both cases, state (context) enters the picture.  Even with that, it
> is not always clear which packet format to use.  The fun part is
> leaving the hard decisions (and, preferably, the implementation
> dependent decisions) to oracles.
>
>     4) Do you really believe that all the kind of stuff we had
>        in 3095 could be captured this way? Note that Roke Manor
>        themselves had problems to make the EPIC stuff operating in
>        anything but unidirectional mode. There is much to consider
>        when using feedback, and operating towards contexts.
>
> Most definitely, the basic approach can.  Whether you would *want* to,
> I don't know.  In other words, the notation we define (i.e., the
> library of encoding rules) may favor packet formats that are different
> from the ones we finally decided to use in 3095.  This is of course
> particularly true if we stick with a single discriminator for the
> whole packet (I believe that is a mistake and you need some form of
> cross-product generation of packet formats, which calls for separate
> discriminators -- something my proposal does not even start to
> address yet).

_______________________________________________
Rohc mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/rohc

---

From: "Price, Richard" <[email-masked]>
Date: Tue, 4 Mar 2003 16:33:53 -0000

> > computation (values, probabilities).

Hi,

It might be simpler to avoid mentioning EPIC and EPIC-lite at this stage,
because the notation can generate a decent set of compressed packet
formats without needing to use either.

In RFC 3095 terminology, both EPIC and EPIC-lite are just encoding
methods, which we may or may not want to use when compressing fields in
a header.  For simplicity let's avoid them for now, and just stick with
the encoding methods that are available in RFC 3095.

In particular, let's try creating a set of compressed packet formats
using the following three encoding methods from RFC 3095:

Static - Encodes a field that takes the same value as in the previous
header.  No "bits on the wire" need to be sent in this case.

Irregular n - Encodes an n-bit field with no discernable pattern (by
sending all n bits in the compressed header).

Self-describing values - Allows a field to be encoded in two different
ways, and sends a 1-bit flag to indicate which way has been chosen.  In
the notation, we denote this encoding method using the symbol "/".

Using these three encoding methods, we can apply ROHC-FN to create a
more complex encoding method designed (say) to handle the TCP Source
Port:

tcp_source_port   ::=   static / irregular (16)

This new encoding method can encode the field either using a single
"0" (if it happens to be the same as in the previous header), or by
sending a "1" followed by the 16-bit Source Port in full.

The new encoding method certainly defines "bits on the wire" - we can
write these out using packet formats as follows:

+-+        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|   or   |1|        TCP Source Port        |
+-+        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The next field in the TCP header can be encoded in the same way:

tcp_destination_port   ::=   static / irregular (16)

Finally, let's join the two fields together to get a set of packet
formats capable of handling both fields:

mini_tcp_header   ::=   tcp_source_port
                        tcp_destination_port

The corresponding packet formats for these two fields are as follows:

+-+-+        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|0|   or   |1|        TCP Source Port        |0|   or
+-+-+        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|1|     TCP Destination Port      |   or
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|1|        TCP Source Port        |1|     TCP Destination Port      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Hopefully it should be clear that we can define how to compress all
of the other fields in a TCP/IP header in a similar manner - then we
just join them up to get our complete "compressed packet formats".

Comments welcome!

Regards,

Richard

---

From: "Price, Richard" <[email-masked]>
Date: Tue, 4 Mar 2003 17:14:42 -0000

Hi,

This is news to us!  Our implementation of EPIC has a full state
machine including feedback, context management, error recovery and
all of the other functionality of RFC 3095.

Perhaps you're thinking of the state machine in the old EPIC-lite
draft, which only supported unidirectional mode?  The reason it
didn't include the more complex features from RFC 3095 was because
we wanted to minimise the risk of IPR claims against the draft -
not because of any technical limitations of a notation-based approach.

Regards,

Richard

---

From: "Lars-Erik Jonsson (EAB)" <[email-masked]>
Date: Wed, 5 Mar 2003 09:29:16 +0100

> draft, which only supported unidirectional mode?  

Yes, that was what I was thinking of. It was rather difficult to
keep up with the changes in the EPIC documents during that period.

Hopefully, this should not be a problem then.

/L-E

---

From: "Lars-Erik Jonsson (EAB)" <[email-masked]>
Date: Wed, 5 Mar 2003 10:28:27 +0100

Richard,

Comments inline...

> It might be simpler to avoid mentioning EPIC and EPIC-Lite at 
> this stage, because the notation can generate a decent set of
> compressed packet formats without needing to use either.

I think referring to EPIC and EPIC-Lite was rather useful here,
because the core of those was actually the glue that, at least
to me, seems to be missing from the current notation->compression
discussion. Last year, we agreed that it is one thing to define 
how to encode each field, and putting all fields together in
compressed headers is another this. The notation obviously covers
the former. The latter includes e.g. how to create the
"discriminator", as Carsten called it. I agree with you that we
do not have to discuss the actual EPIC and EPIC-Lite algorithms
for doing this, but referring to them as Carsten did was still
useful for getting an understanding of the various pieces.

> In RFC 3095 terminology, both EPIC and EPIC-Lite are just encoding
> methods, which we may or may not want to use when compressing 
> fields in a header.

I do not agree with that. An encoding method, in 3095 terminology,
is a way to compress a field, while the core of EPIC and EPIC-Lite
were the algorithms for combining all fields together into 
"distinguishable bits on the wire".

<scroll down>

> write these out using packet formats as follows:

This is a very generic approach, but you do not get very efficient formats.
With these formats, you have one extra bit for each field, and if you want
to have variable length fields, you get even more control bits. The format
"discriminator" gets large. If we want to define automatic means to create
the compressed formats, we need to have means to affect this and reduce
the number of possible combinations to make the discriminator overhead 
smaller.

Anyway, this was still a very good example, but things get much more
complicated when we start addressing fields that are compressed together,
and when we add context interaction. Static fields are just present in
IR/IR-DYN headers, and those are easily defined without automatic means.

BR
/L-E

---

From: "Lars-Erik Jonsson (EAB)" <[email-masked]>
Date: Wed, 5 Mar 2003 11:24:21 +0100

Carsten,

> I think what we came up with is a little different -- it
> describes the meaning of compressed headers in terms of
> the uncompressed headers.

Ok, how does the context(s) come into the picture?

> >        Which format to use when compressing a packet is
> >        further a separate issue. I believe that header
> >        formats that are generated by automatic means might
> >        provide simpler means to create compressed headers,
> >        but these two issues defining compressed formats and
> >        actually compressing headers) are still different
> >        parts of what we are discussing.
>
> In an implementation, yes.  In a formal notation, formally
> defining the structure of the compressed packets without
> defining their relationship to the uncompressed packets is
> not very useful (I'm repeating myself).  Once you describe
> this relationship formally, 
> ******** and find a way to compile the formal notation ********,
> you can build a compressor and a decompressor this way (modulo
> oracles, see below).

Yes, but "the way to compile" is not a "one single obvious way".

> >
> >     1) In Richards last e-mails, he seems to say that the
> >        notation itself gives the compressed formats (bits on
> >        the wire), and I do not buy that. How could that be
> >        possible?
> >
> I believe Richard's/Mark's idea is that the notation defines
> all the bits in the compressed packet (its "body"), apart from
> an initial discriminator.  This discriminator is what differs
> between EPIC and EPIC-Lite.  The discriminator carries all the
> information that is needed to parse the body.  The body carries
> information that is too big to carry in the discriminator;
> essentially orthogonally encodable information.  The notation

Ok, maybe (someone still has to convince me about this) the
notation includes all that is needed to create discriminators,
but as you also indicate, there is not one single way to do this.
The notation does not dictate how to do it, it inly provides the
means to do it. It could be done by hand (as we did in 3095), or
it could be automated using some kind of algorithm, but this is
a decision that must be taken.

> >     2) Richard is confusing compressing headers with
> >        defining the candidate compressed header formats. 
> >
> Well, the compressed header formats are in some way related
> to the uncompressed packet. 

Sure, I would not expect otherwise...=)

> The notation captures this relationship.  The notation can
> use an oracle function to be able to derive more than one

Ok, now we are getting somewhere. Can you elaborate a little
bit on the "oracle" issue? Actually, can you define exactly
what you mean with "oracle", maybe draw some parallel with
well known things, like 3095?

> In other words, the notation we define (i.e., the library
> of encoding rules) may favor packet formats that are
> different from the ones we finally decided to use in 3095.
> This is of course particularly true if we stick with a
> single discriminator for the whole packet (I believe that
> is a mistake and you need some form of cross-product
> generation of packet formats, which calls for separate
> discriminators -- something my proposal does not even start
> to address yet).

I followed you up to "single discriminator", but there you lost
me. Can you elaborate on this?

Thnx,
/L-E

---

From: "Price, Richard" <[email-masked]>
Date: Wed, 5 Mar 2003 13:56:26 -0000

Hi,

If EPIC and EPIC-lite are useful to get an understanding of a
complete notation-based solution, then it's good that Carsten
mentioned them ;-)

However, one point I'd like to clarify is that algorithms like EPIC
and EPIC-lite are for -generating- packet formats, whereas the
notation is for -describing- packet formats.  Another way of
generating packet formats is of course to design them by hand!  But
even if we choose to do this, the notation can still be used to capture
the exact hand-crafted packet formats that we want to use.

I've had a go at explaining this distinction in a bit more detail
using some examples (see below).

> "distinguishable bits on the wire".

Is it always the case that an encoding method compresses exactly one
field?  What about list encoding from RFC 3095?

> This is a very generic approach, but you do not get very efficient formats.

Absolutely - all the original example tries to do is to demonstrate how the
notation gives "bits on the wire".

> "discriminator" gets large.

Ok, let's try something more complicated ;-)

Using the same three encoding methods, we can put in a little more effort
and create the following encoding for the TCP ports:

mini_tcp_header   ::=   format_1 / (format_2 / (format_3 / format_4))

format_1   ::=   static                   ; TCP Source Port
                 static                   ; TCP Destination Port

format_2   ::=   irregular (16)
                 static

format_3   ::=   static
                 irregular (16)

format_4   ::=   irregular (16)
                 irregular (16)

This corresponds to the following packet formats:

+-+        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|   or   |1|0|        TCP Source Port        |   or
+-+        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|1|1|0|     TCP Destination Port      |   or
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|1|1|1|        TCP Source Port        |     TCP Destination Port      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

These packet formats are more efficient than the ones I gave previously,
because a single 1-bit discriminator can be used to indicate that both
the Source and Destination ports are static.

The point I'm trying to make with all of this is that the notation is
just a way of describing how to compress and decompress headers.  If
you use the encoding methods from RFC 3095 then you can create packet
formats just like the ones in 3095, and capture your design decisions
via the formal notation.

Using the notation without EPIC or EPIC-lite can still be quite useful -
the packet formats are "formally" defined, meaning that the notation can
be compiled into executable code.  This saves a lot of implementation
effort!

However, on its own the notation won't reduce the amount of effort
needed to devise efficient new packet formats - for this we need EPIC
or EPIC-lite...

> If we want to define automatic means to create the compressed formats, we
> need to have means to affect this and reduce the number of possible
> combinations to make the discriminator overhead smaller.

This is where EPIC and EPIC-lite come in.  They both offer more efficient
ways of adding discriminators to the compressed header, without having
to go to the trouble of designing the packet formats by hand.

Let's try the above example using EPIC-lite.  We can replace the old
"self-describing values" discriminator (denoted by "/") with a new
discriminator generated by EPIC-lite (which we'll denote using the
symbol "|").

The description of the TCP ports in the formal notation then becomes:

tcp_source_port   ::=   static 90% | irregular (16) 10%

tcp_destination_port   ::=   static 90% | irregular (16) 10%

Note that EPIC-lite needs an additional parameter whenever we offer a
choice of encoding methods - namely the probability that each encoding
method will be used.  EPIC-lite uses this extra information to work out
the best discriminator for each packet format.

In the above example (ignoring byte-alignment and reserving the ROHC
framework indicator bits), EPIC-lite calculates the overall probability
that each packet format will be needed, and assigns shorter discriminators
to the more common formats:

Format:   Source Port:   Destination Port:   Probability:   Discriminator:

   1         static           static              81%            "0"
   2        irregular         static               9%            "10"
   3         static          irregular             9%            "110"
   4        irregular        irregular             1%            "111"

EPIC-lite then sticks the correct discriminator onto the front of each
packet format.  So, we get exactly the same set of packet formats as the
ones we designed by hand above, but generated automatically by the
EPIC-lite algorithm:

+-+        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|   or   |1|0|        TCP Source Port        |   or
+-+        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|1|1|0|     TCP Destination Port      |   or
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|1|1|1|        TCP Source Port        |     TCP Destination Port      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

> IR/IR-DYN headers, and those are easily defined without automatic means.

Fields that are compressed together are easy to handle using the
appropriate encoding method.  For example, suppose that we want to
compress the IP-ID as an offset from the Master Sequence Number.  We can
write this in the notation as follows:

ip_id   ::=   inferred_offset (16, MSN)
              lsb (4, 0) / lsb (8, 0) / irregular (16)

The first line subtracts the Master Sequence Number from the IP-ID.  The
second line compresses the resulting offset by sending a choice of 4 LSBs,
8 LSBs or the 16-bit field in full.

Context interactions are also easy to describe using the notation.  By
default every encoding method automatically updates the context - if
we don't want this to be the case for whatever reason then we can write
the following:

tcp_source_port   ::=   no_update (static / irregular (16))

This allows us, e.g. to prevent the context from being updated if the
packet format doesn't include enough bits of CRC.

Regards,

Richard

---

From: "Lars-Erik Jonsson (EAB)" <[email-masked]>
Date: Wed, 5 Mar 2003 16:03:00 +0100

Richard,

> However, one point I'd like to clarify is that algorithms like
> EPIC and EPIC-lite are for -generating- packet formats, whereas
> the notation is for -describing- packet formats.  Another way of
> generating packet formats is of course to design them by hand! 

Exactly, this is what I have been trying to say all the time.
The notation itself is only for describing the content of compressed
headers, it only provides a structured input to the process of
generating compressed packet formats (by hand or by "automated" 
means).

> But even if we choose to do this, the notation can still be
> used to capture the exact hand-crafted packet formats that we
> want to use.

Yes, the notation should be useful in any case, to get a structured
way of documenting the compressed header content.

> Is it always the case that an encoding method compresses
> exactly one field?  What about list encoding from RFC 3095?

I would not call list compression itself an encoding method in
the sense of 3095, but others might have a different opinion in
that regard. List compression is a rather separate part of 3095,
while the encoding methods I would refer to are those that are
listed as encoding methods in section 4.5.

> Absolutely - all the original example tries to do is to 
> demonstrate how the notation gives "bits on the wire".

This is where the inconsistency appears. The notation, as you 
wrote above, does not generate the actual compressed formats.
One use the notated information when generating the formats,
but this is an additional process. Thus, by just notating the
compressed header content, one will not get "bits on the wire".

> Let's try the above example using EPIC-lite.  We can replace
> the old "self-describing values" discriminator (denoted by "/")
> with a new discriminator generated by EPIC-lite (which we'll
> denote using the symbol "|").
>

Do you mean that the current notation language is not providing
enough information to use more sophisticated means to generate
packet formats? The notation above, i.e. with probabilities,
seems to me to be a very generic approach that should be used in
the ROHC FN. Even if we did not have a notation then, of course we
did have such probability expectations in the back of our heads
when we wrote 3095. 

> In the above example (ignoring byte-alignment and reserving
> the ROHC framework indicator bits), EPIC-lite calculates the
> overall probability that each packet format will be needed,
> and assigns shorter discriminators to the more common formats:

In principle, as we did in 3095 (but not by automatic means).

> So, we get exactly the same set of packet formats as the ones
> we designed by hand above, but generated automatically by the
> EPIC-lite algorithm:

Yes, and therefore I also agree that we could potentially gain
from using such automated means. If we still document the output
in a human readible form, it would still be possible to make
minor adjustments by hand, and the formats would be
independently defined by the profile specification.

> > Anyway, this was still a very good example, but things get
> > much more complicated when we start addressing fields that
> > are compressed together, and when we add context interaction.
> 
> Fields that are compressed together are easy to handle using
> the appropriate encoding method.  For example, suppose that we
> want to compress the IP-ID as an offset from the Master
> Sequence Number.  We can write this in the notation as follows:
> 
> Context interactions are also easy to describe using the
> notation.  By default every encoding method automatically
> updates the context - if we don't want this to be the case
> for whatever reason then we can write the following:
> 

Looks ok!

/L-E

---

From: "Price, Richard" <[email-masked]>
Date: Thu, 6 Mar 2003 15:32:09 -0000

Hi,

A minor point - I think that this conflicts with the definition of a
"rule" as used in Prolog.  Our "encoding methods" are a subset of
"Prolog rules" - every encoding method can be represented as a Prolog
rule, but there are plenty of Prolog rules that don't define encoding
methods.

Regards,

Richard

> -----Original Message-----
> From: Carsten Bormann [mailto:[email-masked]]
> Sent: Thursday, March 06, 2003 2:37 PM
> To: Price, Richard
> Cc: 'Lars-Erik Jonsson (EAB)'; [email-masked]
> Subject: RE: [rohc] Role and approach of the ROHC formal notation
> 
> 
> I liked "rule".  Short, sweet, but does not mean to much (i.e., does not
> get in the way of understanding).  (For the same reason, I prefer "label" or
> maybe "binding" over "variable".)  It is completely OK to define a *small*
> number of "new" terms for *core* concepts of the FN.
> 
> Some typical mistakes when choosing terminology:
> 1) trying to be super-precise and inventing a whole new alphabet soup of
> abbreviations which you *have* to memorize before you can understand
> anything (unfair example: MPLS).
> 2) adopting terms from a different domain and using them in an
> ever-so-slightly different sense so casual readers knowing the original
> domain are misled to no end (unfair example: SIP).
> 
> Applied to the question how to call the component statements of the FN:
> Example for error number one: FDER.
> Example for error number two: production.
> 
> Gruesse, Carsten
> 
> On Thu, 6 Mar 2003, Price, Richard wrote:
> 
> > In this case we may need to pick a more general term to avoid
> > confusion with 3095.  What we're looking for is a term to describe
> > a general "compression function", which converts uncompressed
> > data into compressed data (relative to a context).  It shouldn't
> > matter whether the function compresses a single field, a whole
> > protocol header, or even the entire packet.  Also, it shouldn't
> > matter whether the function outputs compressed bits that are
> > considered to lie in the "discriminator" or in the "compressed
> > body" part of the header.
> >
> > In particular, the term must be equally suitable for describing
> > all of the following:
> >
> > * LSB encoding
> > * Self-describing variable-length values
> > * List encoding
> > * EPIC-lite
> >
> > Any ideas for a good term to use?  Once we have one, I suspect
> > that the scope of the formal notation will be *much* easier to
> > define.
>

---

From: "Lars-Erik Jonsson (EAB)" <[email-masked]>
Date: Thu, 6 Mar 2003 16:37:03 +0100

At this point, I think it is important not to consider such "solution
details", but first figure out what we are really trying to achieve
here.

/L-E

---

From: "Price, Richard" <[email-masked]>
Date: Thu, 6 Mar 2003 17:33:20 -0000

Hi,

Based on our recent discussions, I think that I now understand the
difference between our views on how the notation should be used.

In my view, a ROHC-FN description is a complete specification of
"bits on the wire" (assuming of course that all of the basic encoding
methods have been defined).  In particular, if the compressed header
formats are generated by EPIC-lite then the ROHC-FN description
invokes EPIC-lite, and provides all of the input needed by EPIC-lite
to generate the bits on the wire (which happens to be the content
of the compressed headers, plus a set of probability values).

If the compressed header formats are created manually then the
ROHC-FN description captures the exact hand-crafted packet formats -
not just the content of the compressed headers, but the hand-crafted
"discriminator" bits as well.

> way of documenting the compressed header content.

The notation describes more than just the compressed header content -
it describes the exact packet formats (i.e. bits on the wire).  Even
if we design the packet formats by hand, they can still be described
formally using the notation.

> compressed header content, one will not get "bits on the wire".

As above, in my view the notation should describe the exact bits
on the wire (not just the compressed header content).

> packet formats?

The probability values aren't part of the notation itself - they're
inputs that are needed by the EPIC-lite encoding method.  This
might be clearer if we avoid using the rather confusing symbol "|"
to denote EPIC-lite, and instead write it out explicitly as follows:

tcp_source_port   ::=   epic_lite (static, irregular (16), 90%, 10%)

This means that the TCP Source Port is compressed using EPIC-lite,
which in turn offers us a choice of two encoding methods (static
or irregular) for compressing the field.  After picking one of these
two encoding methods, EPIC-lite outputs a suitable discriminator to
tell the decompressor which choice has been made.

The probability values are just parameters that are needed by EPIC-
lite in order to work out which bits on the wire to send.

> The notation above, i.e. with probabilities, seems to me to be a
> very generic approach that should be used in the ROHC FN.

The probabilities aren't part of the notation - they're just the
parameters which EPIC-lite needs in order to calculate the bits on
the wire.  If the notation is describing hand-crafted packet formats,
then the probabilities aren't included (because they're not needed
to describe the packet formats).

> Even if we did not have a notation then, of course we did have
> such probability expectations in the back of our heads when we
> wrote 3095. 

However, if we generate the packet formats by hand then the
probability values would not be captured in the ROHC-FN description
of the compressed packet formats.  The description would capture
our hand-crafted packet formats instead.

> independently defined by the profile specification.

In my view of how the formal notation works, minor adjustments
to the packet formats would be made within the ROHC-FN description
itself.  We would invoke EPIC-lite to generate the packet formats,
and then we would modify the output of EPIC-lite by applying one
or more additional encoding methods to tweak the "bits on the wire".

The big advantage of making the adjustments within ROHC-FN is that
the description of the compressed packet formats remain machine-
readable, and can still be compiled into executable code without
needing any hand-made adjustments.