Subject: Re: Packet number spaces in multipath (was Re: What to do about multipath in QUIC)

From: Roberto Peon <[email-masked]>
Date: Tue, 1 Dec 2020 17:40:43 +0000

Markus—
There are some drafts (IIRC, from Mike Bishop and Victor Lubashev) and other discussions around partial reliability that got shelved while getting people moving forward on QUICv1, so it could get done.
I do still believe that such a model is better overall, because you get basically all of the datagram goodness with all of the potential goodness of streams. *shrug*

“Ordered, but not necessarily in-order” was how we attempted to describe this in the past. I expect this kind of thing will be natively better for things like video or games, especially for multiparty scenarios.
QUIC has again proven, however, that anything can be done so long as you can route *something* (e.g. datagrams) between peers and allow them to insert data in those somethings.

-=R

From: QUIC <[email-masked]> on behalf of Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Friday, November 27, 2020 at 12:59 AM
To: "[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>
Cc: "[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>, "[email-masked]" <[email-masked]>
Subject: RE: Packet number spaces in multipath (was Re: What to do about multipath in QUIC)

I should perhaps clarify that QUIC does have packet numbers which may or may not be path specific in a multipath scenario. However, QUIC does not associate semantics with the packet numbering scheme with the exception that unacked sufficiently old packet numbers can be considered lost because it is not possible to track history indefinitely, and also because gaps can be introduced to detect false acknowledgments (optimistic ack attack). Specifically a multi-core QUIC engine and an endpoint with multiple hardware offloads, can send packets out of sequence as an optimisation, and later, the network can of course do the same.

Mikkel

On 27 November 2020 at 09.39.46, Mikkel Fahnøe Jørgensen ([email-masked]<mailto:[email-masked]>) wrote:
Hi Markus,

QUIC does not have connection sequencing, unlike TCP, that is one of the key points of QUIC. Only streams carry sequencing.

QUIC Datagram frames do not carry sequencing or even any kind of flow association. That was discussed, but it was found that the application could do that at least as well - with the subtle exception of multiple applications cooperating on the same QUIC connection.

Unreliable streams is something in between where there is stream association and sequence information, but no delivery guarantees, and probably no ordering either but the API could choose to offer that at the end point. Unreliable streams are so far only a concept that has not been fully explored but are expected to be important for video streaming and similar use cases.

So you are right that datagram frames can be harder to reason about on multiple paths, especially if an application makes assumptions based on the received order. For the QUIC engine, the problem of loss detection is the same for all QUIC packets and the problem of ordering within a stream gets more costly due to more reordering, but otherwise remains the same.

Kind Regards,
Mikkel Fahnøe Jørgensen

On 27 November 2020 at 09.20.08, [email-masked]<mailto:[email-masked]> ([email-masked]<mailto:[email-masked]>) wrote:
Hi Christian,

OK, good hint. From my understanding that will not change the general issue of out-of-order reception though.
For clarification, does this means, that a QUIC connection with DATAGRAM frames will not carry any sequence space or only one, the connection sequencing? And that using “unreliable” stream frame will provide two sequence spaces, a connection and a stream space?

Have not found anything about “unreliable” streams in the transport draft, is this exactly the same as with DATAGRAM, no HoL at all?

From: Christian Huitema <[email-masked]<mailto:[email-masked]>>
Sent: Donnerstag, 26. November 2020 18:54
To: Amend, Markus <[email-masked]<mailto:[email-masked]>>; [email-masked]<mailto:[email-masked]>
Cc: [email-masked]<mailto:[email-masked]>; von Hugo, Dirk <[email-masked]<mailto:[email-masked]>>; [email-masked]<mailto:[email-masked]>
Subject: Re: Packet number spaces in multipath (was Re: What to do about multipath in QUIC)

If you want to send unreliable data with sequencing information, it might be simpler to use STREAM frame in "unreliable" mode than to use Datagram frames.
On 11/26/2020 3:34 AM, [email-masked]<mailto:[email-masked]> wrote:
Dear all,

sry for hijacking this conversation. I’m not very familiar with the different multipath designs for QUIC, however I want to draw attention to multipath re-ordering which probably becomes important when multipath is combined with DATAGRAM.

