Borrow Counter: A Generic Sketch Framework for Non-uniform Flow Estimation

Compact data structures, such as sketches and Bloom filters, are extensively studied by researchers in network measurements. Since the fixed-size counter cannot adapt to the non-uniform distribution of real network traffic, a class of frameworks has been proposed to improve memory efficiency and measurement accuracy of sketches and Bloom filters. However, existing frameworks either extend the counting range with a certain probability, which introduces errors, or utilize predefined hierarchical structures that are not suitable for various scenarios. In this paper, considering the non-uniform flow distribution, we propose a new framework called Borrow Counter, whose key idea is to borrow idle bits from adjacent counters and record more significant bits to extend the counting range, while still ensuring accuracy. It shows good generality and can be applied to most sketches and Bloom filters. Extensive experimental results demonstrate that, compared to state-of-the-art frameworks, Borrow Counter improves the accuracy by up to 32%.