Subject: [quicwg/base-drafts] Persistent congestion pseudocode to match text (#4010)

From: Martin Thomson <[email-masked]>
Date: Mon, 17 Aug 2020 18:50:28 -0700

This adds a new variable `first_rtt_sample` that records when the first
RTT was recorded.  This variable is used to avoid declaring persistent
congestion based on packets that were sent prior to this time.

Note that I removed the lame check in `InPersistentCongestion`.  This
avoids the implication that you need to propagate a signal that says
&quot;this is the first RTT sample&quot; all the way from the ACK handling code.
That signal is now propagated using the new variable.

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

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

-- Commit Summary --

  * Persistent congestion pseudocode to match text

-- File Changes --

    M draft-ietf-quic-recovery.md (22)

-- Patch Links --

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

---

From: Marten Seemann <[email-masked]>
Date: Mon, 17 Aug 2020 20:23:20 -0700

@marten-seemann requested changes on this pull request.

> @@ -1514,6 +1517,7 @@ variables as follows:
    bytes_in_flight = 0
    congestion_recovery_start_time = 0
    ssthresh = infinite
+   first_rtt_sample = never

We use 0 to initialize the other time variables.

>       pto = smoothed_rtt + max(4 * rttvar, kGranularity) +
        max_ack_delay
-     congestion_period = pto * kPersistentCongestionThreshold
+     pc_period = pto * kPersistentCongestionThreshold
+
+     // Only look for persistent congestion if the period
+     // starts after getting the first RTT sample.
+     assert(first_rtt_sample is not never)
+     if (largest_lost.time_sent - pc_period > first_rtt_sample):

```suggestion
     if (smallest_lost.time_sent - pc_period > first_rtt_sample):
```

-- 
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/4010#pullrequestreview-468964519

---

From: Martin Thomson <[email-masked]>
Date: Mon, 17 Aug 2020 21:04:11 -0700

@martinthomson pushed 1 commit.

033500d3fa15d3bf2649fb15217783bde9ed95e0  0 means not set

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/4010/files/c036ffa4e021a86a7d8f611a527721fd6e01f593..033500d3fa15d3bf2649fb15217783bde9ed95e0

---

From: Martin Thomson <[email-masked]>
Date: Mon, 17 Aug 2020 21:37:09 -0700

@martinthomson commented on this pull request.

    bytes_in_flight = 0

Yeah, but that means understanding that 0 is not a valid time, and I don't know if that is true.  But I guess that is the convention, so I'll fix it.

        max_ack_delay

`largest_lost` is the name of the variable we have.  This says that the span of length pc_period that ends at the time that the largest lost was sent must start after we first got an RTT sample.

-- 
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/4010#discussion_r471900059

---

From: Martin Thomson <[email-masked]>
Date: Mon, 17 Aug 2020 21:40:21 -0700

max_ack_delay

FWIW, this is AllPacketsLost is not a fair representation of the algorithm in the latest PR.  Only the largest ack-eliciting packet is relevant, and the function needs to ensure that it only considers the first ack-eliciting packet.  But I guess we're abstracting over much of that.

-- 
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/4010#discussion_r471909397

---

From: ianswett <[email-masked]>
Date: Tue, 18 Aug 2020 10:28:16 -0700

@ianswett commented on this pull request.

        max_ack_delay

Yes, we're glossing over a few implementation details with AreAllPacketsLost() below, but I think this is detailed enough.

-- 
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/4010#discussion_r472362793

---

From: ianswett <[email-masked]>
Date: Tue, 18 Aug 2020 17:28:31 +0000 (UTC)

@ianswett approved this pull request.

I was thinking @janaiyengar was going to fix this in #3961, but that PR is large enough so I'm happy to have a separate fix.

-- 
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/4010#pullrequestreview-469672540

---

From: Jana Iyengar <[email-masked]>
Date: Tue, 18 Aug 2020 14:27:57 -0700

@janaiyengar commented on this pull request.

>       // Determine if all packets in the time period before the
      // largest newly lost packet, including the edges and
      // across all packet number spaces, are marked lost.
-     return AreAllPacketsLost(largest_lost, congestion_period)
+     return AreAllPacketsLost(largest_lost, pc_period)

This needs to change. The idea now is that there's a window of packet loss that is pc_period long in time. The comment up there needs to change too.

How about:
```
// Determine if all packets were lost in a period long enough
// to declare persistent congestion.
return AreAllPacketsLostInPeriod(lost_packets, pc_period)
```

You'll have to change the parameter to `InPersistentCongestion()` to be `lost_packets`, but that's easily done, since this function is called from `OnPacketsLost()`.

-- 
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/4010#pullrequestreview-469843082

---

From: ianswett <[email-masked]>
Date: Tue, 18 Aug 2020 14:30:50 -0700

Because lost_packets is from a single PN space, I believe passing it in is insufficient and potentially misleading.

-- 
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/4010#discussion_r472504587

---

From: Jana Iyengar <[email-masked]>
Date: Tue, 18 Aug 2020 14:31:11 -0700

Let's do this here instead of the other unicorning PR.

        max_ack_delay

See my comment below. You can change the param here to lost_packets. I would suggest the following:

We could make `AreAllPacketsLostInPeriod()` return the starting point of the persistent congestion period, and use that up here. Meaning call that function first and then check to see if that period starts after first_rtt_sample.

-- 
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/4010#pullrequestreview-469844711

---

From: Martin Thomson <[email-masked]>
Date: Tue, 18 Aug 2020 17:57:09 -0700

f14448146246f4296e9853f0969aaae7279f3c6c  Fix the AllPacketsLost thing too

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/4010/files/033500d3fa15d3bf2649fb15217783bde9ed95e0..f14448146246f4296e9853f0969aaae7279f3c6c

---

From: Martin Thomson <[email-masked]>
Date: Tue, 18 Aug 2020 18:06:40 -0700

2c029b3b8e4ad14f98c24c2b1a2b4ea4285886db  Merge branch 'master' into pc-starts-now

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/4010/files/f14448146246f4296e9853f0969aaae7279f3c6c..2c029b3b8e4ad14f98c24c2b1a2b4ea4285886db

---

From: Martin Thomson <[email-masked]>
Date: Tue, 18 Aug 2020 18:08:44 -0700

Just so the change is logged for everyone, I've completely rewritten the `InPersistentCongestion` function based on feedback.  `AreAllPacketsLost` is no longer.

If anyone implements this directly, the (CPU) performance will be terrible, but I believe that it matches the text better.  Anyone interested in how I think this might be implemented without deviating too much from the pseudocode can look at the commit comments, but there are probably much better approaches.

-- 
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/4010#issuecomment-675794032

---

From: Marten Seemann <[email-masked]>
Date: Tue, 18 Aug 2020 21:51:24 -0700

@marten-seemann commented on this pull request.

> @@ -1605,26 +1619,36 @@ ProcessECN(ack, pn_space):
 Invoked when DetectAndRemoveLostPackets deems packets lost.
 
 ~~~
-InPersistentCongestion(largest_lost):
-  // Persistent congestion cannot be declared on the
-  // first RTT sample.
-  if (is first RTT sample):
-    return false
+InPersistentCongestion(lost_packets):
+  // Consider lost packets across all packet number spaces.
+  pc_lost += lost_packets

```suggestion
  pc_lost.append(lost_packets)
```

-- 
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/4010#pullrequestreview-470121881

---

From: Martin Thomson <[email-masked]>
Date: Tue, 18 Aug 2020 22:55:39 -0700

e1fc8a9369c83715606cd9efe459fe774ab34624  `.append()` is clear than `+=`

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/4010/files/2c029b3b8e4ad14f98c24c2b1a2b4ea4285886db..e1fc8a9369c83715606cd9efe459fe774ab34624

---

From: Kazu Yamamoto <[email-masked]>
Date: Wed, 19 Aug 2020 23:47:16 -0700

@kazu-yamamoto commented on this pull request.

-  if (is first RTT sample):
-    return false
+InPersistentCongestion(lost_packets):
+  // Consider lost packets across all packet number spaces.
+  pc_lost.append(lost_packets)
+
+  // Disregard packets sent prior to getting an RTT sample.
+  assert(first_rtt_sample != 0)
+  for lost in pc_lost:
+    if lost.time_sent <= first_rtt_sample:
+      pc_lost.remove(lost)
+
+  // Find the largest contiguous set of lost packets that
+  // starts and ends with an ack-eliciting packet.
+  (first, last) = FindLargestContiguousLoss(pc_lost)

I cannot imagine how to detect contiguity for all packet spaces.

-- 
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/4010#pullrequestreview-471289880

---

From: Kazu Yamamoto <[email-masked]>
Date: Wed, 19 Aug 2020 23:48:10 -0700

max_ack_delay
-  congestion_period = pto * kPersistentCongestionThreshold
-  // Determine if all packets in the time period before the
-  // largest newly lost packet, including the edges and
-  // across all packet number spaces, are marked lost.
-  return AreAllPacketsLost(largest_lost, congestion_period)
+  pc_period = pto * kPersistentCongestionThreshold
+  return (last.time_sent - first.time_sent) > pc_period

>From the recovery draft, it is not certain which is correct, `>` or `>=`.

-- 
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/4010#pullrequestreview-471290376

---

From: Kazu Yamamoto <[email-masked]>
Date: Thu, 20 Aug 2020 00:10:47 -0700

max_ack_delay

#3961 says "exceed". So, `>` should be correct.

-- 
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/4010#discussion_r473677956

---

From: Kazu Yamamoto <[email-masked]>
Date: Fri, 21 Aug 2020 13:06:41 -0700

@martinthomson I have implemented this in Haskell quic.

1) With this pseudocode, *global* sequence number (unique and contiguous across the packet number space) is necessary to find the largest contiguity. In Haskell implementation, no additional field is necessary because packet numbers are unique globally.

