Scalable identification and measurement of heavy-hitters

摘要

Existing methods to detect and measure heavy-hitters (frequent items) are either lightweight but too inaccurate and memory-demanding (e.g. those relying on sampling), or too heavyweight to be deployed at high speeds. In this paper, we present several sampled-based algorithms to the problem and show that they exhibit two critical features. First, despite sampling, our schemes provide accurate results and detection guarantees that are independent of the traffic properties. Second, they are provably shown to require memory that is not only constant regardless of the amount of traffic observed and its composition, but a small factor above the theoretical minimum. Thus, unlike most solutions, ours scale in both space and speed; the use of sampling allowing to trade off performance for cost. As we will see, our algorithms build on similar principles. The first two use a constant sampling probability. Upgrading the second to support a variable sampling rate and to adjust it depending on the traffic intensity and CPU available yields our third scheme; a highly versatile solution that performs quasi-optimally and requires minimal configuration.