[tcpm] Tech review of draft-grimes-tcpm-tcpsce-01.txt

[Bob Briscoe <[e-mail]>]

Rod, Pete,

This is a review of the TCP ECN feedback schemes in 
draft-grimes-tcpm-tcpsce-01, on its own terms - i.e. whether it does 
what it aims to do, rather than whether I agree with what it aims to do.

Please do not feel the need to answer this email quickly. It will take 
some working through, altho I have tried to summarize for the list as well.

===Terminology===
p% The instantaneous SCE marking probability
d% The delayed ACK ratio, e.g. d%=25% means the receiver ACKs at least 1 
in 4 data packets.

===Assumption===
SCE is intended to sometimes or even often cause high levels of SCE 
marking, particularly when using DCTCP congestion control, when runs 
approaching 100% SCE can be common for a round trip or so, and certainly 
 >50%.

===Exec Summary===
Why go through all the years of pain of altering the TCP wire protocol 
for an accurate feedback scheme that isn't accurate?

There are 4 schemes proposed, one of which is NOT RECOMMENDED by the 
authors themselves. Of the other three:

  * 'Simple' multiplies up the Delayed ACK ratio the more the marking
    level is above the delayACK ratio (p>d), which rules it out on
    safety grounds.
  * 'Dithered' doesn't meet its own stated goal (apparently by definition).
  * 'Advanced' increases the ACK ratio in the mid-range of SCE marking
    levels. However, not as badly as 'Simple', and similar to DCTCP or
    AccECN. However, in this range...
  * ...unlike DCTCP and AccECN, 'Advanced' can toggle between long
    periods of 0% and long periods of 100% feedback, when subjected to
    ACK thinning, or segmentation offload.
  * All three schemes suffer from more and more bias in their error as
    the SCE marking level increases. It is important to eliminate bias,
    because it causes a congestion control scheme to aim for the wrong
    rate and therefore either causes excessive queuing delay, or
    excessive underutilization.

To summarize, in all cases:

	Meets SCE goal#1 in clean network? 	Maintains DelACK ratio? 	Unbiased 
result when ACK thinned?
Simple 	Y
	N
	N
Dithered 	N
	Y
	N
Advanced 	N
	N~
	N

Where:
'Y' means OK.
'N' means Not OK.
'N~' means not too bad.

No scheme meets more than one of these three show-stopper requirements.  
It was recognized (see RFC7560) that compromises would probably be 
needed because of the limited header space. But in all three cases, SCE 
makes compromises that are show-stoppers.

===Divergent Goals===
 From the email discussion so far, I am told that the goal given in the 
'Dithered' subsection is the goal for all schemes:

    The goal is to have the same number of bytes marked
    with ESCE as arrived with SCE.

(Ironically, dithered never meets this goal, apparently by design)

I'll call this Goal #1.

Actually, as we shall see, each scheme has a different goal for how much 
marking the receiver feeds into the ESCE ACK stream:

  * 'Simple' meets the above goal,
  * 'Dithered' aims for d% of the above goal.
  * 'Advanced' needs to be decoded, rather than being based on the
    amount of marking.

Different receivers seem to be allowed to use different schemes or the 
same scheme with a different parameter (e.g. different values of d% in 
the Dithered case). Each will give different meanings to an ESCE ACK in 
different flows.

What if the sender decodes an ACK stream believing it to be the 
'Advanced' coding, when it is actually 'Dithered' at d%=20%?


===Scheme-by-scheme review===

==4.2 Simple==

    Upon receipt of a packet with an SCE
    codepoint immediate ACK processing SHOULD be done

'Simple' meets Goal #1, but at the expense of causing an ACK ratio of 
max(d%, p%), which is unsafe IMO. For instance, at 75% SCE marking 
(which is not uncommon with a DCTCP congestion control), 75% of data 
packets trigger an ACK. Such a large change in ACK ratio brings a 
significant risk that congestion from the forward path will propagate to 
the reverse path.

