New Directions in Accounting and Traffic Measurement

计费和流量测量的新方向

• 批准号: 0137102
• 负责人: George Varghese
• 金额: --
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-09-15 至 2007-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0137102&HistoricalAwards=false
• 关键词: New; Directions; Accounting; Traffic; Measurement

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.

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