Deviation for Packet Streams

We define the deviation for packet streams in this section. Suppose we have a graph of a packet stream $A$ and a graph of another packet stream $B$. If we move graph $B$ horizontally as well as vertically on the X-Y plane without crossing $A$ so that $B$ is as close as possible to $A$, the average gap on the X-axis between $B$ and $A$ will be small if the two are in the same connection chain and large if the two are unrelated. Intuitively, we define this average gap as the deviation for $B$ from $A$. See Fig. 2 (right) for an example. In this figure, the position of the line showing the data for $B$ is where the average gap between the two lines for $B$ and $A$ is the smallest. The formal definition of the deviation is as follows:

Note that the sequence numbers associated with the data bytes in the $i$th packet of $A$ are $a_{i-1}+1,a_{i-1}+2,\ldots,a_i$ and these are within a single packet so that $t(a_{i-1}+1)=t(a_{i-1}+2)=\cdots =t(a_i)$. The same is true for the sequence numbers and time stamps of $B$. The deviation for $B$ from $A$ is defined only if the total data size of $B$ is larger than that of $A$, so we can assume that $b_m-b_0 \geq a_n-a_0$.

A deviation is a measurement of how far the graph of a packet stream $B$ differs from the graph of a given packet stream $A$. It is basically the average horizontal distance between the two graphs computed along the vertical range of graph $A$. But we have to consider the position of graph $B$ against $A$ so that the average distance between the two is the minimum when computing the deviation.

Since we do not know in advance in what range of $B$ be best matched to $A$, we have to try every range of $B$. This means we move $B$ vertically to find out the vertical position where the average distance between the two graph is the minimum. The $\min_{0\leq k\leq m'}$ of (1) treats this minimization.

We also have to consider the horizontal position. Because if the shapes of the two graphs are almost identical but the horizontal distance between the two graphs is large (due to for example long propagation delays), the deviation would be large, which is obviously not desired. So we move $B$ horizontally as well as vertically to find out the position where the average distance between the two is the minimum. There are two directions for moving $B$ horizontally since $B$ cannot cross $A$. One is to move from left to right and the other is from right to left. The $\min_{1\leq h\leq d}$ of (1) treats the minimization of the horizontal position moving from right to left and the $\max_{1\leq h\leq d}$ of (1) treats the minimization of the horizontal position moving from left to right.