Subject: [quicwg/base-drafts] active_connection_id_limit interacts poorly with Retire Prior To (#3193)

From: Marten Seemann <[email-masked]>
Date: Tue, 05 Nov 2019 21:24:38 -0800

The `active_connection_id_limit` parameters communicates the maximum number of connection IDs sent in NEW_CONNECTION_ID frames that an endpoint is willing to store. This value is only advisory though, there's nothing stopping an implementation from storing more CIDs than this limit, and the peer is allowed to send more CIDs than this limit:
> An endpoint SHOULD NOT provide more connection IDs than the peer’s limit.

We don't specify any behavior in the case the peer provides more CIDs than this limit, but since retiring a CID asks the peer to provide a new CID, it seems like the reasonable thing to do would be to silently drop the CID on the floor:
> Sending a RETIRE_CONNECTION_ID frame indicates that the connection ID will not be used again and requests that the peer replace it with a new connection ID using a NEW_CONNECTION_ID frame.

This means that a peer cannot fulfill its duty of retiring those discarded connection IDs when receiving a NEW_CONNECTION_ID frame with Retire Prior To set:
>  Upon receipt, the peer MUST retire the corresponding connection IDs and send corresponding RETIRE_CONNECTION_ID frames.

This, however, is not guaranteed, either. A peer might decide to send a RETIRE_CONNECTION_ID frame for a sequence number that it already forgot.

Furthermore, depending on how implementations decide with all these uncertainties, one could end up in a situation where an endpoint only has a single active CID available, but its peer assumes that it is still keeping track of `active_connection_id_limit` CIDs and thus won't provide any new CIDs. In this situation, the endpoint won't be able to initiate or respond to a connection migration any more, leading to a failure of the connection.

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

---

From: Eric Kinnear <[email-masked]>
Date: Wed, 06 Nov 2019 00:17:50 -0800

>  it seems like the reasonable thing to do would be to silently drop the CID on the floor

That was the previous recommendation if the peer provided too many CIDs and you didn't want to maintain any more, and I think that still applies if the peer doesn't respect the TP.

For context, this came up in several issues, the TP came in via #1994, with the [conclusion from Tokyo](https://github.com/quicwg/base-drafts/issues/1994#issuecomment-458820197) being that it would be advisory only (hence the SHOULD).

PR #1998 actually made the change which included that SHOULD, and also resolved the concerns from #2403. #2428 helped to clarify some rate-limiting around how quickly you should cycle through CIDs.

All that is to say, if you want to use the limit and explicitly communicate it with the TP, then you SHOULD do that. Everyone SHOULD do that.

If not, or if your peer doesn't respect it, you can always dump those extra CIDs on the floor, with all the potential for running out that comes from taking that action. In this case, you end up maintaining as many as you wanted, probably the same value that you sent in the TP that the other side ignored...

If/when the peer sends RetirePriorTo and requests that you retire them, you retire the ones you haven't yet retired and still know about. Generally, that means that you get a replacement for those, so now you still have `active_connection_id_limit` CIDs. (Side note: The place this gets messy is if the peer suddenly decides to respect the value you put in the TP and doesn't replace them. This has always been a potential consequence of dropping them, though.)

