CBFSketch: A Scalable Sketch Framework for High Speed Network
Haiting Zhu, Yuan Zhang, Lu Zhang, Gaofeng He, Linfeng Liu · 2019
Sketch is a compact data structure used to summarize data streams. It has high measurement accuracy and uses less space than traditional measurement methods. Thus it is widely used in the measurement of network traffic. Currently, there are some typical sketches: Count-Min Sketch, CU Sketch, and Count Sketch, but they still waste memory when storing mice flows. To further improve memory space utilization, we propose a new sketch framework - CBFSketch, which is combined with Count-Min Sketch and Bloom Filter. In the new framework, the sketch is created dynamically and the memory space is adjusted timely according to the traffic size. Our experiments show that the space utilization can be significantly improved, and in the case of using the same memory space, the average relative error is reduced by about 20% to 50% compared with other sketches.