Subject: [rohc] TCP sequence number encoding

From: "West, Mark" <[email-masked]>
Date: Mon, 22 Nov 2004 11:58:22 +0000 (GMT)

Hi all,

Having rambled on enough about ack numbers, here are some thoughts about
sequence number encoding...

In general, sequence numbers increase (this should not come as a great
surprise to anyone); but we obviously have to handle retransmissions.

The point is that I would expect retransmissions to involve a small number
of packets deviating from the general trend of increasing.  In that case,
it may be preferable for the backward jumps to not update the context at
the decompressor.  If they *do* update the context, then when the
retransmission has completed and the sequence number picks up its general
increase, we have to count the current high water-mark + the
retransmission in the LSB window.

On the assumption that the compressor is seeing all of the traffic (ok,
there are scenarios where this isn't the case -- we can't rely upon it),
the compressor may be able to work out whether it's expecting single or
multiple packet retransmits and manage context updating accordingly.

I don't know how significant this is in terms of the overall efficiency
gain (if any!), but thought that it was an issue that we ought to consider
and agree on; even if we're happy to leave the formats as they are...

Cheers,

Mark.

--
Mark A. West, Senior Consultant Engineer
Roke Manor Research Ltd., Romsey, Hants.  SO51 0ZN
Phone +44 (0)1794 833311   Fax  +44 (0)1794 833433

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

---

From: Kristofer Sandlund <[email-masked]>
Date: Mon, 22 Nov 2004 15:14:22 +0100

Hi Mark,

I am not a friend of partially-context-updating packets after the 
UO-1-ID-ext3-packet fiasco in 3095, so I'm going to be sceptic about this.

I agree with the general problem description that it would be nice to let 
backward jumps somehow be non-updating, but how big is the gain really?

Let's say the backwards jump is X*payload size, then we have to send log2(X) 
bits for this jump, and if we update the context, the next packet is likely to 
be (X+1)*payload size, meaning we'll have to send log2(X+1) bits (i.e. probably 
one more bit than for the backwards jump).

If we did not update the context, we could send just "minimum number of bits of 
SEQ in one of our packet formats" (k_min) in the forward jump. From the packet 
formats have have now, I doubt that this will actually gain us any bits, since I 
guess that for most cases log2(X+1) will be equal to k_min. Or is my math off?

And if the gain is large enough, I need to understand _how_ you mean that this 
should work.
Do you wish to add a couple of new packet formats for non-updating SEQ or are 
you saying that "every time the decompressor receives a sequence number located 
to the 'left of the reference' in the interpretation interval, the context 
should not be updated with this value"? If the latter, will things such as 
reordering cause problems?

Also, could this cause inefficiency on streams where both SEQ and ACK change? 
(do we have to send the SEQ in ACK-only changes if this occurs right after a 
non-updating SEQ change?)

/Kristofer Sandlund, Effnet AB

---

From: Carsten Bormann <[email-masked]>
Date: Mon, 22 Nov 2004 16:09:03 +0100

> UO-1-ID-ext3-packet fiasco in 3095, so I'm going to be sceptic about 

I think that fiasco was a bit different -- using the same complex 
subheader format (ext3) in two different contexts with two different 
semantics clearly was a mistake.
We don't need to do that again.

My gut feeling is that the non-updating thing is interesting, but I'm 
not sure yet (I have the same questions you have).

Gruesse, Carsten

---

From: "West, Mark" <[email-masked]>
Date: Tue, 23 Nov 2004 00:32:57 +0000 (GMT)

Hi Kristofer,

> UO-1-ID-ext3-packet fiasco in 3095, so I'm going to be sceptic about this.

I admit that this was very much in my mind when thinking about this :-)
However, I would suggest [I think agreeing with Carsten] that the idea of
non-context updating things need not unleash the full horror of 3095...

... if you want to, of course, why not just make the whole packet
non-context updating?!

> backward jumps somehow be non-updating, but how big is the gain really?

That's the $64000 question.  And I don't know.

> one more bit than for the backwards jump).

Do you really mean log2(X) or log2(X*payload_size)..?  (i.e. this may
depend upon whether or not SEQ is being scaled at the point at which
retransmission is signalled)

I haven't looked (I confess) at possibly values for X (this is probably a
non-trivial question).  Let's assume, though, that a retransmission
happens based on 3 dupacks.  Then (taking an artificially small MSS for
simplicity of example) we might see a sequence of SEQ:
	1000 2000 4000 5000 6000 3000 7000 8000 9000 10000 11000...

If we assume robustness against a degree of loss and re-ordering that is
based on 3-bits of information, and a history of 3 packets at the
compressor then we have, in terms of [best] bit-costs:
	15   15   15   15   15   15   15   16   16   15    15

[using unscaled SEQ values, and assuming that the LSB window is optimally
aligned]

On this basis, yes, it is true -- all that the non-context updating
approach saves is (conceptually) 1 bit from the '8000' and '9000' packets.

> reordering cause problems?

I doubt that your math is off...

One thing that has occurred to me, though, in this discussion is how hard
it is to assess the benefit (or lack thereof) in any particular scheme.
We talk about 'saving a bit' or 'costing a bit' and whether or not this
matters.  I don't think that it's that simple: if I can save 1 bit of SEQ,
4 bits of ACK, and 1 bit of IP ID then that's 7 bits and, if I can find an
appropriate indicator, then maybe I can shave a byte off of a compressed
packet format...

I agree wholeheartedly with the dictum of not spending 80% of the effort
to get 20% of the compression gain.  But saying 'it's only 2 bits of
saving' needs to be set in the context of (i) how that compares to other
means of compressing the field; and (ii) what actual impact this has on
the average compressed packet size -- in some cases, saving a single bit
could translate into a byte saved from a packet format.

Anway, I think that, if this were to be done, then it would have to be
done explicitly (by packet format or some other indicator bit).

> non-updating SEQ change?)

I'm not sure that I understand this point.  If we have a window of n
packets (i.e. sending updates n times for robustness), then a change in
SEQ will impact the next n packets (n can be truncated through acks, of
course)..?  The only case (I think?!) where non-updating SEQ has any
effect is where, after the retransmission, SEQ reverts to a stable value
(i.e. has been sending a bunch of acks), in which case
non-context-updating is better.  But I may be missing the point...

Cheers,

Mark.

---

From: Kristofer Sandlund <[email-masked]>
Date: Tue, 23 Nov 2004 08:38:47 +0100

> simplicity of example) we might see a sequence of SEQ:

So, for now, we see an extremely marginal win on this. And this win will only 
happen if we have one packet format where the seq-bits exactly matched 15 in the 
example above. So, unless we can find an example where this seems to make more 
sense, I'd vote for having all packets update context.

> appropriate indicator, then maybe I can shave a byte off of a compressed

Yes, I agree that we cannot just look at each issue separately. But with that 
kind of discussion, we can at least weigh "bits gained vs complexity" for each 
solution so that we more easily can decide which solutions we should spend most 
effort on.

> done explicitly (by packet format or some other indicator bit).

So, just to be picky: if we add an indicator bit to a current packet format, we 
_seem_ to lose the only bit that we saved above, and if we were to add new 
packet formats, then I guess we'd have to add up to four new packet formats 
(sequential-unscaled, sequential-scaled, random-unscaled, random-scaled), and to 
motivate that I think we would need to see a bigger gain.

> non-context-updating is better.  But I may be missing the point...

I think I confused even myself with that point, so let's leave it at that :)

BR,
	Kristofer