Should Path IDs be reused or not?

[mirjak]

From PR #292:

@huitema huitema on Nov 20, 2023

The path identifier is used to build the nonce. Reusing the same identifier would require either continuing the previously used sequence number space, otherwise the nonce would not be unique. But then that would require keeping these old number spaces in memory until the end of the connection, which seems like a waste of resource. Then there is the risk of confusion, what happens if old packets are delivered from a previous path using the path identifier.

We should make this very clear in the design. If the design goes for "re-use", then the node has to allocate an array of number spaces for the negotiated max number of spaces, and keep that for the duration of the connection. The effect of "Abandon path" becomes complicated -- if a CID for path N has never been used, should it be retired?

If the design goes for "unique path ID", the management of path and sequence numbers becomes simpler, but we need some logic to enforce the "maximum number of active paths". An advantage there is that endpoints can allocate more CID and more path than really needed, so the endpoint is always ready to start a new path after a previous one has been abandoned.

@kazuho kazuho on Nov 21, 2023

I do not feel strongly, but I think current design is fine as is.

In the new design, a QUIC Multipath connection that support N concurrent paths is essentially equivalent to N QUIC v1 connections running in parallel. If we think that way, migrating a particular path of a multipath connection can be equivalent to QUIC v1 doing intentional path migration.

I do not think we have a problem in the design of QUIC v1 doing path migration. Do we?

cc: @marten-seemann as also brought up the point.

@marten-seemann marten-seemann on Nov 21, 2023

I don't think we should reuse path identifiers. As @huitema correctly points out, reusing path identifiers means we can't start the packet number at 0 for reused paths, since that would be nonce reuse. The situation is even worse: As packet numbers are encoded in a maximum of 4 bytes, it wouldn't be possible to reuse a path ID once packet numbers have surpassed 2^32, unless you want to keep state for retired paths.

Here's an idea (not fully fleshed out): We could define a PATH_LIMIT { HighestPathID (i) } frame. The receiver of this frame can then issue CIDs up to the highest Path ID, and the sender can use this path as soon as it received CIDs.

@Yanmei-Liu Yanmei-Liu on Nov 21, 2023

I also prefer "unique path ID" here for AEAD security consideration. Not reusing resources and less corner case.

@kazuho kazuho on Nov 21, 2023

@marten-seemann

> As @huitema correctly points out, reusing path identifiers means we can't start the packet number at 0 for reused paths, since that would be nonce reuse. The situation is even worse: As packet numbers are encoded in a maximum of 4 bytes, it wouldn't be possible to reuse a path ID once packet numbers have surpassed 2^32, unless you want to keep state for retired paths.
I'm afraid this analysis is incorrect (specifically the 2nd sentence).

In QUIC v1, we retain packet numbers and those information for one path. In Multipath QUIC, we can do the same for N concurrent paths.

It is as simple as that.

@Yanmei-Liu

>Not reusing resources and less corner case.

"Not reusing resources" this is correct. But the downside of not reusing path identifiers is that and endpoint has to issue credit to the other side (like MAX_STREAMS or NEW_CONNECTION_ID of QUIC v1).

It is the trade off between the two.

@kazuho kazuho on Nov 21, 2023

For the purpose of pushing this PR forward as an experiment, I'm happy with going with the "no-reuse" route, but I want to have the records straight, as we will be coming back to the discussion of if the "explicit path identifiers" concept really makes sense.

@marten-seemann marten-seemann on Nov 21, 2023

> unless you want to keep state for retired paths

I don't think my analysis is incorrect. You need to be able to reconstruct the packet number if you want to be able to decrypt the packet. So at the very least, you need to keep state to save the highest received packet number for every path ID.

That's not a lot of state, but there are other problems with reusing path IDs, namely that you're introducing much more reliance on timers than if you just keep incrementing. That's the reason why none of the other identifiers we use in the protocol ever wrap around (packet numbers, stream IDs, etc.).

@kazuho kazuho on Nov 21, 2023

>I don't think my analysis is incorrect. You need to be able to reconstruct the packet number if you want to be able to decrypt the packet. So at the very least, you need to keep state to save the highest received packet number for every path ID.

The presumption of reusing path identifiers is, as @huitema points out, that the packet number space would be retained. Highest received packet number is a property of a packet number space, so it does not cause any extra burden.

