Subject: [rohc] Clarification on sliding window.

From: [email-masked]
Date: Mon, 15 Sep 2003 14:11:20 +0530

Dear Experts,

By seeing the rohc specs -

"1)
a) the compressor always uses as v_ref_c the last value that has been
compressed and sent with a protecting CRC.
b) the decompressor always uses as v_ref_d the last correct value, as
verified by a successful CRC."

It looks the CRC is the governing factor at both ends (compressor and
decompressor) in deciding the reference values . Have a look at the
following paragraph below :

"GSW: Generic W_LSB Sliding Window
Each element in GSW consists of all the dynamic fields in the
dynamic chain (defined in section 5.7.7) plus the fields specified
in a) but excluding the fields specified in b).
a) Packet Arrival Time (if TIS = 1)
Scaled RTP Time Stamp (if TSS = 1) (optional)
Offset_i (if RND = 0) (optional)
b) UDP Checksum, TS Stride, CSRC list, IPv6 Extension Headers"

Now question comes out to be why do i need all dynamic fields in GSW, if
those are not to be used as the reference fields. At compressor side to
create the compressed header, at any point in time i am not refering to
rest of the fields apart from (SN, TS, IP-ID in GSW)  what i just need is
single information set corresponding to the last packet that has been
compressed and sent with a protecting CRC.

regards,
vishal

"DISCLAIMER: This message is proprietary to Hughes Software Systems Limited
(HSS) and is intended solely for the use of the individual to whom it is
addressed. It may contain  privileged or confidential information and
should not be circulated or used for any purpose other than for what it is
intended. If you have received this message in error, please notify the
originator immediately. If you are not the intended recipient, you are
notified that you are strictly prohibited from using, copying, altering, or
disclosing the contents of this message. HSS accepts no responsibility for
loss or damage arising from the use of the information transmitted by this
email including damage from virus."

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

---

From: Alan Kennington <[email-masked]>
Date: Wed, 17 Sep 2003 05:48:51 +0930

> following paragraph below :

Vishal,

I am not an ROHC expert, but I think I can answer your question.
My apologies in advance for this very long answer.

The "secure refence principle" is clarified quite well in the introductory
sections of RFC 3095. The motivation of the secure reference principle is
rather well explained, in my opinion. Your statement is correct.  The presence
of a CRC is the main criterion of whether the fields in an ROHC header must or
must not be used as the "current" header fields or protocol parameters in the
decompressor context. It is very important for the compressor and decompressor
to agree on which fields will update the decompressor context. Then the
compressor may make confident guesses about how the decompressor will interpret
future fields. Therefore the compressor can choose the right amount of
information to transmit with each packet.

I have sometimes had a disagreement between my compressor and decompressor as
to which fields will be context-updating. The result of this disagreement is
incorrect decompression. Therefore it is very important to agree on RX context
updating rules for the purpose of interoperability.

> compressed and sent with a protecting CRC.

