Accurate network tra c measurement is required for ac- counting, bandwidth provisioning and detecting DoS at- tacks. These applications see the tra c as a collection of flows they need to measure. As link speeds and the number of flows increase, keeping a counter for each flow is too ex- pensive (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 di erent granularities a small number of \heavy hitters" accounts for a large share of tra c. Our paper introduces a paradigm shift for measurement by concentrating only on large flows | those above some threshold such.
