Subject: [quicwg/base-drafts] Restore CID sequence numbers (#1465)

From: Mike Bishop <[email-masked]>
Date: Wed, 20 Jun 2018 14:35:37 -0700

After trying to find a better way to manage CID changes, probing, etc. I concluded that what we had before and removed is a superior place to start than anything else I'm coming up with.

The result of this PR is that, while we no longer have packet number gaps (so #1280 is no longer an issue), the sequence of CIDs issued by each endpoint is once again ordered.  On each path (local address), you know the sequence number of the CID you're currently using, and you can recognize the sequence number of the CID you're currently receiving (because you assigned it).

Fixes #1452 by requiring that each CID change on a path move to a CID with a greater sequence number; you move to the CID with the matching sequence number if it's usable, but if it's not, you move to something with a higher sequence number.  That will force your peer to meet you on that sequence number instead, and either way you land in equilibrium on each path.

This improves, but doesn't totally fix, the two problems discussed on #1464:
- You can forget the old CIDs you're allowed to use at any time that's convenient to you -- you just won't use them.  Because the CID sequence must advance per path, you can forget old CIDs you've issued once every path has either moved past that sequence number or been abandoned.  However, there's a slight possibility that peers will have different concepts of abandoned (particularly for probing on backup paths that are never migrated to), so we might need to mint a `RETIRE_CONNECTION_IDS` frame to tell the receiver that connection IDs with a sequence before X are no longer recognized by the sender.
- Once you've moved to the CID with sequence number X, the peer knows you can't use CID X-1 on this path even if you've never used it; if you're on the last / next-to-last CID the peer issued, you need more, even if you have some old ones you could still use on a different path.  However, if you have the bad luck to use your last CID for a probe which gets dropped and you're no longer able to send on that path, you can still get stuck if your peer is only giving you one CID at a time.  This probably still requires a `REQUEST_CONNECTION_ID` frame.

While I think the design is mostly sound, this is too wordy.  I'd appreciate help making this more readable.
You can view, comment on, or merge this pull request online at:

  https://github.com/quicwg/base-drafts/pull/1465

-- Commit Summary --

  * Revert "Remove sequence number from NEW_CONNECTION_ID"
  * Require CID sequence number ratcheting
  * Prefer equality

-- File Changes --

    M draft-ietf-quic-transport.md (46)

-- Patch Links --

https://github.com/quicwg/base-drafts/pull/1465.patch
https://github.com/quicwg/base-drafts/pull/1465.diff

-- 
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/pull/1465

---

From: Nick Banks <[email-masked]>
Date: Wed, 20 Jun 2018 21:52:40 +0000 (UTC)

nibanks requested changes on this pull request.

The text here is really confusing and I don't understand what it supposed to be going on. Perhaps you can explain more in the comments and we can figure out some better text.

> @@ -1834,7 +1834,12 @@ new connection IDs using the NEW_CONNECTION_ID frame.
 An endpoint might need to send packets on multiple networks without receiving
 any response from its peer.  To ensure that the endpoint is not linkable across
 each of these changes, a new connection ID is needed for each network.  To
-support this, multiple NEW_CONNECTION_ID messages are needed.
+support this, multiple NEW_CONNECTION_ID messages are needed.  Each
+NEW_CONNECTION_ID is marked with a sequence number.  Connection IDs MUST be used
+on only one local address, and each local address MUST advance to a connection
+ID with a later sequence number each time the connection ID changes.  Once a
+connection ID has been used, connection IDs with an earlier sequence number MUST
+NOT be used for packets with a greater packet number from that local address.

I'm confused as to how this works with probing a new path (but not moving to it). Assume I am currently on Path A using CID 1, then I probe Path B with CID 2. This text seems to state that I may not use CID 1 on Path A with any packet number greater than I used to probe Path B with  CID 2. Is that correct?

> @@ -2613,6 +2627,14 @@ The NEW_CONNECTION_ID is as follows:
 
 The fields are:
 
+Sequence:
+
+: A variable-length integer.  This value starts at 0 and increases by 1 for each
+  connection ID that is provided by the server.  The connection ID that is
+  assigned during the handshake is assumed to have a sequence of -1.  That is,

Is there a real reason we can consider the handshake CID `0` and start from there? I'd rather not have to deal with negative numbers in my code.

-- 
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/pull/1465#pullrequestreview-130601503

---

From: Mike Bishop <[email-masked]>
Date: Wed, 20 Jun 2018 14:55:55 -0700

MikeBishop commented on this pull request.

At that point, you may not use a CID < 1 on path A, and may not use a CID < 2 on path B.  You also aren't allowed to use CID = 2 on path A, because it's been used on a different path.

-- 
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/pull/1465#discussion_r196955161

---

From: Mike Bishop <[email-masked]>
Date: Wed, 20 Jun 2018 21:57:01 +0000 (UTC)

The fields are:
 
+Sequence:
+

Probably not.  This is just the existing text.  It's actually a little worse than that, because the Server's Preferred Address gives the client a CID to use when probing, so there can actually be two CIDs prior to the first one issued by 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/pull/1465#discussion_r196955405

---

From: Mike Bishop <[email-masked]>
Date: Wed, 20 Jun 2018 15:01:34 -0700

Basically:
- For each path, the CID sequence number must advance, but the currently-in-use CID for each path is unrelated.  You could keep probing forever with CID2 on Path B even while Path A has moved up to CID 39, so long as the path isn't abandoned.
- Each CID can only be used on a single path.  If you used CID2 on Path B, you have to skip CID2 on Path A.

-- 
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/pull/1465#discussion_r196956391

---

From: Nick Banks <[email-masked]>
Date: Wed, 20 Jun 2018 15:01:48 -0700

nibanks commented on this pull request.

Ok, maybe instead of "Once a connection ID has been used, connection IDs with an earlier sequence number MUST NOT be used for packets with a greater packet number from that local address." something like "Once a new connection ID is used, earlier connection IDs MUST NOT be used for new packets sent from the new local address".

-- 
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/pull/1465#discussion_r196956451

---

From: Nick Banks <[email-masked]>
Date: Wed, 20 Jun 2018 15:06:11 -0700

The fields are:
 
+Sequence:
+

Then maybe we define handshake as `0`, the server's preferred address as `1` (even if not present) and then new CIDs start from there (i.e. `2`). I don't see any reason to prevent gaps in the CID sequence number space either.

-- 
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/pull/1465#discussion_r196957444

---

From: Mike Bishop <[email-masked]>
Date: Wed, 20 Jun 2018 15:07:34 -0700

@MikeBishop pushed 1 commit.

0d67554  Nick's reword

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1465/files/eda401101ae367fc840dc5f38c33aef616f6a99d..0d675544aaa5263bbfa2c0a3e1879e18dc71200e

---

From: Mike Bishop <[email-masked]>
Date: Wed, 20 Jun 2018 15:12:22 -0700

The fields are:
 
+Sequence:
+

The alternative being -2, -1, and starting from 0.  I think the logic there is the principle that we should try to avoid there being invalid values, and 0/1 would be invalid values still present in the frame.  If the frame can carry a 0, then 0 should be the first value value.

-- 
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/pull/1465#discussion_r196958757

---

From: Mike Bishop <[email-masked]>
Date: Wed, 20 Jun 2018 15:14:57 -0700

The fields are:
 
+Sequence:
+

This also creates an odd situation in that SPA prompts the client to probe, but the server won't have a corresponding CID at that sequence number, so it will have to use the first CID the client issued to it -- *if* the client issues one with/before the probe! -- which will force the client to advance again.

-- 
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/pull/1465#discussion_r196959300

---

From: Nick Banks <[email-masked]>
Date: Thu, 21 Jun 2018 06:27:02 -0700

The fields are:
 
+Sequence:
+

Maybe we have some weird special case, and have handshake and SPA are both considered `0`? I understand and agree that all values should be valid, but I just really don't like the idea of a negative number if we don't absolutely need it.

-- 
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/pull/1465#discussion_r197131356

---

From: Martin Thomson <[email-masked]>
Date: Thu, 21 Jun 2018 17:43:38 -0700

martinthomson commented on this pull request.

Yeah, this is a little tricky.

Perhaps
... on only one local address.  An endpoint MUST use a connection ID with a higher sequence number if it changes to using a different local address or network interface.  Once an endpoint has used a connection ID for packets sent from a given local address, they MUST NOT use a connection ID with a lower sequence number with that address.

 The fields are:
 
+Sequence:
+

There can be very many connection IDs during the handshake with this new Retry packet, so it's all special casing here.  Start at 2^16-N if you feel compelled to track things this way.

>  endpoint MUST NOT send additional packets until a NEW_CONNECTION_ID frame is
-received.
+received.  However, an implementation need not stop sending packets due to a gap
+in sequence numbers; it simply advances to the next currently-available
+connection ID it has received.  Connection IDs with earlier sequence numbers
+which arrive later MAY be retained for use on other local addresses or
+discarded.

OMG wall of text :)

When this happens, it's probably cause to create a new section.

FWIW, I like the idea that once you use a connection ID on a given interface, you can't use a lower-numbered one.  That could extend to responses.  Once you see a connection ID on a given tuple, then you can't use a lower-numbered one.  That leads to some simple rules:

When you use a new interface/address you MUST use of a new connection ID.
When you use a new connection ID, you MUST use one with a higher sequence number than you have ever used before.
You MUST NOT use a connection ID with a lower sequence number than you have either sent or received on that path.

Formulating the text around that is what we need.

Or, create a new section on connection ID use along the lines I describe below and cite that instead.

-- 
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/pull/1465#pullrequestreview-131035960

---

From: Mike Bishop <[email-masked]>
Date: Fri, 22 Jun 2018 10:55:57 -0700

ef8abfb  New CID section

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1465/files/0d675544aaa5263bbfa2c0a3e1879e18dc71200e..ef8abfb7393adb6a050d46e26ed23c48da12e083

---

From: Mike Bishop <[email-masked]>
Date: Fri, 22 Jun 2018 10:56:28 -0700

Moved to a separate section.  Doesn't actually change the line count any, but hopefully it's clearer.

-- 
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/pull/1465#issuecomment-399526404

---

From: Mike Bishop <[email-masked]>
Date: Fri, 22 Jun 2018 11:03:17 -0700

The fields are:
 
+Sequence:
+

What if we just eliminate this statement and let it be implementation-local?  The new text I added to the CID section says that "The series of
connection IDs issued by an endpoint is ordered, with the final connection ID
selected during the handshake coming first."

We could also fix this by removing the CID from SPA and simply saying that the server needs to send the client a CID it can use for the probe pretty promptly if it wants the client to do so.

-- 
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/pull/1465#discussion_r197525078

---

From: Martin Thomson <[email-masked]>
Date: Sun, 24 Jun 2018 16:40:56 -0700

The fields are:
 
+Sequence:
+

I don't think that would help with the suggestion in #1468.  Insisting on a fixed starting point ensures that you can do things like matching.

Removing the connection ID from the preferred address would make it harder to get that right because you then need to wait for a NEW_CONNECTION_ID frame before migrating.

-- 
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/pull/1465#discussion_r197656872

---

From: Martin Thomson <[email-masked]>
Date: Sun, 24 Jun 2018 17:27:08 -0700

Not 100% sure about the organization here, but the text is definitely worth having.  We definitely need to do some reorganizing of the document real soon now, so I'm not going to stress about where text goes.

> +selected during the handshake coming first.  Additional connection IDs are
+provided using the NEW_CONNECTION_ID frame ({{frame-new-connection-id}}), each
+with a specified sequence number.  The series of connection IDs issued SHOULD be
+contiguous, but might not appear to be upon receipt due to reordering or loss.
+
+Each connection ID MUST be used on only one local address. When packets are sent
+for the first time on a new local address, a new connection ID MUST be used with
+a higher sequence number than any connection ID previously used on any local
+address.  At any time, an endpoint MAY change to a new connection ID on a local
+address already in use.
+
+An endpoint MUST NOT send packets with a connection ID which has a lower
+sequence number than the highest sequence number of any connection ID ever sent
+or received on that local address.
+
+Implementations SHOULD ensure that peers have a connection ID with a matching

If this isn't MUST, then the above MUST NOT will just result in broken connections.

> +series of connection IDs over the lifetime of a connection. The series of
+connection IDs issued by an endpoint is ordered, with the final connection ID
+selected during the handshake coming first.  Additional connection IDs are
+provided using the NEW_CONNECTION_ID frame ({{frame-new-connection-id}}), each
+with a specified sequence number.  The series of connection IDs issued SHOULD be
+contiguous, but might not appear to be upon receipt due to reordering or loss.
+
+Each connection ID MUST be used on only one local address. When packets are sent
+for the first time on a new local address, a new connection ID MUST be used with
+a higher sequence number than any connection ID previously used on any local
+address.  At any time, an endpoint MAY change to a new connection ID on a local
+address already in use.
+
+An endpoint MUST NOT send packets with a connection ID which has a lower
+sequence number than the highest sequence number of any connection ID ever sent
+or received on that local address.

This is going to be hard to understand.  It's precise, but I think that we might provide a little more help.  Something like "This guarantees that when an endpoint migrates to a new path the packets sent on that path use new connection IDs in both directions." 

I don't know how to say this, but it seems like it might be worth adding: "Note: A connection ID MUST NOT include an unprotected encoding of the associated sequence number.  Endpoints need to be able to recover the sequence number associated with each connection ID they provide without relying on information available to the recipient of the connection ID.  A connection ID that encodes an unencrypted sequence number could be used to correlate connection IDs across network paths."

-- 
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/pull/1465#pullrequestreview-131442400

---

From: Mike Bishop <[email-masked]>
Date: Tue, 26 Jun 2018 18:03:42 +0000 (UTC)

But the trade-off is that lost packets can cause a peer to appear to violate this temporarily, so it's not realistically enforceable by a peer.  You can't "MUST ensure" something has arrived on the other side, only detect whether it has or not.  And the connection doesn't actually break; the peer will have to advance to a higher-order CID, which will force the endpoint to move off of the one that doesn't have a match (assuming it still hasn't arrived).

Actually, what a smart implementation could do is to bundle the NEW_CONNECTION_ID frame with the corresponding CID in every packet between when it changes to a new CID until *something* gets ACK'd.

-- 
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/pull/1465#discussion_r198244528

---

From: Mike Bishop <[email-masked]>
Date: Tue, 26 Jun 2018 11:10:30 -0700

Good point.  I tried to put it mid-discussion, but it didn't flow, so right now it's tucked at the end.  Editorial discretion welcome.

-- 
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/pull/1465#discussion_r198246753

---

From: Martin Thomson <[email-masked]>
Date: Tue, 26 Jun 2018 15:12:26 -0700

Merged #1465.

-- 
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/pull/1465#event-1702592712

---

From: Martin Thomson <[email-masked]>
Date: Tue, 26 Jun 2018 15:13:46 -0700

The fields are:
 
+Sequence:
+

I've merged this, so let's open an issue to close this out.

-- 
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/pull/1465#discussion_r198314183