Subject: Re: [rohc] proposals for generic notation of compressed header

From: "West, Mark (ITN)" <[email-masked]>
Date: Sat, 04 May 2002 22:04:26 +0100

Hi Qian, Hongbin,

Sorry it's taken so long to get around to replying.  Anyway, at the risk
of excessive indentation, some more inline responses...

Cheers,

Mark.

 >>>
 >>I don't think that it's *quite* that simple!  The notation is
 >>capturing two things: the structure of the header and how to encode
 >>it.  So, there has to be some way of identifying the IP reserved flags
 >>and the TCP reserved flags as well.
 >>
 >>The important point about removing the stack manipulation encodings is
 >>that they impose a particular solution (and one that's quite messy to
 >>use!)
 >>
 >
 > Yeah, agree. We really need a way to present the structure of the header
 > and identify the fields in the uncompressed header before go detail
 > about how to encode it.
 > The formal definition of header in our previous letter may be a good
 > candidate to present the structure of the header.
 > tcp-header := source-port
 >               destination-port
 >               ......
 > source-port      := bits(16)
 > destination-port   := bits(16)
 > ......
 >
 > Note that we may need to add some other notation to present the '|' and
 > '*'. We are now working on this.
 >

Ok.  I see that you've now written another e-mail on this subject, so I
won't go into any real detail here.  Other than to point out that the
key question that this raises is whether the structural and encoding
information should be separate or combined.  I don't have the answer --
I am concerned that we try to avoid excessive redundancy.

 >
 >>>        2. Refine the notation about FORMAT.
 >>>
 >>>[removed to save space]
 >>>
 >
 > Yeah, that is the point. The state machine takes the responsibility that
 > decides which FORMAT should be used. When it decides that the format set
 > should be changed to another one, it just transits back to IR state and
 > initiate a procedure to make sure the decompressor uses the same format
 > set either.
 >

I think that we are probably in agreement on this point...

 >
 >
 >>>    Secondly, we would like to propose some new notations for the
 >>>generic notation of header compression.
 >>>
 >>>
 >>Now it gets interesting ;-)
 >>
 >>
 >>>[removed to save space]
 >>>
 >>
 >>My immediate reaction to this is that it is more of an encoding rule
 >>issue than a notation rule issue.  (Although I'm prepared to be
 >>persuaded otherwise!)  Whatever, it's an interesting thought,
 >>so let's follow it...
 >>
 >
 > Yeah, although we are addressing the compressed header format issue, how
 > to encode headers really affects the notation. That is why we want to
 > introduce a more general structure for compressed headers.
 > EPIC-LITE uses only a single Huffman code to indicate the encoding
 > format set. However, if a type of record occurs multi-times, the profile
 > has to list the probability of each occurrence of the type of record.

Under some cases I think that it may actually be desirable to be able to
associate probabilities with occurences of records.  In fact, for SCTP
one can imagine (ideally) thinking about capturing dependencies between
items in a list.

 > The result is that the profile will be very large and the Huffman code

The size of the profile will be proportional to the number of entries.
It is clear that the more general solution is better for the extreme cases.
Have we found any/many compelling extreme cases yet?

 > table is very large also. For 'out-of-order-sequence', order information
 > also needs encoding. However, if we introduce the proposed hierarchy
 > compressed header format, the 'repeat-sequence' and
 > 'out-of-order-sequence' can be treated in object-oriented way. That
 > means records of 'repeat-sequence' and 'out-of-order-sequence' could use
 > sub-indicator flags to determine their own encoding methods instead of
 > using the top-level Huffman code. This new method will handle 'sparse'
 > records very efficiently.
 >
 >>>
 >>
 >>I'm not sure what you mean by 'complexity' in this context?  In sheer
 >>
 >
 > Here, the complexity refers to the size of the Huffman code table, or
 > format sets.
 >

Ok.  I guess the question is more one of how sensitive we should be to
the size of this table.

 >
 >
 >>processing terms, it is clear that this approach is less
 >>efficient since
 >>you have to perform far more Huffman encoding/decoding operations.
 >>(Method selection is still linear w.r.t. number of fields and
 >>mapping to a Huffman code is near enough constant time regardless of
 >> the number of fields involved)
 >>
 > Sub-indicator flags will be used mostly for 'out-of-order-sequence' and
 > 'repeat-sequence', it will reduce the Huffman code table significantly.
 >
 >>It is also clear that splitting the encoding up into multiple Huffman
 >>codes is less efficient than treating everything as a single
 >>Huffman code.
 >
 > Yeah, that is also a tradeoff between compression ratio and complexity.

