2
$\begingroup$

I am trying to work out a summation for packet delays which is very similar to the summation for estimating RTT, which is an exponentially weighted moving average. I have modified the estimating RTT summation below (I think I did it correctly) but it does not seem to fit correctly with the part I know is right (where 0.1 has been substituted for u). If I have written this summation out correctly can someone explain why the summation raises (1-u) to the ith power and why the summation replaces u with (1-u)^n-1 and why the summation is multiplied by u/(1-u).enter image description here

EDIT: If I had not looked at the estimated RTT summation this is what I would have guessed...

enter image description here

  • 0
    @Mitch [RTT - Round Trip Time](http://en.wikipedia.org/wiki/Round-trip_delay_time)2011-03-31

2 Answers 2

1

HINT

Since there is uncertainty with 1-u, I suggest backtracking, and writing the first few terms completely out:

$d_1 = u(r_1 - t_1)$

$d_2 = (1-u)^1 u(r_1 - t_1) + u(r_2 - t_2)$

$d_3 = (1-u)^2 u(r_1 - t_1) + (1-u)^1 u(r_2 - t_2) + u(r_3-t_3)$

Now, adding in a $(1-u)^0$ which equals one, we can get:

$d_1 = (1-u)^0 u(r_1 - t_1)$

$d_2 = (1-u)^1 u(r_1 - t_1) + (1-u)^0 u(r_2 - t_2)$

$d_3 = (1-u)^2 u(r_1 - t_1) + (1-u)^1 u(r_2 - t_2) + (1-u)^0 u(r_3-t_3)$

By looking at the equations that are written out, the powers of (1-u) are of reverse magnitude to the indexes of r and t. So I think that you're looking for that in your sum. Both summations you have don't do that.

Consider this: it's possible to consolodate everything into one sum, once you match up the powers and indexes correctly.

So here's something that you can try. Take $d_2$, the equation with two terms. How do you write that as a sum, for example $d_2 = \sum_{i=0}^{2-1}{\mbox{equation}}$

Try $d_2 = u\sum_{i=0}^{2-1}{(1-u)^i(r_{2-i}-t_{2-i})}$

This should check out as being $d_2$.

Once this is confirmed, it shouldn't be too much trouble to extend this so that 2 can be replaced with n.

  • 0
    You're very welcome!2011-03-31
1

Your $d_n$ in the first equation is the mean of the quantities $(r_i-t_i)$ where the index $i$ is chosen at random between $1$ and $n$. Calling this random index $I_n$ and introducing $\varphi(i)=r_i-t_i$, one gets $d_n=E(\varphi(I_n))$, with $P(I_n=k)=u(1-u)^{k-1}$ for every $k$ between $1$ and $n-1$ and $P(I_n=n)=(1-u)^{n-1}$. In other words, $I_n$ is distributed like $\min\{G,n\}$, where $G$ is a geometric random variable of parameter $u$. Recall that, by definition, $P(G=k)=u(1-u)^{k-1}$ for every integer $k\ge1$.

This is not consistent with what is written in the red frame. This frame reads as the recursion $d_k=u\varphi(k)+(1-u)d_{k-1}$ (with the convention that $d_0=0$), which yields $ d_n=\sum_{k=1}^nu(1-u)^{n-k}\varphi(k)+(1-u)^n\cdot 0. $ Note the power $n-k$ (and not $k$) of $1-u$ in the coefficient of $\varphi(k)=r_k-t_k$.