Subject: [quicwg/base-drafts] Fix to ECN section regarding validation (#2113)

From: Magnus Westerlund <[email-masked]>
Date: Tue, 11 Dec 2018 14:53:49 +0000 (UTC)

An issue with validation was identified. The first bullet of validation is intended to check so that the ECT code point (0 or 1) are not changed to the other. However, when an ACK includes new CE marks the comparison must deduct those CE marks to not wrongly report a mismatch. 

Also fixed a sentence indicating that is unclear about what is dropped. ECN field value of not-ect could rarely result in that the IP packet to be dropped. 
You can view, comment on, or merge this pull request online at:

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

-- Commit Summary --

  * Addressing issue that CE marks was not handled in per ECT type check.
  * Fixing one unclear sentence.

-- File Changes --

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

-- Patch Links --

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

---

From: mirjak <[email-masked]>
Date: Tue, 11 Dec 2018 15:43:26 +0000 (UTC)

I think it could actually be good to at one short sentence to each bulletpoint to explain what the test is checking for; e.g. as you said on slack "This is to ensure that packets sent as ECT(0) are not arriving as ECT(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/2113#issuecomment-446248746

---

From: Magnus Westerlund <[email-masked]>
Date: Tue, 11 Dec 2018 15:54:50 +0000 (UTC)

Yes, I think that is reasonable to clarify the intention here. I will add 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/2113#issuecomment-446253332

---

From: Magnus Westerlund <[email-masked]>
Date: Tue, 11 Dec 2018 08:12:41 -0800

@gloinul pushed 1 commit.

3a72fbd8afd182f7a025f991b47cb4776a89cbec  Clarifies puprose of the validation bullets.

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/2113/files/eb7c2c8c091b7e5c3a10e33d2f7eaf25223e6287..3a72fbd8afd182f7a025f991b47cb4776a89cbec

---

From: Magnus Westerlund <[email-masked]>
Date: Tue, 11 Dec 2018 08:22:12 -0800

3faded4e058926279280e83550c8c50de6b6173a  Added paragraph of conditions when the comparisons should not be performed.

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/2113/files/3a72fbd8afd182f7a025f991b47cb4776a89cbec..3faded4e058926279280e83550c8c50de6b6173a

---

From: Martin Thomson <[email-masked]>
Date: Tue, 11 Dec 2018 15:02:40 -0800

martinthomson commented on this pull request.

> @@ -3018,11 +3018,19 @@ elements on the network path, an endpoint verifies the following when an ACK
 frame is received:
 
 * The increase in ECT(0) and ECT(1) counters MUST be at least the number of QUIC
-  packets newly acknowledged that were sent with the corresponding codepoint.
+  packets newly acknowledged that were sent with the corresponding codepoint
+  minus the increase in the CE counter. Detects network remarking

```suggestion
  minus the increase in the CE counter. This detects network remarking
```

 * The total increase in ECT(0), ECT(1), and CE counters reported in the ACK
   frame MUST be at least the total number of QUIC packets newly acknowledged in
-  this ACK frame.
+  this ACK frame. Detects if the network remark ECT(0), ECT(1) or CE to

```suggestion
  this ACK frame. This detects if the network remark ECT(0), ECT(1) or CE to
```

 * The total increase in ECT(0), ECT(1), and CE counters reported in the ACK
   frame MUST be at least the total number of QUIC packets newly acknowledged in
-  this ACK frame.
+  this ACK frame. Detects if the network remark ECT(0), ECT(1) or CE to
+  Not-ECT.
+
+If a sender receives an ACK that contains no new acknowledgments, for example
+due to reordering of the ACKs, then ECN counter comparison SHOULD NOT be
+performed. Also if sender do not have state to determine if a particular PSN
+is newly acknowledge or not, then the comparison SHOULD NOT be performed.

I don't think that this is necessary.

The comparison still works if there are no newly acknowledged packets.

The last sentence is good.  If a packet is no longer being tracked, then it has the superposition of states.

If I'm in the rough...
```suggestion
is newly acknowledged or not, then the comparison SHOULD NOT be performed.
```

-- 
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/2113#pullrequestreview-183918102

---

From: Benjamin Saunders <[email-masked]>
Date: Tue, 11 Dec 2018 17:58:04 -0800

I think the verification procedure defined here still spuriously fails when the receiver sends a pair of ACK such that each ACK newly acknowledges at least one packet not acknowledged by the other (for example, due to an implementation aggressively limiting the number of ACK blocks sent), and the ACKs are reordered such when the sender receives them, it sees the one with higher ECN counters first. By my reading, the apparent reduction in ECN would cause verification to fail.

Ignoring ECN blocks from ACKs whose largest acked PN is not higher than that of every previous ACK would resolve this problem by ensuring that reordered ECN blocks are always ignored, and subsumes the "no new acknowledgements" test.

-- 
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/2113#issuecomment-446432740

---

From: Benjamin Saunders <[email-masked]>
Date: Tue, 11 Dec 2018 18:19:08 -0800

Ralith commented on this pull request.

It would also be helpful to briefly mention that the local reference count is maintained (by copying verified ECN blocks from ACKs?)

```suggestion
  this ACK frame. Detects if the network remarks ECT(0), ECT(1) or CE to
```

```suggestion
performed. If the sender does not have state to determine if a particular PSN
```

The implication here seems to be that an implementation should retain extra state to distinguish between a packet that is deemed lost but not yet acknowledged and a packet that was previously acknowledged. Is that intended?

If these two cases are instead conflated, e.g. by forgetting about sent packets once either acknowledged or deemed lost, then at worst the number of newly acknowledged packets in an ACK would sometimes be under-counted, and a verification with a higher rate of false positives seems preferable to going to extra effort to decide to skip verification outright.

-- 
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/2113#pullrequestreview-183985779

---

From: Magnus Westerlund <[email-masked]>
Date: Wed, 12 Dec 2018 02:39:24 -0800

e2b6303b78df8c5527d9a2f9f74369f0e64e69ee  Apply suggestions from code review

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/2113/files/3faded4e058926279280e83550c8c50de6b6173a..e2b6303b78df8c5527d9a2f9f74369f0e64e69ee

---

From: MikkelFJ <[email-masked]>
Date: Wed, 12 Dec 2018 02:43:56 -0800

mikkelfj commented on this pull request.

>    Not-ECT.
 
 If a sender receives an ACK that contains no new acknowledgments, for example
 due to reordering of the ACKs, then ECN counter comparison SHOULD NOT be
-performed. Also if sender do not have state to determine if a particular PSN
-is newly acknowledge or not, then the comparison SHOULD NOT be performed.
+performed. If the sender does not have state to determine if a particular PSN
+is newly acknowledged or not, then the comparison SHOULD NOT be performed.

Please explain PSN - is it Packet Serial Number? In that case "packet", "packet number", or "PN" is more aligned with the rest of the text, I suppose.

-- 
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/2113#pullrequestreview-184113328

---

From: ianswett <[email-masked]>
Date: Wed, 12 Dec 2018 02:46:59 -0800

ianswett commented on this pull request.

I think it's supposed to be packet sequence number?  But the text always uses packet number and abbreviates it to PN, so if that's what it is, it should be changed.

-- 
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/2113#discussion_r240964359

---

From: Magnus Westerlund <[email-masked]>
Date: Wed, 12 Dec 2018 02:47:33 -0800

gloinul commented on this pull request.

Partly, sender need to track if a packet has been acknowledged or not. But, my assumption is that the sender will have a window where such information will be discarded when likely not relevant anymore. So if everything has been ACKed up to PSN=48. Then cleaning up your state and discarding all below 48 is fine. When the reorderd ACK that indicate reception of PSN 44 and 45 can then be determined to be behind this window and ignored. The second sentence is trying to state that for this example case this is fine to do. 

-- 
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/2113#discussion_r240964555

---

From: Magnus Westerlund <[email-masked]>
Date: Wed, 12 Dec 2018 02:50:14 -0800

Sorry, yes I will try to use PN in my comments. 

-- 
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/2113#discussion_r240965429

---

From: Magnus Westerlund <[email-masked]>
Date: Wed, 12 Dec 2018 04:18:29 -0800

0a2edd0cfe63596f68d917f66693d93081a8bec7  Removed unnecessary restriction. Added notices that local reference counters needs to be updated as part of ACK processing. Some editorials.

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

---

From: Magnus Westerlund <[email-masked]>
Date: Wed, 12 Dec 2018 04:33:08 -0800

This uses packet number now. 

-- 
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/2113#discussion_r240996074

---

From: Lars Eggert <[email-masked]>
Date: Wed, 12 Dec 2018 06:59:16 -0800

larseggert commented on this pull request.

 * The total increase in ECT(0), ECT(1), and CE counters reported in the ACK
   frame MUST be at least the total number of QUIC packets newly acknowledged in
-  this ACK frame.
+  this ACK frame. This detects if the network changes ECT(0), ECT(1) or CE to
+  Not-ECT.
+
+If the sender does not have state to determine if a particular packet number is
+newly acknowledged or not, then the comparison SHOULD NOT be performed. By the

Is this really a SHOULD NOT? If the sender doesn't have that state, it **CANNOT** perform that check. That's not a 2119 keyword, unfortunately :-)