For the ones that you discarded, the peer should discard those 3PTO after it sent RetirePriorTo. From [Section 5.1.2](https://quicwg.org/base-drafts/draft-ietf-quic-transport.html#retiring-cids):
```
An endpoint MAY discard a connection ID for which retirement has been requested 
once an interval of no less than 3 PTO has elapsed since an acknowledgement is 
received for the NEW_CONNECTION_ID frame requesting that retirement. Until 
then, the endpoint SHOULD be prepared to receive packets that contain the 
connection ID that it has requested be retired. Subsequent incoming packets 
using that connection ID could elicit a response with the corresponding 
stateless reset token.
```

So the peer that requested retirement can discard any state about them, and you're back to having everyone on the same page about how many are outstanding. 

That generally seems sufficient, although it would be great to cover another scenario or add some text that could be added to explain this better? If the issuing endpoint doesn't use RetirePriorTo then you're fine holding as many as you wanted to maintain forever. If they do use RetirePriorTo, then you're reset back to a good state.

And if you ever get RetirePriorTo indicating an old value, you're also happy since you don't need to do anything.

-- 
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/3193#issuecomment-550197395

---

From: Marten Seemann <[email-masked]>
Date: Wed, 06 Nov 2019 01:49:24 -0800

Dropping connection IDs worked out fine before we introduced the Retire Prior To field. We added that field in #2769, which was merged in July (about half a year after our discussion in Tokyo and the claryfing PRs).

> If/when the peer sends RetirePriorTo and requests that you retire them, you retire the ones you haven't yet retired and still know about.

That's not what the spec says (but maybe what the spec intends to say?). If this was the only issue, we could probably easily resolve this by changing the wording to something like "MUST retire the corresponding connection IDs that it still remembers" or so.

> Generally, that means that you get a replacement for those, so now you still have active_connection_id_limit CIDs. 

That might or might not happen. It all depends on the peer's assumption of what you did: Does it assume that you dropped connection IDs (if so, which ones?)? Does it assume that you actually enforced the limit that you announced in the TP by dropping all CIDs in excess of it?
The situation gets even worse when you assume that  a RETIRE_CONNECTION_ID frame was in flight just when the endpoint provided the new CIDs. In this situation, there's no race-condition-free view of how many CIDs the peer was actually storing, so it's not possible to know how many of the new CIDs were actually stored and how many of them might have been dropped.

-- 
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/3193#issuecomment-550232159

---

From: Kazuho Oku <[email-masked]>
Date: Wed, 06 Nov 2019 05:13:02 -0800

I think the model that @erickinnear's has described is accurate.

At the same time, it seems alarming to me  that we have failed to incorporate that model into the text.

and FWIW also:
> Connection IDs that are issued and not retired are considered active; any active connection ID can be used.

that both assume that all connections IDs are expected to be retired. But as @erickinnear points out, when the issuer provides more than what `active_connection_id_limit` recommends, those connection IDs are not expected to be retired.

I'd like to point out that the way we control the active CIDs sticks out from other "crediting schemes". For all other crediting schemes (i.e. MAX_DATA, MAX_STREAMS, MAX_STREAM_DATA), there is a hard limit. It is a protocol violation when the sender exceeds the allowed maximum. It is only for this active_connection_id_limit - RETIRE_CONNECTION_ID pair that we do not enforce the sender adhering the limit.

Considering these aspects, and the fact that implementors are complaining about the complexity caused by "SHOULD NOT," I think it's worth considering changing the "SHOULD NOT" of "an endpoint SHOULD NOT provide more connection IDs than the peer’s limit" to "MUST NOT."

The counterargument might be that it's an additional complexity; but I doubt if it's that important, compared to the importance of resolving the confusion that we have now.

As @erickinnear have stated, the issuer is excepted to stick to providing *N* active CIDs, where N is a constant throughout the lifetime of a connection. No other approach works. So the *complexity* that is to be added by changing the "SHOULD NOT" to "MUST NOT" is that the issuer would be required to set N to no greater than the value of "active_connection_id_limit" provided by the peer.

I think we can pay that cost for buying a consistent design (that avoids the confusion).

-- 
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/3193#issuecomment-550302894

---

From: Marten Seemann <[email-masked]>
Date: Wed, 06 Nov 2019 05:42:31 -0800

It seems like the problem we're facing here is that 3 things can happen with a new CID:
1. It is stored for later use.
2. It is retired via a RETIRE_CONNECTION_ID frame.
3. It is silently dropped.

For the endpoint providing the CIDs, 1. and 3. are indistinguishable, which might lead to a mismatching view of how many CIDs are actually active. In the extreme case, this mismatch might mean that an endpoint believes that its peer has enough CIDs available, while it actually doesn't have any CIDs besides the one it is currently using, which would then make it impossible to migrate.
At the very least, the indistinguishability between 1. and 3. leads to some non-trivial reasoning about what the peer might or might not have done, if you provide more CIDs than the peer advertised at any point in the connection.

I agree with @kazuho that changing the "SHOULD NOT" to a "MUST NOT" would lead to a significant simplification here, since it would eliminate 3. from the list. With that change, a newly provided CID is active until it is retired. 

Furthermore, I don't think that there's any additional complexity here. On the receiver side, you'll need some logic to protect against a peer that is sending too many CIDs anyway. On the sender side, limiting the number to a constant value seems a lot easier than reasoning about which CIDs might have been dropped.

-- 
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/3193#issuecomment-550313763

---

From: ianswett <[email-masked]>
Date: Wed, 06 Nov 2019 05:53:50 -0800

Changing to "MUST NOT" SGTM

-- 
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/3193#issuecomment-550318541

---

From: Nick Banks <[email-masked]>
Date: Wed, 06 Nov 2019 06:36:40 -0800

I also agree that changing to a "MUST NOT" seems reasonable.

-- 
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/3193#issuecomment-550337493

---

From: Mike Bishop <[email-masked]>
Date: Wed, 06 Nov 2019 11:36:22 -0800

I think a MUST NOT is reasonable; there was considerable pushback in Tokyo for reasons I don't remember clearly.  I don't think you can get out of sync provided the TP is at least 2.

The other possibility, as an implementation, is to track which IDs you've retired/forgotten.  Obviously, the point of not keeping all the CIDs is to reduce the memory consumption and this still requires keeping some memory.  But it's worth pointing out that you don't actually need to have the CID in hand in order to promise you'll never use it again.

For that matter, a naive implementation that wants to save memory at the cost of bytes _could_ retire every CID sequence number up to RPT upon receipt of an increase RPT value, whether it has previously retired it or not.

-- 
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/3193#issuecomment-550467125

---

From: Eric Kinnear <[email-masked]>
Date: Wed, 06 Nov 2019 18:11:06 -0800

I definitely agree that it could cut down a lot of complexity to change from SHOULD NOT -> MUST NOT, although we probably should check the minutes from Tokyo about why we didn't want that at the time.

@marten-seemann, for:
> it's not possible to know how many of the new CIDs were actually stored and how many of them might have been dropped.
I can see where it might be irritating to not know a precise count here, but I'm not sure the two sides actually need to be in sync about that. 

@MikeBishop's point about being able to retire CIDs that you've forgotten is well taken, although it does run the risk that you'll get a replacement (although maybe you drop that too?).

I think @kazuho's argument that changing to a MUST NOT would bring us in line with the other crediting schemes makes a lot of sense, and it would bring us to a much nicer interaction model -- you ask for whatever you want, the peer gives that many to you. (Can they still give you fewer? I think the answer has to be yes, if it's costly to generate and maintain, then the issuer should control that.)

