Subject: Re: [tsvwg] L4S and the detection of RFC3168 AQMs

From: "[email-masked]" <[email-masked]>
Date: Fri, 30 Jul 2021 18:29:16 +0000 (UTC)

Hi Bob, Martin,

There was no reply to this - I assume that the approach still did not seem promising. However with the L4S drafts in WGLC, as it currently stands this option will be foreclosed, so I thought it might be a good idea to check if that is your thinking on the matter.

best,

Alex

On Wednesday, March 24, 2021, 1:54:24 PM GMT, [email-masked] <[email-masked]> wrote: 

Hi Bob, Martin,

The extra factor of 20 (r) , to account for the possibility that the AQM marks smaller packets with lower probability, makes this approach much slower if you account for it in a conservative way.
However, I don't think we have to. Suppose that as well as small ECT(0) probe packets, we send an equal number of ECT(1) probe packets of the same size. 
Then, we wait not to see r * P * 5 marks on all packets, but 6 marks on the ECT(1) probe packets. If in the same time we see no marks on ECT(0) probe packets, then (if my calculations are correct, see below) the posterior probability that the is an RFC3168 AQM present is less than 1%.

The factor of r is still present, but it now comes from the AQM we are dealing with  rather than us having to assume the worst case. If that AQM applies a lower marking probability to small packets, the method is still slow, but if such AQMs are rare then this may still be suitable. 
This is still a bit slower than if we could assume all packet sizes were marked with the same probability (there is a factor of 2 for the ECT(1) probe packets, plus the waiting time has more variability), but if the AQM is marking all packet sizes the same, then it should be much less than the time to see 800 marks.

Note that since we are assuming that the probability each probe is marked is independent, the distance between probes must be random, rather than equal as shown in the slides.

In principal we should also use the information from the number of marked data packets, but I don't see how to do that immediately.

Below is some R code to calculate the posterior probability that an RFC3136 AQM is present.

The arguments need to be set differently for the different methods:
For the original method, NumPackets is the total number of packets (probe and data), ECT0Ratio is P (8 in your example) and ECT0Marks  and ECT1Marks
are the number of observed marks. 
For the above method, NumPackets is the number of ECT1 plus ECT0 probe packets (not including data packets), and ECT0Ratio is 2 (because there are equal number of ECT1 and ECT0 probe packets). 

When passing ECT0Ratio=2, ECT0Marks=0 and ECT1Marks=6, the posterior probability always seems to be less than 1% and does not depend much on NumPackets.

Hope this is of interest,

Alex

 ======= 

library(VGAM)

P_3186Present <- function(NumPackets, ECT0Ratio,ECT0Marks, ECT1Marks) {

  NumECT0Packets = NumPackets/ECT0Ratio
  NumECT1Packets = NumPackets - NumECT0Packets

  likelihood = dbetabinom.ab(ECT0Marks,NumECT0Packets,ECT1Marks+1,NumECT1Packets-ECT1Marks+1)

  if(ECT0Marks>1){
    likelihood_converse <- 0
  }
  else{
    likelihood_converse <- 1
  }

  Prior_RFC3168 <- 0.5
  Prior_NotRFC3168 <- 1 - Prior_RFC3168

  posterior = likelihood * Prior_RFC3168/ (Prior_RFC3168 * likelihood + Prior_NotRFC3168 * likelihood_converse)

   posterior

}

On Wednesday, March 10, 2021, 6:20:19 PM GMT, Bob Briscoe <[email-masked]> wrote: 

Martin, Alex,

In case you missed the pointer in Greg's presentation today, here's the 
link to the slides I prepared on why I don't think this idea is likely 
to fly...
https://bobbriscoe.net/presents/2103ietf/l4s-exclusive-ecn-marking.pdf

TL;DR: Seems too slow for in-band testing (perhaps need 800 CE marks). 
Useful out-of-band, but we already have good out-of-band tests without it.

Pls push back, if you can think of an argument against.

Bob

