Subject: RE: [rohc] TCP/IP EPIC profile

From: "Hongbin Liao (Intl Staffing)" <[email-masked]>
Date: Fri, 8 Mar 2002 09:41:01 +0800

Hi, Mark

	Please see my comments.

Thanks

Hongbin L.
03/08/2002

> -----Original Message-----
> From: West, Mark (ITN) [mailto:[email-masked]] 
> Sent: Thursday, March 07, 2002 6:27 AM
> To: Hongbin Liao (Intl Staffing)
> Cc: Qian Zhang; Julije Ozegovic; rohc
> Subject: Re: [rohc] TCP/IP EPIC profile
> 
> 
> 
> Hi Hongbin,
> 
> Ok - when you choose the encodings, you need to build up some 
> indicator 
> for the selected set of encodings.  These need to be mapped 
> to a node in 
> the Huffman tree (at the compressor).
> 
> In the ideal case, you'd be able to do the mapping in constant time 
> (that is a pair of tables, indexed on 'format identifier' and 
> 'prefix'). 
>   Naturally this would take too much memory, so is not really 
> practical.
> 
> However, suitable constructs like hash-tables should be able 
> to do the 
> mapping in very near to constant time.
> 

It's not so clear to me. Suppose there is the same situation as
previously described, there are 30 fields and each field has 2 choices.
If all prefixes must be stored at the compressor/decompressor, there
will need at least 2*30 bytes (1GB!). Clearly, it's impractical.
However, I am not clear how hash-tables can alleviate such a situation.
Would u give me some examples and time & space requirements for such a
situation?

Moreover, if you restrict the formats generated from a profile to
MAX_FORMAT. How to get the prefix (or flag) in such case? Would u give
me more example? Also, the time & space requirements.

> At the decompressor, you need to be able to go from a prefix 
> to a tree 
> node and, hence, to a format indicator (and set of encodings).  The 
> decoding of the Huffman prefix is linear with respect to the range of 
> prefix lengths.  That is, if there are prefixes of 1 bit to 10 bits 
> long, then it will take at most 10 comparisons to identify the node. 
> Also, in this case, the shorter prefixes are more likely, and more 
> efficient.
> 

Hi Julije, it seems that you are implementating EPIC-LITE, would u give
us something, the time & space requirements, for a profile? It's really
helpful for us to understand it well. Thanks.

