# A Review on Hot-IP Finding Methods and Its Application in Early DDoS Target Detection
## 2 Hot-IP Finding Methods
### Comparison of Hot-IP Finding Methods
#### 2.3.2 Comparison of Hot-IP Finding Time  
We use data sets extracted from UCLA data sets [13] for our experiments. Our experimental data sets have the numbers of records (also the IP addresses) gradually increased to measure the processing time of the Count-Sketch, Count-Min and Group Testing methods. The sizes of the data sets are gradually increased from 10,000 IP addresses to a maximum of 1,000,000 IP addresses. Because of the differences in the input parameters and space required, we create three scenarios to compare these three methods on two pairs, including (1) Count-Sketch and Count-Min; and (2) Count-Min and Group Testing. All experiments in this section are implemented in Java and run on a laptop machine with an Intel core i5-M460 2.53 GHz CPU, 8 GB RAM on 64-bit Microsoft Windows 8. For each dataset, five runs are executed and the average of processing time (excluding the time for I/O operations) is the final result. 1 Scenario 1: Compare Count-Sketch and Count-Min using the same initialization parameters \(\varepsilon=0.005\) and \(\delta=0.00000001\). The experiment result is shown in Table 5.
2 Scenario 2: Compare Count-Sketch and Count-Min using the same processing space. For Count-Sketch, select \(\varepsilon=0.01\) and \(\delta=0.00005\), and select \(\varepsilon=0.00009\) and \(\delta=0.00001\) for Count-Min. The experiment result is shown in Table 4. It can be seen from Tables 4 and 5 that Count-Min is significantly faster than Count-Sketch in both cases of using the same initialization parameters or using the same processing space. 3 Scenario 3: Compare Count-Min and Group Testing using the same matrix size. For Count-Min, select \(\varepsilon=0.00045\) and \(\delta=0.0000001\), and we have the counter matrix \(\mathit{CM}\)[19,6041]. For Group Testing, select \(RS[15,3]_{16}\) and \(d\)-disjunct as 6000 (corresponding to 6000 unique IPs), and we have \(d\)-disjunct matrix \(m\)[240,6000]. The experiment result is shown in Table 6. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Method** & **Count-Sketch** & **Count-Min** & **Group Testing** \\ \hline Space requirements & \(O\left(d\times w+2d\right)=O(\ln\left(\frac{1}{\delta}\right)\times\frac{ \varepsilon}{\varepsilon^{2}})\) & \(O\left(d\times w\right)=O(\ln\frac{1}{\delta}\times\frac{\varepsilon}{ \varepsilon})\) & \(O\left(\log^{3}N\ (\log N+\log M)\right)\) \\ Processing time & \(O\left(d\right)=O(\ln\frac{1}{\delta})\) & \(O\left(d\right)=O(\ln\frac{1}{\delta})\) & \(O(q^{2}\times\mathrm{poly\ (log\ (t))})\) \\ Estimated Hot-IP finding time & \(O\left(d\right)=O(\ln\frac{1}{\delta})\) & \(O\left(d\right)=O(\ln\frac{1}{\delta})\) & \(\mathrm{poly\ (\emph{)}}(d)\times t\times\log^{2}t+O\left(t^{2}\right)\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Complexity comparison of Count-Sketch, Count-Min and Group Testing methods. The experimental results given in Table 6 show that Group Testing is slightly faster than Count-Min in finding Hot-IPs in the IP packet stream. However, the space requirement of Group Testing is much higher than that of Count-Min, even though they use the same width matrices because Group Testing uses the \(d\)-disjunct matrix with a much larger number of tests \(t\). Overall, Count-Min is more efficient than Group Testing because its space requirement is much smaller than that of Group Testing while its processing time is almost equivalent to that of Group Testing. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Number of IP in Stream** & **Count-Min (s)** & **Group Testing (s)** \\ \hline
10,000 & 0.019 & 0.023 \\
50,000 & 0.084 & 0.077 \\
100,000 & 0.159 & 0.143 \\
200,000 & 0.377 & 0.354 \\
300,000 & 0.442 & 0.388 \\
400,000 & 0.625 & 0.497 \\
500,000 & 0.761 & 0.625 \\
600,000 & 0.897 & 0.822 \\
700,000 & 1.035 & 0.916 \\
800,000 & 1.207 & 1.047 \\
900,000 & 1.377 & 1.224 \\
1,000,000 & 1.558 & 1.307 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Time for finding Hot-IPs of Count-Min and Group Testing using the same matrix size.