Subject: RE: [rohc] Formal notation, combined thread

From: "Lars-Erik Jonsson (EAB)" <[email-masked]>
Date: Wed, 2 Apr 2003 23:54:59 +0200

Richard,

> > > RP: The notation language itself shouldn't make a distinction
> > > between EPIC-lite and any other encoding method.
> > 
> > As I have said above, I think it is important to make a clear
> > distinction between these, as they are so different. That is also
> > what we said last year, when we talked about field encoding vs.
> > compressed header encoding.
> 
> As above, I can't see any reason to think of the
> discriminator encodings as "special", or to treat them
> differently in some way.  The distinction between the
> various types of encoding method that we made last year
> was only intended to clarify how the notation handles all
> of the different compression techniques needed by ROHC
> profiles.  From a technical perspective the notation has
> never given special treatment to the discriminator
> encodings, and I think that it would be confusing and
> unnecessarily restrictive to do so.

We obviously disagree here. I still believe it is important to
make this distinction. All field encodings that can send 
compressed data in more than one way calls a discriminator
function, but any function could be used, i.e. the notation
for a profile can be written independent of the actual 
discriminator function that is later chosen. 

> > > RP: 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.
> > 
> > OK, but then we would not even need the notation as a tool, if
> > the actual formats (in written form) would just mean the same.
> 
> The notation provides a really useful benefit even when
> describing hand-crafted compressed headers, which is the
> extra implementation option of writing a "notation compiler"
> to automatically convert a notated description of the
> packet formats into running code.

First of all, I think it would be useful to have the notation to
describe what to put in hand made formats, i.e. as a tool in such
a process. Further, I think we would make a mistake if we tried to
make the notation capable of describing hand made formats, as that
would make the notation unnecessary complex, while the reason does
not really make sense in my mind. 

> > > RP: The big advantage of making the adjustments within ROHC-FN
> > > is that the description of the compressed packet formats remain
> > > machine-readable
> > 
> > We are defining standards, which should be human-readable. There 
> > are probably disagreements in this regard, but personally I think
> > human-readability is more important than machine-readability.
> 
> I agree that human-readability is at least as
> important as machine-readability.  However, in
> my opinion a notated set of packet formats is
> actually rather more human-readable than a set
> of packet formats drawn out pictorially.  

Well, protocol headers are usually drawn out pictorially, so that is
what protocol folks are more used to. 

> > 7. EPIC-Lite 
> >  
> > The EPIC and EPIC-Lite terms have been overloaded several times by
> > now, and they actually do not say much about what they really do.
> > If we want to use the "EPIC-Lite" method for "discriminator
> > encoding" and potentially define it in the general notation
> > document, we should come up with a name that tells us what it does. 
> > 
> > Any ideas?
> 
> We originally used the term "EPIC-lite" to mean
> the entire notation-based solution, including
> the notation itself and the complete library of
> encoding methods.  The algorithm for generating
> the discriminator bits is actually nothing more than
> ordinary Huffman encoding, so perhaps we could
> just call it that instead?

Ok, "Ordinary Huffman" (OH), and "Hierarchical Huffman" (HH) then?

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

---

From: "Price, Richard" <[email-masked]>
Date: Mon, 7 Apr 2003 14:51:52 +0100

> make this distinction.

I think that the distinction only makes sense for a very simple
header which is encoded in exactly two steps: first compress each
field using a choice of one or more field encodings, and then
compress the choices that were made by applying a discriminator
encoding.

In particular, the distinction only works when a single (unique)
discriminator encoding is used to encode all of the discriminator
flags for the header. There are a number of cases where this isn't
the best solution - three that spring to mind are "list", "nbo"
and "format".

The "list" encoding method works much like list encoding in 3095 -
namely that it allows the various list items to turn up in any
order, and thus needs some discriminator bits to send this order
information to the decompressor. In theory it would be possible
to generate these discriminator bits using EPIC-lite: in practice
we would get too many packet formats due to the sheer number of
possible list orderings. The alternative is just to allow list
encoding to create its own discriminator bits, separately from
the ones generated by EPIC-lite.

The "nbo" encoding method offers implementers a choice of whether
to reverse the IP-ID before compressing it. We could encode the
resulting choice using EPIC-lite, but this would be inefficient
because we would always be sending the choice in every compressed
packet. Much better to store an "NBO flag" entry in the context
and to use this when deciding how the IP-ID has been encoded.

The "format" encoding method is designed to create multiple sets
of compressed packet formats. For example, if we wanted to have
separate packet formats for UO-mode and for R-mode then we would
write the following:

