Subject: [QUIC] Packet number recovery

From: Martin Thomson <[email-masked]>
Date: Thu, 10 Nov 2016 16:23:32 +1100

Sayeth Section 4.2.1:

   a QUIC sender MUST NOT have more
   than 2^(packet_number_size - 2) in flight at any point in the
   connection

and:

   Any truncated packet number received from a peer MUST be
   reconstructed as the value closest to the next expected packet number
   from that peer.

(relatively) big questions:

Q1
I don't think that this limit is necessary.  The point is to use a
packet number that is big enough that reordering won't cause an
endpoint to recover the wrong packet number.

I can see how you get here.  You only predict backwards for 2^N-1
packets.  You want to divide that into packets that were in the last
RTT worth and packets that are in the next RTT worth.  The former
because you haven't received an ACK for those yet, and the latter
because you are sending those.  I think that's overly pessimistic by a
factor of two because you only have one RTT plus delta unacknowledged
packets at any instant (delta being the RTT variance plus any ack
collation delays).  Of course I'd be happy to see some data that
proved me wrong.

Q2
I don't think that this is the only possible algorithm, or even the
best.  For instance, before there was anything in the QUIC spec, I
described an algorithm that looks exclusively backwards from the last
received packet.  If a packet with that number was already received,
then it's in the future and add 2^(packet_number_size) to get the real
number.  Otherwise, look in the window around the predicted next
value.  Assuming low loss rates, this doubles the search space.

I don't think that we need a MUST on the actual algorithm, just a
suggestion about what to use.  If someone wants to do something
slightly different, then that's OK.  For instance, I can imagine some
crazy folks doing trial decryption to recover packet numbers over a
larger window.  I can also imagine very limited implementations that
insist on monotonic packet numbers and drop older packets
unconditionally, even if they are only microseconds late.

Some of those options are especially suboptimal on various measures,
but the key point is that none of them introduce interoperability
failures.  Lost frames are retransmitted as necessary and the world
moves one.

(Actually, that last one is probably a terrible idea because it would
create a ridiculously high false loss signal that the congestion
controller would react badly to, but I think that it is still not an
interoperability failure.)

(annoying) little questions:

Q3
Please define "in flight".  I've assumed that this means in the same
RTT. I also realize that this is fuzzy. Jitter, buffering and other
factors mean that you can end up with more or less packets in the air
than your predictions lead you to expect.  I still want a more
concrete definition if we're going with a MUST here.

I can think of several answers:
in_flight = pn[last_sent] - pn[highest_acknowledged]
in_flight = pn[last_sent] - pn[sent_at(now-RTT)]
in_flight = pn[last_sent] - pn[sent_at((now-RTT)/2)]

Q4
What happens if there are two equidistant options?  This happens when
abs(n[last_received] & (2^(packet_number_size)-1) -
received_packet_number) == 2^(packet_number_size-1)  e.g., the last
received is 256 and the next one is an 8-bit 129.  (Points off for
looking at what Ian's code does.)

---

From: Ian Swett <[email-masked]>
Date: Thu, 10 Nov 2016 05:44:37 -0500

> endpoint to recover the wrong packet number.

Agreed, MUST here is completely unnecessary.  I think it's a reasonable
recommendation, however.

> At some point we had FEC.  FEC had a side-effect of limiting how often we
could change the packet number length to once per FEC group.  That and an
abundance of caution was how this was chosen.  We no longer have FEC, so
it's a matter of how cautious we want to be.

I will say that sometimes packets arrive more than one RTT out of
order(crazy, but true), but it's possible we don't care about that case.

> To be fully correct, this would require storing every previous packet
number received.  I think the larger concern is that if one or many packets
in the past were missing, you'd have to do trial decryption every time the
packet 2^(packet_number_size) greater was received, correct?  I believe not
doing trial decryption could end up with a stuck connection in worst case
scenarios.

> interoperability failure.)

Fair point, again the use of MUST on the decoding side seems strong.  Of
course, encoding the packet number is a MUST.

Sure, the receiver would definitely get lower bandwidth, but that would be
the tradeoff.

> in_flight = pn[last_sent] - pn[sent_at((now-RTT)/2)]

