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.