I would say more of a trade-off between compression and flexibility.

 > Moreover, we want to point out that the statement given in the above may
 > not always hold. Suppose there are some cases that the out-of-order case
 > will be occurred frequently and there are a lot of possible entries with
 > few of them will ever actually appear. Using single Huffman code, the
 > order information still needs to be encoded for each field, thus it may
 > not efficient than just encode with sub-tree.
 >

The order information does not (directly) appear in the Huffman code.
Only the selection of the encoding for the order data goes into the
indicator.  The order information can be separately encoded in an
arbitrarily efficient manner.

[snip]

 >>
 >>
 >>When you say 'how often the method will be used', are you
 >>referring to
 >>the SUB-TREE-0 method itself?  And, if so, what other method could be
 >>given as an alternative?
 >>
 > Yeah, the probability is used only for SUB-TREE-0 only. Would you please
 > explain more detail about the second question?
 >

Can I have:
	X = SUB-TREE-0(80%, ...) | SOME-OTHER-METHOD(20%, ...)
and how is this interpreted?

[snip]

 >
 > Great! We will add a notation SUB-TREE-LEN for this case.
 >
 > SUB-TREE-LEN
 >
 > ABNF notation: "SUB-TREE-LEN(" <probability> ","
 > <uncompressed-records-length> "," <encoding_name>
 >         *("," <encoding_name>) ")"
 >
 > The 2nd parameter specifies the length of the sequence of uncompressed
 > records. In summary, the main difference among SUB-TREE-0, SUB-TREE-LEN,
 > and SUB-TREE-N is how to determine the end of the uncompressed records.
 > The difference is listed as follows.
 >
 > SUB-TREE-0		a zero-like type of record is used to indicate
 > the end of the sequence of uncompressed records;
 > SUB-TREE-LEN	the end of the sequence of uncompressed records is
 > specified by the length of the uncompressed sequence;
 > SUB-TREE-N   	the number of the records is given somewhere;
 >

With regard to SUB-TREE-N/SUB-TREE-LEN are there any obvious examples
where the length (for SUB-TREE-LEN) cannot be derived from 'N' by a
fixed translation?  (Which is not to say that it might be prudent to
keep both...)

This discussion raises, I think, another more general question: How
'rich' a set of encodings do we want?  (At least as far as a base
notation goes).  Again, I don't know the answer, but I can see the
question looming!

[snip]

 >>>
 >>
 >>So, are you saying that each <encoding-name> given as a
 >>parameter to the
 >>SUB-TREE-0 method is treated as a 'sub compressed-header'?
 >>
 >>Assuming that this is the case (apologies if I've
 >>mis-understood), a few questions...
 >>
 >>- how are the sub-header indicators generated?
 >>   (if based on Huffman codes, where do the probabilities come from?)
 >>
 >>
 >
 > It can be defined as Huffman codes or not. For simple case, the
 > indicator flags can be index, like 0, 1, 2... If Huffman code is needed,
 > we can add probability for each <encoding_name> in the SuB-TREE-0 and
 > SUB-TREE-LEN notations.
 >

Fair enough (at the cost of some additional complexity).

 >
 >>- following on, what probability would you specify for (e.g.) the
 >>'timestamp' option which, essentially, is either always
 >>present or never present
 >>

I'm still curious about the answer to this one ;-)

 >>- surely this is going to incur a minimum 1-bit overhead per entry in
 >>the list, per packet?
 >>
 > That is tradeoff between robustness and compression efficiency. That is,
 > 1-bit more in each packet and good robustness (no context updating
 > needed) vs. occasional IR packet and not so good robustness (risk that
 > IR packet may be lost in the wireless link)
 >

This is categorically not about robustness!  It is about flexibility.
By including these flags in the header you can have arbitrarily long
chains of list entries.  It is not practical to use the current LIST
approach to do this, because of the way that the encodings are managed.
However, the robustness issues for both approaches are the same.

 >
 >>>SUB-TREE-N
 >>>
 >>>ABNF notation: "SUB-TREE-N(" <probability> "," <value> ","
 >>><encoding_name> ")"
 >>>

