RE: [rohc] TCP/IP EPIC profile

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

> -----Original Message-----
> From: Hongbin Liao (Intl Staffing) [mailto:[e-mail]] 
> Sent: Friday, March 08, 2002 9:41 AM
> To: West, Mark (ITN)
> Cc: Qian Zhang; Julije Ozegovic; rohc
> Subject: RE: [rohc] TCP/IP EPIC profile
> 
> 
> 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.
                     ~~~~
		Sorry, it should be 2**30

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

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