@Yanmei-Liu Yanmei-Liu on Nov 21, 2023

How about we use an interval for PATH_LIMIT { lowest path ID, highest path ID} frame here?
To inform the peer about the available range for Path IDs, and it has a clear signal for retirement of Path IDs.

@kazuho kazuho on Nov 21, 2023

@Yanmei-Liu I'm not sure if we can use a contiguous range for representing valid IDs.

Consider the case of an endpoint sticking to using path ID 0, while retiring all paths between ID 2 to 9.

I think it would make more sense to follow the design that we have for stream IDs / Connection IDs; i.e., have one frame that issues the new maximum, and another that informs the peer one path ID that is being disposed.

@Yanmei-Liu Yanmei-Liu on Nov 21, 2023

Please check the MP_MAX_PATHS frames part, it's Marten's idea and he reminds me of the mechanism is quite the same with MAX_STREAMS. I also update the mechanism of transport parameter for "initial_max_paths". It's true that we will not be able use contiguous range. I just use the maximum value.

@mirjak mirjak on Nov 21, 2023

Should we can keep using the Destination Connection ID sequence number for the nonce and use a common sequence number space for all CIDs (as I believe CIDs should probably to be unique as well)? That means the encryption changes when the CID changes but I don't think that is a big issue...?

@michael-eriksson michael-eriksson on Nov 23, 2023

We should definitely not reuse path IDs. One of the nice things with QUIC is that it doesn't reuse any identifiers, not even packet numbers, which makes implementations cleaner and simpler.

When it comes to limiting the number of paths, I think there are two main designs:

1. Reuse the design for connection IDs: limit the number of active paths. The max number of active CIDs is signalled as a transport parameter (active_connection_id_limit) and an endpoint is allowed to issue a new CID only after the peer has retired a previous CID. Analogously, an endpoint would only issue CIDs for a new path after a previous path had been abandoned.
2. Use a MP_MAX_PATHS frame to dynamically allow new paths (similar to a MAX_STREAMS frame).

In short summary, 1. has less signalling and 2. can dynamically adapt the number of concurrent paths. Both designs have prior art in RFC 9000.

** @michael-eriksson michael-eriksson on Nov 23, 2023**

> Should we can keep using the Destination Connection ID sequence number for the nonce and use a common sequence number space for all CIDs (as I believe CIDs should probably to be unique as well)? That means the encryption changes when the CID changes but I don't think that is a big issue...?

I don't think that a common sequence number space for all CIDs match well with the Retire Prior To field in the MP_NEW_CONNECTION_ID (see also other comment above) so using the path ID is a simpler way to get a unique nonce. When a packet is received, you anyway need to look up the per-path state, and the packet number space in particular, before you can expand the truncated packet number and then decrypt the packet which means that you can trivially also access the path ID.

There is also https://github.com/quicwg/multipath/issues/215 (now closed) as another solution to the nonce handling.

@huitema huitema on Nov 26, 2023

I like@kazuho's suggestion of using the same logic for controlling path ID as for controlling stream ID, but there is a little complicating factor. Stream ID are allocated in clear contexts (uni/bidir, client/server), and then the same stream ID is used in both directions. In the current design, stream IDs are allocated as part of CID, and there is no guarantee that client and server pick the same ID for a new path. DO we want to also handle that?

[mirjak]

Also from PR #292:

huitema on Nov 20, 2023

See comments above. In my mind, using the path ID in the nonce pretty much mandates unique path ID. Something like a monotonously increasing number.

+1 from @michael-eriksson @Yanmei-Liu @qdeconinck

[mirjak]

Sounds like we all agree on this resolution but this might need some clarification in the draft.

[kazuho]

Not that I have a strong opinion, but I do wonder if we need the concept of issuing and retiring new path IDs at all; see #321.

In case of CIDs, we need to have the mechanism of issuing new CIDs, because the path migration can happy many nany times.

But path IDs are not exposed to the path, so endpoints can reuse them. It might sound counterintuitive to reuse an old path ID when intentionally creating a new path. But the catch is that the required behavior of intentionally migrating to a different path is going to be identical to involuntary migration (i.e., NAT rebinding) that we have to handle.

Considering that, to me it seems like an unnecessary complexity to have a different mechanism to handle intentional migration.

[mirjak]

Closing this issue now. Please continue discussion in #321