As long as multipath QUIC is operated with strict reliability (similar to TCP), re-ordering on receiver side is a simple process known from MPTCP. Introducing unreliable DATAGRAM transmission makes it more challenging on receiver side to maintain the packet order, because it is not easy to differentiate between delayed and lost packets. To avoid HoL, a multipath re-ordering process may benefit from having connection and path sequencing. In https://tools.ietf.org/html/draft-amend-iccrg-multipath-reordering-01<https://tools.ietf.org/html/draft-amend-iccrg-multipath-reordering-01> we intend to describe this in section 5.6, how fast packet loss detection can be applied using these different packet sequence spaces. Still the description is meaningless und will be updated until next IETF, however we have successfully implemented this approach in a MP-DCCP prototype, which faces similar challenges in terms of re-ordering. That means, fast packet loss detection is very beneficial for the receiver re-ordering process to not lose time until an outstanding packet is assumed lost.

Br

Markus

From: QUIC <[email-masked]><mailto:[email-masked]> On Behalf Of Jana Iyengar
Sent: Mittwoch, 25. November 2020 04:35
To: Christian Huitema <[email-masked]><mailto:[email-masked]>
Cc: IETF QUIC WG <[email-masked]><mailto:[email-masked]>; Kazuho Oku <[email-masked]><mailto:[email-masked]>
Subject: Packet number spaces in multipath (was Re: What to do about multipath in QUIC)

(I'm taking Spencer's suggestion to spin off a new thread.)

Christian, Kazuho,

Slowly catching up on this, and apologies if I'm missing anything that was previously discussed in the centi-thread earlier.

If I understand the design correctly, it makes sense to me, and is very close to what we had implemented in Chromium a while ago.

Having thought about this problem several times in the past, I'd like to share a few points that come to mind.

First though, a point on terminology: the receiver maintains a separate "ReceivedPackets" for each CID, probably for each CID sequence number (CSN). Let's please not call this a SACK Dashboard, to avoid confusion.

On the question of sending more than 2^32 packets, I think that resetting the packet number (PN) is ok on new CIDs. I don't see why a sender would need to maintain continuity across multiple paths anyways, since the CC and loss recovery contexts are going to be different across paths. A sender _could_ still maintain these packets in the same "SentPackets" structure if it wants to, it would need an internal representation of CSN+PN to key off.

ACK Frames:
------------------
Kazuho pointed out that when acknowledging, the ACK frame format should include CSN. I agree. I would argue for a design where a receiver uses an ACK frame per CSN (and encodes the CSN explicitly). There are multiple values for doing this, the primary being that you benefit from compression when PNs are contiguous within a CSN.

Return Path:
-----------------
There are other ways to decide which return path to send an ACK on this, but I would propose that a receiver respond on the most recently active forward path. That is, the path on which a packet was most recently received. This has the natural effect that a sender that wants to distribute traffic in a particular way also causes ACKs to be distributed similarly across the corresponding reverse paths.

RTT measurements:
---------------------------
The return path for ACK frames will impact RTT measurements. That is fine. It is more important that information reach the sender as soon as possible than that it should not affect RTT measurements; we can fix the sender to measure and compensate as necessary. The estimated RTT statistics reflect the distribution of samples, and if both paths are being used, then the SmoothedRTT will reflect the expected value based on the traffic distribution across paths.

That said, it might be useful to track some new stats, especially about how much later is a "late ack" -- an ACK frame that contains no useful information -- is received. I'd have to think a bit more about this, but I think we can devise a stat here. This gives us useful information on the longest return path, which we can then explicitly use as part of the PTO computations, to compensate for the fact that the RTT is based on the shortest return path. (I would _not_ use this stat in the time-based loss detection timer,  but PTO ought to be fine.)

- jana

On Tue, Nov 17, 2020 at 9:42 AM Christian Huitema <[email-masked]<mailto:[email-masked]>> wrote:

I have been thinking about variations of that. I think we are making progress here.

If we follow your design, we get two constraints:

1) That the receive maintains an acknowledgement list based on the CID through which the packets are received.

2) That the senders guarantee that the same sequence number will not be used more than once with a specific CID.

The main implementation cost is for receivers. They have to allocate and maintain a "SACK Dashboard" in the context of each CID that they issue.

Senders have lots of control. For example, the "only once" condition is also met if a simple sender uses a single number space, as long as it does not send more than 2^32 packets. That makes the design reasonably easy to implement for constrained implementations.

Zero length CID are still possible, but that means the receiver supports only one PN space per sender. Multipath is not impossible, but you end up managing a single RTT and a single recovery structure. Not very good, but similar to what happens if multipath is implemented at the IP level.

There is still an issue for coordinating the take down of a path. Suppose that a client was using both Wi-Fi and LTE, and moves out of Wi-Fi range. The server will find out eventually that the packets sent to the Wi-Fi path are never acknowledged, but that may take some time. It would be better if the client could send a message saying something like "Abandon this path". That's not the same semantic as "retire this CID". We need a new frame for that.