If subjected to ACK thinning, the more SCE marking rises, the more 
'Simple' under-reports. This is because the proportion of ACKs that are 
ESCE marked rises as the marking level rises. So if a proportion of ACKs 
is thinned blindly, proportionately more ESCE ACKs will be thinned.

==4.3 Dithered==
'Dithered' isn't even defined to meet the goal stated in its own 
section. It is defined to factor down the ESCE ACKs to d_r% of the 
proportion of SCE-marked data packets (i.e. d_r% of p%, where 'r' stands 
for receiver).

As introduced earlier, the sender can't even work out the receiver's 
d_r% heuristically. It can see what ratio of ACKs arrive, d_s% (s for 
sender). But the sender cannot know what d_r% was originally, because it 
doesn't know how much d_r% might have been reduced by ACK thinning, 
either by a middlebox or a NIC.

Actually, the way 'Dithered' is described reveals that this section was 
written after some arm-waving but before any thinking. More on 
'Dithered' later.

==4.4 Advanced==
Advanced meets the goal. But only if no ACKs are lost (and they all 
arrive in order). Its accuracy is sensitive to ACK loss (or reordering), 
because it's a stateful algo. Also, I show below that, as the level of 
SCE marking rises, it will quickly become completely broken in the 
presence of simple ACK thinning.

Let's try an example, with d% = 25%, by typing out a finger-random 
sequence of SCE marks.
     01001011000000101000010111001001....
For this sequence, p% = 100*12/32 = 37.5% > d%.

The resulting ESCE ACK stream will be:
     01-010-1---0-0101---010--1-01-0 ....
That's 13 in 32 ~= 41%, compared to 25% for just DelACKs.

This is the same inflation of the ACK rate as (AccECN+TCP Option) or 
(DCTCP-style feedback). The tcpsce draft rather plays down the impact 
though:

    The ACK
    volume is then inflated only slightly compared to an unmarked
    connection


Unlike the SCE schemes, both AccECN and DCTCP can subsequently be 
thinned or coalesced without the error becoming biased. Here's how 
'Advanced' becomes biased.

Let's run the above sequence through a simple algo that thins every 
other ACK:
Before:
     01-010-1---0-0101---010--1-01-0 ....
Forwarded:
     0--0-0-----0--1-1----1---1--1-- ....
Thinned out:
      1--1--1-----0-0----0-0----0--0 ....

Oh dear. You can see what's happening. It thins out all the 1s for a 
while, then switches to thinning out all the zeros. Not only does this 
completely destroy the feedback signal, it does so with a toggling bias 
that will push the congestion control into large swings. This would 
happen for any algo that thins or coalesces an even proportion of ACKs.

So, the original input:
     01001011000000101000010111001001....
decodes as:
     00000000000011111111111111111   ....
I'd say that's pretty broken.


The problem here is that, for higher SCE marking levels, the Advanced 
scheme turns any random sequence into a regular sequence. And some 
thinning/coalescing algos remove information in a regular way.

4.5 ACK Thinning

    Mathematically, the most extreme errors possible in either direction,
    due to ack thinning, are easily corrected during subsequent RTTs.

Starting a sentence with 'mathematically' makes it sound impressive, but 
it's not if you haven't actually done the maths. Even if the error in a 
control signal is unbiased (on average too high as much as too low), 
subsequent RTTs only correct it in cases when the traffic load is in 
steady state. That's hardly ever the case on the Internet, so error will 
not self-correct.

If you are trying to control the /dynamics/ of traffic flows with a 
signal that might sometimes aim too low and sometimes too high, the 
traffic will swing around more wildly, causing more queuing delay and 
less utilization.

Worse, error introduced by thinning any of the SCE-TCP schemes not only 
introduces error, it introduces /biased/ error. As explained in each 
case above. In the case of 'Advanced' the bias toggles at random points. 
Then if it's already aiming towards too much delay (because the error is 
under-reporting), half the time it might swing towards even more delay 
and half the time towards less.

