Subject: Re: [rohc] W-LSB encoding problem

From: Stefan Hendrata <[email-masked]>
Date: Fri, 31 May 2002 20:02:22 +0200

Hello,

your analysis looks correct.

Actually, I also got some other responses telling me to use uncompressed
IP-ID transmission in such a case. In fact I wasn't using fully randomized
sequences but sequences that contain a random change after a number of
uniform increments and I was thinking that the W-LSB compression would be
"robust" enough to deal with such random changes.

After discussing this issue with a colleague and thinking about it, I came to
the following conclusion:

Remember that the sliding window contains all reference values that the
decompressor could possibly use, and the compressor is looking for the
reference value yielding the greatest number k of bits. Thus, using v_min and
v_max of a sliding window to determine the greatest number k of bits needed
to be transmitted works only if v_min and v_max have the minimum and maximum
distances to v compared with all values in the sliding window.

Taking wrap-around arithmetic into account, this is only true as long as
v_max - v_min remains smaller than the half of the range of values. If v_max
- v_min becomes larger, it is no longer assured that v_min and v_max have the
minimum and maximum distances to v (as can be seen in the example given in my
first posting),

Thus, a simple and effective solution to my problem was:
- If the width of the sliding window is smaller than the half of the range of
values, use the algorithm as described in the RFC to determine the number k
of bits.
- If the width of the sliding window is equal or larger than the half of the
range of values, transmit all bits.

This one-line-workaround made our W-LSB encoder "robust" to deal with random
changes.

I understand that the RFC contains statements regarding the limitation of the
maximum width of the sliding window for U- and O-mode. So this issue may be
of no practical relevance but it is theoretically interesting though.

Stefan Hendrata

On Wednesday 29 May 2002 07:25, you wrote:
> Hi.
>
> Following is based on my understanding.
> I think the main reason is because the interpretation interval function in
> ROHC didn't consider the random change in numbers.
>
> Let's assume rule d) proposed in rfc3095 page 26 is used by both compressor
> and decompressor. That is:
> f(v_ref, k) = [v_ref - 2^(k-2) + 1, v_ref + 2^(k-2) *3].
> We also assume the maximum number is 65535 (two bytes integer)
>
> For your case, the window has three values (100, 60000, 50000), thus the
> v_min = 100,
> v_max = 60000, v = 2000.
>
> k1 = g(v_min, v) = g(100, 2000) = 12.
> k2 = g(v_max, v) = g(60000, 2000) = 14;
>
> Thus k = max(k1, k2) = 14.
>
> The bits carried in header will be 00 0111 1101 0000.
> The decompressor interprates the value by replace the lower 14 bits of
> 50000 (1100 0011 0101 0000) by the above bits string and get 1100 0111 1101
> 0000 = 51152.
>
> The reason is becuause the 50000 jumps back too much in the current rule d)
> and cause the value 2000 out of the intersection of the interpretation
> interval of the 50000 and 60000.
> Interpretation interval for 50000 : [45905, 62288]
> Interpretation interval for 60000 : [55905, 6752]
>
> The lower boundry you can jump back is 55248, that means if the third value
> in the window is less than 55248, you may get 51152. If it is greater than
> or equal 55248, you will get the
> right value, 2000.
>
> So, if you want to send random values, you'd better send all the bits
> instead of using W-LSB, for example, the IP_ID filed in the IPV4 header,
> when rnd is on, it is send without
> compression.
>
> If anything wrong in my analysis, please point it out. Let's understand it
> together.
>
> Best regards.
>
> Haiguang
>
>
> ----- Original Message -----
> From: "Stefan Hendrata" <[email-masked]>
> To: <[email-masked]>
> Sent: Tuesday, May 28, 2002 10:27 PM
> Subject: [rohc] W-LSB encoding problem
>
> > Hello,
> >
> > My company is also working on a ROHC implementation and I've come across
> > a problem with the W-LSB encoding scheme for which I don't have an
>
> explanation
>
> > yet:
> >
> > I have feeded our W-LSB encoder/decoder with sequences of numbers
>
> containing
>
> > both uniform increments and random changes for testing. This brought me
> > to
>
> a
>
> > problem of incorrect encoding and decoding, and I don't know if the error
> > lies within our understanding of W-LSB encoding/decoding or if it's
> > within the scheme itself.
> >
> > To come straight to the problem, please look at the following sample
>
> sequence:
> > 100
> > 60000
> > 50000
> > 2000
> >
> > After encoding and decoding the first three numbers, the W-LSB encoder
> > has
>
> a
>
> > v_min of 100 and a v_max of 60000. v_ref of the W-LSB decoder has the
>
> value
>
> > 50000. Now, for encoding and decoding the fourth value v=2000, the
> > encoder takes v_min and v_max to calculate the number k of bits needed.
> > If the decoder gets these k bits and decodes them, it yields a value of
> > 51152
>
> which
>
> > is of course unequal to 2000. Apparently, the number of bits k is not
> > high enough, but k results from v_min and v_max which are closer to the
> > wrongly decoded value (wrap-around view) than the decoder's v_ref.
> >
> > So, the simple question is: What's wrong here?
> >
> >
> > Thank you,
> > Stefan Hendrata
> > acticom GmbH, Germany
> >
> >
> > _______________________________________________
> > Rohc mailing list
> > [email-masked]
> > https://www1.ietf.org/mailman/listinfo/rohc
>
> _______________________________________________
> Rohc mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/rohc

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

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