Open Access
ARTICLE
High Accuracy Network Cardinalities Estimation by Step Sampling Revision on GPU
Jie Xu1, *, Qun Wang1, Yifan Wang1, Khan Asif2
1 Jiangsu Police Institute, Nanjing, 210031, China.
2 Department of Computer Application, Crescent Institutes of Science and Technology, Chennai, 600048, India.
* Corresponding Author: Jie Xu. Email: .
Computers, Materials & Continua 2020, 64(3), 1819-1844. https://doi.org/10.32604/cmc.2020.010727
Received 24 March 2020; Accepted 29 April 2020; Issue published 30 June 2020
Abstract
Host cardinality estimation is an important research field in network
management and network security. The host cardinality estimation algorithm based on
the linear estimator array is a common method. Existing algorithms do not take memory
footprint into account when selecting the number of estimators used by each host. This
paper analyzes the relationship between memory occupancy and estimation accuracy and
compares the effects of different parameters on algorithm accuracy. The cardinality
estimating algorithm is a kind of random algorithm, and there is a deviation between the
estimated results and the actual cardinalities. The deviation is affected by some
systematical factors, such as the random parameters inherent in linear estimator and the
random functions used to map a host to different linear estimators. These random factors
cannot be reduced by merging multiple estimators, and existing algorithms cannot
remove the deviation caused by such factors. In this paper, we regard the estimation
deviation as a random variable and proposed a sampling method, recorded as the linear
estimator array step sampling algorithm (
L2S), to reduce the influence of the random
deviation.
L2S improves the accuracy of the estimated cardinalities by evaluating and
remove the expected value of random deviation. The cardinality estimation algorithm
based on the estimator array is a computationally intensive algorithm, which takes a lot of
time when processing high-speed network data in a serial environment. To solve this
problem, a method is proposed to port the cardinality estimating algorithm based on the
estimator array to the Graphics Processing Unit (GPU). Experiments on real-world highspeed network traffic show that
L2S can reduce the absolute bias by more than 22% on
average, and the extra time is less than 61 milliseconds on average.
Keywords
Cite This Article
J. Xu, Q. Wang, Y. Wang and K. Asif, "High accuracy network cardinalities estimation by step sampling revision on gpu,"
Computers, Materials & Continua, vol. 64, no.3, pp. 1819–1844, 2020. https://doi.org/10.32604/cmc.2020.010727