Re: [iccrg] AIMD versus AIAD

[Bob Briscoe <[e-mail]>]

Jonathan,

On 20/11/2020 07:59, Jana Iyengar wrote:
> Jonathan,
>
>     MD:  O(1) signals causes O(N) reduction in cwnd.
>
>
> 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.

[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

>
> - jana
>
> _______________________________________________
> iccrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/iccrg

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