Premium
Accurate counting algorithm for high‐speed parallel applications
Author(s) -
Wang Junchang,
Li Tao,
Fu Xiong
Publication year - 2018
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.5090
Subject(s) - computer science , consistency (knowledge bases) , scalability , deep packet inspection , counting problem , parallelism (grammar) , algorithm , network packet , parallel computing , artificial intelligence , computer security , operating system
Summary Statistical counter offers the appeal of an efficient and scalable counting mechanism on multi‐core architectures where parallelism has been increasing sharply. Statistical counter has been widely used in practice (eg, in high‐end network devices to count the number of packets received) despite the truth that it can only provide weak consistency guarantee on the counting results it returns, that is, statistical counter could miscount and the returned results may be inaccurate. As hardware and its parallelism advances, the miscount issue has raised concerns in both industry and academy. This paper is motivated by this real‐world miscount issue that we were facing when building a high‐speed intrusion detection system on a commercial multi‐core server with 40Gbps NICs. To tackle the problem, we first systematically analyze the miscount issue and quantify the miscounts in counting results. Then, we present a novel counting algorithm that (1) is competitive to statistical counter in performance on multi‐core architectures and (2) provides strong consistency guarantee on counting results returned. Experiments show that it takes the new counting algorithm 10ns and 1,500ns to perform an update and a read operation, respectively. Moreover, the counting results returned are accurate.