I think it would drastically simplify if we made this MUST NOT. Happy to send a PR for that.
Do we want a protocol violation if exceeded? We will likely need #3197 too along with 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/3193#issuecomment-550587584

---

From: Mike Bishop <[email-masked]>
Date: Thu, 07 Nov 2019 11:45:44 -0800

Another potential pitfall of "MUST NOT":  Assume you've filled the peer's quota, but now need to revoke all prior CIDs and start a new generation.  You have to send at least one NCID to carry the RPT and give the client something in the new generation of CIDs.  Depending on the client's implementation, the limit might be exceeded during the processing of the frame.

This can be addressed if the client takes actions in this order:
- Retire all unretired CIDs <= RPT, queuing the RCID frames for transmission
- Add the new CID to the connection
- Send the queued RCID frames using the new CID

During this transition, though, there are zero active CIDs on the connection.  A more savvy implementation might retire _all but one_ of the old CIDs (so data flow never gets stalled), install the new CID, then retire the last old one.  Of course, that gets trickier in a multipath world; you have to make sure that the one you keep is okay for the currently-active path.

What the client can't do is add the new CID first, check the limit, then process any retirements; in that order, the limit gets breached.

-- 
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/3193#issuecomment-551234463

---

From: Eric Kinnear <[email-masked]>
Date: Thu, 07 Nov 2019 12:42:27 -0800

