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

From: "Hongbin Liao (Intl Staffing)" <[email-masked]>
Date: Mon, 11 Mar 2002 16:30:37 +0800

Hi, Mark

    Thanks for your comments. However, there comes several more issues.

    1. whether can TCP/IP EPIC profile correctly describe the behavior of TCP? Or, whether EPIC is powerful enough to describe the complicated behavior of TCP/IP?

    In EPIC, fields are assumed to be independent from each other. Once each field's behaviors are described well, the whole protocol's behaviors are also well-studied. However, in practice, fields in a protocol may not behave independently completely from each other. There may be some connections (or causality) among several fields. For example, most TCP traffics only contain one-way traffic (WWW browsing, FTP downloading, etc.), i.e., only SEQ changes on the forward path (from server to client) and only ACK changes on the backward path (from client to server). The ACK on the forward path and SEQ on the backward path remain constant. However, in TCP/IP EPIC profile, the probabilities for SEQ and ACK are specified seperately:

seqno-co = LSB(8,63,5%) | LSB(14, 4096, 80%) | LSB(20,16384,10%) | IRREGULAR(32,5%)

ackno-co = LSB(8,0,5%) | LSB(14,0,80%) | LSB(20,0,10%) | IRREGULAR(32,5%)

That means, the most frequent packet format is SEQ(LSB-14)/ACK(LSB-14) with probability 64% according to the EPIC profile. However, the most frequent formats are SEQ(LSB-14)/ACK(LSB-8) and SEQ(LSB-8)/ACK(LSB-14) instead. The result is that the compressor uses the shortest Huffman prefix with a not so frequent case and a longer prefix with the most frequent case. The overall performance downgrades.

    Not only SEQ and ACK have this kind of issue in TCP/IP, TCP options, WINDOW and etc. also have the such an issue. EPIC TCP/IP profile give a wrong, at least not appropriate, probability for each combination of encodings of all fields. To solve it, we have to give the probabilities of each combination of encodings of all fields instead of the probailities of each field individually. However, it seems that EPIC has no such a method to do that. Also, it's impractical to write a profile listing each combination of encoding of all fields.

    2. MAX_FORMATS

    To alleviate the memory requirement on compressor and decomressor, EPIC uses MAX_FORMATS to restrict the packet formats generated from profiles. However, if a list of encoding methods doesn't fall in the supported formats, how EPIC encodes it? How to give the accurate information for each encoding method in this kind of lists? Or, the worst encoding method is used for this kind of lists? However, whatever is used, there will be an extra overhead for the encoding methods not falling in the MAX_FORMATS. The issue is how efficiently EPIC handles this situation. It may depends on how to set MAX_FORMATS. The issue is that, is there such a MAX_FORMATS which alleviate the memory requirements and reduce the extra overhead simultaneously? How to determine it? Could you have a rough number on it?

Hongbin L.
11/03/2002

> -----Original Message-----
> From: West, Mark (ITN) [mailto:[email-masked]]
> Sent: Friday, March 08, 2002 7:21 PM
> To: Hongbin Liao (Intl Staffing)
> Cc: Qian Zhang; Julije Ozegovic; rohc
> Subject: Re: [rohc] TCP/IP EPIC profile
>
>
>
> >
> > 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?
>
>
> 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.
>
>
> --
> 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)
>

---

From: "West, Mark (ITN)" <[email-masked]>
Date: Mon, 11 Mar 2002 23:46:22 +0000

Hi Hongbin,

Responses inline...

Cheers,

Mark.

Hongbin Liao (Intl Staffing) wrote:

>     1. whether can TCP/IP EPIC profile correctly describe the behavior 
> of TCP? Or, whether EPIC is powerful enough to describe the complicated 
> behavior of TCP/IP?
> 

Ok, there are 2 issues here.  Firstly, TCP is a complex protocol -- no 
argument there!  Does the profile adequately capture it?  I don't know! 
  But there have been arguments to suggest that the protocol is *too* 
complicated!  However, the complexity of the profile is a function of 
the complexity of the protocol.

EPIC can capture arbitrarily complex behaviour.  But (as has been 
discussed) there is a trade-off between profile complexity and 
usefulness.  I could make the profile significantly more complex 
(honestly!)  But would that actually be useful?!

This, I think, is a general issue.  It may be possible to write a highly 
accurate description of TCP, but this complexity would translate 
directly into the implementation of the header compression scheme 
(regardless of how the scheme is expressed).

