Border cases in packet number decoding

[huitema]

I am afraid that the specification of packet number decoding in the transport spec is a bit ambiguous.
The transport spec says:

The sender MUST use a packet number size able to represent more than twice as large a range than
the difference between the largest acknowledged packet and packet number being sent. A peer
receiving the packet will then correctly decode the packet number, unless the packet is delayed in
transit such that it arrives after many higher-numbered packets have been received. An endpoint
SHOULD use a large enough packet number encoding to allow the packet number to be recovered
even if the packet arrives after packets that are sent afterwards.

As a result, the size of the packet number encoding is at least one more than the base 2 logarithm of
the number of contiguous unacknowledged packet numbers, including the new packet.

For example, if an endpoint has received an acknowledgment for packet 0x6afa2f, sending a packet
with a number of 0x6b4264 requires a 16-bit or larger packet number encoding; whereas a 32-bit
packet number is needed to send a packet with a number of 0x6bc107.

So, let's suppose a node that is processing a packet. The packet header says that the packet number is encoded on 2 bytes, and the value is PN=0x8000. The highest received number is R=0x10000. Should the receiver expand PN to PN64=0x180000, or to PN64=0x8000?

[mcmanus]

A packet number is decoded by finding the packet number value that is closest to the next expected packet. The next expected packet is the highest received packet number plus one.

what I have done is interpreted that given 16 bits of recvd = 0x8000, and expected = 0x10001 .. the packet is decoded as 0x8000 because 0x8000 is closer to 0x10001 than the other choice 0x18000

nonetheless, I would much prefer packet numbers to be concrete 64 bit numbers variably length encoded somehow.

[ianswett]

Can you clarify what the ambiguity is? 0x8000 is closer to 0x10001 than 0x18000 is as Patrick said, so you choose 0x8000.

Minus the variable length aspect, I don't believe this is that dissimilar from how TCP decodes sequence numbers, is it?

[ianswett]

Actually, in this case 0x18000 is closer by 2:
0x8000 = 32768
0x10001 = 65537
0x18000 = 98304

But Patrick's logical reasoning is still correct.

[mcmanus]

hah - yes. a little base-10 brain action.

[huitema]

Thanks for the explanation. Right now, I am just trying to write test vectors, and I was little bit puzzled. So, to keep my example, the test vector will be:
Highest = 0x10000
Expected = 0x10001
PN = 0x8000
Hypothesis 1: 0x18000, delta to expected = 0x7FFF
Hypothesis 2: 0x8000, delta to expected = 0x8001
Prefer Hypothesis 1, PN64 = 0x18000

Of course, this algorithm breaks down in this particular case:
Highest = 0xFFFF
Expected = 0x10000
PN = 0x8000
Hypothesis 1: 0x18000, delta to expected = 0x8000
Hypothesis 2: 0x8000, delta to expected = 0x8000
Do something arbitrary.
(Prefer lowest value, probably.)

[martinthomson]

Yes. There is a single case where the decoded value could equally be one of two different values. Given that this is a corner case, and given that I don't think that the specific answer matters, can someone toss a coin and tell me which one to use? Failing that, I'll pick Christian's answer (the lower value).

[ianswett]

The lower value is fine. It really should never matter since we'd expect to only receive packets within 1/4 of expressible range, just like TCP sequence numbers aren't supposed to use the entire space.

At some point, Jana and I considered recommending the peer close the connection if the packet number was in the half of the space you don't expect, but we weren't convinced that was actually helpful.

[ianswett]

Adding pseudocode and tweaking the existing text should clarify this.

[huitema]

I agree that adding pseudo code will solve the issue.

[martinthomson]

Closed by #1493.