New Directions in Accounting and Traffic Measurement

准确的网络流量测量是计费、分配带宽和检测DOS攻击的必要条件。但是，使用计数器来测量一百万个并发流中的每个流发送的流量过于昂贵（使用SRAM）或缓慢（使用DRAM）。目前最先进的方法（例如Cisco NetFlow）定期记录采样数据包，速度慢，不准确，并且占用大量内存。这一提议引入了一种范式转换，将注意力集中在仅测量“重”流量|的问题上，即流量超过某个阈值（如链接的1%）的流量。在证明了基于缓存计数器和经典采样的一些简单解决方案不起作用之后，研究人员描述了两种新颖的可扩展方案，用于此目的，每个数据包使用恒定数量的内存引用，并使用少量内存。此外，与NetFlow估计不同，我们对测量率的准确性和假阴性的概率有可证明的界限。研究人员建议实施、评估和微调这些新想法。以这些观点为基础，研究人员还提出了以下问题。首先，他们将研究一种新的会计形式，称为阈值会计，其中只有超过阈值的流量按使用量收费，其余流量按固定费用收费。阈值会计概括了熟悉的基于使用和基于持续时间的定价概念。其次，他们建议研究一个更普遍的问题：使用非常少量的高速内存以非常快的速度计算流量统计。其他可能有用的流量统计的例子包括流量的数量、流量大小的标准偏差、流量的平均持续时间等。用于测量此类数量的朴素算法都与流量数量成线性比例。最后，与CAIDA的同事一起，研究人员计划将我们的算法实时部署到5个流量监视器上，这些监视器放置在战略互联网站点（AIX， UCSD主干，可能还有Abilene）上。这一提议的潜在影响是为会计、计量和安全开发新颖实用的工具。这是互联网从研究网络向商业企业转变的三个核心问题。

Accurate network traffic measurement is required for accounting, bandwidth provisioning, and detecting DOS attacks. However, keeping a counter to measure the traffic sent by each of a million concurrent flows is too expensive (using SRAM) or slow (using DRAM). The current state-of-the-art (e.g., Cisco NetFlow) methods which log periodically sampled packets are slow, inaccurate, and memory-intensive. This proposal introduces a paradigm shift by concentrating on the problem of measuring only "heavy" flows | i.e., flows whose traffic is above some threshold such as 1% of the link. After showing that a number of simple solutions based on cachedcounters and classical sampling do not work, the resarchers describe two novel and scalable schemes for this purpose which take a constant number of memory references per packet and use a small amount of memory. Further, unlike NetFlow estimates, we have provable bounds on the accuracy of measured rates and the probability of false negatives. The researchers propose to implement, evaluate, and fine-tune these new ideas. Using these ideas as a basis, the researchers also propose to investigate the following questions. First, they will investigate a new form of accounting called threshold accounting in which only flows above threshold are charged by usage while the rest are charged a fixed fee. Threshold accounting generalizes the familiar notions of usage-based and duration based pricing. Second, they propose to investigate a more general question: the computation of flow statistics at very high speeds using very small amounts of high speed memory. Examples of other potentially useful flow statistics include the number of flows, the standard deviation of flow sizes, the average duration of a flow etc. Naive algorithms to measure such quantities all scale linearly with the number of flows. Finally, with colleagues at CAIDA, the researchers plan to deploy our algorithms in real-time on 5 traffic monitors placed at strategic Internet sites (AIX, the UCSD backbone, and possibly on Abilene). The potential impact of this proposal is the development of novel and practical tools for accounting, measurement, and security. These are three central problems as the Internet transitions from a research network to a commercial enterprise.