There definitely was a reason we avoided making this a strict requirement, and I think this played into it, but this is the benefit of having RPT delivered in the same frame that delivers a new one. 

Perhaps modify the text to indicate that the error is if the limit is exceeded after retiring any in RPT?

Or even some non-normative text along the lines of “If RPT retires all outstanding CIDS, immediately start sending new packets with the new CID and make sure you only check the limit after retiring any indicated in RPT”? 

On one hand, it’s kind of an annoying thing to keep track of. But on the other, making it a hard requirement does decently simplify a lot of other scenarios. 

That said, we should probably go dig up the other reasons we avoided this the first time around. 

-- 
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/3193#issuecomment-551254796

---

From: Mike Bishop <[email-masked]>
Date: Thu, 07 Nov 2019 13:17:34 -0800

The [minutes](https://github.com/quicwg/wg-materials/blob/master/interim-19-01/minutes.md#issue-1994-endpoints-don-t-know-how-many-connections-ids-the-peer-is-willing-to-store) aren't super informative....  @kazuho was against it being an error, and @ekr thought it needed to be a hard requirement if present.  Nothing else specific about who opposed it or why.

I really wish we audio-recorded these meetings.

-- 
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/3193#issuecomment-551268264

---

From: Eric Kinnear <[email-masked]>
Date: Thu, 07 Nov 2019 13:23:36 -0800

Ah, thanks for looking that up! In that case, probably worth thinking through if there are other situations like this, but even if so I'm inclined towards the proposed change, albeit with additional text to cover the edge cases/provide implementation guidance.

-- 
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/3193#issuecomment-551270536

---

From: Kazuho Oku <[email-masked]>
Date: Thu, 07 Nov 2019 23:26:21 -0800

@MikeBishop 
> The [minutes](https://github.com/quicwg/wg-materials/blob/master/interim-19-01/minutes.md#issue-1994-endpoints-don-t-know-how-many-connections-ids-the-peer-is-willing-to-store) aren't super informa…

IIRC, some mildly opposed to the addition of active_connection_id_limit because it's an unnecessary complexity, arguing that the model could be simple as: issue-some initially, then issue more as the peer uses the CIDs. After the discussion, the middle ground that we agreed was to make it an advisory settings. Note that we made this decision prior to the addition of Retire Prior To.

But now, with the introduction of Retire Prior To, we have another way of retiring CIDs. I think that the simple model is no longer unsustainable.

-- 
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/3193#issuecomment-551416956

---

From: Marten Seemann <[email-masked]>
Date: Thu, 07 Nov 2019 23:57:44 -0800

@kazuho That matches what I remember from the discussion in Tokyo.

I think we actually need normative text along the lines that @MikeBishop suggests. I don't think it's a problem that during the time you process a NEW_CONNECTION_ID frame the number of active connection IDs might temporarily reach 0, if we assume that these frames are processed atomically. And I can't really think of a reason why any implementation might want split processing of the Retire Prior To field and adding the new CID.

I updated #3201 with a suggestion in 8354804a2a30580fd1b7deadb19f3baf3ad68fd8. WDYT?

-- 
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/3193#issuecomment-551424928

---

From: Mike Bishop <[email-masked]>
Date: Fri, 08 Nov 2019 06:58:17 -0800

I'm going to contradict me-from-yesterday a little, or at least complicate the point.

The reason we have the 1-RTO window is that some implementations might not be able to actually retire CIDs instantly (packets are queued in hardware offloads, you want to avoid racing in-flight packets against the packet containing the RCID, etc.).  If we require the retirement to be done as part of processing the frame, processing the frame can take up to an RTO.  What happens to other frames in the packet?  Does this packet get ACK'd if you're not done with this process yet?  Plus, you can't actually send the RCID frames until you've got the new CID *unless* you have a race with one more RCID frame in a subsequent packet.  This can get sticky very quickly.

If I had an implementation where I couldn't retire CIDs right away, I would probably tag them for retirement upon receipt of this frame and say those that are tagged don't count toward the limit.  But that's not entirely compliant with the text in your commit, and also assumes I have some headroom I'm not telling the peer about, because I have to remember all of them temporarily.

-- 
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/3193#issuecomment-551859959

---

From: Marten Seemann <[email-masked]>
Date: Fri, 08 Nov 2019 07:57:46 -0800

> If I had an implementation where I couldn't retire CIDs right away, I would probably tag them for retirement upon receipt of this frame and say those that are tagged don't count toward the limit. 

I agree that this would be a reasonable thing to do in this case. Clearly, if you have such an implementation, it's a highly optimized one that uses async processing and / or hardware offloads. I don't think it's too much too ask for that such an implementation takes appropriate steps to bridge the time it takes to retire a CID.
Do you have any suggestion how to improve the text in the PR without getting too much into implementation details?

-- 
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/3193#issuecomment-551883178

---

From: Mike Bishop <[email-masked]>
Date: Fri, 08 Nov 2019 08:11:58 -0800

Perhaps to say that the peer MUST NOT consider the connection IDs it has been asked to retire when calculating whether the limit has been exceeded, even if they haven't actually retired them yet?  That gives implementations the latitude to hang onto them for a bit if needed, but keeps you from going over the limit even so.

Then it's the implementation's business whether it wants to defer adding the CID (and block processing of this frame), add it and exceed the limit temporarily, retire the old CIDs on the spot, or something else.

-- 
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/3193#issuecomment-551888962

---

From: Eric Kinnear <[email-masked]>
Date: Mon, 11 Nov 2019 15:55:27 -0800

Right, I think the issues about packets that are already enqueued, etc. are more for the person requesting retirement of the CID to know that some packets might still show up (although potentially not after the ACK for the NCID frame that had RPT if they're all in the same queue? Not sure I'd want to rely on that ordering even before looking at the network). The endpoint that is retiring the CID can simply stop sending _new_ packets with that CID and be fine.

And leaving it up to the implementation but making a note that it's not a problem to retire/replace right up to the limit 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/3193#issuecomment-552671227

---

From: Eric Kinnear <[email-masked]>
Date: Mon, 18 Nov 2019 01:37:15 -0800

Proxying from the PR in regards to enforcing MUST error if the limit is exceeded: 
@MikeBishop:
> "MUST error" requires tracking. It's possible that an implementation might decide to drop some CIDs and reduce the number it keeps without closing the connection. "SHOULD/MAY error" provides the same deterrent effect for the issuer's misbehavior without placing a requirement on the receiver.

@marten-seemann: 
> We're requiring other limit checks (e.g. for STREAM_LIMIT_ERROR and for FLOW_CONTROL_ERROR), so I'd prefer to keep this a requirement as well.
>
>I don't think dropping should be regarded as acceptable behavior (although you can't prevent implementations from doing it), since a CID issued by an endpoint consumes state on that endpoint as well.

@janaiyengar: 
> I'm in agreement with @MikeBishop -- I would suggest changing this to a SHOULD error. This is different than the flow control errors, since an endpoint does not have to store all connection IDs that have been received.

@kazuho: 
> I might suggest having a design discussion in the issue (i.e. #3193) rather than here. There has been certain amount of discussion in that issue, and it seems to me that we have preference for MUST NOT.

@erickinnear:
> I'm not sure that I'm against the SHOULD, but I think the idea behind enforcing this was that an endpoint would indeed now need to store every CID it receives, and if it's not willing to store X amount, then it shouldn't have advertised a limit of X.
>
> And even if you still didn't store them all, you technically don't need to store them to keep track of how many you've been issued, which you'll probably need in order to cope with getting Retire Prior To anyways.

-- 
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/3193#issuecomment-554934384

---

From: Jana Iyengar <[email-masked]>
Date: Mon, 18 Nov 2019 17:21:51 -0800

Having discussed this offline with @erickinnear and @kazuho, I now understand the new model that you are proposing. I'm fine with it. I'll leave my comments on the PR.

-- 
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/3193#issuecomment-555287450