"Abandon this path" is an extreme case. There are half-way steps, like manage the relative priority of a path.

---

From: <[email-masked]>
Date: Wed, 2 Dec 2020 07:52:19 +0000

Hi Robert,

I believe, that reliability, partial reliability or no reliability can be easily implemented and I also think that concept is already proven with (PR-)SCTP, which covers exactly those three cases. However, finding well working re-ordering strategies on receiver side then is an additional topic. A simple “wait until arrive” as it is applied for strict reliability purposes or “wait for a fixed time” to cover partial/no reliability or to do nothing is maybe not the best approach. While applications which implements countermeasures against out-of-order delivery probably don’t need support, there might be others which do, because they rely on transport mechanism.

Especially for any QUIC tunneling approaches as discussed in MASQUE, which transports then plenty of services with different demands on in-order delivery, bringing packets (partially) in-order might be essential. Also path migration as part of QUICv1 can cause out-of-order delivery but moreover any future multipath-QUIC will cause an enormous out-of-order rate when latency differences between aggregated paths are given.

Br

Markus

From: Roberto Peon <[email-masked]>
Sent: Dienstag, 1. Dezember 2020 18:41
To: Mikkel Fahnøe Jørgensen <[email-masked]>; [email-masked]; [email-masked]; Amend, Markus <[email-masked]>
Cc: [email-masked]; [email-masked]; von Hugo, Dirk <[email-masked]>
Subject: Re: Packet number spaces in multipath (was Re: What to do about multipath in QUIC)

Markus—

-=R
From: QUIC <[email-masked]<mailto:[email-masked]>> on behalf of Mikkel Fahnøe Jørgensen <[email-masked]<mailto:[email-masked]>>
Date: Friday, November 27, 2020 at 12:59 AM
To: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>, "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>, "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Cc: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>, "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>, "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Subject: RE: Packet number spaces in multipath (was Re: What to do about multipath in QUIC)

Mikkel

Kind Regards,
Mikkel Fahnøe Jørgensen

As long as multipath QUIC is operated with strict reliability (similar to TCP), re-ordering on receiver side is a simple process known from MPTCP. Introducing unreliable DATAGRAM transmission makes it more challenging on receiver side to maintain the packet order, because it is not easy to differentiate between delayed and lost packets. To avoid HoL, a multipath re-ordering process may benefit from having connection and path sequencing. In https://tools.ietf.org/html/draft-amend-iccrg-multipath-reordering-01 we intend to describe this in section 5.6, how fast packet loss detection can be applied using these different packet sequence spaces. Still the description is meaningless und will be updated until next IETF, however we have successfully implemented this approach in a MP-DCCP prototype, which faces similar challenges in terms of re-ordering. That means, fast packet loss detection is very beneficial for the receiver re-ordering process to not lose time until an outstanding packet is assumed lost.

Br

Markus

Christian, Kazuho,

ACK Frames:
------------------

Return Path:
-----------------

RTT measurements:

- jana

---

From: Mirja Kuehlewind <[email-masked]>
Date: Wed, 2 Dec 2020 11:02:14 +0000

Hi Jana,

can you maybe confirm what you mean by “the design” below just to make sure we are all on the same page: Is that different PN spaces per path, but using the same key on all paths with CIDs as part of the nonce?

Thanks!
Mirja

From: QUIC <[email-masked]> on behalf of Jana Iyengar <[email-masked]>
Date: Wednesday, 25. November 2020 at 04:35
To: Christian Huitema <[email-masked]>
Cc: IETF QUIC WG <[email-masked]>, Kazuho Oku <[email-masked]>
Subject: Packet number spaces in multipath (was Re: What to do about multipath in QUIC)

Christian, Kazuho,

ACK Frames:
------------------

Return Path:
-----------------

RTT measurements:

- jana

---

From: Jana Iyengar <[email-masked]>
Date: Wed, 2 Dec 2020 20:07:10 -0800

Mirja,

I'm referring to what Christian was summarizing below. Separate PN spaces
but path ID is implicit as the sequence number of the connection ID, and
ACKs reflect this sequence number.

- jana

On Wed, Dec 2, 2020 at 3:02 AM Mirja Kuehlewind <
[email-masked]> wrote:

