[e2e] cwnd update correction for congestion avoidance

[Michael Welzl]

Dear all,

I'm now taking this to tcpm, too...

On tuesday, Anil Agarwal sent a message to the end2end list
which made it clear that the equation:

cwnd += SMSS*SMSS/cwnd

from 2581 does not really add a segment every RTT as desired.
(He also went into some ABC related details, but I'll
not go into them for now to keep things simple.)


The underlying problem is that cwnd changes with every
ACK that comes in, leading to a slightly decreasing
increase factor with each ACK. While tons of books and
papers erroneously state that this equation adds
*EXACTLY* one segment per RTT, RFC 2581 correctly says
that it is an acceptable approximation.

Mathematica couldn't solve the equation x(t+1) += 1/x(t)
(counting in segments now), but MS Excel told me that the
effect is quite negligible for, say, a window of 1000
segments which have 1000 bytes each.


However, the problem may become aggravated when cwnd
is small compared to the b-d-product. Anil gave this
simple example, assuming MSS=1000 and cwnd=1000 at
the beginning, and counting in bytes:


> After 1 RTT, cwnd = 1000 + (1000 * 1000) / 1000 = 2000
> 
> In the second RTT, 2 segments are sent and acknowledged.
> After the first ACK, cwnd = (2000 + (1000 * 1000) / 2000) = 2500
> After the second ACK, cwnd = (2500 + (1000 * 1000) / 2500) = 2900
> 
> In the third RTT, 2 segments are sent and acknowledged.
> After the first ACK, cwnd = (2900 + (1000 * 1000) / 2900) = 3244
> After the second ACK, cwnd = (3244 + (1000 * 1000) / 3244) = 3552


Only TWO segments are sent in the third RTT - I can imagine
that right after a congestion event, this problem might
play a role, depending on the spacing of ACKs.


I really don't understand why this isn't fixed - it seems
to be easy?!

* When entering congestion avoidance, set old_cwnd = cwnd

* Whenever a non-duplicate ACK arrives during congestion
  avoidance, do:

  cwnd += SMSS*SMSS/old_cwnd;

  if ( (cwnd - old_cwnd) >= SMSS )
      old_cwnd = cwnd;


This will have old_cwnd advance in SMSS-steps.

Perhaps I'm missing something here, but if this code above
is wrong, there surely is some other easy way to fix the
problem.


Cheers,
Michael