> With regard to the mappings, there is some degree of space/time 
> trade-off.  However, there is no obvious area of inefficiency.
> 
> I can give more detail, if this would help?
> 
> Cheers,
> 
> Mark.
> 
> 
> Hongbin Liao (Intl Staffing) wrote:
> 
>  > Hi, Mark
>  > 	The overhead (time and space) of encoding a compressed packet
>  > can be splitted into two parts. One part is encoding for 
> each fields,  > and the other part is the overhead of 
> selecting the indicator (or flag)  > to indicate the encoding 
> methods of all fields. Clear, the overhead of  > the former 
> should be linearly to the number of fields. However, how  > 
> about the overhead of the later part or the overhead of 
> determining  > which Huffman prefix (function 
> 'get-indicator-flags' in ROHC-LITE)  > should be used in the 
> compressed packet?  >  > Hongbin L.  > 03/06/2002  >  >  >  
> >>-----Original Message-----
>  >>From: West, Mark (ITN) [mailto:[email-masked]]
>  >>Sent: Wednesday, March 06, 2002 8:01 AM
>  >>To: Qian Zhang
>  >>Cc: Julije Ozegovic; rohc
>  >>Subject: Re: [rohc] TCP/IP EPIC profile
>  >>
>  >>
>  >>
>  >>Hi Qian,
>  >>
>  >>Thanks for these comments, which raise some important and  
> >>interesting issues.  I've added some comments of my own!  
> >>  >>Cheers,  >>  >>Mark.  >>  >>  >> >  >> > [Julije] 
> Detailed profiles tend to result in complex  
> >>applications/protocols.  >> >  >> > [Mark] I'd have put 
> that the other way around (complex  >>protocols =>  > 
> detailed profiles), but I think I agree...  >  >> > [Julije] 
> The purpose of this posting is to point out the  >>complexity 
> of  > whole thing, regarding the fact that almost  >>every 
> line of profile ends  > up with (at least) one data  
> >>structure in end user application.  >  > [Mark] Yes, it is  
> >>quite complex.  So is RFC 3095 ;-) I would agree that  > it 
>  >>is more 'dense' than RFC 3095, for example, as most of the 
>  >  >>information is packed into the profile.  >  > Certainly 
> every  >>field (or meta-field) requires a data-structure.  
> Again,  >  >>I'm not sure how this is different from any 
> other header compression  >>scheme?  >> >  >> > [Qian] I 
> agree that the complex protocol such as TCP/IP  >>will cause 
> a  > detailed profile. What I would like to point  >>out is 
> that the compressed  > format generation should be a  
> >>tradeoff between the efficiency and the  > complexity.  >  
> >  >>Mark, would you please comments on the complexity about  
> >>generating a  > compressed format based on the input 
> profile.  >>Suppose there are 30  > fields need to be 
> considered, each  >>field may have two choices, how about  > 
> the complexity for  >>determining the compressed format?  >>  
> >>I assume that you are referring to the complexity in the  
> >>compressor, rather than in the off-line processing to build 
>  >>the Huffman prefixes (which is obviously not so 
> time-critical)?  >>  >>Overall, I would suggest that the 
> complexity of compression  >>(and this is a general statement 
> about header compression) is  >>broadly linear with respect 
> to the number of fields: double  >>the number of fields - 
> double the complexity.  >>  >>Taking your more specific 
> example, let's assume that we have  >>30 fields with 2 
> choices.  (It's worth pointing out that this  >>is a slightly 
>  >>unusual case in that a number of fields are likely to only 
> have a  >>single, fixed encoding and others will have more 
> than 2.  >>However, as an  >>example to discuss the issue it 
> works just fine, of course)  >>  >>One of the important 
> pieces of information that needs to be  >>factored in, 
> though, is the relative likelihood of the  >>various choices. 
>  I generally assume (though this may not  >>always be true) 
> that encodings are tested in decreasing order  >>of 
> probability.  After all, if one encoding is likely to be  
> >>used 99% of the time, it's probably best to try that one 
> first!  >>  >>Anyway, back to the example.  >>  >>In the best 
> case, you will test 30 encodings (one per field)  >>to end up 
> with the compressed packet.  >>  >>In the worst case, you 
> will test 60 encodings (2 per field).  >>It is also likely in 
> this case that you will have to send an  >>IR-DYN packet.  
> With typical probability values, the least  >>likely format 
> is really very, very unlikely (think 1%^30...)  >>  >>The 
> average case depends upon the probability bias, but in  
> >>general is going to be quite low.  (In this case, perhaps 
> an  >>average of 1.1 encodings per field, or around 33 
> overall?)  >>  >>Since it is clear that the number of fields 
> is important, we mustn't  >>lose sight of the fact that in 
> addition to the defined fields in a  >>protocol header, there 
> are a bunch of additional meta-fields used for  
> >>compression.  (For example, RTP TS scale factor, IP ID NBO  
> >>flag, etc...)  >>  >>Something else to bear in mind is that 
> some of the encodings  >>are more complex than others.  
> VALUE, for example, is very  >>simple since there is no 
> context history to worry about; only  >>a simple test between 
> two values.  STATIC is simple, but is  >>still requires 
> checking the context history.  >>  >>Anyway, this all leads 
> me to suggest that the complexity is based on:
>  >>- the  number of actual fields, plus the number of meta-fields
>  >>- some factor to indicate the average search depth per field
>  >>- a factor based on the depth of the context
>  >>
>  >>(I should point out that you can describe ROHC RTP in this 
>  >>way and perform a similar analysis)  >>  >>For anyone who 
> hasn't had a look, we have submitted an I-D  >>that contains 
> an EPIC profile corresponding to (a subset of) ROHC RTP:  >>  
> >>http://search.ietf.org/internet-drafts/draft-surtees-rtp-epic-00.txt
>  >>
>  >>You may like to see how the description in the profile 
> maps  >>onto the description of the field processing in RFC 
> 3095.  >>(3095 is a little more verbose; the draft is 
> somewhat terse,  >>but anyway...)  >>  >> >  >> > I would 
> like to raise a discussion on the rough number of  
> >>compressed  > formats that plan to support for TCP/IP  
> >>compression. Considering the  > complex behaviors for 
> TCP/IP  >>protocol itself, personally, I think we may  > need 
> more  >>formats than RFC 3095. However, considering that the  
> >  >>compression ratio is not the only target for TCP/IP 
> header  >>compression,  > we also may not need to generate 
> too much  >>kinds of format.  >  >>  >> > Can we come out a 
> reasonable number of the max_formats for  >>the TCP/IP  > 
> compressed header and provide a simpler profile  >>to 
> describe the behavior  > of each field?  >  >>  >>This is an 
> interesting question.  >>  >> From our perspective, if you 
> build the compressed packet up  >>by processing on a 
> field-by-field basis (as described in the  >>draft), then the 
> number of formats is not a very important  >>issue.  (Rather, 
> it is possible to support a very large  >>number of formats). 
>  >>  >>RFC 3095 has very few basic packet formats.  However, 
> once you start  >>factoring in the extensions and the 
> variability in extension  >>3 (plus the  >>additional flags), 
> there are actually quite a lot of formats.  >>  >>We should 
> bear in mind that the compressed packets are  >>generated by 
> an algorithmic process -- each packet does not  >>have a 
> separate encoding  >>function.  >>The mapping between 
> selected encodings and packet format (and vice
>  >>versa) should be simple and equally quick for all formats. 
>  >>The quantity of data required to describe a profile (and the
>  >>formats) to a compressor/decompressor is minimal.
>  >>
>  >>(I'm at home at the moment, and don't have any numbers to  
> >>hand, but I'll  >>send some figures when I'm next in the 
> office)  >>  >>What is interesting to note is that the 
> predicted benefit of  >>adding more formats decreases as the 
> number of formats gets larger.  >>  >>It is, however, clearly 
> an issue that we will have to decide  >>with regard to the 
> TCP profile.  I think that this requires  >>us to start 
> getting an idea of the probabilities that should  >>be 
> assigned to encodings.  This lets us have some indication  
> >>of the effect of adding (or removing) formats.  >>  >>
>  >>--
>  >>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)  >>  >>  >>  >
> 
> 
> -- 
> 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)
> 
> 
> 

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