-- 
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/2113#pullrequestreview-184220206

---

From: Magnus Westerlund <[email-masked]>
Date: Wed, 12 Dec 2018 08:27:47 -0800

Okay, I will rewrite this as non 2119 terms basically stating to not perform the comparison. 

It is a bit like the formulation in RFC 3550: 
"Note that if R is zero, the
      percentage of senders is never greater than S/(S+R), and the
      implementation must avoid division by zero."

-- 
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/2113#discussion_r241086084

---

From: Magnus Westerlund <[email-masked]>
Date: Wed, 12 Dec 2018 08:48:02 -0800

Benjamin Saunders did point out that if one have ACKs with none overlapping ACK ranges and they get reordered there is still an issue with performing the comparison in some cases. Example:

Receiver sent: 
ACK:1  PN:1,2,3,4 ECT(0)=4, ECT(1)=0, CE=0
ACK:2  PN:5,6,7,8 ECT(0)=8, ECT(1)=0, CE=0
ACK:3  PN:9,10,11 ECT(0)=11, ECT(1)=0, CE=0

Sender receives:
ACK:1  PN:1,2,3,4 ECT(0)=4, ECT(1)=0, CE=0
ACK:3  PN:9,10,11 ECT(0)=11, ECT(1)=0, CE=0
ACK:2  PN:5,6,7,8 ECT(0)=8, ECT(1)=0, CE=0