example_packet_formats   ::=   format(uo_mode, r_mode)

We could encode the choice of packet formats using EPIC-lite, but
we'd lose efficiency because we'd end up sending the choice in
every compressed packet. The solution is to create a new context
entry to store the choice of packet formats instead.

> All field encodings that can send compressed data in more than
> one way calls a discriminator function, but any function could
> be used, i.e. the notation for a profile can be written independent
> of the actual discriminator function that is later chosen. 

I outlined three cases where the above assumption fails - i.e. you
get a field encoding that can send compressed data in more than
one way, but where the resulting choice needs to be encoded using
a discriminator function other than EPIC-lite.

Currently this poses no problem for the notation, because we invoke
EPIC-lite just like any other encoding method. Therefore we have
control over when to encode the discriminator flags using EPIC-lite,
and when a different encoding method would be more appropriate.

We'd run into difficulty if we had to use a single (unspecified)
discriminator function for every case where compressed data can be
sent in more than one way. We'd be forced to use a single method to
encode every discriminator, even for the special cases where a
different method is more memory efficient or gets a better
compression ratio.

> would make the notation unnecessary complex,

I disagree with the above - in general, there's no relation between
the expressive power of a language and its complexity.

The current notation is powerful enough to describe hand-crafted
packet formats, as we can compress the discriminator bits using any
encoding method we like. We can apply EPIC-lite to the whole header
or we can use separate discriminator encoding methods for each field
(or any combination of the two).

This approach also makes the notation rather more simple than the
case where the discriminator flags are treated separately. Currently,
discriminator flags are treated exactly like any other data that
needs to be sent to the decompressor. In particular, we don't need
to worry about having new data structures to hold the discriminator
flags - they can be stored in the same data structures that we use
for the "ordinary" header fields (namely the labels and the context).
Moreover we don't have any special syntax for handling the
discriminator flags - we can compress them by applying our choice
of encoding method (e.g. EPIC-lite) just like we would apply LSB
encoding to compress a particular field.

> while the reason does not really make sense in my mind. 

Having a formal description of the packet formats is a huge saving
in terms of implementation effort, because it eliminates all of the
confusion and misunderstandings that occur when trying to code a
complicated set of packet formats by hand.

> what protocol folks are more used to. 

Pictorial descriptions are generally restricted to simple protocol
headers. For more complex protocols it's usual to define the headers
via a formal notation, such as ABNF for SIP or ASN.1 for H.323.

> Ok, "Ordinary Huffman" (OH), and "Hierarchical Huffman" (HH) then?

Sounds ok to me!

Regards,

Richard

---

From: "Lars-Erik Jonsson (EAB)" <[email-masked]>
Date: Wed, 16 Apr 2003 10:52:45 +0200

> compress the choices that were made by applying a discriminator

I rather believe it is important to make even more distinctions,
as I agree with you that there are more "alternative" methods.

> the best solution - three that spring to mind are "list", "nbo"

Let's look at these three...
 
> the ones generated by EPIC-lite.

I agree with you, list encoding is rather special, it differs
significantly from normal field-based encoding, and should be
treated separately, but that has nothing to do with the usefulness
of clarifying the difference between field encoding methods and
discriminator encodings for the field methods.

> and to use this when deciding how the IP-ID has been encoded.

This is a tricky one, as it changes the packet format interpretation,
but if it is used, it is of course another special detail. Still,
it does not affect the concepts of field encoding vs. discriminator
encoding.

> of compressed packet formats. 

I really hope that when we define future profiles, we will be able
to agree to avoid changing packet format interpretation "on the
fly" within a profile, as it adds unnecessary profile complexity
and/or unreliability. But even if we define multiple sets, I can
not see why it should affect making a clear distinction between
field encoding and discriminator encoding.

> different method is more memory efficient or gets a better

I think you missed my point. The point was to have a notation where 
you would have an unspecified (generic) function, but that would not
out rule having other functions for some special cases, like context
based choices (that might be another general method). What I am
after is that where you could choose to use OH (Ordinary Huffman),
you could as well use HH (Hierarchical Huffman), or some other
discriminator function with the same purpose and input. It is just
about using a different algorithm, and the choice is in my mind a
rather subjective one, made when one define a profile. I do not
think a profile should use both OH, HH, and/or even more
discriminator functions, but instead I would like to see a generic
way of notating, and then the profile definition would state which
discriminator function to actually use for those places where this
¨generic method is called in the notation.

> encoding to compress a particular field.

