New directions in traffic measurement and accounting
Authors:
Open Access
- 19 August 2002
- journal article
- conference paper
- Published by Association for Computing Machinery (ACM) in ACM SIGCOMM Computer Communication Review
- Vol. 32 (4) , 323-336
Abstract
Accurate network traffic measurement is required for accounting, bandwidth provisioning and detecting DoS attacks. These applications see the traffic 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 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 different granularities a small number of "heavy hitters" accounts for a large share of traffic. Our paper introduces a paradigm shift for measurement by concentrating only on large flows --- those above some threshold such as 0.1% of the link capacity.We propose two novel and scalable algorithms for identifying the large flows: sample and hold and multistage filters, 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/\sqrtM$, 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 traffic traces, by an order of magnitude. Our schemes allow a new form of accounting called threshold accounting in which only flows above a threshold are charged by usage while the rest are charged a fixed fee. Threshold accounting generalizes usage-based and duration based pricing.
Keywords
This publication has 11 references indexed in Scilit:
- Inter-AS traffic patterns and their implications2003
- A proposal for a flexible service plan that is attractive to users and Internet service providers2002
- Controlling high bandwidth aggregates in the networkACM SIGCOMM Computer Communication Review, 2002
- Rapid profiling via stratified sampling2001
- Charging from sampled network usage2001
- Trajectory sampling for direct traffic observation2000
- Deriving traffic demands for operational IP networks2000
- Traffic Flow Measurement: Architecture1999
- New sampling-based summary statistics for improving approximate query answers1998
- Space/time trade-offs in hash coding with allowable errorsCommunications of the ACM, 1970