2) It seems to me that `pc_lost` is over engineering if it is used only to detect persistent congestion. However, this structure can be also used to prevent spurious retransmission due to reordering, pointed out @kazuho. For example, if an endpoint receives ACK 1,3 and then ACK 2, the current pseudo code interprets that packet 2 is lost. If we use `pc_lost` as lost packet candicates and delay the decision, this issue can be resolved. So, we can justify the introduction of `pc_lost`. :-)

3) `pc_lost` consumes much resource because it is cleared only when persistent congestion happens. But, if we use `pc_lost` as lost packet candidates, it should be reduced when retransmission. Since the pseudocode does not describe how retransmission is implemented, we can left how to reduce `pc_lost` as implementation dependent and need not to implement it in this pseudocode.

-- 
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/4010#issuecomment-678469958

---

From: Martin Thomson <[email-masked]>
Date: Sun, 23 Aug 2020 20:42:18 -0700

Thanks for reviewing @kazu-yamamoto.

Regarding the global sequence space, I figure that you can do this without a global sequence number in other ways.  For instance, you could track the sending time of all outstanding packets or you could enter all outstanding packets into a linked list, either of which allows you to establish a total ordering.  (In the absence of a single sequence number space, I decided not to do a total global ordering on the basis that detecting persistent congestion during the handshake was not so important.)