The TCP draft(https://tools.ietf.org/html/rfc5681) defines flight size,
which is typically known as inflight or inflight in my experience, but I
realize QUIC should have it's own definition, since there's no cumulative
acknowledgement point.

FLIGHT SIZE: The amount of data that has been sent but not yet
      cumulatively acknowledged.

I'll propose: The amount of data that has been sent but not yet
acknowledged or declared lost.

> looking at what Ian's code does.)
Well, the approach should be changed to a SHOULD from a MUST, so maybe it
doesn't matter :)

In seriousness, if one is using a 4x cushion, then this should never be a
problem, so I think either is fine.

---

From: Martin Thomson <[email-masked]>
Date: Thu, 10 Nov 2016 22:14:27 +1100

On 10 November 2016 at 21:44, Ian Swett <[email-masked]> wrote:
> To be fully correct, this would require storing every previous packet number
> received.  I think the larger concern is that if one or many packets in the
> past were missing, you'd have to do trial decryption every time the packet
> 2^(packet_number_size) greater was received, correct?

In our DTLS implementation, we track the last received packet and use
a bit vector to mark the N packets that precede it.  That was what I
was thinking here.  As long as N is greater than the number of packets
in flight in most cases, this should work.

Trial decryption isn't necessary, it just allows you to go even
further into the future if you want.  It lets you go further into the
past if you want to repair gaps a long way back or you don't track
received messages.

---

From: Ian Swett <[email-masked]>
Date: Thu, 10 Nov 2016 06:19:48 -0500

On Thu, Nov 10, 2016 at 6:14 AM, Martin Thomson <[email-masked]>
wrote:

> number

It isn't strictly necessary, but if I have a 100 packet gap sometime in the
past, then every time I receive a packet that lines up with that gap, I
would try to decrypt it as the old packet number, which would fail, and
then I'd either drop it or do trial decryption.  Dropping it seems very
problematic, as it creates 'echoes' of losses which could repeat
indefinitely.

Or possibly the above isn't what you had in mind?

---

From: Martin Thomson <[email-masked]>
Date: Thu, 10 Nov 2016 22:51:16 +1100

On 10 November 2016 at 22:19, Ian Swett <[email-masked]> wrote:
> would try to decrypt it as the old packet number, which would fail, and then
> I'd either drop it or do trial decryption.  Dropping it seems very

Ahh, so packet 1 is lost, but then packet 257 comes along as it
identified as slotting into that hole, forcing it to be dropped.  Even
if that was the very next packet.

The idea is bad because it effectively searches first in the range
(last-2^sz, last-1).  It commits to this range when there is packet
loss, leading to the problem you identified.  It can't be repaired
without trial decryption: the thing I was hoping to avoid :(.

---

From: Kyle Rose <[email-masked]>
Date: Sun, 13 Nov 2016 15:07:04 +0900

> acknowledged or declared lost.

Is "amount of data" the right way to phrase this? To avoid ambiguity in
reconstructing the (full) packet number, isn't the limit around the range
of packet numbers that have been unacked?

Given that a packet can be arbitrarily delayed, there's no way to guarantee
that a failed trial decryption based on the wrong reconstructed (full)
packet number won't ever happen; but with the right property around the
sender's behavior, I think you can limit a packet to a single decryption,
at which point it's either accepted or obsolete. The desired property seems
to be that the sender and receiver will not disagree on which (full) packet
number a partial* packet number represents when the corresponding packet
would not have already have been considered lost.

(*truncated? windowed? I'd like a term to make this more precise so
algorithms making use of either full or partial packet numbers are
unambiguous.)

Given the following:

n = packet_number_size
M = largest (full) packet number sent
L = largest acked (full) packet number from most recently-received ACK frame
O = receiver's largest-observed (full) packet number
R = half-size of reordering window (i.e., at any time, receiver will accept
packets with (full) packet number in interval (O-R, O+R))

Then:

Sender knows that L <= O <= M
=> Sender can choose a (full) packet number in interval [M+1, L+R) and know
that (if received timely) the receiver will be accept it: O will eventually
advance to at most L+R-1, at which point (full) packet numbers in the
interval (L-1, L+2R-1) will be accepted, which includes all of [M+1, L+R)
=> Max number of packets that can be safely sent until L advances is
L+R-(M+1) <= M+R-M-1 < R

If we set 2R = 2^{n-1}, then:

 * When O = L < M+1, the reordering window is (L-2^{n-2}, L+2^{n-2})
 * When O = L+R-1, this window is (L-1, L+2^{n-1}-1)
 * The union of these intervals is (L-2^{n-2}, L+2^{n-1}-1)

The size of this union is 2^{n-1}+2^{n-2}-1 < 2^n, so (full) packet numbers
can be unambiguously reconstructed from partial packet numbers mod 2^n if
they are within a 2^{n-1}-sized reordering window; and if they're not
within that window, the corresponding packets would have been thrown away
anyway. Assuming I haven't botched something someplace, I conclude two
things about this scheme:

(1) The number of packets in flight (actually max delta from
currently-known last acked) should be < 2^{n-2}.
(2) Only one decryption should be necessary, with one exception.

This scheme is not robust to jumps in O of R or more, as the receiver would
either correctly reconstruct the (full) packet number and throw away the
packet as too far in the future (which seems dumb?) or would reconstruct
the wrong (full) packet number and also throw away the packet. Some of
these cases (e.g., a flood of packets are sent and a few are received
wildly out of order) will correct themselves, but others seem unrecoverable.

In particular, a byzantine case is one in which a middlebox drops >= 2^n
packets: there is no way for the receiver to reconstruct the correct (full)
packet number without doing multiple (and potentially unbounded) trial
decryptions: is the right number O+2^n? Or O+2*2^n? O+3*2^n? Etc.

IMO at some point you have to throw up your hands in these cases, and
requiring multiple trial decryptions seems like a good place to draw the
line.

In the process of going through all of this I began to worry more and more
about the sender and receiver getting out of sync on (full) packet number
reconstruction in places where the (full) packet number isn't
authenticated, such as in ACK frames. Is it possible for the sender to
reconstruct the a different largest acked from what the receiver intended,
for instance? I don't think so, as the sender would presumably have stopped
sending packets if it hadn't received an ACK frame in a long time, but I am
starting to think there should be some proof (not necessarily in the draft,
just documented somewhere) that both endpoints are speaking in the same
subset of the packet number space.

Kyle