Subject: [quicwg/base-drafts] Define AreAllPacketsLost() (#3290)

From: Alessandro Ghedini <[email-masked]>
Date: Fri, 06 Dec 2019 09:30:14 -0800

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

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

-- Commit Summary --

  * Define AreAllPacketsLost()

-- File Changes --

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

-- Patch Links --

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

---

From: Alessandro Ghedini <[email-masked]>
Date: Fri, 06 Dec 2019 09:34:19 -0800

@ghedo pushed 1 commit.

1774a154dfc804130e703342bdab757f0c038f5f  Fix formatting of some pseudo-code

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3290/files/c01acf9469f5729c882ec987adc3df69f79e2a97..1774a154dfc804130e703342bdab757f0c038f5f

---

From: Alessandro Ghedini <[email-masked]>
Date: Fri, 06 Dec 2019 09:35:04 -0800

Also added the formatting fix from https://github.com/quicwg/base-drafts/pull/3289

-- 
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/3290#issuecomment-562667109

---

From: ianswett <[email-masked]>
Date: Fri, 06 Dec 2019 09:37:09 -0800

ianswett commented on this pull request.

>       pto = smoothed_rtt + max(4 * rttvar, kGranularity) +
        max_ack_delay
      congestion_period = pto * kPersistentCongestionThreshold
      // Determine if all packets in the time period before the
      // newest lost packet, including the edges, are marked
      // lost
-     return AreAllPacketsLost(largest_lost_packet,
-                              congestion_period)
+     return congestion_period >
+       largest_lost_packet.time_sent - earliest_lost_packet.time_sent

I think it's possible a packet is acked between earliest and largest, so I believe you may need to pass in lost_packets and check that they're contiguous.  Then you can do an early return if no packets are lost or if they're not contiguous.

ie: 
all_packets_lost =  acket_packets.length() ==
   (acked_packets.last().packet_number - acked_packets.first().packet_number - 1)

-- 
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/3290#pullrequestreview-328353030

---

From: Alessandro Ghedini <[email-masked]>
Date: Fri, 06 Dec 2019 09:49:04 -0800

@ghedo pushed 1 commit.

5592e9825ac843170e0ed5869a99af73047f78d9  Also check that lost packets are contiguous

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3290/files/1774a154dfc804130e703342bdab757f0c038f5f..5592e9825ac843170e0ed5869a99af73047f78d9

---

From: Alessandro Ghedini <[email-masked]>
Date: Fri, 06 Dec 2019 09:49:46 -0800

ghedo commented on this pull request.

        max_ack_delay

Done I think, though did `s/acked_packets/lost_packets/` (also got a bit creative with the indentation).

-- 
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/3290#discussion_r354954864

---

From: ianswett <[email-masked]>
Date: Fri, 06 Dec 2019 09:50:58 -0800

max_ack_delay

Sorry, I meant 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/3290#discussion_r354955334

---

From: Alessandro Ghedini <[email-masked]>
Date: Fri, 06 Dec 2019 09:53:05 -0800

max_ack_delay

Also, is the `- 1` really needed here?

-- 
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/3290#discussion_r354956194

---

From: ianswett <[email-masked]>
Date: Fri, 06 Dec 2019 09:53:53 -0800

Almost there I think.

> @@ -1407,15 +1409,23 @@ Invoked when an ACK frame with an ECN section is received from the peer.
 Invoked from DetectLostPackets when packets are deemed lost.
 
 ~~~
-   InPersistentCongestion(largest_lost_packet):
+   InPersistentCongestion(lost_packets):

I'd add an early return at the very beginning to check if lost_packets is false to avoid questions about whether first() and last() are properly defined.

      // newest lost packet, including the edges, are marked
      // lost
-     return AreAllPacketsLost(largest_lost_packet,
-                              congestion_period)
+     all_packets_lost =
+       lost_packets.length() == (lost_packets.last().packet_number -
+                                 lost_packets.first().packet_number - 1)

My mistake on the example, this should be:

```suggestion
                                 lost_packets.first().packet_number + 1)
```

-- 
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/3290#pullrequestreview-328360642

---

From: ianswett <[email-masked]>
Date: Fri, 06 Dec 2019 09:57:06 -0800

max_ack_delay

+1 is.  

Think through the example where 0, 1 and 2 are lost.  lost_packets has length 3.  But 2 - 0 = 2, so you need to add 1.

-- 
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/3290#discussion_r354957810

---

From: Alessandro Ghedini <[email-masked]>
Date: Fri, 06 Dec 2019 09:59:43 -0800

~~~

I think this is already checked before calling `OnPacketsLost()`?
```
  if (!lost_packets.empty()):
    OnPacketsLost(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/3290#discussion_r354958934

---

From: Alessandro Ghedini <[email-masked]>
Date: Fri, 06 Dec 2019 10:01:04 -0800

max_ack_delay

But also, now that I think about it, `lost_packets` only contains lost in-flight packets right? So checking `lost_packets.length()` against the packet number difference might fail because of other lost but not in-flight packets adding gaps, is this a problem?

-- 
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/3290#discussion_r354959482

---

From: Alessandro Ghedini <[email-masked]>
Date: Fri, 06 Dec 2019 10:01:40 -0800

@ghedo pushed 1 commit.

0dacc7ad81c1388984183e5399bf92678ee74d1c  Also check that lost packets are contiguous

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3290/files/5592e9825ac843170e0ed5869a99af73047f78d9..0dacc7ad81c1388984183e5399bf92678ee74d1c

---

From: Alessandro Ghedini <[email-masked]>
Date: Fri, 06 Dec 2019 10:01:53 -0800

Fixed.

-- 
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/3290#discussion_r354959785

---

From: ianswett <[email-masked]>
Date: Fri, 06 Dec 2019 10:28:28 -0800

~~~

Agreed, thanks.

-- 
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/3290#discussion_r354970226

---

From: Nick Banks <[email-masked]>
Date: Fri, 06 Dec 2019 10:37:44 -0800

nibanks commented on this pull request.

+       lost_packets.length() == (lost_packets.last().packet_number -
+                                 lost_packets.first().packet_number + 1)

This assumes you don't send with gaps. I personally don't think we need complete psuedocode here. I think text should be enough. I feel like this logic could be very dependent on the implementation.

-- 
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/3290#pullrequestreview-328384446

---

From: ianswett <[email-masked]>
Date: Fri, 06 Dec 2019 10:40:47 -0800

max_ack_delay

Good point, that is a problem.  I think that was why we resorted to a helper method to begin with.

For a packet between smallest and largest to be acknowledged AND smallest not previously declared lost, I believe it must occur in the ACK frame that caused smallest and largest to be lost.  Otherwise the time threshold would have kicked in long before persistent congestion.

Therefore, if the largest lost packet is smaller than the earliest newly acknowledged packet, we can guarantee the lost packets are contiguous.  However, then we do not trigger persistent congestion if a packet sent at the very beginning of the congestion period is acknowledged in a long delayed ACK, and at the same time a much later packet is ACKed.  I'm not sure we care about capturing that case, but it's worth considering.

If we were ok with more complex code, we could loop over all newly acked packets and ensure none were between the smallest and largest 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/3290#discussion_r354975276

---

From: Junho Choi <[email-masked]>
Date: Fri, 06 Dec 2019 11:43:16 -0800

junhochoi commented on this pull request.

Better to have `>=`, not `==`?

-- 
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/3290#pullrequestreview-328418630

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Fri, 06 Dec 2019 17:36:08 -0800

tatsuhiro-t commented on this pull request.

        max_ack_delay

Isn't it `congestion_period <= largest_lost_packet.time_sent - earliest_lost_packet.time_sent` because congestion_period is the threshold that defines duration of persistent congestion?

-- 
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/3290#discussion_r355089680

---

From: ianswett <[email-masked]>
Date: Mon, 09 Dec 2019 09:41:02 -0800

I'm tending to agree with @nibanks, I'm not sure there's anything we can add here which will meaningfully clarify the pseudocode without making it quite implementation dependent.

-- 
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/3290#discussion_r355587712

---

From: Jana Iyengar <[email-masked]>
Date: Mon, 09 Dec 2019 17:46:12 -0800

janaiyengar commented on this pull request.

Yes, this gets too detailed very fast, and I don't think more code is the answer. @ghedo: Is there more we can add to the comment above to help 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/3290#discussion_r355806983

---

From: Alessandro Ghedini <[email-masked]>
Date: Wed, 11 Dec 2019 05:13:14 -0800

IMO the text or the comment should at the very least include the points that were raised in this disucssion, otherwise we'll just keep revisiting this over and over, and discussions on GitHub really won't help implementers once the spec is final. Also, I think the slight restructuring of the pseudo-code, where `InPersistentCongestion()` takes the whole list of lost packets is also more helpful to clarify what the information needed to make the decision is.

I can look into making another PR to do that, while keeping `AreAllPacketsLost()` undefined, if no one else wants to try.

-- 
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/3290#discussion_r356590369