Analysis of Deviations

We analyze what a deviation, defined by Def. 4 means in this section. The following lemma gives an upper bound on the deviation.

Proof. Let $\alpha$ and $\beta$ be the differences between an accurate clock and the clocks of $A$ and $B$ respectively, and denote $\tilde{t}(s)=t(s)+\alpha$ and $\tilde{u}(r)=u(r)+\beta$. Since the connections of $A$ and $B$ are in the same connection chain and the packets of both are moving in the same direction, there exists $k$ such that each data byte associated with a sequence number $b_k+h  (h=1,2,\ldots,d=a_n-a_0)$ in $B$ is equal to the data byte associated with a sequence number $a_0+h$ in $A$. We denote $\tilde{T}(h,k)=\tilde{u}(b_k+h)-\tilde{t}(a_0+h)$, and without loss of generality, will focus the proof on the case where $\tilde{T}(h,k)\geq 0$. This is the case covered by the first equation inside the braces of $\min$ in (1):

$$\frac{1}{d}\sum_{h=1}^d\left(T(h,k)\!-\!\min_{1\leq h\leq d}\!\{T(h,k)\}\right) = \frac1d\sum_{h=1}^d\left(\tilde{T}(h,k)\!-\!\min_{1\leq h\leq d}\!\{\tilde{T}(h,k)\}\right)$$ (1)

$$= E(\tilde{T}(h,k)) - \min_{1\leq h\leq d}\!\{\tilde{T}(h,k)\}$$ (2)

where $E(\tilde{T}(h,k)) = \frac1d\sum_{h=1}^d\tilde{T}(h,k)$ is the average of $\tilde{T}(h,k)$. Note that $\tilde{T}(h,k)$ is the propagation time for the data byte associated with a sequence number $a_0+h$ to travel from the network location at $A$ to the network location at $B$ as measured by accurate clocks. Therefore, the deviation calculated by (1) is less than the value of (3), which is the average propagation delay minus the minimum propagation delay between the connections of $A$ and $B$.$\qedsymbol$ ARRAY(0x24a9908) $\qedsymbol$

Assuming that the average propagation delay a packet travels from the beginning of a connection chain to the end of the connection chain is at most a few seconds, the deviations for packet streams on those connections are also at most a few seconds.