Local Reference Counters: 0,0,0
1: Comparison ECT(0)_diff=4, Newly ACKed=4 (with ECT(0)) OK
Local Reference Counters: 4,0,0
3: Verification ECT(0)_diff=7, Newly ACKEd=3
Local Reference Counters: 7,0,0 (Based on ACKed packets)
Local Reference Counters: 11,0,0 (Latest Received ACK)

2: Verification ECT(0)_diff=1 or -3 (Based on ACKed, vs Latest Received).
Newly ACKed=4
Comparison fails if run.  

So the question is how to deal with this. From my perspective there are multiple implementation strategies that could solve this. So my question is should we mandate any particular or simply try to illustrate the issue. I think the most straight forward and which I don't so far sees any flaws with are:

- Don't perform verification with ACK frames that on arrivial is not highest PN seen. 

Opinions?

-- 
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/2113#issuecomment-446658001

---

From: Benjamin Saunders <[email-masked]>
Date: Wed, 12 Dec 2018 17:27:31 +0000 (UTC)

This reads to me like the comparison of the new ECN block to the local reference (i.e. the verification procedure) should not be performed if the ACK acknowledges any packets which are outside the window and hence are not guaranteed not to be new acknowledgements. Should it instead indicate that such an acknowledgement should not be counted towards new acknowledgements?

-- 
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/2113#discussion_r241110556

---

From: Magnus Westerlund <[email-masked]>
Date: Wed, 12 Dec 2018 17:33:15 +0000 (UTC)

43b6f677582ae0d917e759c7d002d69a174d64f2  Added text on dealing with reordered ACKs.

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/2113/files/0a2edd0cfe63596f68d917f66693d93081a8bec7..43b6f677582ae0d917e759c7d002d69a174d64f2

