Re: comments on RFC1323.bis

[Sally Floyd <[e-mail]>]

  *> 	* A significant technical issue: the current RTTM discussion
  *> 	  does not mention anything about altering the constants used
  *> 	  for the exponentially-weighted moving average when updating
  *> 	  the estimate of RTT. 

Short summary:

>From a quick look, I think that you could make a small
change to the weight in the exponential weighted moving average, and
get a "time constant" (in numbers of samples averaged, not in seconds)
to use for the timestamp option that gives roughly the same "time
constant" as the old weight without the timestamp option.

Another outstanding question about the timestamp option is whether,
with more accurate samples and therefore a more accurate estimate of
the mean and mean deviation, it is still sufficient to set the RTO to
the average plus *four* times the mean deviation.  The more
conservative thing to do, in compensation for the more accurate
estimates, would be to use a larger multiple for the mean deviation.

It seems to me that this leaves open the questions of whether (1) this
gives sufficient benefit over the old method; or (2) we should take the
hit now and check out other methods for calculating the RTO.  However,
my *guess* would be that timestamps with the changed weight gives
better performance than no timestamps...

Details:

(The question is whether your average RTT is reflecting the samples of
the RTT taken over a number of roundtrip times, or whether your average
RTT is only reflecting the samples of the RTT taken from the most
recent congestion window of packets.)

Assume, for purposes of simple illustration, that the measured RTT
abruptly changes to "new", and we are using the old algorithm.
Then we update the RTT estimate once per window, as follows:

  avg <- (1-w) avg_0 + w new

Where "avg_0" is the original estimate of the RTT.

Now imagine that instead, we are using the timestamp option. 
We probably have a much more accurate measurement of "new", but we will
ignore that for the moment.  The key thing is that instead of
updating the RTT estimate once, we update it N times, as follows:
(We are using weight w1 with the timestamp option.)

First packet:
  avg <- (1-w1) avg_0 + w1 new1
Second packet:
  avg <- (1-w1) ((1-w1) avg_0 + w1 new1) + w1 new1

N-th packet:
  avg <- (1-w1)^n avg_0 + sum_i=0^(n-1) (1-w1)^i w1 new1

So if we set w1 so that 

  (1-w1)^n = (1-w),

or

     w1 = ( 1 - (1-w)**(1/n) ),

then we get something with the timestamp option that is close to
what we get without the timestamp option with weight w.  

(Unfortunately, I usually do this stuff on mathematica, and things seems
to have changed so that I now need a special password to use
mathematica.  But scripts for very simple numerical experiments on S
are below.)

That means, for example, that for a weight w of 1/32 without
timestamps, the weight with timestamps and a congestion window N of 10
packets would be 1 - (1-w)**(1/N), which is 0.003169835, or roughly
1/256.  (Well, actually, N represents not the congestion window, but
the number of estimates of the RTT that are averaged-in in one RTT.)

(This could use a second check from someone else...)

If anyone is moved to investigate further, the ns simulator has an
option for TCP timestamps (Agent/TCP set timestamps_ true), but it is
not tested in any of the validation tests (even in the validation test
for retransmit timers, "test-all-tcp" in tcl/test), so I don't know if
it works correctly these days or not.  (Analytical investigations are
useful if we assume that the RTT samples come from some stationary
distribution, but that is clearly a stretch...)

- Sally
--------------------------------
http://www-nrg.ee.lbl.gov/floyd/

Scripts for S:

The function avgg(old, new, N, w0) computes the new average RTT
when the old average was "old", the new measurements are all "new",
there are N samples of the new measurement, and the weight used
in the exponential weighted moving average is "w".

Working data will be in /home/pig/u1/floyd/.Data
> avgg <- function(avg, new, k, w) 
{
        if (k>1) {
          newavg <- (1-w)*avg + w*new 
          count <- k-1
          avgg(newavg, new, count, w) 
        }
        else
          (1-w)*avg + w*new   
}
+ + + + + + + + > w0 <- 1/32
> N <- 10
> old <- 2
> new <- 1
> w1 <- 1 - (1-w0)**(1/N)
> avgg(old, new, 1, w0)		## without timestamps
[1] 1.96875
> avgg(old, new, N, w0)		## timestamps, old weight, window = N 
[1] 1.727976
> avgg(old, new, N, w1)		## timestamps, new weight, window = N
[1] 1.96875

> old <- 1
> new <- 2
> avgg(old, new, 1, w0)
[1] 1.03125
> avgg(old, new, N, w0)
[1] 1.272024
> avgg(old, new, N, w1)
[1] 1.03125

> w0
[1] 0.03125
> w1
[1] 0.003169835