Complexity is not just about implementation, but also about structured
concepts. Functionally, discriminators might just be created by using
"just another encoding method", but we should make the difference
clear conceptually, when we outline this new approach for describing
a header compression process.

Further, I strongly believe that there is a difference in how you
choose discriminator encoding, compared to how you pick field encoding
methods. The latter is (almost) purely based on field behavior, while
the former choice is not as obvious, it is a more subjective profile
designer choice.

> > Ok, "Ordinary Huffman" (OH), and "Hierarchical Huffman" (HH) then?

Fine, let's try to use those then.

/L-E

---

From: "Price, Richard" <[email-masked]>
Date: Thu, 24 Apr 2003 15:30:47 +0100

Hi,

Apologies for the late reply - the Easter holiday got in the way ;-)
I've added some further comments inline.

Now that a complete implementation of the current ROHC-FN draft is
available, would it be worth collecting together all of the unresolved
issues related to the notation? This thread is discussing the "scope
and purpose" of the notation, but there are also some more technical
issues that still need to be ironed out, such as whether to keep the
temporary variables, whether to allow unbounded lists and so on.

Regards,

Richard

> based choices (that might be another general method).

I think that having an unspecified "generic" encoding method that can
be defined later on is only possible if there are two or more methods
with the same purpose and inputs. I'm not currently aware of any
encoding methods that work like this.

> What I am after is that where you could choose to use OH (Ordinary
> Huffman), you could as well use HH (Hierarchical Huffman), or some
> other discriminator function with the same purpose and input.

The OH and HH algorithms have the same purpose, but their inputs are
actually somewhat different. Certain field encodings can be used in
conjunction with HH that can't be used with OH - an example is the
so-called Least Significant Part (LSP) encoding that was considered
briefly for use in 3095. Conversely, some encoding methods can be
used in conjunction with OH that can't be used with HH - for example
the "uncompressible" encoding method as defined in the notation draft.

> It is just about using a different algorithm, and the choice is in
> my mind a rather subjective one, made when one define a profile.

True. However, once this decision is made, a different set of field
encodings will be available to the profile designer depending on
whether OH or HH is used.

> I do not think a profile should use both OH, HH, and/or even more
> generic method is called in the notation.

The only way to do this would be to restrict the set of field
encodings to ones that can work in conjunction with both OH and HH.
At present it's entirely up to the profile designer whether to do
this or not. For example, if we want to create two profiles for
TCP/IP - one using OH and one using HH - then we have two choices:
either create two profiles that use the same (restricted) set of
field encodings, or use the optimal set of field encodings for each
case (even though some field encodings only work for OH and others
only work for HH).

I think that both approaches have their merits - the first is
simpler, whilst the second will get a better compression ratio due
to having a wider range of field encodings available for each of
the profiles. What I'd like to avoid is forcing profile designers
to use only the generic approach, because we'll typically know the
discriminator encoding that the profile will use and can therefore
take advantage of this knowledge when selecting the field encodings.

> a header compression process.

From a conceptual point of view, I'm not at all clear on the difference
between a discriminator encoding and, say, a field encoding.

The way I visualise encoding methods is just as "subroutines" that can
be called in the ROHC-FN language. Each subroutine is designed to
compress some or all of the bits in the header, and, naturally, the
more complex subroutines are defined in terms of simpler ones. Thus, a
typical set of packet formats is created using layers of progressively
more complex encoding methods, e.g:

Whole header:             Ordinary Huffman
                                / \
Part of header:                /  List
                              /    /\
Individual fields:       IP-ID  NBO  Irregular
                          / \
Partial fields:     Offset   LSB

In this layered approach it's difficult to find a single property
that defines whether an encoding is a field encoding, a discriminator
encoding or something else entirely. It's not the case that only the
discriminator encodings offer implementation-specific choices, because
a number of field encodings offer them as well (e.g. NBO). Similarly,
it's not the case that discriminator encodings need to be applied to
the whole header, because the discriminator encodings such as list
are applied to part of the header only. Unless of course we make list
encoding into a special case (which would be peculiar, because it
generates discriminator bits no differently from, say, OH or HH).

Any other suggestions for what is actually meant when we talk about
"discriminator encodings"?

> the former choice is not as obvious, it is a more subjective profile

I don't believe that this is the case. For example, in the proposed
TCP packet formats we're already making a subjective choice to simplify
the field encodings, by using LSB encoding instead of the more powerful
but more complicated LSP encoding. Similarly, our choice of which
version of list encoding to use, whether to allow NBO encoding and so
on are all subjective decisions that must be made independently of the
decision on whether to use OH, HH etc.