Subject: [quicwg/base-drafts] are flow control frames really idempotent? (#1612)

From: Subodh Iyengar <[email-masked]>
Date: Mon, 30 Jul 2018 20:17:20 -0700

we say that in the draft

"All QUIC frames are idempotent.  That is, a valid frame does not cause undesirable side effects or errors when received more than once"

However max stream data has one peculiar property, i.e. lets say a sender sends 4 packets:

packet 1:
max_data ->  value = 1000

packet 2:
max_data ->  value = 2000

packet 3:
max_data ->  value = 1000

packet 4:
max_data -> value = 200

Here the sender, either due to malice or a bug decides to send the same max data in 2 different packets.

Let's say no loss occurs and the receiver gets all the packets. Obviously the receiver could ignore the max data in packets 3 and 4, however a receiver who wants to help peers prevent flow control bugs from happening can know that the peer had sent packet 3 after packet 2 and had thus attempted to accidentally reduce the value. We currently do this in our implementation to help avoid nasty issues like this and has helped us detect bugs. However with some offline discussions people had mixed opinions about this one. One could say that the sentence about idempotence could warrant a receiver allowing this behavior, however what about packet 4 if the sender had clearly never sent the value 200 before?

-- 
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/1612

---

From: ianswett <[email-masked]>
Date: Mon, 30 Jul 2018 20:22:31 -0700

I think it's ok to close the connection or stream in this case, but I don't believe it should be mandated.  A MAY seems appropriate on the receiver side and a MUST on the sender side?

-- 
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/1612#issuecomment-409081761

---

From: Subodh Iyengar <[email-masked]>
Date: Mon, 30 Jul 2018 20:28:34 -0700

Ya I think a MAY should suffice on the receiver side and I would be very happy with a MUST on the sender, however the general sentence about all QUIC frames are idempotent might mislead people into thinking that they can send any frame at any time. Do you think that "a valid frame" covers this case?  That is after sending a higher max data frame lower max data frames become invalid.

-- 
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/1612#issuecomment-409082614

---

From: Marten Seemann <[email-masked]>
Date: Mon, 30 Jul 2018 20:36:20 -0700

I think the sequence of values sent in packets 1-4 should be valid, and that an implementation MUST NOT error when receiving these.

When retransmitting a packet, you can do two different optimisations:

1. you can update the offset in the MAX_DATA frame, and thereby save a few bytes that you'd otherwise spend on sending a new MAX_DATA frame.
2. you can retransmit the MAX_DATA frame as is, and instead keep track that packet X is a retransmission of packet Y. When receiving an ACK for X, you then know that Y doesn't need to be retransmitted (and vice versa).

According to my measurements, 2. is a much better optimisation than 1. However, it can lead to exactly the sequence that you described. 
It might be possible to combine 1. and 2., but this will create **a lot** of complexity: If the retransmission of a packet contains an updated MAX_DATA frame, you can't just cancel the retransmission for that packet if the original packet is acknowledged, since you need to make sure that the MAX_DATA containing the updated offset is delivered reliably.

I see little value in enforcing that peers implement optimisation 1., since the expected performance gains are minimal, while 2. offers a real benefit on lossy connections.

-- 
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/1612#issuecomment-409083746

---

From: Subodh Iyengar <[email-masked]>
Date: Mon, 30 Jul 2018 20:43:50 -0700

When you're doing 2 why would you not send the latest update?

We also do 2, but we send the latest update. We additionally keep track of the packet number of the last sent max data per stream and per conn, that way we know when we get an ack for X we know that we still have a max data pending. It's not super complex :)

-- 
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/1612#issuecomment-409084763

---

From: Martin Thomson <[email-masked]>
Date: Mon, 30 Jul 2018 20:57:42 -0700

So this was opened and closed already in #447, though there wasn't a whole lot of discussion and the issue was closed with no action.

The action that @marten-seemann suggests is slightly bad - retransmitting packets is rarely the best choice from a correctness perspective - but the conclusion from the other issue was that there was little point in allowing endpoints to police continuous increases to limits.

Note that this advice would also need to apply to stream limits.

(To answer the question in the issue: Yes, these packets are still idempotent - the definition of idempotency has to allow for the state of the world to change in a way that changes the result the action when attempted again.  For example. `GET /foo` is idempotent, but if there is a `DELETE /foo` that happens, the result of another `GET /foo` will be different.)

-- 
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/1612#issuecomment-409086659

---

From: Marten Seemann <[email-masked]>
Date: Mon, 30 Jul 2018 21:16:25 -0700

I didn't say it's impossible, but it would add a lot of code for saving a tiny number of bytes, occasionally.
I don't think we should force implementations to perform an optimisation when the performance benefits are probably barely measurable at all.

-- 
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/1612#issuecomment-409089185

---

From: Subodh Iyengar <[email-masked]>
Date: Mon, 30 Jul 2018 21:29:45 -0700

@marten the issue isn’t about saving bytes or an optimization. The issue is a peer being able to distinguish a correct  implementation from an incorrect one. Correct implementations might be very cognizant of this behavior and do it explicitly, however allowing this makes it much harder for a peer to give early feedback to peers that did this accidentally due to another bug

-- 
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/1612#issuecomment-409090907

---

From: Subodh Iyengar <[email-masked]>
Date: Mon, 30 Jul 2018 21:32:51 -0700

Thanks for the pointer @martinthompson and the clarification about idempotence.

this would definitely apply to any limit frame

-- 
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/1612#issuecomment-409091394

---

From: MikkelFJ <[email-masked]>
Date: Tue, 31 Jul 2018 09:22:36 +0000 (UTC)

I think it is pretty clear that later recieved lower numbered limits should be ignored or result in a protocol error - or ignore if the reciever cannot be bothered to check.

If it is explicitly required that limits are increased monotonically, it is protocol error, otherwise it is a ignore.

>From a quick read over the spec, I can't see that there are rules thay enforce that limits cannot be reduced sender size?

While it makes sense to transmit the largest limit on retransmission there are cases where this is not ideal because it can require synchronization. The same applies to packet numbers which must increase, but the more values that must be in sync, the harder it becomes to do parallel processing or to have separate responsibilities.

As to being helpful - I don't think the receiver should fix sender bugs - the most helpful thing is a hard protocol error, log output and a friendly email to the responsible dev team. If bugs starts to get worked around, ossificiation will ensue at scale. In this particular case it may not even be a bug, but a deliberate synchronizatin artefact.

-- 
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/1612#issuecomment-409155257

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 31 Jul 2018 03:36:00 -0700

@marten-seemann 
> I didn't say it's impossible, but it would add a lot of code for saving a tiny number of bytes, occasionally.

FWIW, my understanding is it's actually simple to implement the optimal way. What you would do is:
* transmit the maximum when `max(acked_max, inflight_max)` is below the threshold
* when receiving an ack for the max frame, update the `acked_max` and `inflight_max`
* when deeming a packet that contained the max frame as lost, reset `inflight_max` to `acked_max` if the number of max frames in flight is zero, otherwise you leave `inflight_max` as-is. Then, you check if transmission of the maximum is necessary by referring to the rule above

This strategy works well in QUIC v1, because packets are deemed lost in the order they are sent, and there is a guarantee in the logic that packets that are sent later contain a equal-to or greater maximum. The logic is not "perfect" when multipath is involved, though I would assume that it would work well enough in practice.

Regarding the issue, I am fine with allowing receivers to raise protocol error when they see the issue. I would oppose to making that a MUST 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/1612#issuecomment-409175332

---

From: Kazuho Oku <[email-masked]>
Date: Tue, 31 Jul 2018 03:53:05 -0700

> Regarding the issue, I am fine with allowing receivers to raise protocol error when they see the issue. I would oppose to making that a MUST though.

Let me retract my this comment. My understanding is that some existing QUIC implementations simply retransmit a packet (by re-encrypting it using a new PN) when it is deemed lost. I think that such implementations should be allowed to exist.

Considering that, I would oppose to even allowing implementations to raise a protocol error when they observe a smaller maximum value in a packet that has a greater PN.

-- 
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/1612#issuecomment-409179355

---

From: MikkelFJ <[email-masked]>
Date: Tue, 31 Jul 2018 04:10:39 -0700

A protocol error would also go against the idempotency principle and unnecessarily tie frames to packet numbers. If there is implied ordering, the ordering should not originate from PN (possibly outside of handshake?).

-- 
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/1612#issuecomment-409183549

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 31 Jul 2018 12:31:32 +0000 (UTC)

@siyengar writes:
> a receiver who wants to help peers prevent flow control bugs from happening

One could detect _potential_ bugs in the peer in many other cases.  I vote against mandating such error detection at the protocol level.

@kazuho writes:
> some existing QUIC implementations simply retransmit a packet (by re-encrypting it using a new PN) when it is deemed lost. I think that such implementations should be allowed to exist.

This is true. This is what the LiteSpeed implementation does with GQUIC's _WINDOW_UPDATE_ frames. The smaller values are [ignored](https://github.com/litespeedtech/lsquic-client/blob/04468d215dc184ae64e7aa1d0e940da50c724e2f/src/liblsquic/lsquic_stream.c#L1855). It is more expedient (and is cheaper) to discard lower values on receipt rather than update or remove the old values on retransmit.

Yes, let us exist!

-- 
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/1612#issuecomment-409203779

---

From: Subodh Iyengar <[email-masked]>
Date: Tue, 31 Jul 2018 15:00:53 +0000 (UTC)

@kazuho I don't think we should make it a MUST on the receiver, just a MAY and maybe a MUST on the sender. It is already a MUST, i.e. you MUST not reduce the flow control window.

@dtikhonov of course other bugs are possible, however this is a pretty major one if the sender actually tried to reduce the flow control. Without enforcement the MUST of "sender MUST not reduce the window" is almost impossible to enforce. Ignoring it will just kick the can down the road with such issues only getting discovered way after deployment vs at dev time. 

While I think it's fine to allow senders to copy over the packets that they have sent before, I don't think that should be a goal of QUIC. That is senders that are doing this should be aware of what they are signing for and take appropriate precautions. There are efficient ways to implement copying packets but updating max data. Preventing the efficient enforcement of a clear MUST would be very sad.

-- 
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/1612#issuecomment-409251712

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 31 Jul 2018 08:15:37 -0700

@siyengar, where do you see "sender MUST not reduce the window?"  I cannot find it in the drafts.

-- 
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/1612#issuecomment-409257267

---

From: Subodh Iyengar <[email-masked]>
Date: Tue, 31 Jul 2018 15:27:44 +0000 (UTC)

@dtikhonov sorry it's not those exact words, here's the exact wording: https://quicwg.org/base-drafts/draft-ietf-quic-transport.html#flow-control

> A receiver MUST NOT renege on an advertisement; that is, once a receiver advertises an offset, it MUST NOT subsequently advertise a smaller offset. A sender could receive MAX_DATA or MAX_STREAM_DATA frames out of order; a sender MUST therefore ignore any flow control offset that does not move the window forward.

the operative words being "MUST NOT subsequently advertise a smaller offset"

-- 
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/1612#issuecomment-409261863

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 31 Jul 2018 08:56:00 -0700

I see what you mean, @siyengar.  (Near-identical wording is used to describe _MAX_STREAM_ID_ behavior.)  If we keep the _MUST NOT renege_, then the receiver SHOULD check for this error.  As you pointed out above, it is easily done.

>From the implementation perspective, it is quite doable as well.  These frame types are to be added to the list of frames to be deleted from a packet upon retransmission (e.g. _ACK_ frame).  Erasure of these frames would trigger generation of new _MAX_DATA_ (and friends) frames.

On the other hand, I like the simplicity of ignoring lower values -- but that's just my pragmatic side...

-- 
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/1612#issuecomment-409272439

---

From: Christian Huitema <[email-masked]>
Date: Tue, 31 Jul 2018 09:21:03 -0700

I think the current state is just fine: the receiver just ignores values lower than the highest advertised max data, etc. That means that, for the sender, attempting to send a lower value would just be a noop.

Triggering errors is problematic. Not just because of retransmission, which is indeed easy to fix, but mostly because of reordering. Take the extreme case of an implementation that sends max data with every ack. Someof those are bound to arrive out of order. Do you really want to tear down the connection at that point?

-- 
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/1612#issuecomment-409281058

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 31 Jul 2018 09:27:12 -0700

@huitema, the reordering can be handled by keeping the packet number along with the maximum received value, as @siyengar [described above](https://github.com/quicwg/base-drafts/issues/1612#issuecomment-409084763).

-- 
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/1612#issuecomment-409282950

---

From: Christian Huitema <[email-masked]>
Date: Tue, 31 Jul 2018 09:31:01 -0700

Sure. But that's just additional complexity, and I don't think it is justified.

-- 
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/1612#issuecomment-409284169

---

From: MikkelFJ <[email-masked]>
Date: Tue, 31 Jul 2018 16:33:53 +0000 (UTC)

@siyengar 

> @mikkelfj what do you mean by the ordering not coming from packet number?

I mean that the general principle of QUIC is for packets to vessels of frames that do not carry any semantic such as ordering, except for the connection context itself. I am not saying there is other ordering for MAX_DATA, only that when there is ordering, it should not, and generally does not, derive from packet numbers. For example, streams are ordered by stream offsets, and streams are ordered by stream ID's. Implying a problem because of ordering related to packet numbers is fundamentally against this design.

-- 
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/1612#issuecomment-409284998

---

From: MikkelFJ <[email-masked]>
Date: Tue, 31 Jul 2018 09:46:21 -0700

If frames are seen as a stream, reordering can legally happen before packetization, for example when concurrent packet transmitters draws from a single frame stream. In this context, packet numbers cannot conlude anything.

On reneg of limits: there is a difference between a lower limit as lower bound, and in fact advertising a lower limit. The former ought to be valid, the latter would lead to all sorts of problems.

-- 
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/1612#issuecomment-409288947

---

From: Subodh Iyengar <[email-masked]>
Date: Tue, 31 Jul 2018 10:08:43 -0700

@huitema Not sure I understand, do you mean verifying a MUST behavior is not justfied? In my reading of the clause, an implementation that checks for whether the peer is sending lower values is totally allowed in the current draft if it knows that the peer has sent this subsequently. This is because my reading of the MUST check. 

I think a receiver should be allowed to verify that this happens, it is just not required to do so, and we should also allow for implementations that don't verify this check. So if an implementation does send a frame pattern like this, it should be aware that it will not interoperate against some implementations. 

If we want to change this, then you might want propose a change, otherwise I think the current draft allows receivers to verify the MUST.

@mikkelfj was there any discussion about this? My understanding is that we have always implied that packet number == ordering. All the loss recovery mechanisms assume this. If this is not true we need to have a deeper conversation :) Also I don't agree with the analogy of frames as streams.

-- 
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/1612#issuecomment-409296493

---

From: Marten Seemann <[email-masked]>
Date: Tue, 31 Jul 2018 17:37:27 +0000 (UTC)

> A receiver MUST NOT renege on an advertisement; that is, once a receiver advertises an offset, it MUST NOT subsequently advertise a smaller offset. A sender could receive MAX_DATA or MAX_STREAM_DAT…

This sentence is maximally confusing. You're not allowed to advertise a smaller offset, but then the peer is not allowed to check for this violation either. If I interpret this correctly,  Chrome, Litespeed and quic-go are violation the spec by implementing a slightly less than optimal retransmission strategy, and mvfst is violating the spec by performing a check of the flow control offset.
We should definitely make this wording clear, one way or the other.

I understand that optimisations are fun to implement, and once you've done it they seem trivial and obvious, but we shouldn't require an implementation to optimise anything. Retransmitting every packet as it is (just repacking it with a different packet number) is the most basic retransmission strategy that allows for a functional implementation of the protocol, and I think an implementation should be allowed to do this.

-- 
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/1612#issuecomment-409305491

---

From: MartinThompson <[email-masked]>
Date: Tue, 31 Jul 2018 10:39:38 -0700

I think you guys have tagged the wrong Martin Thompson. You should double check and re-tag the correct one.

Regards!
-martin

> On Jul 31, 2018, at 10:37 AM, Marten Seemann <[email-masked]> wrote:
> 
> —
> You are receiving this because you were mentioned.
> Reply to this email directly, view it on GitHub <https://github.com/quicwg/base-drafts/issues/1612#issuecomment-409305491>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AKJz01HO0JVyi1Vvrh8zTD4Szvsvj1nvks5uMJXXgaJpZM4VniAh>.
> 

-- 
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/1612#issuecomment-409306120

---

From: Dmitri Tikhonov <[email-masked]>
Date: Tue, 31 Jul 2018 17:42:03 +0000 (UTC)

> I think a receiver should be allowed to verify that this happens, it is just not required to do so, and we should also allow for implementations that don't verify this check. So if an implementatio…

In practice, it will mean that all sender implementations will make sure not to send such frame pattern.  When I see that something _MAY result in an error_ (we have some other instances in the other QUIC drafts), it always strikes me as odd:  Surely, if something MAY result in an error, it forces the peer's hand; it is effectively a MUST.

-- 
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/1612#issuecomment-409306881

---

From: Martin Thomson <[email-masked]>
Date: Tue, 31 Jul 2018 16:52:31 -0700

Yes, we generally couple a *MAY result in an error* text with a MUST for the peer (because a MAY is always a MUST in the sense that it mandates tolerance).  In this case, we're saying MUST NOT go backwards, coupled with a MUST NOT generate an error if the peer doesn't comply.  That was explicitly to enable the sort of thing that @marten-seemann and @dtikhonov do, even if that is maybe slightly objectionable to the purists.

I think that the fix is as follows:

> A receiver cannot renege on an advertisement; that is, once a receiver advertises an offset, advertising a smaller offset has no effect. A sender MUST ignore any flow control offset that does not increase maximum (stream) data.

Would that work for people?

-- 
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/1612#issuecomment-409404254

---

From: Christian Huitema <[email-masked]>
Date: Tue, 31 Jul 2018 17:11:31 -0700

Works for 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/1612#issuecomment-409407355

---

From: Subodh Iyengar <[email-masked]>
Date: Tue, 31 Jul 2018 19:30:17 -0700

While I'm not a huge fan of this change, it looks like I'm in the minority here, so it's fine with 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/1612#issuecomment-409428946

---

From: ekr <[email-masked]>
Date: Tue, 31 Jul 2018 19:42:00 -0700

I'm not sure @siyengar is in the minority here. This seems like a pretty
easy implementation error to make, and the check he proposes would allow
you to detect it in practice. It's not really clear to me what the
significant optimization is that relaxing this enables.

On Tue, Jul 31, 2018 at 7:30 PM, Subodh Iyengar <[email-masked]>
wrote:

> Reply to this email directly, view it on GitHub
> <https://github.com/quicwg/base-drafts/issues/1612#issuecomment-409428946>,
> or mute the thread
> <https://github.com/notifications/unsubscribe-auth/ABD1oeDLKluYmVqJ0iPL_ff7M8iwEL8xks5uMRK4gaJpZM4VniAh>
> .
>

-- 
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/1612#issuecomment-409430942

---

From: ianswett <[email-masked]>
Date: Tue, 31 Jul 2018 21:52:29 -0700

I'm torn because I don't think retransmitting frames is right in this case, but on the other hand, I'm not sure increasing packet numbers always indicate one cannot send old frames.  With multipath, this problem may become intractable in practice, so I think the PR is an improvement.

-- 
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/1612#issuecomment-409448726

---

From: Martin Thomson <[email-masked]>
Date: Tue, 31 Jul 2018 22:45:28 -0700

Closed #1612 via #1622.

-- 
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/1612#event-1764352588