RE: [rohc] TCP/IP EPIC profile

["Hongbin Liao (Intl Staffing)" <[e-mail]>]

Hi, Mark

	Please see my comments.

Thanks

Hongbin L.
03/08/2002


> -----Original Message-----
> From: West, Mark (ITN) [mailto:[e-mail]] 
> 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:[e-mail]]
>  >>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 [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)  >>  >>  >>  >
> 
> 
> -- 
> 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)
> 
> 
> 

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