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

From: "Qian Zhang" <[email-masked]>
Date: Tue, 5 Mar 2002 13:04:36 +0800

Hi Julije and Mark,

I would like to add some comments for TCP/IP compression and EPIC
profile related issues.

Please see my comments inline.

Regards,

Qian

----------------------------------------------------------------------

[Julije]First of all, I think that TCP/IP header compression is needed. 

Also I think that EPIC(-lite) high level "compression definition 

language" is right approach. Also, I support EPIC "protocol 

independence". However, all this did motivate me for profile 

'expansion'.

EPIC provides total freedom of profile writing, when profile 

author has possibility to deal with header on bit-by-bit basis.

[Qian] Agree. I want to emphasize one thing that the key for TCP/IP
header compression (ROHC-TCP) is to clearly and accurately understand
and analyze the behavior of each field (includes the changing pattern,
sharable characteristics, etc.). As both of you mentioned, EPIC-LITE is
a high-level compression definition language, and it is protocol
independent.

In ROHC-TCP, EPIC-Lite can be viewed as a tool to generate the
compressed header format. It is independent with the state machine of
ROHC-TCP. The state machine part will take care of the context updating,
compressor/decompressor states and modes management. The interaction
between state machine and compressed format generation is that the
estimated congestion window or link feedback obtained by state machine
is the control parameter for format generating.

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

Any comments?

-------------------------------------------------------------

---

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

Hi Qian,

Thanks for these comments, which raise some important and interesting
issues.  I've added some comments of my own!

Cheers,

Mark.

applications/protocols.
 > detailed profiles), but I think I agree...
 >
scheme?
 > 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...)

 > compressed header and provide a simpler profile to describe the behavior

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)