[snip]

 >>>
 >>I feel obliged to point out that it is a trivial notational tweak to
 >>introduce an encoding based on the current LIST encoding that
 >>specifies a repeat of up to 'N' items...
 >
 > Maybe we had not explained clearly enough about SUB-TREE-N notation in
 > the previous email.
 > SUB-TREE-N is different for the LIST with 'N' items. SUB-TREE-N uses a
 > length flag to indicate how many records there are and each
 > sub-indicator-flag for each occurrence of the type of record to specify
 > the encoding method for that occurrence of the type of record. However,
 > LIST will generate a single Huffman-code to indicate how many records
 > there are and encoding methods for each occurrence of the type of
 > record.

LIST generates the encodings for each entry in the list (whether present
or not!).  However, neither the length of the list (nor the order of the
list) directly contribute to the Huffman code.  They do so indirectly
since the encodings for the 'presence' and 'order' information have to
be selected.

 >
 >
 >
 >>>Using SUB-TREE-N, the multi-occurrences don't need notating in the
 >>>profile. SUB-TREE-N will produce several (sub) compressed
 >>>
 >>header, one of
 >>
 >>>them is the number of the occurrences of the type of
 >>>
 >>records, others are
 >>
 >>>the compressed header for each occurrence of the type of records.
 >>>
 >>>
 >>
 >>To pick a simple example, the CSRC list for RTP, how does this handle
 >>insertion or deletion?  Imagine I have a list of 6 CSRC entries.  Now
 >>imagine that an entry is inserted or deleted at index 1.  With this
 >>approach, do all entries after the point of change need to be
 >>re-encoded?
 >>
 >>And, again, if a Huffman token is used for each entry, doesn't this
 >>introduce a fixed minimum 1-bit overhead per entry per packet?
 >>
 >>To re-iterate this efficiency point, one of the issues with using
 >>Huffman codes is that they are maximally efficient when everything is
 >>folded into the one token.  I accept that splitting the information
 >>across multiple codes adds some flexibility, but it also sacrifices
 >>efficiency.
 >>
 >>
 >
 > Yeah, however, one token of Huffman code cannot efficiently handle the
 > cases of 'out-of-order-sequence' and 'repeat-sequence', especially, when
 > they are sparse.
 >

This would be true.  However, this is not the case taken by the current 
list encoding.

 > IMHO, as a general notation of compressed header formats, flexibility
 > should be one of main factors.
 > Please note that SUB-TREE-* is not proposed for replacing LIST of
 > EPIC-LITE. Instead, it should only be used to efficiently handle sparse
 > 'out-of-order-sequence' and 'repeat-sequence' cases.
 >

The key issue (regarding compression of lists) is whether we wish to be
able to support arbitrarily long lists of items.  If this is the case,
then additions like those proposed are essential.  There may also be
other cases where they are of benefit.

These are good questions to pose about the notation..!

 > Cheers, comments are welcome.
 >
 >
 >

-- 
Mark A. West, Consultant Engineer
Roke Manor Research Ltd., Romsey, Hants.  SO51 0ZN
Phone +44 (0)1794 833311   Fax  +44 (0)1794 833433