> Hi Jana,
>
>
>
> can you maybe confirm what you mean by “the design” below just to make
> sure we are all on the same page: Is that different PN spaces per path, but
> using the same key on all paths with CIDs as part of the nonce?
>
>
>
> Thanks!
>
> Mirja
>
>
>
>
>
> *From: *QUIC <[email-masked]> on behalf of Jana Iyengar <
> [email-masked]>
> *Date: *Wednesday, 25. November 2020 at 04:35
> *To: *Christian Huitema <[email-masked]>
> *Cc: *IETF QUIC WG <[email-masked]>, Kazuho Oku <[email-masked]>
> *Subject: *Packet number spaces in multipath (was Re: What to do about
> multipath in QUIC)
>
>
>
> Slowly catching up on this, and apologies if I'm missing anything that was
> previously discussed in the centi-thread earlier.
>
>
>
> If I understand the design correctly, it makes sense to me, and is very
> close to what we had implemented in Chromium a while ago.
>
>
>
> First though, a point on terminology: the receiver maintains a separate
> "ReceivedPackets" for each CID, probably for each CID sequence number
> (CSN). Let's please not call this a SACK Dashboard, to avoid confusion.
>
>
>
> On the question of sending more than 2^32 packets, I think that resetting
> the packet number (PN) is ok on new CIDs. I don't see why a sender would
> need to maintain continuity across multiple paths anyways, since the CC and
> loss recovery contexts are going to be different across paths. A sender
> _could_ still maintain these packets in the same "SentPackets" structure if
> it wants to, it would need an internal representation of CSN+PN to key off.
>
>
>
> ACK Frames:
>
> ------------------
>
> Kazuho pointed out that when acknowledging, the ACK frame format should
> include CSN. I agree. I would argue for a design where a receiver uses an
> ACK frame per CSN (and encodes the CSN explicitly). There are multiple
> values for doing this, the primary being that you benefit from compression
> when PNs are contiguous within a CSN.
>
>
>
> Return Path:
>
> -----------------
>
> There are other ways to decide which return path to send an ACK on this,
> but I would propose that a receiver respond on the most recently active
> forward path. That is, the path on which a packet was most recently
> received. This has the natural effect that a sender that wants to
> distribute traffic in a particular way also causes ACKs to be distributed
> similarly across the corresponding reverse paths.
>
>
>
> RTT measurements:
>
> The return path for ACK frames will impact RTT measurements. That is fine.
> It is more important that information reach the sender as soon as possible
> than that it should not affect RTT measurements; we can fix the sender
> to measure and compensate as necessary. The estimated RTT statistics
> reflect the distribution of samples, and if both paths are being used, then
> the SmoothedRTT will reflect the expected value based on the traffic
> distribution across paths.
>
>
>
> That said, it might be useful to track some new stats, especially about
> how much later is a "late ack" -- an ACK frame that contains no useful
> information -- is received. I'd have to think a bit more about this, but I
> think we can devise a stat here. This gives us useful information on the
> longest return path, which we can then explicitly use as part of the PTO
> computations, to compensate for the fact that the RTT is based on the
> shortest return path. (I would _not_ use this stat in the time-based loss
> detection timer,  but PTO ought to be fine.)
>
>
>
> - jana
>
>
>
> On Tue, Nov 17, 2020 at 9:42 AM Christian Huitema <[email-masked]>
> wrote:
>
> The main implementation cost is for receivers. They have to allocate and
> maintain a "SACK Dashboard" in the context of each CID that they issue.
>
> Senders have lots of control. For example, the "only once" condition is
> also met if a simple sender uses a single number space, as long as it does
> not send more than 2^32 packets. That makes the design reasonably easy to
> implement for constrained implementations.
>
> Zero length CID are still possible, but that means the receiver supports
> only one PN space per sender. Multipath is not impossible, but you end up
> managing a single RTT and a single recovery structure. Not very good, but
> similar to what happens if multipath is implemented at the IP level.
>
> There is still an issue for coordinating the take down of a path. Suppose
> that a client was using both Wi-Fi and LTE, and moves out of Wi-Fi range.
> The server will find out eventually that the packets sent to the Wi-Fi path
> are never acknowledged, but that may take some time. It would be better if
> the client could send a message saying something like "Abandon this path".
> That's not the same semantic as "retire this CID". We need a new frame for
> that.
>

---

From: Quentin De Coninck <[email-masked]>
Date: Fri, 4 Dec 2020 10:20:59 +0100

Jana and all,

I just have a concern about such a design using sequence number of the 
connection ID as the path ID.

Assume that the server is willing to offer two available connection IDs 
at any time, and that the client is using both at the same time for 
multipath transfer. It uses the CID with seq num 0 on path A and the CID 
with seq num 1 on path B. Then, for any reason (like privacy), the 
client wants to change the connection ID used on path B (using seq num 
1). However, the host cannot retire the CID with seq num 1 without 
retiring the CID with seq num 0 too. If the server does not want to 
provide additional connection IDs and the client is not willing to reuse 
CID with seq num 1 on path A, the client is stuck with the CID with seq 
num 0 on path A and cannot use the path B anymore.

