New directions in traffic measurement and accounting
New directions in traffic measurement and accounting
复制标题
DOI：
10.1145/964725.633056
复制
发表时间：
2002-10-01
影响因子：
2.8
通讯作者：
Varghese, G
中科院分区：
文献类型：
--
作者：
Estan, C;Varghese, G
需要会计，带宽供应和检测DOS攻击需要准确的网络流量测量。这些应用程序将流量视为需要测量的流量集合。随着链路速度和流量的增加，保持每个流量的计数器太贵（使用SRAM）或慢速（使用DRAM）。当前的最新方法（Cisco的采样NetFlow）周期性采样数据包缓慢，不准确且资源密集。先前的工作表明，在不同的粒度上，少数“重型击球手”占交通份额很大。我们的论文引入了仅通过集中在大流量上的范式进行测量的范式转移 - 高于某些阈值的链接容量的0.1％。我们提出了两种新颖的可伸缩算法，用于识别大流量：样品和保留和多阶段过滤器，这些算法采用每个数据包的恒定内存引用，并使用少量内存。如果M是可用的内存，我们通过分析表明，我们的新算法的误差与1/m成正比，相比之下，基于经典采样的算法的误差与1/rootm成正比，从而提供了较小的准确性，从而为较低的准确性而言，对于该算法的准确性降低了。相同的内存。我们还描述了进一步的优化，例如早期删除和保守更新，这些更新进一步提高了我们算法的准确性，如在实际交通轨迹上，通过数量级来衡量。我们的方案允许一种新的会计形式称为阈值会计，其中仅通过使用范围向阈值收取仅高于阈值的流量，而其余的则收取固定费用。阈值会计概括了基于用法和基于持续时间的定价。
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/rootM, 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.