On 15/02/2021 11:26, [email-masked] wrote:
> Martin, Bob, all,
> I am happy for these ideas to be taken forward by Bob or anyone else  - unfortunately I am unlikely to have time to contribute, as I am not working on networking at present.  As such I don't have any opinions on what is the appropriate doc.
>
> best,
> Alex
>
>
> On Thursday, February 11, 2021, 12:29:45 AM GMT, Bob Briscoe <[email-masked]> wrote:
>
>
>
>
>
> Martin,
>
> Greg and I spoke about this very question earlier in the week.
>
> At minimum, we could write all the details covered in this thread into the tech report about Classic ECN AQM Fallback that Asad & I prepared earlier. "We" might mean Alex or me, or someone else? I would be happy to either ACK Alex or include him as a co-author - if he was willing.
>
> I feel that would be more appropriate than an IETF draft at the mo, at least while it's not implemented or tested. Then the IETF drafts (l4sops, ecn-l4s-id, dualQ, etc.) could give a brief outline of the idea, while referring out for fuller details.
>
> In that tech report, there is already a section on ideas for the design of active tests, which it says have not been implemented or tested. It would be published on arXiv as a new version, which is suitable as an archival ref.
>
> Then, as Alex suggests, we would need to update the dualQ draft.
> As Alex pointed out, not supporting ECT0 can later be reversed (e.g. if the L4S experiment later moves to PS), whereas supporting ECT0 from the start, them removing it later would miss the opportunity to provide certainty. This is the part I like most.
>
> We would also have to not make ECT0 support the default in the reference Linux implementation of the DualQ.
>
>
> Bob
>
>
> On 10/02/2021 18:37, Martin Duke wrote:
>
>
>>    
> Well this all seems very promising!
>
>
>
>
> Does anyone have the bandwidth to write something down? Should there be a separate draft that articulates the design? Would this replace the current Prague approach?
>
>
>
>
> Martin
>
>
>
>
>
> On Tue, Feb 9, 2021 at 3:09 PM Bob Briscoe <[email-masked]> wrote:
>
>
>> Richard,
>>
>> First, thank you for reviving this thread, because it brought Alex's
>> last posting (in Dec) to my attention. I'll respond to that separately
>> (probably mañana, as it's getting late).
>>
>> Pls see inline tagged [BB]...
>>
>> On 09/02/2021 11:05, Scheffenegger, Richard wrote:
>>> Martin, group,
>>>
>>>
>>> AccECN is not tied to RFC3168 (and quite the opposite, it tries to be as
>>> impartial to the specifics of when/why packets were marked in whichever
>>> way).
>> [BB] Also, in case people aren't aware: an L4S sender using TCP MUST
>> negotiate the use of Accurate ECN TCP feedback with its peer. So I think
>> there's no case where a transport would not provide feedback for Alex's
>> idea.
>>
>>> Therefore the Packet-CE counter (you refer to it as PCE, while the draft
>>> refers to the (full) counter as cep [from CE_packet] is incremented
>>> regardless of which packet arrives with the CE mark (control, data,
>>> retransmission, ...).
>>>
>>> Similar for the Byte-CE counter (BCE, in the AccECN draft ceb from
>>> CE_bytes). As only TCP payload bytes arriving with the CE mark would be
>>> accounted, the behavior as expected in the discussion below is already
>>> implicitly available when using AccECN.
>> [BB] ...only if the data receiver supports sending the AccECN TCP Option
>> (optional) and the new TCP Option traverses the path successfully and
>> the data sender supports reading the TCP Option (optional).
>>
>> Nonetheless, if any of these three is not the case, it might still be
>> possible to work out whether a CE marking was on a probe packet...
>>
>> The ACK that carries the CE packet counter also carries an ACKno (and
>> possibly SACK options). When a zero-sized probe is sent, it won't elicit
>> an ACK on its own (TCP doesn't ACK pure ACKs). But if the probe is CE
>> marked, when the data receiver ACKs subsequent data packet(s), the CE
>> packet counter will include any CE marking on the probe. It seems that
>> doesn't help, because the data sender cannot tell whether the CE mark
>> was on the data packets or the probe. But if the counter ever increases
>> by more than the number of data packets covered by the ACK, the probe
>> must have been marked as well.
>>
>> That sounds like having to wait quite a time for the possibility of all
>> packets together being marked. But there might be a more deterministic
>> way by use the same trick that keep alive probes use...
>>
>> That is, send a zero-sized probe with SEG.SEQ = SND.NXT-1. Being out of
>> window, each of these probes would immediately elicit a pure ACK from
>> the receiver. This might cause problems alongside the other regular
>> ACKs, because I think these might look like Dup ACKs (when the trick was
>> invented for keepalives, this wasn't a problem 'cos there were no other
>> data packets being ACK'd). However, it's possible the sender can work
>> out that they are not Dup ACKs, given it knows it sent a probe.
>>
>> (I'm not totally certain of my facts here - we'd need a TCP expert to
>> confirm - Richard?)
>>
>>
>> Bob
>>
>>>
>>> There may be some ambiguity, as AccECN doesn't strictly require an
>>> immediate ACK on a CE (only that the next packet after a received CE
>>> mark has to convey the changed CE-related counters), but in the general
>>> case, AccECN would allow and support such a detection scheme.
>> [BB]
>>
>>
>>> Best regards,
>>>     Richard
>>>
>>>
>>>
>>> Am 12.12.2020 um 00:22 schrieb Martin Duke:
>>>> Excellent, thank you for the reminder. So the L4S sender could
>>>> interleave some ECT(0) marked pure ACKs (or retransmissions of the last
>>>> acknowledged byte) and hope that the PCE counter increases without
>>>> corresponding increases in BCE.
>>>>
>>>> The AccECN spec might need to be updated to specify that these should be
>>>> reported in PCE even though they are not 3168 compliant.
>>>>
>>>> Scheduling these probes might not exactly be trivial, but if they are
>>>> temporally correlated with ECT(1)->CE marks, this would be highly
>>>> suggestive, yes?
>>>>
>>>> On Fri, Dec 11, 2020 at 3:03 PM Black, David <[email-masked]
>>>> <mailto:[email-masked]>> wrote:
>>>>
>>>>      In which case, RFC 8311 Section 4.3 allows experimental usage of ECN
>>>>      with such packets (https://tools.ietf.org/html/rfc8311#section-4.3
>>>> <https://tools.ietf.org/html/rfc8311#section-4.3>).____
>>>>
>>>>      __ __
>>>>
>>>>      Thanks, --David____
>>>>
>>>>      __ __
>>>>
>>>>      [EXTERNAL EMAIL] ____
>>>>
>>>>      My understanding of 3168 is that only in-window data packets are
>>>>      marked ECT(0). A zero-length segment is a equivalent to a pure ACK,
>>>>      which is not marked.____
>>>>
>>>>      __ __
>>>>
>>>>      On Fri, Dec 11, 2020 at 12:09 PM C. M. Heard <[email-masked]
>>>>      <mailto:[email-masked]>> wrote:____
>>>>
>>>>          On Fri, Dec 11, 2020 at 11:51 AM Martin Duke
>>>>          <[email-masked] <mailto:[email-masked]>>
>>>>          wrote:____
>>>>
>>>>              This falls under the "much easier to do in other transports"
>>>>              category, where I could just send a PING or HEARTBEAT marked
>>>>              ECT(0) to test the queue in mid-connection, without
>>>>              affecting the latency of anything that matters. But in the
>>>>              TCP case, I'm not sure how to resolve Bob's second objection
>>>>              (running ECT(0) for a long time would be unacceptable).____
>>>>
>>>>          __ __
>>>>
>>>>          Could zero-length TCP segments be used instead of PING or
>>>>          HEARTBEAT? ____
>>>>
>>>>          ____
>>>>
>>>>          Mike Heard ____
>>>>
>> -- 
>> ________________________________________________________________
>> Bob Briscoe                               http://bobbriscoe.net/
>>
>>
>>
>

-- 
________________________________________________________________
Bob Briscoe                              http://bobbriscoe.net/