This is why I believe we should not link the path ID to the sequence 
number of the Connection ID (because it is a monotonically increasing 
sequence number), and rather have a separate space for them.

Best regards,

Quentin

> Mirja,
>
> I'm referring to what Christian was summarizing below. Separate PN 
> spaces but path ID is implicit as the sequence number of the 
> connection ID, and ACKs reflect this sequence number.
>
> - jana
>
> On Wed, Dec 2, 2020 at 3:02 AM Mirja Kuehlewind 
> <[email-masked] <mailto:[email-masked]>> 
> wrote:
>
>     Hi Jana,
>
>     can you maybe confirm what you mean by “the design” below just to
>     make sure we are all on the same page: Is that different PN spaces
>     per path, but using the same key on all paths with CIDs as part of
>     the nonce?
>
>     Thanks!
>
>     Mirja
>
>     *From: *QUIC <[email-masked]
>     <mailto:[email-masked]>> on behalf of Jana Iyengar
>     <[email-masked] <mailto:[email-masked]>>
>     *To: *Christian Huitema <[email-masked]
>     <mailto:[email-masked]>>
>     *Cc: *IETF QUIC WG <[email-masked] <mailto:[email-masked]>>, Kazuho
>     Oku <[email-masked] <mailto:[email-masked]>>
>     *Subject: *Packet number spaces in multipath (was Re: What to do
>     about multipath in QUIC)
>
>     Slowly catching up on this, and apologies if I'm missing anything
>     that was previously discussed in the centi-thread earlier.
>
>     If I understand the design correctly, it makes sense to me, and is
>     very close to what we had implemented in Chromium a while ago.
>
>     Having thought about this problem several times in the past, I'd
>     like to share a few points that come to mind.
>
>     First though, a point on terminology: the receiver maintains a
>     separate "ReceivedPackets" for each CID, probably for each CID
>     sequence number (CSN). Let's please not call this a SACK
>     Dashboard, to avoid confusion.
>
>     On the question of sending more than 2^32 packets, I think that
>     resetting the packet number (PN) is ok on new CIDs. I don't see
>     why a sender would need to maintain continuity across multiple
>     paths anyways, since the CC and loss recovery contexts are going
>     to be different across paths. A sender _could_ still maintain
>     these packets in the same "SentPackets" structure if it wants to,
>     it would need an internal representation of CSN+PN to key off.
>
>     ACK Frames:
>
>     ------------------
>
>     Kazuho pointed out that when acknowledging, the ACK frame format
>     should include CSN. I agree. I would argue for a design where a
>     receiver uses an ACK frame per CSN (and encodes the CSN
>     explicitly). There are multiple values for doing this, the primary
>     being that you benefit from compression when PNs are contiguous
>     within a CSN.
>
>     Return Path:
>
>     -----------------
>
>     There are other ways to decide which return path to send an ACK on
>     this, but I would propose that a receiver respond on the most
>     recently active forward path. That is, the path on which a packet
>     was most recently received. This has the natural effect that a
>     sender that wants to distribute traffic in a particular way also
>     causes ACKs to be distributed similarly across the corresponding
>     reverse paths.
>
>     RTT measurements:
>
>     The return path for ACK frames will impact RTT measurements. That
>     is fine. It is more important that information reach the sender as
>     soon as possible than that it should not affect RTT measurements;
>     we can fix the sender to measure and compensate as necessary. The
>     estimated RTT statistics reflect the distribution of samples, and
>     if both paths are being used, then the SmoothedRTT will reflect
>     the expected value based on the traffic distribution across paths.
>
>     That said, it might be useful to track some new stats, especially
>     about how much later is a "late ack" -- an ACK frame that contains
>     no useful information -- is received. I'd have to think a bit more
>     about this, but I think we can devise a stat here. This gives us
>     useful information on the longest return path, which we can then
>     explicitly use as part of the PTO computations, to compensate for
>     the fact that the RTT is based on the shortest return path. (I
>     would _not_ use this stat in the time-based loss detection timer, 
>     but PTO ought to be fine.)
>
>     - jana
>
>     On Tue, Nov 17, 2020 at 9:42 AM Christian Huitema
>     <[email-masked] <mailto:[email-masked]>> wrote:
>
>         1) That the receive maintains an acknowledgement list based on
>         the CID through which the packets are received.
>
>         2) That the senders guarantee that the same sequence number
>         will not be used more than once with a specific CID.
>
>         The main implementation cost is for receivers. They have to
>         allocate and maintain a "SACK Dashboard" in the context of
>         each CID that they issue.
>
>         Senders have lots of control. For example, the "only once"
>         condition is also met if a simple sender uses a single number
>         space, as long as it does not send more than 2^32 packets.
>         That makes the design reasonably easy to implement for
>         constrained implementations.
>
>         Zero length CID are still possible, but that means the
>         receiver supports only one PN space per sender. Multipath is
>         not impossible, but you end up managing a single RTT and a
>         single recovery structure. Not very good, but similar to what
>         happens if multipath is implemented at the IP level.
>
>         There is still an issue for coordinating the take down of a
>         path. Suppose that a client was using both Wi-Fi and LTE, and
>         moves out of Wi-Fi range. The server will find out eventually
>         that the packets sent to the Wi-Fi path are never
>         acknowledged, but that may take some time. It would be better
>         if the client could send a message saying something like
>         "Abandon this path". That's not the same semantic as "retire
>         this CID". We need a new frame for that.
>
>         "Abandon this path" is an extreme case. There are half-way
>         steps, like manage the relative priority of a path.
>

