Subject: [quicwg/base-drafts] Redefine outstanding (#299)

From: Martin Thomson <[email-masked]>
Date: Mon, 13 Feb 2017 17:09:38 -0800

In #288, I tried to keep the calculations intact.  This builds on that and changes the calculation to what we agreed on in the discussion on #286.

Closes #286.
You can view, comment on, or merge this pull request online at:

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

-- Commit Summary --

  * Random initial packet number
  * Rewrite text on packet numbers
  * Redefine the calculation for packet number size in terms of the range of outstanding numbers, not the count

-- File Changes --

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

-- Patch Links --

https://github.com/quicwg/base-drafts/pull/299.patch
https://github.com/quicwg/base-drafts/pull/299.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/299

---

From: ianswett <[email-masked]>
Date: Tue, 14 Feb 2017 07:47:05 -0800

ianswett commented on this pull request.

Two suggestions, but looks good.

-The complete packet number is a 64-bit unsigned number and is used as part of a
-cryptographic nonce for packet encryption.  To reduce the number of bits
-required to represent the packet number over the wire, at most 48 bits of the
-packet number are transmitted over the wire.  A QUIC endpoint MUST NOT reuse a
-complete packet number within the same connection (that is, under the same
-cryptographic keys).  If the total number of packets transmitted in this
-connection reaches 2^64 - 1, the sender MUST close the connection by sending a
+## Packet Numbers
+
+The packet number is a 64-bit unsigned number and is used as part of a
+cryptographic nonce for packet encryption.  Each endpoint maintains a separate
+packet number for sending and receiving.  The packet number for sending MUST
+increase by one after sending any packet.

At least one.

> @@ -646,10 +661,10 @@ that the client selected.
 
 When the client receives a Version Negotiation packet from the server, it should
 select an acceptable protocol version.  If the server lists an acceptable
-version, the client selects that version and resends all packets using that
-version. The resent packets MUST use new packet numbers.  These packets MUST
-continue to have the VERSION flag set and MUST include the new negotiated
-protocol version.
+version, the client selects that version and reattempts to created a connection
+using that version.  The client MUST update packet numbers when attempting to
+connect with the updated version.  Packets MUST continue to have the VERSION

I think "The client MUST update packet numbers when attempting to continue to connect with the updated version." is unclear.  How about  "The client must select a new initial random packet number.", since you mention including the version in the next sentence?

-- 
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/299#pullrequestreview-21782955

---

From: Igor Lubashev <[email-masked]>
Date: Wed, 15 Feb 2017 08:26:52 -0800

igorlord commented on this pull request.

>  CONNECTION_CLOSE frame with the error code QUIC_SEQUENCE_NUMBER_LIMIT_REACHED
-(connection termination is described in {{termination}}.)  For unambiguous
-reconstruction of the complete packet number by a receiver from the lower-order
-bits, a QUIC sender MUST NOT have more than 2^(packet_number_size - 2) in flight
-at any point in the connection.  In other words,
+(connection termination is described in {{termination}}.)
+
+To reduce the number of bits required to represent the packet number over the
+wire, only the least significant bits of the packet number are transmitted over
+the wire, up to 48 bits.  The actual packet number for each packet is
+reconstructed at the receiver based on the largest packet number received on a
+successfully authenticated packet.
+
+A packet number is decoded by finding the packet number value that is closest to
+the next expected packet.  The next expected packet is the highest received

> A packet number is decoded by finding the packet number value that is closest to the next expected packet.

The definition of "the next expected packet" is unclear.  If following example suggest that "the next expected" is "highest successfully authenticated packet + 1", this will not work in cases of occasional random packet delay.

Imagine we started with no loss/delay and few packets outstanding.  The sender would then use an 8-bit packet number to send packet 0x0a. Now that packet is very delayed, so the sender is increasing its packet number length to 16 bits and sends packet 0x010a.  If that delayed 0x0a packet finally arrives, the rule would say to treat 0x0a as 0x010a (since 0x0109 has been successfully decoded).

It seems that the receiver should extend packet numbers with higher order bits from the smallest unacknowledged packet instead of looking for closest numbers.

-- 
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/299#pullrequestreview-22043219

---

From: ianswett <[email-masked]>
Date: Wed, 15 Feb 2017 11:12:28 -0800

I believe, "highest successfully authenticated packet + 1" is the most robust definition, as well as how QUIC was originally intended to be specified.

Smallest unacknowledged packet is undefined.  A receiver has to give up on packets at some point, and though currently there is stop waiting(which is going away), even now the receiver must be able to unilaterally give up on waiting for packets, due to memory pressure/etc.  

The sender should budget enough packet number space to send any available CWND in addition to the space needed for current outstanding packets.  If it fails to do so, then the cost is slightly increased packet loss under relatively large scale(>256 packets at a minimum) reordering.

---

From: ianswett <[email-masked]>
Date: Wed, 15 Feb 2017 11:12:54 -0800

Comment for Igor.

-- 
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/299#issuecomment-280108359

---

From: Igor Lubashev <[email-masked]>
Date: Wed, 15 Feb 2017 12:36:25 -0800

> Smallest unacknowledged packet is undefined. A receiver has to give up on packets at some point, [...]

By "smallest unacknowledged packet" I meant the "Smallest unacknowledged packet that has not been marked as lost (see {{QUIC-RECOVERY}})".  I was trying to be brief but caused some confusion.

> The sender should budget enough packet number space to send any available CWND in addition to the space needed for current outstanding packets.

That would be an alternative way of solving this -- to always assume that you may need to distinctly address a large number of packets, even if right now you have few packets on the wire.  I am afraid that this defeats the purpose of variable-length packet numbers.  If you must always be ready for the worst case of packet loss/delay, you must always use the max possible packet number length for your connection.

Instead I am proposing that to each incoming packet number, the receiver alway prepends missing high-order bits from the "smallest unacknowledged packet that has not been marked as lost (i.e. still waited-for) (see {{QUIC-RECOVERY}})".  This is very easy to implement and solves the problem.

---

From: ianswett <[email-masked]>
Date: Wed, 15 Feb 2017 13:03:29 -0800

Loss recovery is implemented on the sender side, not the receiver side, so the receiver would not know what the smallest unacknowledged packet that has not been marked as lost is.

---

From: Igor Lubashev <[email-masked]>
Date: Wed, 15 Feb 2017 13:19:42 -0800

Receiver would still need logic to stop reporting missing packets in ACKs at some point.  STOPWAITING was the mechanism for Sender to notify the Receiver of this. W/o STOPWAITING there would be some alternative mechanism (based on the number of packets, rtt estimate vs elapsed time since receipt of a packet with a higher number, etc.). It could feed from the same algorithm.

Anyway, I am open to any other reasonable specification that works for delayed packets.

---

From: ianswett <[email-masked]>
Date: Wed, 15 Feb 2017 13:31:09 -0800

The smallest packet a receiver is waiting for is relatively well defined, but I don't think it's what we want.  The goal of latching to the largest packet is to favor forward progress over handling unlimited reordering.  Otherwise a receiver may never give up on waiting for a packet, and the sender won't know that, causing issues.  Whereas the sender knows the largest packet the receiver has acked.

The sender has all the information to decide when it sends a packet how large the packet number space needs to be.  When coming out of quiescence, it needs to make the packet number slightly larger than otherwise necessary to accommodate large scale reordering, but that's a transitory issue and easy to implement.

---

From: janaiyengar <[email-masked]>
Date: Thu, 16 Feb 2017 22:29:00 -0800

janaiyengar commented on this pull request.

I think this PR needs to be rebased.

-- 
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/299#pullrequestreview-22429787

---

From: Martin Thomson <[email-masked]>
Date: Fri, 17 Feb 2017 00:53:02 -0800

Rebased.  De-conflicting multiple in-flight pull requests is hard.

-- 
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/299#issuecomment-280591973

---

From: Igor Lubashev <[email-masked]>
Date: Fri, 17 Feb 2017 06:10:59 -0800

I see. So you are worried that in the absence of STOPWAITING, the Sender may decide that packet 10  has been lost, and not consider it outstanding, and use short packet numbers; while the Receiver is still waiting for packet 10.

Maybe I missed it in the updated spec, but I thought that  the Receiver will keep mentioning packets it is still waiting for in Acks. If that's not true, it makes sense to keep the current behavior.

-- 
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/299#discussion_r101763148

---

From: janaiyengar <[email-masked]>
Date: Fri, 17 Feb 2017 09:41:32 -0800

janaiyengar approved this pull request.

-- 
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/299#pullrequestreview-22550940

---

From: janaiyengar <[email-masked]>
Date: Fri, 17 Feb 2017 09:41:37 -0800

Merged #299.

-- 
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/299#event-967304517