Prob-CS: A Probabilistic Cuckoo Sketch for Accurate Network Traffic Measurement

For Internet of Things (IoT) networks and devices, the network traffic measurement owns security significance. It usually focuses on the frequency estimation and top-k flows detection, two basic measurement tasks where the sketch has been widely used as the outline data structure. Existing measurement schemes make tradeoffs between efficiency, accuracy and speed. Some of them, such as the recently proposed augmented sketch, improve the accuracy of measurement tasks by separating elephant flows from mouse flows. Yet, the performance can be severely degraded due to the exchange of traffics between the filter and the sketch section. In this article, the probabilistic cuckoo sketch (Prob-CS), a new data structure consisting of several buckets with two hash functions, is proposed to obtain the high accuracy as well as the good memory utilization for the measurement tasks. Specifically, a probabilistic replacement strategy is utilized to reduce the impact of mouse flows on elephant flows, which helps the proposed Prob-CS to accurately record the elephant flow. Meanwhile, the cuckoo hashing is introduced to relocate the replaced flows, thus fully improving the memory utilization. Numerous experimental results show that our Prob-CS achieves the best frequency estimation accuracy, and owns the competitive performance in terms of the top-k precision and the throughput compared to well-established programs.