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

From: "Qian Zhang" <[email-masked]>
Date: Tue, 9 Apr 2002 14:04:53 +0800

Mark,

    As I promised in the MSP meeting, we would like to contribute on the
generic compressed header notation part.

   First, I would like to clarify some of our discussion about the
notation part in MSP meeting.

        1. Current stack encoding methods defined in EPIC-LITE should be
removed from the generic notation. 

         As we all agreed that in the general notation part, in stead of
describing how to group the related fields together, people only need to
describe which fields can be grouped together for efficiently encoding.

         We can just explicitly describe it in the notation part.  For
example, in TCP/IP profile, the IP's reserved flag and TCP's reserved
flag are encoded together, the notation can be written as follows:

     tcpip-reserved-flags = ip-reserved-flags

                   tcp-reserved-flags

        2. Refine the notation about FORMAT. 

         The FORMAT encoding method is used to create more than one set
of compressed header formats.   Notice that the first set of format is
used as the default compressed format before the compressor chooses to
change the format.  In EPIC-LITE, an index flag is appended to the
uncompressed header to indicate which set of formats is currently in
use.  Thus, all encoding methods are present in the IR(-DYN) packets, so
an IR(-DYN) packet may be sent to change to a new set of compressed
header formats.   

         For a generic notation, we propose to separate the
functionalities between notation and the state machine for different
header compression profile.  In this way, the FORMAT change decision
should be made by the state machine and only happens when the state
machine jumps back to the IR state.

    Secondly, we would like to propose some new notations for the
generic notation of header compression.

Before we go deep into the notation for compressed header, we want to
first give a more formal definition of the uncompressed packet header.
A header is the control information of a message or packet of data.
Suppose a record is a sequence of bits, each record has a corresponding
type (or name).  Moreover, a header can be formally defined as a
sequence of records. 

For example, TCP header can be defined as follows:

tcp-header := source-port
              destination-port
              sequence-number
              acknowledgment-number
              data-offset
              reversed
              ecn
              control-bits
              window
              tcp-checksum
              urgent-pointer
              tcp-options
source-port      := bits(16)
destination-port   := bits(16)
sequence-number    := bits(32)
acknowledgment-number := bits(32)
data-offset      := bits(4)
reversed       := bits(4)
ecn       := CWR
             ECE
control-bits := URG
                ACK
                PSH
                RST
                SYN
                FIN
CWR          := bits(1)
ECE          := bits(1)
URG          := bits(1)
PSH          := bits(1)
RST          := bits(1)
SYN          := bits(1)
FIN          := bits(1)
window        := bits(16)
tcp-checksum     := bits(16)
urgent-pointer    := bits(16)
tcp-options := *(tcp-opt-end | tcp-opt-nop | tcp-opt-mss
                | tcp-opt-wscale | tcp-opt-sack-permitted
                | tcp-opt-sack | tcp-opt-timestamp
                | tcp-opt-generic)
tcp-opt-end      := bits(8)
tcp-opt-nop      := bits(8)
tcp-opt-mss      := bits(32)
tcp-opt-wscale      := bits(24)
tcp-opt-sack-permitted := bits(16)
tcp-opt-sack      := bits(16)
                    (tcp-opt-sack-block)+
tcp-opt-sack-block  := bits(64)

In most cases, the header consists of a sequence of records in which
each one has a different type (or name) and appears in the header in the
specified order , e.g.  source-port, destination-port, etc.  However,
there exist records which may appear in any order, e.g., options in the
tcp-options. Moreover, there may exist some records with the same type
(or name) which occurs multi-times, e.g., NOP, SACK-BLOCK.  We will
refer to the later two cases as 'out-of-order-sequence' and
'repeat-sequence' respectively and the former one as
'in-order-sequence'.

EPIC-LITE uses Huffman compression to generate the indicator flags for
each compressed header format.  Each format is treated as one character
in the Huffman character set.  To determine the entire format set (the
character set in Huffman compression), people must determine how many
records (or fields) a header has and how many possible encoding methods
there are for each records.  For 'in-order-sequence', the format set can
be calculated easily. However, for 'out-of-order-sequence' and
'repeat-sequence' cases, the calculation CANNOT be done easily and
efficiently since there are types of records which can appear in any
order or have more than one occurrence.   The LIST encoding method in
EPIC-LITE is introduced to handle these cases. For types of records
which may appear multi-times, the LIST encoding method treat each
occurrence of the same type of record as a new type of record and list
the maximum occurrences in the set of encoding methods of LIST.  For
example, in RTP profile, the CSRC list field lists all possible 16 CSRC
entries, in TCP profile, the SACK option lists all possible 4 SACK
blocks.  For types of records which may appear in any order, the LIST
encoding method encodes the 'order' information and delivery it to the
decompressor to make sure the compressed header can be decompressed
correctly.  However, as the number of types of records in the
'out-of-order-sequence' increases, LIST needs more bits to encode the
'order'. (roughly, if there are N types of records, N*log2(N) bits are
needed.)  If some types of records may appear more than one times, more
bits are needed to represent the order in the LIST method.

