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

From: "Hongbin Liao (Intl Staffing)" <[email-masked]>
Date: Wed, 6 Mar 2002 16:51:41 +0800

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

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

---

From: "West, Mark (ITN)" <[email-masked]>
Date: Wed, 06 Mar 2002 22:26:33 +0000

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.

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.

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.

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

---

From: Julije Ozegovic <[email-masked]>
Date: Thu, 07 Mar 2002 15:38:32 +0100

Hi,

I think this important issue deserves new thread!

The question of computing efficacy (when compressing and 
decompressing) starts with "implementation specific" dilemma:

1. Interpreter:

Interpreting implementation benefits of larger flexibility in 
changing and adding supported profiles.

Of course, I do not mean pure "text" interpreter, but rather 
specific "profile compiler" that builds necessary data 
structures in "off line processing phase", and then traverses 
through them during the compression and decompression process 
("on line processing phase").

In this approach, it is easy to submit new profile and  compile 
it, without need to change internal interpreting engine. that 
means that application does not need to be changed or recompiled 
for every new profile.

2. Compiler:

Compiled implementation is much more "computational efficient", 
regarding the fact that profile structure is built in code 
itself. However, adding new profile requires application to be 
recompiled. It can hardly be done online.

Toolbox methods and general online framework can be common, and 
recompiled for every (set of) supported profile(s). A kind of 
EPIC library can be distributed to ease this procedure.

3. Conclusion:

It seem that everybody is concerning "interpreting application".

4. UNI Split implementation

Implementation at University of Split is interpreting one. We 
build dynamic (profile specific) structures in the memory from 
the text written profile. Compressor - decompressor engine is 
protocol independent. Its duty is to engage appropriate toolbox 
method, regarding state of the engine, context, and state of the 
process (header field concerned, along the profile). At the 
moment, the "simple TCP/IP profile" is supported.

When rising the issue of complexity few days ago, I was 
motivated  by the complexity of data structures needed to 
support protocol independent engine of interpreting 
implementation, regarding the new "complex TCP/IP profile". 
However, we did not succeed to compile it yet, so I can not give 
you actual numbers.

Best regards,
Julije Ozegovic

West, Mark (ITN) wrote:

> ------------------------------------------------------------------------
> 
> The information contained in this e-mail and any attachments is confidential to Roke 
> Manor Research Ltd and must not be passed to any third party without permission. This 
> communication is for information only and shall not create or change any contractual 
> relationship.
> 
> RMRL-Disclaimer.txt
> 
> Content-Type:
> 
> text/plain
> Content-Encoding:
> 
> 7bit
> 
>

---

From: "West, Mark (ITN)" <[email-masked]>
Date: Thu, 07 Mar 2002 18:56:56 +0000

Hi all,

As ever, comments in-line...

Cheers

Mark.

Julije Ozegovic wrote:

> The question of computing efficacy (when compressing and decompressing) 
> starts with "implementation specific" dilemma:
> 

I hope it's a choice, rather than a dilemma..!

;-)

> 1. Interpreter:
> 
> Interpreting implementation benefits of larger flexibility in changing 
> and adding supported profiles.
> 
> Of course, I do not mean pure "text" interpreter, but rather specific 
> "profile compiler" that builds necessary data structures in "off line 
> processing phase", and then traverses through them during the 
> compression and decompression process ("on line processing phase").
> 
> In this approach, it is easy to submit new profile and  compile it, 
> without need to change internal interpreting engine. that means that 
> application does not need to be changed or recompiled for every new 
> profile.
>

Which is, of course, a large part of the basis of EPIC(-lite).

> regarding the fact that profile structure is built in code itself. 
> However, adding new profile requires application to be recompiled. It 
> can hardly be done online.
> 
> recompiled for every (set of) supported profile(s). A kind of EPIC 
> library can be distributed to ease this procedure.
> 

This is quite interesting.  I haven't really though too much about this 
approach.  I'm not entirely sure how much of a performance gain this 
would actually give, though.  A lot of the complexity (such as it is) is 
in the processing of the encoding methods (which are always [?] 
compiled).  All you are saving here is some kind of list traversal, 
which should be pretty quick?

We have used a 'hybrid' approach, which we mentioned briefly a long time 
ago, when trying to get some performance metrics from an earlier 
implementation.  In this case we were looking at an RTP profile.  It was 
clear that the most common packet format (the equivalent of the UO-0 
packet in RFC-3095) was much more likely to occur than any other.
So, we added some code to predict the changes for this most likely case 
and treat it 'optimally'.  This meant that we avoided any of the header 
parsing and mapping normally required in this case -- it makes a 
substantial difference to the performance.

However, this cannot be regarded as compiling the profile - it's a very 
specific 'tweak'.

> It seem that everybody is concerning "interpreting application".

Personally, my view is that the 'interpreter' view is the most useful 
starting point.  As you may have noticed, profiles in the early stages 
of development need to be tested and change quite regularly ;-)

An interpreting compressor/decompressor makes it easy to try out ideas 
and see what works and what effect this has on efficiency.  This may 
well be easier than making changes in a compiled environment.

Also, I'll be interested to see how fast an 'interpreting' 
implementation works.  If it's 'fast enough' for most applications then 
there may not be a pressing need to go for compilation.

> Implementation at University of Split is interpreting one. We build 
> dynamic (profile specific) structures in the memory from the text 
> written profile. Compressor - decompressor engine is protocol 
> independent. Its duty is to engage appropriate toolbox method, regarding 
> state of the engine, context, and state of the process (header field 
> concerned, along the profile). At the moment, the "simple TCP/IP 
> profile" is supported.
> 

Our implementation is also interpretation based.

When you say the 'simple TCP/IP profile is supported' I assume you mean 
that this is the only profile you have currently run?  That is, since 
it's protocol independent, you don't care what the profile is for?

> When rising the issue of complexity few days ago, I was motivated  by 
> the complexity of data structures needed to support protocol independent 
> engine of interpreting implementation, regarding the new "complex TCP/IP 
> profile". However, we did not succeed to compile it yet, so I can not 
> give you actual numbers.
> 

Well, there are clearly some bugs with the more complex profile that we 
haven't sorted out yet.  But I'm not sure that there's anything 
dramatically more *complex* in this protocol.  There's a lot more of it, 
but it still follows the same rules for processing.  Some of the methods 
are more complex, but...

At the compressor, a profile is (essentially) a list of methods.  Each 
element in that list may have list of encodings associated with it.  An 
encoding can have a set of parameters which can be integers or pointers 
to methods.
All the compressor does is traverse the list of methods, trying to find 
a successful encoding for each one.  Some nodes will expand into 
sub-trees, which simply repeats this process.  Some encodings can invoke 
other methods - but this is written into the implementation of the encoding.
The processing of any profile is really quite straight-forward and does 
not get any more complex for a bigger profile.  There's just more to do...