---

From: Mikkel Fahnøe Jørgensen <[email-masked]>
Date: Fri, 4 Dec 2020 07:55:18 -0800

If there is a unique CID per path, that problem would go away, right?

Using the same CID on multiple paths could both cause privacy and routing
issues.

Mikkel

On 4 December 2020 at 10.21.33, Quentin De Coninck (
[email-masked]) wrote:

Jana and all,

Assume that the server is willing to offer two available connection IDs at
any time, and that the client is using both at the same time for multipath
transfer. It uses the CID with seq num 0 on path A and the CID with seq num
1 on path B. Then, for any reason (like privacy), the client wants to
change the connection ID used on path B (using seq num 1). However, the
host cannot retire the CID with seq num 1 without retiring the CID with seq
num 0 too. If the server does not want to provide additional connection IDs
and the client is not willing to reuse CID with seq num 1 on path A, the
client is stuck with the CID with seq num 0 on path A and cannot use the
path B anymore.

This is why I believe we should not link the path ID to the sequence number
of the Connection ID (because it is a monotonically increasing sequence
number), and rather have a separate space for them.

Best regards,

Quentin

Mirja,

- jana

---

From: Kazuho Oku <[email-masked]>
Date: Sat, 5 Dec 2020 03:52:27 +0900

2020年12月4日(金) 18:21 Quentin De Coninck <[email-masked]>:

> num 0 too.

I'm not sure if that is the case.

The consumer of a connection ID (in this case the client) can retire
connection IDs supplied by the issuer (the server) in any given order.
Separately, the issuer might ask the consumer to retire all connection IDs
with sequence numbers below a certain threshold by using the Retire Prior
To field, but in such case, the issuer can (and is expected to) supply
enough number of new connection IDs.

> If the server does not want to provide additional connection IDs and the
> client is not willing to reuse CID with seq num 1 on path A, the client is
> stuck with the CID with seq num 0 on path A and cannot use the path B
> anymore.
>
>> Slowly catching up on this, and apologies if I'm missing anything that
>> was previously discussed in the centi-thread earlier.
>>
>>
>>
>> The return path for ACK frames will impact RTT measurements. That is
>> fine. It is more important that information reach the sender as soon as
>> possible than that it should not affect RTT measurements; we can fix the
>> sender to measure and compensate as necessary. The estimated RTT statistics

-- 
Kazuho Oku

---

From: Quentin De Coninck <[email-masked]>
Date: Sat, 5 Dec 2020 09:43:23 +0100

Hi Kazuho, see inline.

Le 4/12/20 à 19:52, Kazuho Oku a écrit :
>
>
> 2020年12月4日(金) 18:21 Quentin De Coninck <[email-masked] 
> <mailto:[email-masked]>>:
>
>     Jana and all,
>
>     I just have a concern about such a design using sequence number of
>     the connection ID as the path ID.
>
>     Assume that the server is willing to offer two available
>     connection IDs at any time, and that the client is using both at
>     the same time for multipath transfer. It uses the CID with seq num
>     0 on path A and the CID with seq num 1 on path B. Then, for any
>     reason (like privacy), the client wants to change the connection
>     ID used on path B (using seq num 1). However, the host cannot
>     retire the CID with seq num 1 without retiring the CID with seq
>     num 0 too.
>
>
> Separately, the issuer might ask the consumer to retire all connection 
> IDs with sequence numbers below a certain threshold by using the 
> Retire Prior To field, but in such case, the issuer can (and is 
> expected to) supply enough number of new connection IDs.

