Cuckoo Counter: Adaptive Structure of Counters for Accurate Frequency and Top-k Estimation
IEEE/ACM Transactions on Networking · 2023-08 · 31 (4) · 1854-1869
DOI: 10.1109/tnet.2022.3232098 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE/ACM Transactions on Networking, 2023-08. Verfasst von Qilong Shi und 6 weiteren Autor:innen. Die Arbeit wurde bisher 37-mal zitiert (Crossref) und nennt 54 Literaturangaben. Gefördert von: Key-Area Research and Development Program of Guangdong Province, National Key Research and Development Program of China, Major Key Project of Peng Cheng Laboratory.
Abstract (Originalsprache)
Frequency estimation and top-k flows identification are fundamental problems in network traffic measurement. Sketch, as a basic probabilistic data structure, has been extensively investigated and used in different management applications. However, few of them is suitable for both estimating frequency and finding top-k flows due to the unbalanced distribution of real-world network streams. By introducing a pre-filtering stage to isolate elephant and mice flows, the recently proposed Augmented Sketch (ASketch) significantly improves accuracy for both tasks. However, it suffers from serious performance degradation because of frequent flow exchanges. In this paper, we propose Cuckoo Counter (CC), an adaptive structure that consists of several buckets organized in a specific way. The size of the entry in each bucket is carefully designed to match the actual distribution of streams. During processing, CC hashes a flow to buckets and uses the idea of cuckoo hashing to relocate the flow if an overflow or collision happens, which contributes to fully utilizing memory. Therefore, the replacement strategy helps CC precisely record elephant flows and cover more mice flows, and also guarantees the throughput. Extensive experimental results show that CC has the highest (Freq.) accuracy, excellent (Heavy hitter / change) accuracy, highest (Top-k) precision, and competitive throughput compared to the state-of-the-art. Specifically, CC improves the throughput and accuracy by around 1 and 2 orders of magnitude respectively compared to the well-known ASketch.
Förderung
- Key-Area Research and Development Program of Guangdong Province
- National Key Research and Development Program of China
- Major Key Project of Peng Cheng Laboratory
- National Natural Science Foundation of China
- Basic Research Enhancement Program of China
- China Post-Doctoral Science Foundation
- International Post-Doctoral Exchange Fellowship Program of China
- Open Research Projects of Zhejiang Laboratory
Zitieren
APA
Shi, Q., Xu, Y., Qi, J., Li, W., Yang, T., Xu, Y., & Wang, Y. (2023). Cuckoo Counter: Adaptive Structure of Counters for Accurate Frequency and Top-k Estimation. IEEE/ACM Transactions on Networking, 31(4), 1854-1869. https://doi.org/10.1109/tnet.2022.3232098
Vancouver
Shi Q, Xu Y, Qi J, Li W, Yang T, Xu Y, et al. Cuckoo Counter: Adaptive Structure of Counters for Accurate Frequency and Top-k Estimation. IEEE/ACM Transactions on Networking. 2023;31(4):1854-1869. doi:10.1109/tnet.2022.3232098
BibTeX
@article{Shi2023,
author = {Shi, Qilong and Xu, Yuchen and Qi, Jiuhua and Li, Wenjun and Yang, Tong and Xu, Yang and Wang, Yi},
title = {Cuckoo Counter: Adaptive Structure of Counters for Accurate Frequency and Top-k Estimation},
journal = {IEEE/ACM Transactions on Networking},
year = {2023},
volume = {31},
number = {4},
pages = {1854--1869},
doi = {10.1109/tnet.2022.3232098}
}
EUVIMED