---

From: Julije Ozegovic <[email-masked]>
Date: Fri, 08 Mar 2002 11:05:37 +0100

Hi all!

here is the short explanation of our CDE (Compressor 
Decompressor Engine).

1. We have profile structures in the memory, in form of double 
linked list.

2. On arrival of the uncompressed packet, compressor traverses 
the header AND the profile top-down, trying to optimally 
compress each field. Chosen methods are identified in a "method 
string". Method string indicates the actual profile.

  3. Method string is used to traverse coder Huffman tree, which 
finally yields predetermined ID_bits. This step can be done 
during the field compression step by step, but we decided to 
keep it this way for debugging purposes (separate functions as 
much as you can).

4. On arrival of compressed packet, decompressor chooses 
appropriate decoder Huffman tree (one per format set) and 
traverses it according to ID_bits. When finished, predetermined 
"method string" is picked from the list. Actually, we have 
(max_sets+2)*max_formats different method strings.

5. Decompressor traverses profile and compressed header 
bottom-up according to picked method string.

The main memory waste is the decompressor method string storage, 
  and that's why I argue for simpler profile (lower number of 
formats) :)

Our application is currently file-to-file oriented, and is 
stuffed with screen dump of every step in the process. Being 
concentrated to the function itself, we did not set up proper 
performance testing environment. It's planned in the future.

Cheers,
Julije

---

From: "West, Mark (ITN)" <[email-masked]>
Date: Fri, 08 Mar 2002 11:21:23 +0000