(Yes, I do know that my disclaimer is in an attachment.  And, no, I
didn't ask for it to be that way)

---

From: "West, Mark (ITN)" <[email-masked]>
Date: Sun, 05 May 2002 12:14:23 +0100

Hi Qian, Hongbin,

I think that there is one critical issue raised by this proposal:

Should the structure and encoding of the header be described in a single
or separate notation(s)?

Clearly what you are proposing implies separate description of the
structure and the encodings.  However, the notation that we have
proposed uses a single description.

My main concern about separating the notation is the redundancy that
this may imply (and, perhaps, the efficiency -- is there any need to be 
able to deconstruct the packet header other than to compress/encode it?) 
  On that basis, can you explain in more detail why you are proposing 
this approach?  (I'd hesitate to say at this stage which is the 
right/better answer, but I'd like to understand the landscape a little 
better...)

Cheers,

Mark.

Qian Zhang wrote:

  > Hi Mark,
  >
  > As we promised in the last email, we now give the generic notation for
  > the structure of header and identify the fields in the uncompressed
  > header.
  >
  > Regards,
  >
  > Qian & Hongbin
  >
  >
  >>Yeah, agree. We really need a way to present the structure of the
  >>
  > header
  >
  >>Note that we may need to add some other notation to present the '|'
  >>
  > and
  >
  > We introduce the following notations to express the uncompressed header.
  >
  > a. BITS
  > ABNF notation: "BITS(" <length> ")"
  > The length in bits of the record is <length>.
  >
  > b. VALUE
  > ABNF notation: "VALUE(" <value> "," <length> ")"
  > The value of record is <value> and the length in bits of the record is
  > <length>.
  >
  > c. PADDING-F
  > ABNF notation: "F-PADDING(" <record-name> "," <alignment> ","
  > <pad-value> "," <pad-value-length> ")"
  > The record specified by <record-name> is aligned on <alignment> bits,
  > the padded value is <pad-value> which length in bits is
  > <pad-value-length>. The padded value is added at the front of the
  > record's value.
  >
  > d. PADDING-T
  > ABNF notation: "T-PADDING(" <record-name> "," <alignment> ","
  > <pad-value> "," <pad-value-length> ")"
  >
  > The record specified by <record-name> is aligned on <alignment> bits,
  > the padded value is <pad-value> which length in bits is
  > <pad-value-length>. The padded value is added at the tail of the
  > record's value.
  >
  > e. LIST-N
  > ABNF notation: "LIST-N(" <expression> "," <record-name> "," *(","
  > <record-name>) ")"
  > The record is composed of a list of records (we will refer them as
  > sub-record) in any order, and each sub-record of them may occurs 0 or
  > more times. The <expression> specifies the number of sub-records in the
  > list. The rest <record-name>s are the possible sub-records of the list.
  > Furthermore, the second <record-name> specify a default record-name if a
  > sub-record cannot match other <record-name>s.
  >
  > f. LIST-0
  > ABNF notation: "LIST-0(" <record-name> "," <record-name> "," *(","
  > <record-name>) ")"
  > The record is composed of a list of records (we will refer them as
  > sub-record) in any order, and each sub-record of them may occurs 0 or
  > more times. The first <record-name> specifies the sub-record which is
  > used as the indicator of the ending of list. The rest <record-name>s are
  > the possible sub-records of the list. Furthermore, the second
  > record-name specify a default <record-name> if a sub-record cannot match
  > other <record-name>s (including the first <record-name>.)
  >
  > g. LIST-L
  > ABNF notation: "LIST-L(" <expression> "," <record-name> "," *(","
  > <record-name>) ")"
  > The record is composed of a list of records (we will refer them as
  > sub-record) in any order, and each sub-record of them may occurs 0 or
  > more times. The <value> specifies the maximum length in octets of the
  > record. The following <record-name>s are the possible sub-records of the
  > list. Furthermore, the first <record-name> specify a default record-name
  > if a record cannot match other <record-name>s.
  >
  > The following is the notation of uncompressed TCP header:
  >
  > uncompressed-tcp-header := tcp-source-port
  > 		
	tcp-destination-port
	tcp-sequence-number
	tcp-acknowledgment-number
	tcp-data-offset
	tcp-reversed
	tcp-ecn
	tcp-control-bits
	tcp-window
	tcp-checksum
	tcp-urgent-pointer
	PADDING-T(tcp-options, 32, 0, 8)
  >
  > tcp-source-port       := BITS(16)
  > tcp-destination-port  := BITS(16)
  >
  > tcp-sequence-number	   := BITS(32)
  > tcp-acknowledgment-number  := BITS(32)
  >
  > tcp-data-offset	:= BITS(4)
  >
  > tcp-reversed := BITS(4)
  >
  > tcp-ecn :=	tcp-cwr
  > 		tcp-ece
  > tcp-cwr := BITS(1)
  > tcp-ece := BITS(1)
  >
  > tcp-control-bits := tcp-urg
  > 			  tcp-ack
  > 			  tcp-psh
  > 			  tcp-rst
  > 			  tcp-syn
  > 			  tcp-fin
  > tcp-urg	:= BITS(1)
  > tcp-ack	:= BITS(1)
  > tcp-psh	:= BITS(1)
  > tcp-rst	:= BITS(1)
  > tcp-syn	:= BITS(1)
  > tcp-fin	:= BITS(1)
  >
  > tcp-window	:= BITS(16)
  > tcp-checksum := BITS(16)
  > tcp-urgent-pointer	:= BITS(16)
  >
  > tcp-options	:= LIST-0(tcp-opt-end, tcp-opt-generic, tcp-opt-nop,
  > tcp-opt-mss, tcp-opt-wscale, tcp-opt-sack-permitted, tcp-opt-sack,
  > tcp-opt-timestamp)
  >
  > tcp-opt-generic := tcp-opt-type
  > 			 tcp-opt-len
  > 			 LIST-N(tcp-opt-len - 2, tcp-opt-octet)
  > tcp-opt-len	:=	BITS(8)
  > tcp-opt-octet :=	BITS(8)
  >
  > tcp-opt-end	:=	VALUE(0, 8)
  > tcp-opt-nop	:=	VALUE(1, 8)
  >
  > tcp-opt-mss	:=	VALUE(2, 8)
  > 			VALUE(4, 8)
  > 			BITS(16)
  > tcp-opt-wscale :=	VALUE(3, 8)
  > 			VALUE(3, 8)
  > 			BITS(8)
  >
  > tcp-opt-sack-permitted := VALUE(4, 8)
  > 		
	  VALUE(2)
  > tcp-opt-sack :=	VALUE(5, 8)
  > 			tcp-opt-sack-len-of-blocks
  > 			tcp-opt-sack-blocks
  > tcp-opt-sack-len-of-blocks := BITS(8)
  > tcp-opt-sack-blocks := LIST-N((tcp-opt-sack-len-of-blocks-2)/8,
  > tcp-opt-sack-block)
  > tcp-opt-sack-block :=	tcp-opt-sack-block-left
  > 		
	tcp-opt-sack-block-right
  > tcp-opt-sack-block-left  :=	BITS(32)
  > tcp-opt-sack-block-right :=	BITS(32)
  >
  > tcp-opt-timestamp := VALUE(8, 8)
  >                      VALUE(10, 8)
  >                      tcp-opt-timestamp-tsval
  >                      tcp-opt-timestamp-tsecho
  > tcp-opt-timestamp-tsval  :=	BITS(32)
  > tcp-opt-timestamp-tsecho :=	BITS(32)
  >

---

From: "Lars-Erik Jonsson (EPL)" <[email-masked]>
Date: Fri, 17 May 2002 15:07:34 +0200

Qian, Mark & Hongbin,

> > > QZ:
> > >    +----------------------
> > >    | compressed header   ...
> > >    +----------------------
> > >          /       \
> > >         /         \
> > > +-------+---------------------------+---------------------------+--
> > > | flags | (sub) compressed header 1 | (sub) compressed header 2 | .
> > > +-------+---------------------------+---------------------------+--
> > >               /       \
> > >              /         \
> > >        +-------------+-------------------------------+---
> > >        | (sub) flags | (sub-sub) compressed header 1 | ...
> > >        +-------------+-------------------------------+---
> > >                        /       \
> > >                       /         \
> > >                             .....
> > > QZ: Note that, the compressed header format in EPIC-LITE can be
> > > viewed as the above header format with just one level, which is
> > > a special case of our proposed general compressed header format.
> >  
> > MW: My immediate reaction to this is that it is more of an encoding
> > rule issue than a notation rule issue.  (Although I'm prepared to be 
> QZ: Yeah, although we are addressing the compressed header format 
> issue, how to encode headers really affects the notation. That is
> why we want to introduce a more general structure for compressed headers.

Maybe "generic compressed header notation" might be a slightly misleading
name. In my mind, the notation will be a general format for describing how
how various fields are compressed, including the encoding methods used
for each field, thus the information to transmit in compressed headers.
However, this does not cover how to encode the information into compressed
headers, that might be done in different ways, like for example EPIC and 
EPIC-Lite use different format encodings. Maybe "generic header compression
notation" is a better name. It does not really matter as long as we agree
on what it means.

Cheers,
/L-E

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