基于迭代方法的流数估计算法

流数估计是网络管控的重要参考尺度,对网络流量全局特征信息的深入挖掘具有重要意义.针对目前已有的多种估计算法以过度消耗测量设备存储资源和计算资源提高估计精度的缺陷,采用报文抽样技术,提出一种新的迭代收敛型估计算法.实验测试表明,该算法在估计精度和内存消耗上优于EM算法,在迭代更新上优于Iteration算法.     

基于TCBF算法的网络流信息统计

针对传统的网络流信息统计算法容易溢出、频繁更新等特点,提出一种基于TCBF(time bloom filter & counting bloom filter)的网络流信息统计算法用于实时在线统计高速网络流信息.算法一方面利用短流超时特点使用time bloom filter抽取短流信息;另一方面利用网络流量分布呈现重尾分布的特性使用counting bloom filter 过滤长流报文.分析了算法的复杂度和误判率,并通过模拟数据分析了算法参数配置对于流信息统计准确性和抽样率的影响.理论分析和仿真结果表明,与标准counting bloom filter相比,TCBF算法可以在使用较少的存储空间的条件下,及时、准确地对网络流量信息进行统计,满足实际测量需要.     

基于动态计数型过滤器的网络流公平抽样机制

传统的包抽样方法对每一个数据包都以同等的比率抽取,这样就导致了大部分被抽中的是大流,而短流和一般流非常少。高速网络的流量检测需要全面的流信息。针对传统流抽样的缺陷,结合现有的SGS(Sketch Guided Sampling)抽样比与流量成反比的公平抽样思想和动态计数型过滤器,提出更加高效的公平抽样算法DCFS(Dynamic Count Fair Sampling)。DCFS算法使用动态统计过滤器DCF(Dynamic Count Filter)统计流量,相对于SGS算法该方法空间更加高效,而且估计准确性也更好。     

基于多级CBF的长流识别

针对高速网络流量难测量的问题及长流占网络流量大部分的特点,提出一种基于多级CBF的长流识别算法,对报文进行抽样,将抽取的报文通过经过一系列哈希映射到长流信息表中,查找是否存在该流信息,若存在则更新流信息,若不存在则将该报文用多级CBF结构对流信息进行过滤,报文数达到阈值的流被识别为长流,并在长流信息表中创建和维护该长流的信息.该算法在很大程度上减少了短流因为哈希冲突而被误判为长流的概率,降低了资源开销,对指定报文数为阈值的长流识别具有很好的扩展性.     

空间高效的数据包公平抽样算法

数据包公平抽样通过牺牲长流的包抽样率以换取更高的短流包抽样率,因而比均匀随机包抽样更能保证数据流之间的公平性.现有的公平抽样算法SGS(sketch guided sampling)存在空间效率低、短流估计误差大的问题.提出了一种空间高效的数据包公平抽样算法SEFS(space-efficient fair sampling).SEFS算法的新颖之处在于采用多解析度抽样统计器对数据流流量作近似估计,各个统计器由d-left哈希表实现.采用在OC-48和OC-192骨干网采集的真实流量数据,在数据流流量测量以及长流检测的应用背景下,对SEFS算法和SGS算法的性能进行了比较.实验结果表明,与SGS算法相比,SEFS算法在空间复杂度降低65%的前提下,仍具有更高的估计精度.特别是对于占网络数据流绝大多数的短流而言,SEFS算法估计精度高的优势更为明显.     

一种基于流数约减的非线性公平采样算法

针对现有采样算法存在可扩展性和公平性差的问题,提出一种基于流数约减的非线性公平采样算法(adaptive fair sampling based on reducing flow numbers,AFS-RFN).AFS-RFN算法首先采用均匀抽样的方法对要统计流数进行约减,获得样本流集合;然后,对属于样本流集合的分组采用非线性的方法进行公平采样,实现控制统计流数目的同时保证统计流信息的准确性.仿真表明,与ANLS(adaptive non-linear sampling)算法相比,AFS-RFN算法大幅降低了存储开销,同时,将算法的公平性提高了60％.算法具有良好的可扩展性和公平性.     

基于抽样和Bloom Filters的长流检测

