Re: [rohc] TCP/IP EPIC profile

["West, Mark (ITN)" <[e-mail]>]

> 
> 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 [phone]   Fax  [phone]

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