Re: [iccrg] AIMD versus AIAD

Jonathan,

On 20/11/2020 08:21, Jonathan Morton wrote:
>> On 20 Nov, 2020, at 9:59 am, Jana Iyengar <jri.ietf@gmail.com> wrote:
>>
>> This goes all the way back to Chiu and Jain.
> I see in that paper that a primitive type of AQM signalling is described - one that is only capable of sending one signal per "time slot", possibly an abstract representation of RTT.  This has a fairly obvious lineage to RFC-3168 ECN, which is also capable of handling only one congestion signal per RTT.  Under these conditions, an MD response to that singular signal is the only one that is correct.

[BB] In addition to the other corrections that people have already given 
later in this thread, it's also not necessarily correct that a step can 
only give one signal per RTT. I'm not a fan of a step threshold (see 
below for why), but it can provide a higher fidelity ECN signal when 
there's a mix of long and short flows, which was the use-case it was 
designed for. Then the intensity of short flows combined with the 
increases of the long flows that are smaller and slower in comparison 
determines the percentage of marking in any one round.

This was the point I made in the DCTCP tutorial part of my talk this 
morning about how one or many DCTCPs leave headroom /under/ the marking 
threshold for the recent pattern of short flows or bursts. This is 
because each of their reductions depends on their memory of what the 
marking probability was during recent rounds (held in their EWMA).

However, note that, as the EWMA dies away, DCTCP does not pointlessly 
keep reducing if there are no actual congestion signals. Altho it 
continues to decay the EWMA, it does not /use/ it unless it sees an 
actual mark echoed.

This has parallels to the way CoDel's control law holds memory of the 
next drop, and how CoDel's filtered max enables or disables use of that 
memory. For similar reasons, of course.

>
> With high-fidelity congestion signalling applied to DCTCP (or TCP Prague), that same single Congestion Experienced signal, issued once per RTT, produces a very different response.  It only subtracts a constant from the cwnd, instead of reducing it to some fraction.  That is clearly consistent with the Additive Decrease formula in the Chiu/Jain paper.

[BB] I've noticed before that you believe DCTCP subtracts an amount from 
cwnd on every marked packet. This is also not the case.

a) DCTCP does not apply a reduction on /each/ echoed mark. It applies 
one reduction per RTT, then goes into CWR state, which suppresses any 
further reduction for an RTT. It then does no further reduction until a 
subsequent mark is echoed, which triggers the next reduction, but based 
on the most recently computed value of the EWMA (alpha).

I drew the process for the DCTCP tutorial I gave this morning. But I 
relegated the picture of DCTCP's two independent event cycles to the 
spare slides, in the interests of time. You'll need to read slide 6 then 
slide 20.
https://datatracker.ietf.org/meeting/109/materials/slides-109-iccrg-prague-congestion-control-00#page=20

b) There is a description of an idea for reducing cwnd a little on each 
CE mark in section 5.2 of [DCTCP-stability] 
<https://web.stanford.edu/~balaji/papers/11analysisof.pdf#page=11>, but 
it is /not/ how the Linux implementation works, nor the Windows 
implementation (assuming Windows DCTCP works as RFC8257 says it does). 
There were attempts to do the reduction this way in Linux, and we've 
tried it as well, but it is hard to stabilize. Nonetheless, I'd dearly 
like to get something similar to this per-ACK approach to be more stable 
- I actually started revisiting it last week.

c) If DCTCP were to reduce cwnd a little on each echoed CE mark, if it 
used the approach in [DCTCP-stability], it would not subtract a small 
constant. It would subtract alpha / 2 segments per echoed mark. And 
importantly alpha is a /measured variable/, not a constant. Otherwise it 
would not be extent based cwnd reduction.

d) You might be confusing DCTCP with Relentless TCP, which subtracts 1/2 
a segment per echoed loss or mark. But Relentless doesn't do any 
smoothing of the congestion signals itself (no EWMA), unlike DCTCP and 
Prague.

[DCTCP-stability] Alizadeh, M., Javanmard, A., and B. Prabhakar, 
"Analysis of DCTCP: Stability, Convergence, and Fairness", ACM 
SIGMETRICS 2011 , June 2011

>
> The added capability of high-fidelity congestion feedback is that there can now be *more than one* congestion signal per RTT.  But it means that O(N) signals must be issued by the network in order to reduce cwnd by an O(N) factor.  Each signal only produces an O(1) response.

[BB] As I said when you raised your point in iccrg today, repeated 
addition or subtraction is a multiply. The more subtle point here is 
that repeating a subtraction only on a marked packet, effectively 
multiplies by the marking probability. For instance, comparing these two:
* Repeatedly subtracting 1/2 from W on each ACK'd packet roughly results 
in W - W*(1/2) after one window of subtractions,
     which is the product (1 - 1/2)*W
* Repeatedly subtracting 1/2 from W on each _echoed marked packet_ 
results in W - p*W*(1/2) after one window of subtractions.
     because if the probability of marking over the last round was p, by 
definition there are p*W marks in the window.
     so over one round W evolves to the product (1 - p/2)*W

Bob
>
> Regardless of whether you accept the above argument, there is a clear qualitative difference between the conventional AIMD response and that of DCTCP, which needs accurate terminology to describe.  That is my point here.
>
>   - Jonathan Morton
> _______________________________________________
> iccrg mailing list
> iccrg@irtf.org
> https://www.irtf.org/mailman/listinfo/iccrg

-- 
________________________________________________________________
Bob Briscoe                               http://bobbriscoe.net/
                PRIVILEGED AND CONFIDENTIAL