Oh, right. Indeed, the RETIRE_CONNECTION_ID frame does not retire all 
the lower IDs, it is only the "Retire Prior To" field of 
NEW_CONNECTION_ID so this problem is actually not one :-)

 From a functional point of view, using the sequence number of CID as 
path ID could work then. I still have an operational concern about the 
number of paths/connection IDs that are concurrently in use. Assume the 
server provides a large number of Connection IDs (let say 8) to let the 
client handle migration and possibly use a second network path. How can 
the server prevent the client from using all the available Connection 
IDs (in this case 8) to different paths at the same time (i.e., how can 
the server control the number of paths used by the client if it provides 
Connection IDs in advance)?

Best,

Quentin

>     If the server does not want to provide additional connection IDs
>     and the client is not willing to reuse CID with seq num 1 on path
>     A, the client is stuck with the CID with seq num 0 on path A and
>     cannot use the path B anymore.
>
>     This is why I believe we should not link the path ID to the
>     sequence number of the Connection ID (because it is a
>     monotonically increasing sequence number), and rather have a
>     separate space for them.
>
>     Best regards,
>
>     Quentin
>
>>     Mirja,
>>
>>     I'm referring to what Christian was summarizing below. Separate
>>     PN spaces but path ID is implicit as the sequence number of the
>>     <[email-masked]
>>     <mailto:[email-masked]>> wrote:
>>
>>         Hi Jana,
>>
>>         can you maybe confirm what you mean by “the design” below
>>         just to make sure we are all on the same page: Is that
>>         different PN spaces per path, but using the same key on all
>>         paths with CIDs as part of the nonce?
>>
>>         Thanks!
>>
>>         Mirja
>>
>>         *Cc: *IETF QUIC WG <[email-masked] <mailto:[email-masked]>>,
>>         Kazuho Oku <[email-masked] <mailto:[email-masked]>>
>>         *Subject: *Packet number spaces in multipath (was Re: What to
>>         do about multipath in QUIC)
>>
>>         Slowly catching up on this, and apologies if I'm missing
>>         anything that was previously discussed in the centi-thread
>>         earlier.
>>
>>         If I understand the design correctly, it makes sense to me,
>>         and is very close to what we had implemented in Chromium a
>>         while ago.
>>
>>         Having thought about this problem several times in the past,
>>         I'd like to share a few points that come to mind.
>>
>>         First though, a point on terminology: the receiver maintains
>>         a separate "ReceivedPackets" for each CID, probably for each
>>         CID sequence number (CSN). Let's please not call this a SACK
>>         On the question of sending more than 2^32 packets, I think
>>         that resetting the packet number (PN) is ok on new CIDs. I
>>         don't see why a sender would need to maintain continuity
>>         across multiple paths anyways, since the CC and loss
>>         recovery contexts are going to be different across paths. A
>>         sender _could_ still maintain these packets in the same
>>         "SentPackets" structure if it wants to, it would need an
>>         internal representation of CSN+PN to key off.
>>
>>         ACK Frames:
>>
>>         ------------------
>>
>>         Kazuho pointed out that when acknowledging, the ACK frame
>>         format should include CSN. I agree. I would argue for a
>>         design where a receiver uses an ACK frame per CSN (and
>>         encodes the CSN explicitly). There are multiple values for
>>         doing this, the primary being that you benefit from
>>         compression when PNs are contiguous within a CSN.
>>
>>         Return Path:
>>
>>         -----------------
>>
>>         There are other ways to decide which return path to send an
>>         ACK on this, but I would propose that a receiver respond on
>>         the most recently active forward path. That is, the path on
>>         which a packet was most recently received. This has the
>>         natural effect that a sender that wants to distribute
>>         traffic in a particular way also causes ACKs to be
>>         distributed similarly across the corresponding reverse paths.
>>
>>         RTT measurements:
>>
>>         The return path for ACK frames will impact RTT measurements.
>>         That is fine. It is more important that information reach the
>>         sender as soon as possible than that it should not affect RTT
>>         measurements; we can fix the sender to measure and compensate
>>         as necessary. The estimated RTT statistics reflect the
>>         distribution of samples, and if both paths are being used,
>>         then the SmoothedRTT will reflect the expected value based on
>>         the traffic distribution across paths.
>>
>>         That said, it might be useful to track some new stats,
>>         especially about how much later is a "late ack" -- an
>>         ACK frame that contains no useful information -- is received.
>>         I'd have to think a bit more about this, but I think we can
>>         devise a stat here. This gives us useful information on the
>>         longest return path, which we can then explicitly use as part
>>         of the PTO computations, to compensate for the fact that the
>>         RTT is based on the shortest return path. (I would _not_ use
>>         this stat in the time-based loss detection timer,  but PTO
>>         ought to be fine.)
>>
>>         - jana
>>
>>             1) That the receive maintains an acknowledgement list
>>             based on the CID through which the packets are received.
>>
>>             2) That the senders guarantee that the same sequence
>>             number will not be used more than once with a specific CID.
>>
>>             The main implementation cost is for receivers. They have
>>             to allocate and maintain a "SACK Dashboard" in the
>>             context of each CID that they issue.
>>
>>             Senders have lots of control. For example, the "only
>>             once" condition is also met if a simple sender uses a
>>             single number space, as long as it does not send more
>>             than 2^32 packets. That makes the design reasonably easy
>>             to implement for constrained implementations.
>>
>>             receiver supports only one PN space per sender. Multipath
>>             is not impossible, but you end up managing a single RTT
>>             and a single recovery structure. Not very good, but
>>             There is still an issue for coordinating the take down of
>>             a path. Suppose that a client was using both Wi-Fi and
>>             LTE, and moves out of Wi-Fi range. The server will find
>>             out eventually that the packets sent to the Wi-Fi path
>>             are never acknowledged, but that may take some time. It
>>             would be better if the client could send a message saying
>>             something like "Abandon this path". That's not the same
>>             semantic as "retire this CID". We need a new frame for that.
>>
>>             "Abandon this path" is an extreme case. There are
>>             half-way steps, like manage the relative priority of a path.
>>
>
>
> -- 
> Kazuho Oku

