Implementation

In this section, we show how to compute deviations, defined by Def. 4 in an efficient manner.

Suppose we have a given packet stream $A$ as an array of $n$ elements in main memory.

$$A:\quad \langle (t(a_1),a_1), (t(a_2),a_2) ,\ldots ,(t(a_n),a_n) \rangle$$

Also suppose that we have traffic data $S$, packets in which are stored in chronological order as they were captured in a storage disk, which is a source of packet streams for comparing with $A$ to compute deviations. It is essential that $S$ should be scanned once sequentially for efficient implementation.

The entire structure of the implementation is described in the following steps.

1. Until we reach the end of $S$ repeat the following.
   1. Take the next packet $p$ to the previous one taken from $S$.
   2. Retrieve the entry of the packet stream to which $p$ belongs from a hash, or create a new entry in the hash when there is no packet stream to which $p$ belongs or $p$ is the first packet of a connection.
   3. Do some computation on the entry of the packet stream in the hash to update the values relating to the deviation for that packet stream.
2. Traverse the hash to iterate all the entries of the packet streams to get the deviations for them.

The key to the hash is the 4-tuple TCP connection parameters together with the direction of packet $p$. We will describe the details of the step (1c) in the next section. We denote that the entry of the packet stream $B$ is retrieved at step (1b) and that the packet taken at step (1a) is the $k$th packet of $B$.

$$B:\quad \langle (u(b_1),b_1), (u(b_2),b_2) ,\ldots ,(u(b_k),b_k),\ldots \rangle$$

We also denote that $v(r, s) = u(r) - t(s)$.