>     In EPIC, fields are assumed to be independent from each other. Once 
> each field's behaviors are described well, the whole protocol's 
> behaviors are also well-studied. However, in practice, fields in a 
> protocol may not behave independently completely from each other. There 
> may be some connections (or causality) among several fields. For 
> example, most TCP traffics only contain one-way traffic (WWW browsing, 
> FTP downloading, etc.), i.e., only SEQ changes on the forward path (from 
> server to client) and only ACK changes on the backward path (from client 
> to server). The ACK on the forward path and SEQ on the backward path 
> remain constant. However, in TCP/IP EPIC profile, the probabilities for 
> SEQ and ACK are specified seperately:
> 
> That means, the most frequent packet format is SEQ(LSB-14)/ACK(LSB-14) 
> with probability 64% according to the EPIC profile. However, the most 
> frequent formats are SEQ(LSB-14)/ACK(LSB-8) and SEQ(LSB-8)/ACK(LSB-14) 
> instead. The result is that the compressor uses the shortest Huffman 
> prefix with a not so frequent case and a longer prefix with the most 
> frequent case. The overall performance downgrades.
> 
>     Not only SEQ and ACK have this kind of issue in TCP/IP, TCP options, 
> WINDOW and etc. also have the such an issue. EPIC TCP/IP profile give a 
> wrong, at least not appropriate, probability for each combination of 
> encodings of all fields. To solve it, we have to give the probabilities 
> of each combination of encodings of all fields instead of the 
> probailities of each field individually. However, it seems that EPIC has 
> no such a method to do that. Also, it's impractical to write a profile 
> listing each combination of encoding of all fields.
> 

It is quite fair to say that the fundamental starting point of the EPIC 
approach is that fields are considered independently.  However, it is 
quite wrong to say that it is not possible to account for dependent 
field behaviour.

(I certainly describe the fields as independent for your '30 fields with 
2 choices each' example -- you have given me no information to suggest 
otherwise.  If you want to describe a relationship between a subset of 
the fields, I'm happy to modify my description...)

For example, though, in the complex TCP profile, there are 3 different 
format sets for each of the cases of 'interactive traffic', 'bulk data 
flow' and 'bulk ack flow'.  (I'm quite happy to accept that these do not 
yet correctly reflect the TCP behaviour that we want, but it is clearly 
the case that they capture the existence of a dependency between 
sequence and acknowledgement number...)

You don't (necessarily) have to give probabilities to all combinations 
(which would obviously be impractical), but it is true that you should 
account for the gross dependencies.

(In the example that you discuss above, for example, it is clear that 
the profile description and the probabilities in the text do not match. 
  It is trivial, however, to make the profile match the text).

It is disingenuous to suggest that this is an EPIC specific issue, 
though!  Any set of packet formats that are written out make an implicit 
statement about the relative probabilities of certain occurences.  (This 
is certainly true of RFC 3095...)

Fundamentally, for header compression, it is clear that it is not 
practical to have an exact match for the behaviour of a complex 
protocol.  However (and this is something that we have touched on in 
previous discussions), there is a point beyond which increasingly 
accurate descriptions achieve relatively little in terms of compression 
efficiency.

>     2. MAX_FORMATS
> 
>     To alleviate the memory requirement on compressor and decomressor, 
> EPIC uses MAX_FORMATS to restrict the packet formats generated from 
> profiles. However, if a list of encoding methods doesn't fall in the 
> supported formats, how EPIC encodes it? How to give the accurate 
> information for each encoding method in this kind of lists? Or, the 
> worst encoding method is used for this kind of lists? However, whatever 
> is used, there will be an extra overhead for the encoding methods not 
> falling in the MAX_FORMATS. The issue is how efficiently EPIC handles 
> this situation. It may depends on how to set MAX_FORMATS. The issue is 
> that, is there such a MAX_FORMATS which alleviate the memory 
> requirements and reduce the extra overhead simultaneously? How to 
> determine it? Could you have a rough number on it?
> 

This, again, is an interesting point -- but one that is the subject of a 
trade-off in *any* header compression scheme.  If a 'CO' format cannot 
be found to encode a particular format, then an IR-DYN packet is used. 
This, of course, is identical to RFC 3095.  You cope with the most 
likely compressed packets efficiently and use a dynamic packet for the 
remainder.  This provides a less efficient encoding but (1) increases 
robustness, since the IR-DYN refreshes the dynamic context as a 
side-effect and (2) avoids trying to cope with extraordinarily unlikely 
change combinations.

I don't know how the figures work out, but I hope that with a moderate 
MAX_FORMATS value, there is an extremely high likelihood of matching a 
compressed packet format.  If one in a thousand packets uses IR-DYN 
because of an unlikely change-pattern, does that really affect efficiency?!

Critically, we need to preserve transparency.

And, anyway, RFC-3095, as I say, contains much the same trade-offs.