长流检测对网络检测和管理有着重要的意义.提出一种基于抽样和Bloom Filters的长流检测算法,首先对报文进行抽样,然后通过Bloom Filters哈希运算,在内存中用临时表和流信息表来判断到达阈值的流并维护其信息,满足了高速网络环境下长流检测的要求,在保证测量精度的同时有效得控制了资源消耗.实验分析表明,和已有的方法相比,具有简单易行、资源可控等优点.     

基于抽样流记录的RTT估计

往返时延(RTT)是网络测量中的一个重要测度,是刻画网络性能的重要指标。传统的RTT测量都是基于报文的,需要专门的主动或被动测量平台的支持。提出一种新的 RT T 估计方法,仅使用现有路由器设备提供的流记录,不需要额外的网络测量设施。通过对 TCP 块状流传输特性的分析,分别建立了当套接字缓冲区长度与带宽延迟积BDP相对较小、较大和相近这3种情况下的RTT估计模型。实验结果表明,这些模型都能很好地完成RTT估计。同时,由于在估计当中只使用了流持续时间和总报文两个变量,因此,该方法同样适用于以抽样流记录为输入的环境,能够有效地应用于现有的大规模主干网环境的网络检测与管理。     

一种新的估计流长度分布的方法

为提高流测量系统的运行效率,减小其所消耗资源,提出了一种新的用于测量流长度分布的估计方法。对到达的报文进行抽样后,用两个哈希函数来确定更新相应计数单元的值,定期收集计数空间中的数据进行离线处理。利用EM算法和最小二乘法,得到了流长度分布。通过应用于来自不同网络的数据进行实验测试,实验结果表明该模型对于流分布的估计是精确的。     

PTP网络非对称时延抖动修正算法设计与分析

为了改进PTPV2时间同步网络非对称时延抖动对主从时钟同步精度的影响,设计了传输报文的非对称时延抖动修正算法。基本思路是在主从时钟交换报文信息中,找出最佳报文用于从时钟的调整。采用两级过滤先进增强时间恢复算法,即使发生网络传输阻塞,也能筛选出未受阻塞的幸运报文用于时钟偏差估计。新算法能够很容易集成到PTPV2协议中,而不会影响基本的报文信息交换。实际测试结果表明,新设计的时间恢复算法,在普通交换机网络中,可有效抑制非对称时延抖动,主从时钟同步精度也可优于100ns。     

Double sampling for flow measurement on high speed links

Traffic measurement and monitoring are an important component of network QoS management and traffic engineering. With high speed Internet links, efficient and effective packet sampling techniques for traffic measurement are not only desirable, but increasingly becoming a necessity. Packet sampling has become an attractive and scalable means to measure flow data on high speed links. Passive traffic measurement increasingly employs sampling at the packet level and makes inferences from sampled network traffic. However, it meets difficulty in estimating the original flow distribution. To circumvent the problem, we propose and analyze a double sampling technique for flow measurement. In particular, we rewrite the expectation maximization (EM) algorithm that estimates flow distribution for double sampling. Using real network traffic traces, we show that the proposed double sampling technique indeed produces the desired accuracy in estimating the flow distribution.     

Fast Filtered Sampling

Traffic sampled from the network backbone using uniform packet sampling is commonly utilized to detect heavy hitters, estimate flow level statistics, as well as identify anomalies like DDoS attacks and worm scans. Previous work has shown however that this technique introduces flow bias and truncation which yields inaccurate flow statistics and “drowns out” information from small flows, leading to large false positives in anomaly detection.In this paper, we present a new sampling design: Fast Filtered Sampling (FFS), which is comprised of an independent low-complexity filter, concatenated with any sampling scheme at choice. FFS ensures the integrity of small flows for anomaly detection, while still providing acceptable identification of heavy hitters. This is achieved through a filter design which suppresses packets from flows as a function of their size, “boosting” small flows relative to medium and large flows. FFS design requires only one update operation per packet, has two simple control parameters and can work in conjunction with existing sampling mechanisms without any additional changes. Therefore, it accomplishes a lightweight online implementation of the “flow-size dependent” sampling method. Through extensive evaluation on traffic traces, we show the efficacy of FFS for applications such as portscan detection and traffic estimation.     

Scalable algorithms for estimating flow length distributions from sampled data

