Subject: [quicwg/base-drafts] Allow smaller packet number representations (#323)

From: Martin Thomson <[email-masked]>
Date: Fri, 17 Feb 2017 14:02:07 -0800

The text currently mandates (MUST!) a 4 times safety margin against reordering when picking the packet number size.  This is purely a safety margin feature, so mandating a value isn't justified.

An implementation could, though perhaps it is unwise, use a much smaller packet number than this.  The risk is that there is reordering greater than 2^size and the packets are delivered but cannot be recovered at the receiver.  That's terrible, it will trigger loss recovery and send bad signals.  However, the protocol doesn't actually break.

At a minimum, we should make this a recommendation.  Setting a mandatory floor on the value might be reasonable, but I'd be reluctant to do that unless it was pretty low, or if the value were different for different packet number sizes (smaller margins are probably more justifiable for larger packet number encodings).

Ideally, we should science this and try to measure probabilities of reordering.  Ideally reordering probability as a function of outstanding packets.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/323

---

From: Ryan Hamilton <[email-masked]>
Date: Fri, 17 Feb 2017 15:26:37 -0800

This makes sense to me. Of course, it's worth pointing out that we need to consider loss in addition to reordering. For example, let's say that a sender *always* sent 1 byte packet numbers. If it happened that 256 consecutive packets were lost (I realize this is not typical, but long fat pipe :>) then the 1 byte number for the 257th packet would be interpreted by the receiver as the same as the first lost packet and decryption would fail. Thus, If the sender never increased the size the connection would fail. (You are probably already aware of this, and I'm probably being utterly redundant. If so, I'm sorry!)

So I think we need a MUST of some sort in this area, though I'm not exactly sure what it should say. I am sure it can be much looser than the 4x safety margin, though.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/323#issuecomment-280794569

---

From: janaiyengar <[email-masked]>
Date: Fri, 17 Feb 2017 18:19:21 -0800

The loss scenario is the more interesting one to consider than the simple reordering one, and you don't have to lose all 256 for this to be a problem. You just need a send-range + receive-range that exceeds the sequence space, and that can happen (i) when the first packet in your scenario is lost, and (ii) the retransmission ends up with the same short-form sequence number. I agree that there is a risk of being stuck. 

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/323#issuecomment-280814107

---

From: ianswett <[email-masked]>
Date: Sat, 18 Feb 2017 14:33:43 -0800

Jana and I had a few conversations about this in Seoul.  

One important point is that in QUIC, if the packet number is decoded incorrectly, decryption fails and the packet is dropped.  In TCP, the stream is corrupted and you're in a much worse place.  

Ryan's point is completely correct, but the sender always has the option of increasing the packet number length, so if they implement the spec correctly, the connection should never fail.

So I think we want text like:
"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.  The sender SHOULD use a packet number large enough to fit all packets it expects to have in flight simultaneously with the current packet into half the range in order to tolerate arbitrary reordering or loss of any packet in flight."

Jana's point about retransmissions and not being able to increase the packet number length (without splitting frames) is completely valid, but that's an implementation problem, as we've already decided implementations could split stream frames.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/323#issuecomment-280880278

---

From: Ryan Hamilton <[email-masked]>
Date: Sat, 18 Feb 2017 15:03:27 -0800

Your proposed language sounds good to me!

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/323#issuecomment-280881868

---

From: Martin Thomson <[email-masked]>
Date: Sun, 19 Feb 2017 22:44:17 -0800

I'd like to go through this a little more thoroughly, making sure that I understand the principles driving it.  I think that there are just two problems that we have to deal with: gaps and reordering.

I've finally had some quiet time to think this over.  It's over-engineering time.  Sorry about the length of this, but this has been bugging me for some time.

## Gaps

The other side might have a large gap.  If this happens, you don't want them confusing packet `N` with `N + 2^(size-1)`.  

BTW, I hope that this never happens, losing `2^(size-1)` packets is pretty serious, even for 8-bit packet numbers.

The first part of Ian's proposal deals with this: if you have seen an acknowledgment for packet `N`, then you can send packets up to `N + 2^(size-1)` and be sure that the receiver will not mistake them for earlier packets.  Ian is right in picking MUST here, anything else is inviting complete lack of synchronization.

## Reordering

Reordering turns out to be far more complex. 

Here the concern is that a is delayed so far that it drops behind a packet that was sent after it, or maybe many packets.  The failure case is where packet `N` arrives after packet `N + 2^(size-1) - 1`.  Packet `N` and the expected packet (`N + 2^(size-1)`) are interchangeable, but packet `N` will simply fail to be decrypted and will be dropped.

One model that we might use to analyze this selects a packet size that results in packet `N` being dropped on arrival only when that reordering would otherwise result in the [packet being declared lost](https://quicwg.github.io/base-drafts/draft-ietf-quic-recovery.html#detecting-lost-packets).  As it turns out, loss recovery treats packets as lost so aggressively that this basically never happens.  In the time-based model, loss is is declared after a mere eighth of the RTT (kTimeReorderThreshold = 1/8); when counting packets, just three packets of reordering is all that we see before a packet is declared lost (kReorderingThreshold = 3).  That obviously favors retransmission pretty heavily, which is sensible, but it means that any window we would need for reordering based on that model is much smaller than the window needed for gaps.

The absolute minimum size we already have for dealing with gaps is either 1 RTT worth of packets in time (8 times larger than we'd need for reordering), or 128 in packets (42 times more).

That says to me that "tolerate arbitrary reordering or loss of any packet in flight" isn't a goal that this can achieve without a pretty significant change to loss recovery.

A better model recognizes the difference between detected and actual loss.  In that model, a reordered packet that has its packet number recovered is far more useful to the receiver, even if it has to be retransmitted.  That suggests that there is value in a larger packet number encoding, even if packets end up being marked as lost.

If recognizing the difference between detected and actual loss is the goal then "in flight" or outstanding isn't the right basis upon which to choose the size.  Anything loss recovery tells us doesn't help because we've already established that the packet is being declared lost after the tiniest bit of reordering.  What you want to do is avoid actually needing the retransmission, even if you have to waste the bandwidth on sending a second copy of the data.  In choosing an encoding size, the only factor you want to consider is how much reordering you are *really* getting (or, how much reordering the other side is getting).

(On this point, real data would allow us to learn what a sensible global value might be.  It might be based on RTT or BDP or something if we were getting fancy.  That's about the best we can expect to have.)

If the intent is to use the oldest outstanding packet as a proxy for that, then it's not really that much different to the gaps thing.  It's only adding an eighth to the number of packets that are considered in scope, up to three extra packets.

Better to simply state two things: reordering is more likely to result in packets being declared lost than it is in packets actually being unusable, even with small packets; and, suggest using a larger packet number as it increases the chances that retransmission won't be needed for a badly reordered packet.  No "SHOULD" necessary I think.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/323#issuecomment-281000358

---

From: Brian Trammell <[email-masked]>
Date: Mon, 20 Feb 2017 03:17:39 -0800

On gaps, another +1 to Ian's proposed language. 

As for reordering, the amount of reordering you can experience is a function of your inflight window, as is the packet size selection, so this shouldn't have any impact on packet number size selection, unless I'm missing something basic. A packet that arrives after it was already retransmitted and acknowledged can simply be dropped; there's nothing you can do to increase its utility.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/323#issuecomment-281053248

---

From: Dragana Damjanovic <[email-masked]>
Date: Mon, 20 Feb 2017 06:51:11 -0800

Just one note: The packet number size influence the max size of a frame that can be sent. So if a packet (let's say containing only one frame that take the full max size of a packet) gets lost. And in between sending the packet and retransmitting the frame the packet number size needs to be increased, it would be good to be able to retransmit that frame with the smaller packet number, otherwise you will need an extra packet to retransmit only 1 byte of data.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/323#issuecomment-281098594

---

From: mirjak <[email-masked]>
Date: Mon, 20 Feb 2017 07:36:02 -0800

@ddragana I don't really see this problem; I guess you'd only increase the packet number size if you have more data to send. First the retransmitted frame goes in a new packet that probably has a packet number that needs the larger size. And second if might just put the new 1 byte frame into a packet with other frames (assuming you have more data to send).

Regarding packets that arrive late and have already been retransmitted. I guess the question is how to distinguish a very late packet from a new one if the packet number wrapped around in between. I guess that is now kind of the same problem we have with TCP and retransmissions (hopefully this just happens much less often). If we decide to have a packet number echo, we could use that to distinguish old and new packets...

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/323#issuecomment-281110015

---

From: Martin Thomson <[email-masked]>
Date: Mon, 20 Feb 2017 15:30:19 -0800

@britram,

> the amount of reordering you can experience is a function of your inflight window

That doesn't match the definition we have for "in flight" (either not acknowledged or declared lost).  If you consider not acknowledged as potentials, then that works, but then you are probably considering packets that are truly lost in the calculation and it gets sticky.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/323#issuecomment-281205562

---

From: Martin Thomson <[email-masked]>
Date: Mon, 20 Feb 2017 15:55:42 -0800

@ddragana, does it help if you stop considering this as retransmission of the *frame* and just a repair of lost *data*?  If you lose a packet, then the frames it contains don't need to be retransmitted, it's the data that needs to be assembled into new frames in new packets.

I realize that this changes the dynamics significantly.  You decide that you need a new packet, then you look for things to stuff into it.  But I think that works better overall.  If you lost a packet that had one STREAM frame, you might find that you have an ACK to send, or a few WINDOW_UPDATEs.  All of those things are reasons that you need to send less than the entirety of what was lost.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/323#issuecomment-281208535

---

From: Dragana Damjanovic <[email-masked]>
Date: Tue, 21 Feb 2017 03:43:58 -0800

I do not see it as a big problem, I wrote it just as a note that that can happened and that we have a small overhead of sending a frame header for only one byte of data.
Form implementation perspective the things should be looked separately: we have data streams and not queued frames(or something). 
This was just a note, not a problem. 

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/323#issuecomment-281320084