Subject: [iccrg] AIMD versus AIAD

From: Jonathan Morton <[email-masked]>
Date: Fri, 20 Nov 2020 09:44:52 +0200

At the end of today's session, I had the opportunity to highlight the central feature of TCP Prague, inherited from DCTCP, which is the change in response to a CE mark (additive instead of multiplicative).  The response from the presenters (Bob & Koen) indicated that we need to clarify some terminology before the discussion can begin in earnest.

Specifically:  what is Multiplicative Decrease, and what is Additive Decrease, and which one does TCP Prague use?

It is well established that NewReno and CUBIC are AIMD algorithms, indeed Reno was the original AIMD CC.  A single packet loss or CE mark causes the cwnd to reduce to some fixed fraction of its previous value within one RTT of the congestion signal being recognised.  Or, mathematically:

MD:  O(1) signals causes O(N) reduction in cwnd.

Conversely, looking at DCTCP and ignoring the low-pass filters which disappear in the long run, each CE mark causes half a segment to be subtracted from the cwnd.  This is classic Additive Decrease.  There is still (barring implementation bugs) a Multiplicative Decrease response to packet loss.  So, distilling:

AD:  O(1) signals causes O(1) reduction in cwnd; to get O(N) reduction requires O(N) distinct signals.

The above is true regardless of how closely spaced the congestion signals are.  With precise feedback of CE marks, you can successfully register a mark on every data packet during a whole RTT and obtain, effectively, a multiplicative decrease - but that does not make the response MD, because the response to a *single* CE mark is O(1) segments.

 - Jonathan Morton

---

From: Jana Iyengar <[email-masked]>
Date: Thu, 19 Nov 2020 23:59:14 -0800

Jonathan,

That's not quite right. MD refers to a multiplicative reduction in the rate
or window _per RTT_. That is, the reduction in the window is f(window).
That's a critical aspect of the definition of all these terms. This goes
all the way back to Chiu and Jain
<https://www.cse.wustl.edu/~jain/papers/ftp/cong_av.pdf>.

> Conversely, looking at DCTCP and ignoring the low-pass filters which
> disappear in the long run, each CE mark causes half a segment to be
> subtracted from the cwnd.  This is classic Additive Decrease.

For the same reason, this is not correct. Presumably, since the number of
CE marks are f(window), I would argue that the reduction _over an RTT_ is
f(window). That makes this MD, not AD.

- jana

---

From: daihuichen <[email-masked]>
Date: Fri, 20 Nov 2020 08:06:45 +0000

Hello Jonathan,

I believe that subtracting half a segment from the cwnd upon a CE mark is still MD, 'cause we need to look at it from an RTT granularity.

I presented a congestion control algorithm in the last IEFT meeting, tsvwg, where I subtract beta (a parameter in unit of segment size, e.g., 0.5, 0.25) from cwnd once an ECE flag is received,
and increase cwnd by alpha/cw (alpha is also a parameter in unit of segment size, typically 1) if the ACK does not carry an ECE flag.
I referred to this operation "per-packet AIMD".

If you are interested you can find the draft and slides here:
https://www.ietf.org/id/draft-dai-tsvwg-pfc-free-congestion-control-00.txt
https://www.ietf.org/proceedings/108/slides/slides-108-tsvwg-sessb-82-pfc-free-low-delay-control-protocol-00

The cwnd update rule is simply as follows:

   if ECN-Echo = 0, cw = cw + alpha/cw
   if ECN-Echo = 1, cw = cw - beta
   where alpha and beta are constants, and cw >= 1 (0 < alpha, beta <=1).

Best,
/Huichen Dai

-----Original Message-----
From: iccrg [mailto:[email-masked]] On Behalf Of Jonathan Morton
Sent: Friday, November 20, 2020 3:45 PM
To: iccrg IRTF list <[email-masked]>
Subject: [iccrg] AIMD versus AIAD

 - Jonathan Morton
_______________________________________________
iccrg mailing list
[email-masked]
https://www.irtf.org/mailman/listinfo/iccrg

---

From: Jonathan Morton <[email-masked]>
Date: Fri, 20 Nov 2020 10:21:49 +0200

> On 20 Nov, 2020, at 9:59 am, Jana Iyengar <[email-masked]> 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.

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.

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.

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

---

From: Luca Muscariello <[email-masked]>
Date: Fri, 20 Nov 2020 11:03:07 +0100

There is a series of DEC technical reports by Dah-Ming Chiu, Raj Jain and
K.K. Ramakrishnan published in 1987,
still available online, which covers this topic

"Congestion Avoidance in Computer Networks with a Connectionless Network
Layer"
Part I: Concepts, Goals and Methodology
Part II: An Explicit Binary Feedback Scheme
Part III: Analysis of Increase/Decrease Algorithms

On Fri, Nov 20, 2020 at 8:59 AM Jana Iyengar <[email-masked]> wrote:

> That's not quite right. MD refers to a multiplicative reduction in the
> rate or window _per RTT_. That is, the reduction in the window is
> f(window). That's a critical aspect of the definition of all these terms.
> This goes all the way back to Chiu and Jain

---

From: Saverio Mascolo <[email-masked]>
Date: Fri, 20 Nov 2020 11:52:51 +0100

there is also additive increase adaptive decrease, i.e. reducing cwnd based
on measured bandwidth
sm

On Fri, Nov 20, 2020 at 8:45 AM Jonathan Morton <[email-masked]>
wrote:

> At the end of today's session, I had the opportunity to highlight the
> central feature of TCP Prague, inherited from DCTCP, which is the change in
> response to a CE mark (additive instead of multiplicative).  The response
> from the presenters (Bob & Koen) indicated that we need to clarify some
> terminology before the discussion can begin in earnest.
>
> Specifically:  what is Multiplicative Decrease, and what is Additive
> Decrease, and which one does TCP Prague use?
>
> It is well established that NewReno and CUBIC are AIMD algorithms, indeed
> Reno was the original AIMD CC.  A single packet loss or CE mark causes the
> cwnd to reduce to some fixed fraction of its previous value within one RTT
> of the congestion signal being recognised.  Or, mathematically:
>
> subtracted from the cwnd.  This is classic Additive Decrease.  There is
> still (barring implementation bugs) a Multiplicative Decrease response to
> packet loss.  So, distilling:
>
> The above is true regardless of how closely spaced the congestion signals
> are.  With precise feedback of CE marks, you can successfully register a
> mark on every data packet during a whole RTT and obtain, effectively, a
> multiplicative decrease - but that does not make the response MD, because
> the response to a *single* CE mark is O(1) segments.
>
>  - Jonathan Morton

-- 
Saverio Mascolo,  Professore Ordinario di Automatica

Direttore del
Dipartimento di Ingegneria Elettrica e dell'Informazione (DEI)
Politecnico di Bari

Via Orabona 4, 70125 Bari Italy
Tel. +39 080 5963621
Fax. +39 080 5963410
email:[email-masked]

http://c3lab.poliba.it

=================================
 This message may contain confidential and/or legally privileged
information.
  If you are not the intended recipient of the message, please destroy it.
 Any unauthorized dissemination, distribution, or copying of the material in
 this message, and any attachments to the message, is strictly forbidden.

---

From: Bob Briscoe <[email-masked]>
Date: Fri, 20 Nov 2020 16:46:40 +0000

Jonathan,

> 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 fa…

[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 subtract…

[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…

[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

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

---

From: Praveen Balasubramanian <[email-masked]>
Date: Fri, 20 Nov 2020 17:45:03 +0000

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 <[email-masked]> On Behalf Of Bob Briscoe
Sent: Friday, November 20, 2020 8:47 AM
To: Jonathan Morton <[email-masked]>; Jana Iyengar <[email-masked]>
Cc: iccrg IRTF list <[email-masked]>
Subject: [EXTERNAL] Re: [iccrg] AIMD versus AIAD

Jonathan,

On 20 Nov, 2020, at 9:59 am, Jana Iyengar <[email-masked]><mailto:[email-masked]> wrote:

[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.

[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

[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

 - Jonathan Morton

iccrg mailing list

[email-masked]<mailto:[email-masked]>

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>

---

From: Bob Briscoe <[email-masked]>
Date: Fri, 20 Nov 2020 17:53:14 +0000

Jonathan,

On 20/11/2020 07:59, Jana Iyengar wrote:
> f(window). That's a critical aspect of the definition of all these 
> terms. This goes all the way back to Chiu and Jain 
>     Conversely, looking at DCTCP and ignoring the low-pass filters
>     which disappear in the long run, each CE mark causes half a
>     segment to be subtracted from the cwnd.  This is classic Additive
>     Decrease. 
>
>
> For the same reason, this is not correct. Presumably, since the number 
> of CE marks are f(window), I would argue that the reduction _over an 
> RTT_ is f(window). That makes this MD, not AD.

[BB]  Indeed, thanks Jana,

@Jonathan, the difference you are grappling with between DCTCP's 
response and Reno's is what makes Reno doubly multiplicative, whereas 
DCTCP is singly multiplicative (deliberately). The doubly multiplicative 
cause Reno's sqrt.

Let's see if I can explain this. I'll outline rough 'balance equations' 
between:
* the addition to W in a round and
* the subtractions from W in a round.
In steady state the two will be equal.
(But please don't beat me up about the numerical constants - they aren't 
correct 'cos I'm simplifying)
I'll use 'NACK' to mean either a dropped packet or an ECN-marked packet

==Reno==
AI: W <- W + 1                                                 Eqn (1)
MD: W <- W - W/2 * (probability of at least one NACK in a round)        
Eqn (2)

Definition: p is the probability of any individual packet being marked 
during this round.
So the probability of any one of W packets being NACK'd is p*W.

So Eqn(2) becomes
MD: W <- W - W/2 * p*W

At balance: AI = MD
     1 = pW^2/2
Rearranging: W = sqrt(2/p)

With a more precise model, the constant is roughly 3/2, not 2, but I'll 
just call it C for now.
W = sqrt(C/p)
or
p = C/(W^2)                                                             
Eqn (3)

==DCTCP==

AI: W <- W + 1                                                         
     Eqn (4)
MD: W <- W - alpha*W/2 * (probability of at least one NACK in a round)   
     Eqn (5)
As with Eqn (3), that is:
MD: W <- W - alpha*W/2 * p*W

At balance: AI = MD
     1 = p*alpha*W^2/2

Given alpha is the EWMA of p over a number of rounds, in steady state, 
alpha -> p.
     1 = p^2 * W^2/2
Rearranging: W = 2/p                                                     
Eqn (6)

===Scaling==

Let's call the number of NACKs in a round, v.
By the definition of p:
     v = pW.

Substituting from the balance formulae for W:
v_reno = C/(W^2) * W
             = C/W                                                     
             Eqn (7)

v_dctcp: v = p * 2/p
                 = 2       Eqn (8)

So, as W increases,
     v_reno reduces proportionately.
     v_dctcp remains invariant at 2

That's why DCTCP can be called scalable.

HTH

Bob