In my (humble) opinion, the sliding window concepts in RFC 3095 are
"implementation hints". In other words, (a) they are included to assist the
implementer, (b) they are included to help understand the semantics of the
interface specification, and (c) they should not be there, because protocol
standards should not place any constraint on implementations. Part (c) is a
strongly held philosophical position by many protocol standards people.
Personally, I think that implementation hints in a standard are okay, as long
as the implementer is free to _not_ implement them. (For example, I do not
implement the 3 "compression states" IR/FO/SO etc. because I think they are
not useful. But that's another story...)

Now on the TX side (compressor), it is very convenient to keep a history (or
"sliding window") of recent packet transmissions.  (Currently I use 32 packets
in my "window".) I store _all_ IP header fields transmitted (uncompressed) and
all protocol parameters (e.g.  NBO, RND, TS-stride) for all 32 packets
transmitted. I also store "confidence" values, which is the probability that
each packet has arrived at the RX side. Also I store a bit-mask of which fields
are context-updating in each packet transmitted.

Using such a TX packet history, the compressor can always determine the total
confidence over time that each header field or protocol parameter has been
updated in the peer RX context. Therefore, the compressor can determine whether
it is "confident" that the fields/parameters have been received or must be
retransmitted.

Now my main point:
Yes, the SN/TS/IP-ID are the only fields which are subject to the 
modulo compression algorithm (called W-LSB in ROHC), but if you
think about this long enough, _all_ of the fields are subject to the
W-LSB algorithm. 

Example:
The TOS field is 8 bits.
You can only send 0 bits or 8 bits of the TOS field.
Therefore this uses W-LSB with k = 0 or 8.
There are only two possible values of k.
So this is a special case of the W-LSB algorithm!!

When I am choosing my ROHC header for a TX packet, I treat all fields equally.
They _all_ use W-LSB. But every field has only 2 possible values for k ....
except for SN/TS/IP-ID, which have more than 2 possibilities for k.

In my (still humble) opinion, this is the most important sentence in RFC 3095:

============================================
5.3.1.2.  Compression logic and packets used (U-mode)

   The compressor chooses the smallest possible packet format that can
   communicate the desired changes, and has the required number of bits
   for W-LSB encoded values.
============================================

(It took me several thousand lines to implement this sentence.)
Take the example of the TOS field. If the TOS field changes, you must
send it often enough in RX context-updating packets so that your
confidence is high enough that the RX side has the TOS field.
In this case the "string" of TOS values is constant. 
The easiest way to implement this is by storing the TOS field of all
past TX packets (but not too many). Then you can always look back
in history to determine if enough packets were sent.
In the case of non-trivial W-LSB encoded fields like SN, you have to
consider all possible values of k, and keep increasing the value of k
until you have enough bits to be confident that one of the past packets
will enable the RX context to correctly decode the field.

Consider also this:
If you do not store all of the past TX packet fields in your compressor's
sliding window, then if a field (like TOS) changes, you must 
(1) keep a count of how many times you have sent your TOS field, so that
you know when to stop sending it, or
(2) send all dynamic fields until you are confident that the TOS field is
in the decompressor context. (This is like FO state.)

It is much more efficient to count how many times you send each field.

So probably you could implement your compressor's sliding window without
all of the header fields - but then you must keep count of how many
times you sent each field after the last change (just like CSRC
table entries and CSRC list items), or you can do what I do:
I calculate a confidence value of decompressor reception of each field
using probability theory and a channel bit-error-rate model.

So there you have 4 implementation options:
-	Put all fields in the compressor's sliding window.
-	Count how many times you have sent the current value of _each_ field.
-	Use probability theory to determine confidence for each field.
-	Count hom many times you have sent _all_ dynamic fields together.

In my opinion, you are free to implement as you wish, as long as you have the
correct semantics. If your implementation is not open source, nobody will know!

Cheers,
Alan Kennington.

---

From: [email-masked]
Date: Wed, 17 Sep 2003 13:22:59 -0400

Hello Vishal,

I see Alan has given very detailed answers already. Below are my 
shorter ones (some of them are just confirming what he explained).

BR,
Zhigang

> decompressor) in deciding the reference values . 

Two purposes of CRC: a) avoid context damage and damage propagation
due to transmission errors; b) An indication that whether current packet
is a context updating packet. Purpose b) is somewhat implicit but important.

I noticed the above quote is from section 4.5.1, not from 4.5.2 which
describes the W-LSB. For W-LSB, the compressor must maintain a sliding
window of values (not only the last one sent) to deal with possible 
packet loss. See section 4.5.2 and below.

> compressed and sent with a protecting CRC.

You seem to ask two questions here: a) why does the compressor need to keep
all dynamic fields other than SN, TS and IP-ID? b) why to keep a sliding 
window instead of simply the last packet sent?

For a), the answer is that other fields can also be compressed using W-LSB. 
Actually, any sequence of values that tend to change with certain pattern
can be efficiently compressed using W-LSB. Alan gave a good example. 

For b), the answer is robustness to packet loss. The compressor simply cannot
tell which reference value it sent was actually received by the decompressor.
So it has to keep all of them and calculate the necessary bits to send in current
packet, assuming each of the previously sent reference values may be used by
the decompressor. In other words, it has to calculate k for the worst case.

Note: you may implement the compressor in different ways. However, the 
implementation must guarantee that a decompressor compliant to RFC 3095
can decompress a compressed packet correctly. That is the bottom line
and part of the protocol. Beyond that, it's a performance issue. For example, 
the worst value of k is the length of the original value of a header field, 
meaning a "lazy" implementation may just transmit uncompressed value and avoid
the sliding window for a certain field. It's still robust and RFC 3095 
compliant, but may sacrifice compression ratio - one of the goals/reasons 
of RFC 3095. A good implementation should weigh the tradeoff carefully.