In summary, why go to all the bother of introducing a high-fidelity SCE 
signal, then feeding it back inaccurately, and lop-sidedly?

==Dithered: How to Implement?==

    If some
    of the packets to be ACKed have SCE state set then some proportional
    number of ACK packets SHOULD be sent with the ESCE code point set.

Let's say d=50%. After 2 data packets, let's say one is SCE-marked, so 
we have to send half the next ACK packets with ESCE. But we only have 
one ACK for these two packets...

OK, we send half the next 2 ACK packets with ESCE. But then we've 
accumulated another two 2 data packets, with 0 1 or 2 SCE marks needing 
feed back. We need 2 more ACKs. But then we'll have between 0 and 4 more 
SCE marks to feed back. This will always snowball.

Hmmm. From its description, it looks like 'Dithered' wasn't thought 
through 'much'.

One could set each ESCE probabilistically, based on the fraction of 
marks since the last ACK. That would be noisy feedback, not accurate 
feedback though.

Instead, one could multiply using a repetitive add-subtract algo, to 
multiply the number of packets between SCE marks by d%, in order to 
count ACKs until the next ESCE feedback.

Even though that removes the noise of randomness, it's still a very 
inaccurate way to be accurate. For instance, for d%=25% and p%=1%, every 
100 packets would be SCE marked, so every 25 ACKs would be ESCE marked.

The problem is it's only communicating 1 bit per ACK. If instead it 
exploited n bits per ACK it would be able to maintain precision while 
sending ACKs 2^n times less frequently.

===Bigger Picture===
A new feedback scheme requires a change to the TCP wire protocol, which 
is one of the core Internet protocols. This requires change at both ends 
before it will work. Therefore, ideally, a new feedback protocol needs 
to be more generic than any one feedback scheme that might use aspects 
of the protocol.

That is why a requirements exercise [RFC7560] preceded AccECN, which 
took years in itself. The requirements admit that compromises will be 
needed. So they are more a checklist of things to consider. And you'll 
need a good reason, if you don't think you need to meet them.

There's also probably requirements missing from RFC7560, 'cos it's hard 
to think of requirements in the abstract, particularly subtle ones.

AccECN is close to becoming more frozen, but it's still open to change. 
You might want to think of other ways of repurposing it, while the 
opportunity to make tweaks is still open.


Bob

On 04/11/2019 22:04, Rodney W. Grimes wrote:
> All, Cross posting to tsvwg and tcpm due to overlap in areas covered,
>
> I have just posted an updated version of TCPSCE which hopefully addresses
> most of the feedback provided since the original publication.
>
> The document structure is unchanged, and the history tool works well
> to show what has been changed since the last revision.
>
> Thanks to those who have provided feedback, and assistance in updating
> this draft.
>
> Regards,
> Rod
>
>> A new version of I-D, draft-grimes-tcpm-tcpsce-01.txt
>> has been successfully submitted by Rodney W. Grimes and posted to the
>> IETF repository.
>>
>> Name:		draft-grimes-tcpm-tcpsce
>> Revision:	01
>> Title:		Some Congestion Experienced in TCP
>> Document date:	2019-11-04
>> Group:		Individual Submission
>> Pages:		6
>> URL:            https://www.ietf.org/internet-drafts/draft-grimes-tcpm-tcpsce-01.txt
>> Status:         https://datatracker.ietf.org/doc/draft-grimes-tcpm-tcpsce/
>> Htmlized:       https://tools.ietf.org/html/draft-grimes-tcpm-tcpsce-01
>> Htmlized:       https://datatracker.ietf.org/doc/html/draft-grimes-tcpm-tcpsce
>> Diff:           https://www.ietf.org/rfcdiff?url2=draft-grimes-tcpm-tcpsce-01
>>
>> Abstract:
>>     This memo classifies a TCP code point ESCE ("Echo Some Congestion
>>     Experienced") for use in feedback of IP code point SCE ("Some
>>     Congestion Experienced").
>>
>>                                                                                    
>>
>>

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