New directions in traÆc measurement and accounting

Accurate network traÆc measurement is required for accounting, bandwidth provisioning and detect-ing DoS attacks. These applications see the traÆc as a collection of ows they need to measure. As link speeds and the number of ows increase, keeping a counter for each ow is too expensive (using SRAM) or slow (using DRAM). The current state-of-the-art methods (Cisco's sampled NetFlow) which log periodically sampled packets are slow, inaccurate and resource-intensive. Previous work showed that at dierent granularities a small number of \heavy hitters " accounts for a large share of traÆc. Our paper introduces a paradigm shift by concentrating on measuring only large ows | those above some threshold such as 0.1 % of the link capacity. We propose two novel and scalable algorithms for identifying the large ows: sample and hold and multistage lters, which take a constant number of memory references per packet and use a small amount of memory. If M is the available memory, we show analytically that the errors of our new algorithms are proportional to 1=M; by contrast, the error of an algorithm based on classical sampling is proportional to 1= p M, thus providing much less accuracy for the same amount of memory. We also describe further optimizations such as early removal and conservative update that further improve the accuracy of our algorithms, as measured on real traÆc traces, by an order of magnitude. Our schemes allow a new form of accounting called threshold accounting in which only ows above a threshold are charged by usage while the rest are charged a xed fee. Threshold accounting generalizes usage-based and duration based pricing.