Re: [iccrg] [EXTERNAL] Re: AIMD versus AIAD

[Praveen Balasubramanian <[e-mail]>]

Correct DCTCP as sepc’ed does multiplicative decrease, but based on the extent of congestion. The fluid model is not implemented in Linux or Windows  AFAIK.

From RFC 8257:
   Just as specified in [RFC3168], DCTCP does not react to congestion
   indications more than once for every window of data.  The setting of
   the CWR bit is also as per [RFC3168].  This is required for
   interoperation with classic ECN receivers due to potential
   misconfigurations.


From: iccrg <[e-mail]> On Behalf Of Bob Briscoe
Sent: Friday, November 20, 2020 8:47 AM
To: Jonathan Morton <[e-mail]>; Jana Iyengar <[e-mail]>
Cc: iccrg IRTF list <[e-mail]>
Subject: [EXTERNAL] 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 <[e-mail]><mailto:[e-mail]> 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<https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fdatatracker.ietf.org%2Fmeeting%2F109%2Fmaterials%2Fslides-109-iccrg-prague-congestion-control-00%23page%3D20&data=04%7C01%7Cpravb%40microsoft.com%7Cf8402ca5aded4025e53408d88d73e3a9%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C1%7C637414876770053794%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=vURaGPBpLHY%2BczR5dSHD1rJaXE1Ii7Y5OiEbwh2lAz0%3D&reserved=0>

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://nam06.safelinks.protection.outlook.com/?url=https:%2F%2Fweb.stanford.edu%2F~balaji%2Fpapers%2F11analysisof.pdf%23page%3D11&data=04%7C01%7Cpravb%40microsoft.com%7Cf8402ca5aded4025e53408d88d73e3a9%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C1%7C637414876770063787%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=PnPnpSrcjTh1soS8bi5QjWSk1tPRXtbhiIbGBXDz7jc%3D&reserved=0>, 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

[e-mail]<mailto:[e-mail]>

https://www.irtf.org/mailman/listinfo/iccrg<https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.irtf.org%2Fmailman%2Flistinfo%2Ficcrg&data=04%7C01%7Cpravb%40microsoft.com%7Cf8402ca5aded4025e53408d88d73e3a9%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C1%7C637414876770063787%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=dT2MQrq7mmplsbJ3tcy9xw6KIfGyzi8d9syp%2BfN8bYY%3D&reserved=0>



--

________________________________________________________________

Bob Briscoe                               http://bobbriscoe.net/<https://nam06.safelinks.protection.outlook.com/?url=http%3A%2F%2Fbobbriscoe.net%2F&data=04%7C01%7Cpravb%40microsoft.com%7Cf8402ca5aded4025e53408d88d73e3a9%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C1%7C637414876770073776%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=h5fPjKHoMVTZ8HreuVbiObp6%2FU0gm4jlY8fVPAvcF%2FY%3D&reserved=0>

               PRIVILEGED AND CONFIDENTIAL