With the rapid growth of link speed, obtaining detailed traffic statistics becomes much more difficult. In order to reduce the resource consumption of measurement systems, more and more passive traffic measurement employs sampling at the packet level. Packet sampling has become an attractive and scalable method to measure flow data on high-speed links. However, knowing the length distributions of traffic flows passing through a network link is very useful for network operation and management. In this paper, we consider the problem of estimating flow length distributions based on sampled flow data. This paper introduces two algorithms for estimating flow length distributions, fitting estimation and factoring estimation. The fitting estimation uses piecewise Pareto distribution to fit the original traffic for a small sampling period. The factoring estimation is used for a large sampling period. It first factorizes the large sampling period into a product of some smaller integer factors, then iteratively invokes fitting estimation or other algorithms such as ${\textit{EM}}$ in the arranged order of the factors. Evaluations of the proposed algorithms on large Internet traces obtained from several sources demonstrate that they have high measurement accuracy with low computation overhead. The algorithms allow us to recover the complete flow length distributions.     

随机分组抽样下子群体的流大小分布估计

随机分组抽样是网络管理和测量中最常见的抽样方法。已有的研究大都集中在此抽样方法下基于总体的流大小分布估计算法,但一些网络应用更关心总体流量中某个子群体的流大小分布。本文将总体的网络流划分成子群体S和子群体的补集-S,提出了一种在随机分组抽样下运用TCP协议信息的由S与S-共同组成流大小的联合分布的估计算法。实验证明,该算法能够较好地还原子群体及其在总体下的流大小分布的特征;另一方面,通过运用样本流中TCP协议信息,提高了子群体流大小分布估计算法的准确性。     

Algorithms and estimators for summarization of unaggregated data streams

Statistical summaries of IP traffic are at the heart of network operation and are used to recover aggregate information on subpopulations of flows. It is therefore of great importance to collect the most accurate and informative summaries given the router's resource constraints. A summarization algorithm, such as Cisco's sampled NetFlow, is applied to IP packet streams that consist of multiple interleaving IP flows. We develop sampling algorithms and unbiased estimators which address sources of inefficiency in current methods. First, we design tunable algorithms whereas currently a single parameter (the sampling rate) controls utilization of both memory and processing/access speed (which means that it has to be set according to the bottleneck resource). Second, we make a better use of the memory hierarchy, which involves exporting partial summaries to slower storage during the measurement period.     

基于网络断层扫描的传感器网络链路丢包研究

文中提出了一种基于网络断层扫描的无线传感器网络链路丢包率测量方法,通过边界节点的丢包率来估计传感器内部链路丢包的情况。根据无线传感器网络数据聚合的特点,提出了网络逻辑拓扑和链路报文丢包模型,在将链路报文丢失率推测问题形式化为MLE问题的基础上,用引入修正因子的μ的EM算法来推测链路报文丢失率。NS2仿真结果证明,μ-EM算法推测的链路报文丢失率与预设值更加接近,特别是在大规模网络中μ-EM算法在精确度和有效性方面均明显优于EM算法。     

Random sampling approach to state estimation in switching environments

This paper deals with the state estimation for the systems under measurement noise whose mean and covariance change with Markov transition probabilities. The minimum variance estimate for the state involves consideration of a prohibitively large number of sequences, so that the usual computation method becomes impractical. In the algorithm proposed here, the estimate is calculated with a relatively small number of sequences sampled at random from the set of a large number of sequences. The average risk of the algorithm is shown to converge to the optimal average risk as the number of sampled sequences increases. An ideal sampling probability yielding a very fast convergence is found. The probability is approximated in a minimum mean squared sense by a probability according to which sequences can be sampled sequentially and with great ease. This policy of determination of sampling probability makes it possible to design practical and efficient algorithms. Digital simulation results show a good performance of the proposed algorithm.     

流测量算法综述

理解网络行为对于网络管理、规刬和发展都有重要意义,而流测量是了解网络行为的基础。由于网络的高速与流数量的巨大,使得实时在线的流测量变得很困难。因此各种流测量技术、流测量算法成为研究热点。文章综述了目前利用抽样和哈希技术在流识别和流分布方面取得的成果,并分析了各种算法的优缺点。最后分析了抽样与哈希技术的长处与不足,提出了多种技术相结合的研究方向。