For the other points, the goal of this is to explain above any requirement to be performant.  You can, as I suggest in commit comments, drop pc_lost more often to limit the overhead.  It is a fair bit more complex to fit into the spec though.

-- 
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/4010#issuecomment-678887472

---

From: Kazu Yamamoto <[email-masked]>
Date: Sun, 23 Aug 2020 22:27:48 -0700

> Regarding the global sequence space, I figure that you can do this without a global sequence number in other ways. For instance, you could track the sending time of all outstanding packets or you could enter all outstanding packets into a linked list, either of which allows you to establish a total ordering. 

Yes. I think that this is what @kazuho explains in https://github.com/quicwg/base-drafts/issues/3939#issuecomment-662808337.

(It seems to me that this assumes entries can be *marked* to detect *contiguity*. But it is very hard to implement marking in Haskell. Marking is a destructive operation which is not allowed in purely functional data structure.)

What I pointed out is that there is no such data structure in the current pseudocode. (`sent_packets` is separated into three.) Probably, *global* sequence number is one of the easiest approaches.

-- 
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/4010#issuecomment-678911640

---

From: mjoras <[email-masked]>
Date: Mon, 24 Aug 2020 10:15:50 -0700

> Regarding the global sequence space, I figure that you can do this without a global sequence number in other ways. For instance, you could track the sending time of all outstanding packets or you c…