---

From: Magnus Westerlund <[email-masked]>
Date: Wed, 12 Dec 2018 17:33:46 +0000 (UTC)

So now there is a proposal for how resolve Benjamin's comment. Please 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/2113#issuecomment-446674375

---

From: Benjamin Saunders <[email-masked]>
Date: Wed, 12 Dec 2018 09:40:10 -0800

That addresses the issue, thanks!

 * The total increase in ECT(0), ECT(1), and CE counters reported in the ACK
   frame MUST be at least the total number of QUIC packets newly acknowledged in
-  this ACK frame.
+  this ACK frame. This detects if the network changes ECT(0), ECT(1) or CE to
+  Not-ECT.
+
+If the sender does not have state to determine if a particular packet number is
+newly acknowledged or not, then the verifications using this acknowledgement
+cannot be performed. If an acknowledgement arrive with a packet number that
+isn't the highest to arrived so far, i.e. some reordering has occured, then the
+verification may fail erronously. To prevent this the sender MUST NOT perform
+ECN verification using older acknwoeldgements. By the end of the verification

```suggestion
ECN verification using older acknowledgements. By the end of the verification
```

-- 
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/2113#pullrequestreview-184305206

---

From: Martin Thomson <[email-masked]>
Date: Wed, 12 Dec 2018 16:14:08 -0800

Yes, we should not validate (or increase the sender-side view of where the counters are) if the largest acknowledged packet does not increase.

-- 
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/2113#issuecomment-446793575

---

From: Martin Thomson <[email-masked]>
Date: Wed, 12 Dec 2018 22:35:24 -0800

> @@ -3018,11 +3018,23 @@ elements on the network path, an endpoint verifies the following when an ACK
 frame is received:

I think that we need a little restructuring here.

> To reduce the risk of bad ECN markings affecting the operation of an endpoint, an endpoint verifies the counts it receives when it receives new acknowledgements:
> 
> * \[bullets]
>
> This validation is only performed if the ACK frame increases the largest received packet number.  Reordered acknowledgments could have lower counter values and might not be successfully validated as a result.
>
> These counts might be inflated if acknowledgments are never received for packets that were successfully delivered.  If validation succeeds, an endpoint MUST increase its expected counter values to those it receives.

Note that I almost didn't use MUST on that last clause, because there is no interop loss from doing that; it only means that validation is less likely to catch bad markings.

I also removed the "If the sender does not have state to determine if a packet is newly acknowledged..."  Such a packet - such as a packet that is declared lost - will never be considered to be newly acknowledged.

Would you like this as a PR?

-- 
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/2113#pullrequestreview-184517682

---

From: Magnus Westerlund <[email-masked]>
Date: Thu, 13 Dec 2018 07:56:21 +0000 (UTC)

frame is received:

I think the restructuring is fine. On a high level I agree with your removal of the if you are missing state. However, considering some of the discussion on the quicdev slack I do wonder if something along those lines needs to be included to ensure that people are not interpreting this as requiring one to maintain state further into history than what one otherwise would. 

-- 
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/2113#discussion_r241300008

---

From: Magnus Westerlund <[email-masked]>
Date: Thu, 13 Dec 2018 00:44:24 -0800

566f72e0f63a235471787ad0eaafdbda6977bcd5  Applying Martin Thomson's suggested fixes for restructuring.

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/2113/files/43b6f677582ae0d917e759c7d002d69a174d64f2..566f72e0f63a235471787ad0eaafdbda6977bcd5

---

From: Martin Thomson <[email-masked]>
Date: Thu, 13 Dec 2018 15:21:27 -0800

frame is received:

Thanks for that.

The pseudocode in the recovery draft drops packets from the "in flight" structure when they are declared lost and only treats packets as "newly acknowledged" if they are in that structure.  I think that makes it clear 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/2113#discussion_r241597873

---

From: Martin Thomson <[email-masked]>
Date: Thu, 13 Dec 2018 15:21:34 -0800

Merged #2113 into master.

-- 
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/2113#event-2025600071