Cache Assisted Randomized Sharing Counters in Network Measurement
Qian Liu, Haipeng Dai, Alex X. Liu, Qi Lecky Li, Xiaoyu Wang, Jiaqi Zheng · 2018
This paper proposes a new counter architecture for network measurement called Cache Assisted and randomizEd ShAring counteRs (CAESAR). One of the greatest challenges for per-flow traffic measurement is designing an online measurement module to keep up with the rapid growth of link speed. To address this challenge, we use a fast on-chip memory as the cache before the slow off-chip SRAM counters, thereby decreasing the accesses per flow to off-chip counters to improve time efficiency without any packet loss. We use randomized sharing counters among multiple flows in SRAM to achieve a compact data structure with high storage efficiency. By removing the impact from other flows sharing counters with a specific flow, we theoretically analyze the expectation and confidence interval of its estimated flow size accurately. In this paper, we use the real-world network traces for software simulations and FPGA experiments on the Xilinx Virtex-7 FPGA chip to validate our theoretical findings. The results show that CAESAR is up to 92.4% and 90% faster than prior work CASE and RCS respectively, and CAESAR reduces the average relative error of CASE and RCS by more than half.