Re: [iccrg] AIMD versus AIAD

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:iccrg-bounces@irtf.org] On Behalf Of Jonathan Morton
Sent: Friday, November 20, 2020 3:45 PM
To: iccrg IRTF list <iccrg@irtf.org>
Subject: [iccrg] AIMD versus AIAD

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
_______________________________________________
iccrg mailing list
iccrg@irtf.org
https://www.irtf.org/mailman/listinfo/iccrg