Flow sampling under hard resource constraints
Flow sampling under hard resource constraints
复制标题
DOI：
10.1145/1005686.1005699
复制
发表时间：
2004-06
期刊：
影响因子：
--
通讯作者：
N. Duffield;C. Lund;M. Thorup
中科院分区：
文献类型：
--
作者：
N. Duffield;C. Lund;M. Thorup
许多网络管理应用程序使用其数据流量，这些流量通过IP地址或端口号等属性进行区分。通常为此目的收集IP流记录：这些记录可以确定网络资源的细粒度使用情况。然而，流量统计数据量的不断增加导致测量基础设施的资源成本随之增加。本文主要讨论流记录的抽样策略。最近的工作表明，为了控制观察到的流长重尾分布引起的估计方差，非均匀采样是必要的。然而，虽然这种方法控制估计方差，但它并没有对采样流的数量进行严格限制。这样的限制往往需要在任意下游采样，resstrike和聚合操作中采用的analysisofdata.This本文提出了一种相关的采样策略，是能够选择一组流的任意小数目的“最佳”代表。我们表明，使用估计产生这样的选择是无偏的，并显示如何估计他们的方差，离线建模的目的，和在线期间的采样本身。该选择算法可以在一个类似于存储器的数据结构中实现，在该数据结构中，存储器使用在测量期间是一致有界的。最后，我们比较了我们的计划与其他潜在的方法的复杂性和性能。
Many network management applications use as their data traffic volumes differentiated by attributes such as IP address or port number. IP flow records are commonly collected for this purpose: these enable determination of fine-grained usage of network resources. However, the increasingly large volumes of flow statistics incur concomitant costs in the resources of the measurement infrastructure. This motivates sampling of flow records.This paper addresses sampling strategy for flow records. Recent work has shown that non-uniform sampling is necessary in order to control estimation variance arising from the observed heavy-tailed distribution of flow lengths. However, while this approach controls estimator variance, it does not place hard limits on the number of flows sampled. Such limits are often required during arbitrary downstream sampling, resampling and aggregation operations employed in analysis of the data.This paper proposes a correlated sampling strategy that is able to select an arbitrarily small number of the "best" representatives of a set of flows. We show that usage estimates arising from such selection are unbiased, and show how to estimate their variance, both offline for modeling purposes, and online during the sampling itself. The selection algorithm can be implemented in a queue-like data structure in which memory usage is uniformly bounded during measurement. Finally, we compare the complexity and performance of our scheme with other potential approaches.