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

From: "Qian Zhang" <[email-masked]>
Date: Tue, 09 Apr 2002 20:24:51 +0800

--------------
I had sent this email twice; however, I can not find it in ROHC mailing list 
:-(. So I have to try again.
--------------

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

_________________________________________________________________
MSN Photos is the easiest way to share and print your photos: 
http://photos.msn.com/support/worldwide.aspx

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

---

From: "Qian Zhang" <[email-masked]>
Date: Mon, 15 Apr 2002 18:09:22 +0800

Hi, Mark

Comments inline again..., :)

Cheers,

Qian & Hongbin

> 
> Qian Zhang wrote:
> 
> > [removed to save space, however, need we save the earth first? just
> > a joke.]
> 
> 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.

> > [removed to save space]
> 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...
> 

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.

> >     Secondly, we would like to propose some new notations for the
> > generic notation of header compression.
> > 
> 
> Now it gets interesting ;-)
>  
> > [removed to save space]
> > 
> 
> 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...
> 

Actually SUB-TREE-X is proposed to provide an efficient presentation for
those cases, in which there are a lot of possible entries, but few of
them will ever actually appear. We will come back to this later.

> > 
> > To propose more efficient encoding methods for
> 'out-of-order-sequence'
> > and 'repeat-sequence', we first propose an improvement on
> the compressed header format.
> > 
> > into two parts: the indicator flags and the compressed fields as
> > illustrated below:
> > 
> > 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   ...
> >    +----------------------
> >          /       \
> >         /         \
> > 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.
> > 
>  
> 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.
The result is that the profile will be very large and the Huffman code
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.

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

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

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

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

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;

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

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

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)

> 
> > 
> > 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.
> > 
>  
> Same question as before regarding the <probability> parameter.
> 
> >  
> > 
> > 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'.
> > 
> 
> 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.

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

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.

Cheers, comments are welcome.

---

From: "Qian Zhang" <[email-masked]>
Date: Tue, 30 Apr 2002 10:20:50 +0800

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

> '*'. We are now working on this.

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)