> Would u give me some examples and time & space requirements for such a

ok.  Let's take this example of 30 fields with 2 choices.  I can store a 
'0' or a '1' bit for each choice as I move from field to field.  This 
clearly gives me a space with 2^30 possible outcomes.

Since it is obviously impractical to make use of all possible formats, 
we have to restrict the number of formats that are actually used.

The point that I was trying to make, though, was that we can see a 
theoretically constant-time mapping: if I assume a table that contains 
all 2^30 possible outcomes, each can have a flag indicating whether the 
combination is present in the reduced list of formats.  If the 
combination is one of the MAX_FORMATS possibilities, then the table also 
contains the Huffman prefix.

Of course, in this case, even if the number of formats used is small, we 
still have this huge (2^30 entry) table.

If I set MAX_FORMATS to 400, say, then I am only keeping the 400 most 
likely headers.  This is less than 1 millionth of the possible 
combinations, so it's fair to say that the table to do the mapping is 
quite sparse!

What I am suggesting is that we create a table with a minimum of 400 
entries (but more realistically something like 500 - 600) and hash the 
30-bit format indicator down to a 9 or 10-bit hash table index.

Provided that the hash function is
- efficient (in time)
- relatively collision resistant
then you should retain very close to constant-time mapping, without a 
large cost in memory.

Does that clarify things?

Cheers,

Mark.

(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, 10 Mar 2002 13:49:10 +0000

Hi Julije,

Comment inline...

Cheers,

Mark.

Julije Ozegovic wrote:

 > Hi all!
 >
 > here is the short explanation of our CDE (Compressor Decompressor 
Engine).
 >
 > 1. We have profile structures in the memory, in form of double linked 
list.

ok.

 > 2. On arrival of the uncompressed packet, compressor traverses the
 > header AND the profile top-down, trying to optimally compress each
 > field. Chosen methods are identified in a "method string". Method string
 > indicates the actual profile.
 >

So you work through each field, selecting an encoding and storing the
set of chosen encodings.  So far, so good...  (Of course it's the act of
traversing the profile that automatically breaks down the header)

 >  3. Method string is used to traverse coder Huffman tree, which finally
 > yields predetermined ID_bits. This step can be done during the field
 > compression step by step, but we decided to keep it this way for
 > debugging purposes (separate functions as much as you can).
 >

This may just be a terminology issue, but I don't think that there is
(or shouldn't be) any traversal of the Huffman tree going on.  The
'tree' is built as part of the off-line processing of the profile and
yields a set of indicator flags.  The 'method string' will map to a node
which is itself associated with a prefix.

To work out the prefix you may need to do some fiddling around with
prefix lengths - is that what you mean?

I don't believe that it is practical/possible to do prefix
identification step by step.  It's not only preferable for debugging but
also, I suspect, performance...

 > 4. On arrival of compressed packet, decompressor chooses appropriate
 > decoder Huffman tree (one per format set) and traverses it according to
 > ID_bits. When finished, predetermined "method string" is picked from the
 > list. Actually, we have (max_sets+2)*max_formats different method 
strings.

Yes.  Although, again, it's not really a full tree traversal, but a
match against value ranges for each prefix length.  The ID maps to a
'format string', which gives you the codings.

 > 5. Decompressor traverses profile and compressed header bottom-up
 > according to picked method string.
 >

Yes.

 > The main memory waste is the decompressor method string storage,  and
 > that's why I argue for simpler profile (lower number of formats) :)
 >

I don't believe that the 'method string' storage should be particularly
memory intensive.  From Hongbin's simple example of 30 fields with 2
encodings per field we can build a 'format string' in 30 bits.  Any
field that has only one encoding choice does not need to appear in the
format string.  Every other field needs at most ceiling(log2(n)) bits,
where n is the number of encodings.  The sum of these over all the
fields gives you the answer...

 > Our application is currently file-to-file oriented, and is stuffed with
 > screen dump of every step in the process. Being concentrated to the
 > function itself, we did not set up proper performance testing
 > environment. It's planned in the future.
 >
 > Cheers,
 > Julije
 >