Subject: [quicwg/base-drafts] An example ECN validation algorithm (#3320)

From: Martin Thomson <[email-masked]>
Date: Mon, 06 Jan 2020 18:11:34 -0800

This turned out to be fairly simple, but I think that it&#39;s worth writing
down.  I don&#39;t have concrete recommendations, but I could add them if
people thought that they help.  See the commented-out bit.

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

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

-- Commit Summary --

  * An example ECN validation algorithm

-- File Changes --

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

-- Patch Links --

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

---

From: Martin Thomson <[email-masked]>
Date: Mon, 06 Jan 2020 18:13:54 -0800

martinthomson commented on this pull request.

> +
+The testing period runs for a number of packets or round trip times as
+determined by the endpoint.  During this time, packets sent are marked with
+ECT(0).  The goal is to limit the duration of the testing period, but to ensure
+that enough marked packets are sent that it is likely that ECN counts will
+provide a clear indication of how the path treats marked packets.
+
+<!-- Do we need a more concrete recommendation here?  For instance, I might say
+"Endpoints could test with packets that amount to between 1 to 2 times the
+initial congestion window over a period between 1 to 2 times the estimated RTT."
+-->
+
+After the testing period ends, the ECN state for the path becomes "unknown".
+From the "unknown" state, successful validation of the ECN counts an ACK frame
+(see {{ecn-ack}}) causes the ECN state for the path to become "capable", unless
+no marked packet has been acknowledged.

This extra condition caught me by surprise.  The problem is that if every packet you mark is lost, the ECN counts remain valid, but you have a fair indication that the path is a black hole.  That's not worth belabouring because black holes are exceedingly rare, but the extra condition seems necessary even if we don't provide a whole lot of explanation.

-- 
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/3320#pullrequestreview-338999305

---

From: mirjak <[email-masked]>
Date: Tue, 07 Jan 2020 02:35:31 -0800

mirjak commented on this pull request.

Given that black-holing is rare, I'd rather keep simply all packet ECT-marked until a failure is detect. If black-holing is happening, that's actually the easiest case to detect (as you will have a time-out). Moreover if you plan to send more than one cwnd of packets with ECT marks in testing, you will get blocked anyway as you can't send anymore packets without receiving an ack. 

> @@ -3488,6 +3489,54 @@ Even if validation fails, an endpoint MAY revalidate ECN on the same path at any
 later time in the connection.

+#### Exemplary ECN Validation Algorithm {#ecn-alg}
+
+Each time that an endpoint commences sending on a new network path, it
+determines whether the path supports ECN.  If the path supports ECN, the goal is
+to use ECN.  Endpoints might also periodically reassess a path that was
+determined not support ECN.
+
+This section describes one method for testing new paths.  This algorithm is
+intended to show how a path might be tested for ECN support.  Endpoints can
+implement different methods.
+
+The path has an ECN state that is one of "testing", "unknown", "failed", or
+"capable".  In the "testing" and "capable" states the endpoint sends packets
+with an ECT(0) marking; otherwise, the endpoint sends unmarked packets.

I would say: "the endpoints sends packet with an ECT marking, by default ECT(0);"

> +To start testing a path, the ECN state is set to "testing" and existing ECN
+counts are remembered as a baseline.  It should not be necessary to disregard
+the effect of packets sent prior to starting testing, though it is necessary for
+a sender to remember what markings were used for every packet that is
+acknowledged; see {{ecn-ack}}.
+
+The testing period runs for a number of packets or round trip times as
+determined by the endpoint.  During this time, packets sent are marked with
+ECT(0).  The goal is to limit the duration of the testing period, but to ensure
+that enough marked packets are sent that it is likely that ECN counts will
+provide a clear indication of how the path treats marked packets.
+
+<!-- Do we need a more concrete recommendation here?  For instance, I might say
+"Endpoints could test with packets that amount to between 1 to 2 times the
+initial congestion window over a period between 1 to 2 times the estimated RTT."
+-->

Currently the ECN validation section says "To reduce the chances of misinterpreting congestive loss as packets
   dropped by a faulty network element, an endpoint could set the ECT(0)
   codepoint in the first ten outgoing packets on a path, or for a
   period of three RTTs, whichever occurs first."
Why is that not sufficient?

> @@ -3488,6 +3489,54 @@ Even if validation fails, an endpoint MAY revalidate ECN on the same path at any
 later time in the connection.

+#### Exemplary ECN Validation Algorithm {#ecn-alg}

If we want an algorithm like this I think this should go into the appendix.

> @@ -3473,6 +3473,7 @@ to be greater than the number of packets acknowledged in an ACK frame.  When
 this happens, and if validation succeeds, the local reference counts MUST be
 increased to match the counts in the ACK frame.

Related note: I just realised that we don't test the case where ALL ECT get remarked to CE which should also lead to failure.

-- 
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/3320#pullrequestreview-339150098

---

From: Jana Iyengar <[email-masked]>
Date: Tue, 07 Jan 2020 15:06:30 -0800

janaiyengar commented on this pull request.

Thank you for working on this. 

```suggestion
Each time an endpoint commences sending on a new network path, it
```

Paths don't have ECN state. Suggestion: "For each path an endpoint sends on, it records known ECN support on that path as one of ..."

```suggestion
"capable".  On paths that are recorded as "testing" or "capable", the endpoint sends packets
```

It's not clear what "effect of packets" this is talking about.

```suggestion
The testing period runs for a number of packets or round-trip times, as
```

```suggestion
determined by the endpoint.
```

Redundant. You've already said this 2 paras above.

```suggestion
The goal is not to limit the duration of the testing period, but to ensure
```

+

```suggestion
that enough marked packets are sent for received ECN counts to
```

This is an example, and as such, it's useful for us to provide a specific value here. We should also expect that anyone implementing this is likely to use these exemplary values.

Why does this have to go to "unknown" and not directly to "capable" or "failed"?

You will be blocked, but only until the PTO timer fires. There is a question still of what to do afterwards. While it is rare, I suspect we need this fallback as a failsafe.

+At any point, if validation of ECN counts fails, the ECN state becomes "failed".

```suggestion
If validation of ECN counts fails at any time, the endpoint records ECN state for the path as "failed".
```

-- 
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/3320#pullrequestreview-339557244

---

From: Martin Thomson <[email-masked]>
Date: Tue, 07 Jan 2020 21:23:22 -0800

Though Mirja will disagree, this algorithm is extremely conservative, consistent with the existing test, and it disables ECT markings after this period in case there is a black hole.  I suspect that some implementations will just always mark and that's cool, but that's somewhat simpler, I think.  In that case, the algorithm is "mark unless validation on that path has recently failed".

-- 
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/3320#discussion_r364068057

---

From: Martin Thomson <[email-masked]>
Date: Tue, 07 Jan 2020 21:27:15 -0800

@martinthomson pushed 2 commits.

0b4e94bc529863f950a674fa6929ce3a9385454f  Take some of the editorial suggestions
e8c7b2ffc1af3efc0c5d096cf126c37748a5c064  Move ECN algorithm to an appendix

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

---

From: Martin Thomson <[email-masked]>
Date: Tue, 07 Jan 2020 21:29:28 -0800

Thanks both for the reviews, I've taken some of the suggestions and moved this to the appendix.

-- 
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/3320#issuecomment-571897272

---

From: mirjak <[email-masked]>
Date: Thu, 09 Jan 2020 02:21:58 -0800

My thinking was that if you get an PTO in testing to go straight to failed and don't sent any ECT markings anymore.

-- 
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/3320#discussion_r364660387

---

From: ianswett <[email-masked]>
Date: Thu, 09 Jan 2020 08:23:12 -0800

ianswett approved this pull request.

> @@ -6263,6 +6266,48 @@ DecodePacketNumber(largest_pn, truncated_pn, pn_nbits):
    return candidate_pn
 ~~~
 
+
+# Sample ECN Validation Algorithm {#ecn-alg}
+
+Each time an endpoint commences sending on a new network path, it determines
+whether the path supports ECN; see {{ecn}}.  If the path supports ECN, the goal
+is to use ECN.  Endpoints might also periodically reassess a path that was
+determined not support ECN.

```suggestion
determined to not support ECN.
```

-- 
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/3320#pullrequestreview-340643592

---

From: Martin Thomson <[email-masked]>
Date: Thu, 09 Jan 2020 18:37:31 -0800

I don't think that works without additional constraints or checks as you could exit the testing state before any PTO might occur.

-- 
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/3320#discussion_r365050893

---

From: Martin Thomson <[email-masked]>
Date: Thu, 09 Jan 2020 18:37:59 -0800

@martinthomson pushed 1 commit.

6c011b9efad2b5511d28f4bca2b6300505cc3af0  add "to"

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/3320/files/e8c7b2ffc1af3efc0c5d096cf126c37748a5c064..6c011b9efad2b5511d28f4bca2b6300505cc3af0

---

From: mirjak <[email-masked]>
Date: Tue, 14 Jan 2020 05:47:54 -0800

I think the idea would be to only have three states: "Unknown/testing" and "capable" where ETC marking is enabled, "failed" where ECT marking is disabled and you stay in "unknown/testing" until the path has be validate for failed. 

-- 
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/3320#discussion_r366346120

---

From: Martin Thomson <[email-masked]>
Date: Tue, 21 Jan 2020 15:49:27 -0800

After discussing with editors, we agreed that this was a reasonable interpretation of existing text.  We do agree that it would be worth discussing Mirja's views on ECN reliability and possibly changing the algorithm to reflect that, but it would be a design change.

-- 
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/3320#issuecomment-576940888

---

From: Jana Iyengar <[email-masked]>
Date: Tue, 21 Jan 2020 15:50:37 -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/3320#pullrequestreview-346269800

---

From: Martin Thomson <[email-masked]>
Date: Tue, 21 Jan 2020 15:58:55 -0800

Merged #3320 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/3320#event-2968222669