From the above analysis, LIST encoding method is not an efficient
encoding method for 'out-of-order-sequence' and 'repeat-sequence'.
(Actually the agreement for this statement had been achieved in the
discussion on the MSP meeting.)  For example, in SCTP, the Selective
Acknowledgment (SACK) chunk may contains thousands of Gap Ack Blocks and
Duplicate TSNs.  It's impossible to list thousands of them in the
profile of SCTP.  

To propose more efficient encoding methods for 'out-of-order-sequence'
and 'repeat-sequence', we first propose an improvement on the compressed
header format.

The compressed header format in EPIC-LITE divides each compressed header
into two parts: the indicator flags and the compressed fields as
illustrated below:

      +---+---+---+---+--------------------+--------------------+---
      | 0 | 1 | 1 | 0 | Compressed Field 1 | Compressed Field 2 |...
      +---+---+---+---+--------------------+--------------------+---
       \   \     /   /                  \     /
        \   \   /   /                    \   /
       Indicator Flags             Compressed Fields

Our proposed compressed header format extends it to a more general
format by introducing the concept of hierarchy. At the top level, each
compressed header can be divided into also two parts: the indicator
flags and the (sub) compressed headers. The indicator flags contain 0 or
more bits and specify how to decompress those (sub) compressed header.
The (sub) compressed header may be another level of compressed header or
just the compressed value of the record. The structure of the proposed
compressed header format can be
illustrated as follows:

   +----------------------
   | compressed header   ...
   +----------------------
         /       \
        /         \
 
+-------+---------------------------+---------------------------+---
      | flags | (sub) compressed header 1 | (sub) compressed header 2 |
...
 
+-------+---------------------------+---------------------------+---
              /       \
             /         \
       +-------------+-------------------------------+---
       | (sub) flags | (sub-sub) compressed header 1 | ...
       +-------------+-------------------------------+---
                       /       \
                      /         \
                            .....

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.

With the proposed compressed header format, the global format set of
Huffman compressed, which contains all possible combinations of
compressed methods of every field,  is split into several format sets
which is associated with each (sub) compressed header, and each format
set can be tweaked into a manageable size. The complexity of finding
indicator flags from compressing method of each field and vice versa can
be alleviated in a divide-and-conquer way.

For 'out-of-order-sequence' and 'repeat-sequence', we propose two new
encoding methods, SUB-TREE-0 and SUB-TREE-N, to handle them
respectively.

SUB-TREE-0

ABNF notation: "SUB-TREE-0(" <probability> "," <encoding_name>
        *("," <encoding_name>) ")"

SUB-TREE-0 encoding method tries to compress a sequence of records with
one ending flag. For example, tcp-options is a sequence of tcp options
with END as the ending flag.

The first parameter probability indicates how often the method will be
used. Note that, this probability only affects the format set of the
same level the SUB-TREE-0 is used, it cannot affect the format set of
the other levels.

The probability is followed by a set of encoding methods that can be
used to compress individual records in the 'out-of-order-sequence'. The
first <encoding_name> also specify the ending flag of that sequence.

Using SUB-TREE-0, the order of different types of records is unnecessary
to encode since the compressed headers also appear in the same order as
the original records.  SUB-TREE-0 encoding method will produce several
(sub) compressed headers and generate a unique and compact indicator
flag for each type of record listed in the <encoding_name> sequence.

SUB-TREE-N

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

SUB-TREE-N encoding method try to compress a sequence of the same type
of records with a length field which is defined somewhere. For example,
CSRC list entries and SACK blocks can be used with this method.
SUB-TREE-N encoding method will produce several (sub) compressed
headers.

The first parameter probability indicates how often the method will be
used. Note that, this probability only affects the format set of the
same level the SUB-TREE-N is used, it cannot affect the format set of
the other levels.

The second parameter specifies the maximum occurrences of the type of
record.

The third parameter is the encoding method used to compress the each
record in the 'repeat-sequence'.

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.

-----

Note that we can combine those two encoding methods into one method with
an additional parameter to indicate the type of records ending approach.

-----

TCP options field can be notated with these two new encoding methods as
follows:

tcp-options-co = SUB-TREE-0(40%,
               tcp-opt-end,
               tcp-opt-nop,
               tcp-opt-timestamp,
               tcp-opt-sack,
               tcp-opt-generic)