---

From: "Martin Thomson" <[email-masked]>
Date: Mon, 07 Dec 2020 10:24:15 +1100

As this wasn't mentioned in the discussion:

On Wed, Nov 25, 2020, at 14:34, Jana Iyengar wrote:
> resetting the packet number (PN) is ok on new CIDs.

A design like this would require changes to the way that keys are generated.  Unfortunately, I think that this also increases the cost of key generation a little for reasons specific to the internal workings of the key derivation function.

---

From: Kazuho Oku <[email-masked]>
Date: Mon, 7 Dec 2020 09:04:15 +0900

2020年12月7日(月) 8:24 Martin Thomson <[email-masked]>:

> A design like this would require changes to the way that keys are
> generated.  Unfortunately, I think that this also increases the cost of key
> generation a little for reasons specific to the internal workings of the
> key derivation function.
>
>
I think Jana is discussing a different problem. Let me go through.

For multipath, I think that it is a good idea to have packet number spaces
for each path.

Then, the question is if we want to use different encryption keys for each
path, or if we want to use the same keys. As AEAD prevents nonce reuse, the
sensible option here is to use the 32-bit unused space of 96-bit nonce to
contain the identifier of the path (note: RFC 5116 recommends AEAD should
support nonce of at least 96 bits). Therefore, we do not need to restrict
the number of packets being sent on one path to 2^32 or whatever.

However, there is a separate issue. That is that the packet format of QUIC
v1 does not allow an endpoint to start from a CID that is greater than 2^31.

Therefore, if an endpoint intends to use a new path ID (which is being the
CID sequence number), but wants to continue using packet number space of a
different CID, then it needs to ensure that the next packet number to be
used is below 2^31.

IIUC this is the problem that Jana is referring to, and arguing that it is
okay because an endpoint can always reset the packet number to zero on a
new path.

-- 
Kazuho Oku

---

From: Mike Bishop <[email-masked]>
Date: Thu, 10 Dec 2020 20:31:15 +0000

Or we change the way the keys are used.  If the input were not just packet
number, but CSN+PN, we still have the never-repeated property we need even
if packet numbers are reset with each CID change.

-----Original Message-----
From: QUIC <[email-masked]> On Behalf Of Martin Thomson
Sent: Sunday, December 6, 2020 6:24 PM
To: [email-masked]
Subject: Re: Packet number spaces in multipath (was Re: What to do about
multipath in QUIC)

On Wed, Nov 25, 2020, at 14:34, Jana Iyengar wrote:
> sequence number (CSN). Let's please not call this a SACK Dashboard, to
avoid confusion.
> resetting the packet number (PN) is ok on new CIDs.

A design like this would require changes to the way that keys are generated.
Unfortunately, I think that this also increases the cost of key generation a
little for reasons specific to the internal workings of the key derivation
function.