# Rough Estimator Based Asynchronous Distributed Super Points Detection on High Speed Network Edge
## 4 RE Based Distributed Super Points Detection Algorithm READ
### Scanning IP Pair in a Distributed Environment  
Distributed scanning IP address pairs is to scan the IP address pairs collected at each observation node. Let \(\mathcal{O}_{\text{I}}\) denote the I-th observation node and \(\mathbb{S}_{\mathcal{T},\text{I}}^{\textit{pair}}\) denote all IP address pairs in time window \(\mathcal{T}\) on \(\mathcal{O}_{\text{I}}\). READ uses RE estimator and LE estimator to record IP information. Each observation node has the same cardinality estimation structure: the same number of RE and LE, and the same number of counters in RE and LE. The basic operation of \(\mathcal{O}_{\text{I}}\) when scanning IP address pairs is to update RE and LE. READ uses RE to generate global candidate super points, and LE to estimate the cardinality of each global candidate super point. In a distributed environment, because only part of the network traffic can be observed at each observation node, it is impossible to determine whether a host is a global candidate super point according to RE when scanning IP address pairs. In a distributed environment, the algorithm of super points detection must be able to recover the global candidate super points directly, such as DCDS and VBFA. In order to recover candidate super points, READ adopts a new data structure, Rough Estimator Cube (REC). REC is a three-dimensional data structure composed of RE, as shown in Figure 3. Inspired by VBFA, READ restores candidate super points by concatenating sub bits of RE indexes in REC. The basic element of REC is RE. Several RE constitutes a one-dimensional RE vector (REV); the set of REV constitutes a two-dimensional RE array (RE Array, REA). The three-dimensional REC can be regarded as a set of REA, which contains \(2^{r}\) REA and \(r\) is a positive integer less than 32. Each REA of REC has the same structure, that is, the REA contains the same number of RE, and the associating REV contains the same number of RE. Let \(u\) denote the number of REV contained in REA and \(2^{v_{i}}\) denote the number of RE contained in the \(i\)th REV. Three indexes can be used to locate a RE in REC accurately. All observation nodes have their own REC, and the structure of REC at different observation nodes is the same, that is, the \(r\), \(u\), \(2^{v_{i}}\) of REC at different observation nodes are the same. When the IP address pair is scanned at the observation node, the REC at the observation node will be updated. Let \(\mathbb{R}^{\text{I}}\) denote the REC on the observation node \(\mathcal{O}_{\text{I}}\), \(\mathbb{R}^{\text{I}}_{(i,j,k)}\) denote the \(j\)-th RE of the \(i\)-th REV on the \(k\)-th REA, where k is an integer between 0 and \(2^{r}-1\), i is an integer between 0 and \(u-1\), and j is an integer between 0 and \(2^{v_{i}}-1\). In time window \(\mathcal{T}\), for each IP address pair \(<\texttt{a},\texttt{b}>\) of \(\mathbb{S}_{\mathcal{T},\text{I}_{u}}^{\textit{pair}}\) READ selects \(u\) RE from \(\mathbb{R}^{\text{I}}\) according to a, and updates \(u\) RE with b. How to map a to \(u\) RE in REC determines whether READ can recover global candidate super points from REC. The \(u\) RE associating with a are located in the same REA. READ divides \(\mathbb{A}\) into two parts: the first part is \(r\) bits on the right (Right Part, RP), and the second part is 32-\(r\) bits on the left (Left Part, LP). READ selects a REA in the REC based on the IP of a. REC has \(2^{r}\) REA, so the RP of a can determine only one REA in the REC. READ divides \(\mathbb{A}\) into \(2^{r}\) subsets according to \(r\) bits on the right side of the IP address. Each subset of \(\mathbb{A}\) associates with a REA in the REC. During the operation of the algorithm, the number of RE in the REC is fixed, and each RE is used to record opposite hosts of multiple a. When \(\mathbb{A}\) contains many IP addresses, by increasing \(r\), the number of hosts sharing the same RE can be reduced. The LP of a is used to select \(u\) RE in REA, i.e., one RE from each REV.