tcp-options-dyn = SUB-TREE-0(100%,
               tcp-opt-end,
               tcp-opt-nop,
               tcp-opt-timestamp,
               tcp-opt-sack-permitted,
               tcp-opt-mss,
               tcp-opt-wscale,
               tcp-opt-generic)

tcp-opt-sack  = SUB-TREE-N(100%,
               4,
               tcp-opt-sack-block)

 Comments are welcome,

Best Regards

Qian and Hongbin

---

From: "West, Mark (ITN)" <[email-masked]>
Date: Wed, 10 Apr 2002 21:53:06 +0100

Hi Qian, Hongbin,

Comments, as ever, inline...

Cheers,

Mark.

> generic compressed header notation part.

Good! Thanks...

> removed from the generic notation.

Yes.

>      tcpip-reserved-flags = ip-reserved-flags

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!)

> machine jumps back to the IR state.

Again, to summarise, we agreed that it was sensible to identify a 
default format set to use (in the absence of any other information).

Although the index flag is in the current EPIC-lite draft it is not (I 
believe) actually necessary.  So we may be able to get rid of this. 
However, you are right that the IR(-DYN) packets can be used to select 
the format.

I don't think that you can necessarily insist that the format only 
changes when the state machine wants to change to IR state anyway. 
Consider a FORMAT encoding to handle the UDP checksum.  This will have 2 
choices 'with-checksum' and 'without-checksum'.  Now, imagine a UDP flow 
changing its checksum behaviour.  (Yes, it would be weird, but...)
It is clear that the 'with-checksum' encoding will also be able to 
handle the 'without-checksum' case, and so the format change could be 
deferred.  However, if the checksum starts being used on a flow that is 
using the 'without-checksum' encoding, the format transition is forced 
by the fact that it is the only way to encode the packet.

However, for the more speculative 'this format might be more efficient 
than the current one' transitions, you may well be better off waiting 
for a natural transition to IR state...

So, I think I *almost* agree (but with reservations)!

> generic notation of header compression.

Now it gets interesting ;-)

> For example, TCP header can be defined as follows:

[BNF-type definition snipped out to save space -- I agree with what's in 
it...]

> 'repeat-sequence' respectively and the former one as 'in-order-sequence'.
> 

This analysis is quite thorough and correct, as far as it goes. 
However, it is clearly incorrect to say that LIST requires N*log2(N) 
bits to encode the order data for an N-ary LIST.
It is true that the LIST encoding will generate this many bits for the 
'order' meta-field.  It is also true that the current set of encodings 
do not provide any obvious way of efficiently encoding the LIST order. 
Some thought leads us to recognise that the biggest problem is when the 
list is 'sparse'.  That is, there are a lot of possible entries, but few 
of them will ever actually appear in the LIST.  Sending a complete order 
for the entire list is clearly very wasteful.
The simplest fix for this is to introduce an encoding (or set of 
encodings?) that are capable of more efficiently representing the order 
meta-field.  For example, an encoding that sends order information only 
for those elements present in the list will be far more efficient.

Anyway, apologies for this (not so) brief digression on list order 
encoding, and back to the discussion in hand...

> Duplicate TSNs.  It's impossible to list thousands of them in the 

Ok - see above for a partial rebuttal.  I sort of hope that an SCTP 
packet typically won't contain 'thousands of Gap Ack Blocks', but I take 
the point...

>       | flags | (sub) compressed header 1 | (sub) compressed header 2 | ...

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...

> be alleviated in a divide-and-conquer way.

I'm not sure what you mean by 'complexity' in this context?  In sheer 
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)

It is also clear that splitting the encoding up into multiple Huffman 
codes is less efficient than treating everything as a single Huffman code.

> encoding methods, SUB-TREE-0 and SUB-TREE-N, to handle them respectively.
>  
> SUB-TREE-0
> 

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?

> first <encoding_name> also specify the ending flag of that sequence.

(A minor point, but...)  I'm not sure that the idea of specifying an 
'ending flag' is as flexible as the length-based approach that we 
currently have.  For example, how would you apply this to SCTP chunk 
headers?

> flag for each type of record listed in the <encoding_name> sequence.

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?)

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

- surely this is going to incur a minimum 1-bit overhead per entry in 
the list, per packet?

> SUB-TREE-N encoding method will produce several (sub) compressed headers.
> 

Same question as before regarding the <probability> parameter.

> record in the 'repeat-sequence'.

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...

> 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.

> an additional parameter to indicate the type of records ending approach.

This is minor notational issue.  (But, for the record, my programming 
background tends to prefer different methods rather than excessive 
parameterisation...)

> tcp-opt-sack  = SUB-TREE-N(100%,

Well, I've made plenty of specific comments above.  As a more general 
comment on the 3rd part of this e-mail, regarding list encoding, I think 
it is clear that there is some more thinking to do on this.  So, I would 
also encourage more comments and suggestions...

-- 
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)