Mvfst has always stored outstanding packets in a single sequence container. It makes the ACK handling code a little bit more complicated since we have multiple PN spaces in a single sequence, but it makes things like this nominally easier to implement. That being said there's still considerable complexity (and as @martinthomson says, likely CPU cost). I'm very curious how many people are going to bother implementing this rather than just throwing up our hands and not declaring persistent congestion across PN spaces.

Probably having the pseudocode is the right thing to do though, and as always implementations will do what they think is actually necessary.

-- 
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/4010#issuecomment-679256317

---

From: Jana Iyengar <[email-masked]>
Date: Mon, 24 Aug 2020 18:48:59 -0700

~~~

Perhaps suggest that pc_lost could be time-indexed instead of pn-indexed

You want the (first, last) around the largest _period_ of loss, not the largest set of lost packets. Perhaps `FindLargestLossPeriod` ?

@kazu-yamamoto : you can use time indexing for this purpose.

-- 
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/4010#pullrequestreview-474037338

---

From: Martin Thomson <[email-masked]>
Date: Mon, 24 Aug 2020 18:54:56 -0700

d02b6a07b89ebb6b6da5af44cefd4bea608fa3ff  Rename and use a direct result

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/4010/files/e1fc8a9369c83715606cd9efe459fe774ab34624..d02b6a07b89ebb6b6da5af44cefd4bea608fa3ff

---

From: Martin Thomson <[email-masked]>
Date: Mon, 24 Aug 2020 18:57:00 -0700

58b14118236476b3ef193b958e672cc292a4778b  Add an implementation tip

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/4010/files/d02b6a07b89ebb6b6da5af44cefd4bea608fa3ff..58b14118236476b3ef193b958e672cc292a4778b

---

From: Jana Iyengar <[email-masked]>
Date: Mon, 24 Aug 2020 18:58:20 -0700

@janaiyengar approved this pull request.

Looks great, thank you for working through the review!

-- 
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/4010#pullrequestreview-474040857

---

From: Jana Iyengar <[email-masked]>
Date: Mon, 24 Aug 2020 18:59:22 -0700

I think we should wait for #3961 before merging 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/pull/4010#issuecomment-679457021

---

From: Kazu Yamamoto <[email-masked]>
Date: Mon, 24 Aug 2020 19:55:45 -0700

> I'm very curious how many people are going to bother implementing this rather than just throwing up our hands and not declaring persistent congestion across PN spaces.

@mjoras Please read https://github.com/quicwg/base-drafts/issues/3972#issuecomment-666040269

-- 
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/4010#issuecomment-679473045

---

From: Jana Iyengar <[email-masked]>
Date: Wed, 26 Aug 2020 14:29:25 -0700

@mjoras: Really, this is only during the handshake that multiple pn spaces even matters, so in terms of implementations or impact, I think this matters little. Many use single PN space -- we do too -- so implementing this is fairly trivial, but because the pseudo code is being more explicit in the separation of PN spaces, this particular piece is a bit tricky.

-- 
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/4010#issuecomment-681133852

---

From: ianswett <[email-masked]>
Date: Mon, 31 Aug 2020 14:48:47 -0700

@ianswett requested changes on this pull request.

This is likely good, but I'm worried this is becoming overly complex and implementation dependent.

I'd actually suggest we remove pseudocode for InPersistentCongestion() and leave it up to implementers.

-- 
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/4010#pullrequestreview-478978660