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

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

避免数据包重复采集的分布式流量测量算法

针对D PC算法存在的问题,提出一种“标记”数据包头的分布式流量测量算法。为避免同一数据包被不同测量点重复采集,在网络入口测量点处,对到达的数据包进行抽样,修改被抽取数据包头中标志位的预留位为1;在网络的中间节点,通过查看数据包的预留位判断数据包是否已被抽取,对于已被抽取的数据包,不再重复记录,对于尚未被抽取的数据包,根据抽样规则决定是否抽取,避免多次采集相同数据包导致计算资源和存储资源的重复消耗。通过理论推导和实例验证了该算法的有效性,为分布式网络流量测量的扩展应用提供了解决途径。     

基于DCF的资源可控流抽样

Cisco的NetFlow是流测量中广泛应用的方案,但因其采用静态抽样率,当网络流量突然上升时,消耗过多的路由器资源,甚至影响路由器的正常转发功能。提出了基于DCF的资源可控流抽样,对测量间隔内到达的报文采取固定数量的抽样,并采用DCF哈希算法维护流记录,有效控制了资源的消耗。理论和实验分析结果表明,该方法具有抽样率自适应性、简单性、资源可控性,同时不失准确性。     

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

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

网络自适应公平分组抽样算法研究

针对SGS(sketch guided sampling)的缺陷,提出了一种网络自适应公平抽样算法.根据抽样分组估计出值流量大小,并依据该值调整抽样比,使之适应于流量变化,从而达到对各种流的公平抽样的效果.对算法的相关性质进行了证明与分析,基于实际互联网数据进行了实验比较,实验结果表明,该算法具有准确性、自适应性、易于工程实现等优点.     

一种基于分组抽样的TRW改进算法

端口扫描是最常见的网络异常流量,TRW是端口扫描检测中最有代表性的算法之一。在高速网络环境下,网络测量通常采用分组抽样技术。已有的研究表明,分组抽样对原始流的流大小分布有细化和扭曲的作用,使得TRW检测算法随着抽样率的增加,成功检测率和误检率呈现出先增加后减少的趋势。本文提出了一种TRW的改进算法,原理是利用抽样后样本流中包含的TCP协议信息改善分组抽样下的流大小分布估计,从而提高TRW检测算法的有效性。实验证明,新算法与原算法相比,在成功检测率差不多的情况下,误检率明显降低了。     

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

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

流测量中基于测量缓冲区的时间分层分组抽样

NetFlow是流测量中广泛应用的解决方案,但NetFlow的抽样方法存在一定的缺陷:泛洪攻击时消耗路由器过多的资源;用户很难选择适合所有流量组成情况的静态抽样率,以平衡资源消耗量和准确率.提出了一种易于实现的分组抽样方法.该方法利用测量缓冲区对定长时间内到达的分组进行固定数量的抽样,既可以使抽样率自适应于流量变化,又可以控制资源的消耗.证明了抽样估计的无偏性,并推导出估计值相对标准差的理论上界.实验结果表明,与已有方法相比,该方法在具有简单性、自适应性及资源可控性的同时不会失去准确性.     

基于近似方法的抽样报文流数估计算法

维护每个报文的流记录需要占用大量测量资源.目前已有多种抽样技术估计网络流统计信息,然而精确地估计出流数统计信息是目前的研究难点.提出了Integral和Iteration 两种基于报文抽样样本估计网络流数的算法.Integral算法只需使用抽样流长为1的流数信息就可以近似推导出未抽样的流数.Iteration算法通过建立迭代函数估计未抽样流数,然后根据未抽样流数和已抽样的流数推断出原始流量的流数.采用CERNET(China education andresearch network)骨干网络链路数据将这两种算法与EM(expectation maximization)算法进行对比,表明Iteration算法具有较好的精度和性能.     

基于流记录的主干网活跃IP地址空间检测

掌握IP地址的实际使用情况对于网络管理和网络安全等研究领域有着重要的意义.提出一种以抽样流记录为分析数据源的活跃地址检测算法,其核心思路是将存在双向通信流量作为地址活跃判定条件.算法基于被动测量技术,以流记录为分析数据源使其可以在主干网边界运行.讨论了抽样、伪造地址等问题对算法的影响以及相应的应对策略,用DPI分析检验了算法的准确性和有效性.最后基于NBOS平台,将其部署在CERNET全部38个主节点,完成了全网活跃IP地址空间的检测.     

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

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

流测量算法综述

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

基于流抽样和LRU的高速网络大流检测算法

在高速主干网络中,随着网络链路速率的不断提高和网络流数量的增加,如何及时、准确地检测出网络中的大流信息,成为目前网络流测量的热点问题。根据传统LRU算法由于突发性大量小流导致淘汰大流的测量缺陷和网络重尾分布的特点,提出一种新的识别大流的算法——基于流抽样和LRU的大流检测算法。算法通过流抽样技术过滤大部分的小流,并通过LRU算法识别大流信息,将过滤和识别过程分离,减少小流错误淘汰大流的可能性,提高算法测量准确性。分析算法的复杂度和漏检率,并通过实际试验数据分析了算法参数配置对于大流测量的准确性的影响。理论分析和仿真结果表明,与标准LRU算法和LRU_BF算法相比,在使用相同的存储空间下,新算法具有更高的测量准确性和实用性。     

一种基于包速率自适应的报文抽样算法*

针对NetFlow抽样概率需手动配置的缺陷,提出了一种基于包速率自适应的分组抽样算法。通过测量包速率,采用预定义测量误差的方法,根据包速率的变化自适应地调整抽样概率,从而在有限资源情况下达到控制测量误差的目的。基于实际互联网数据进行了实验比较,结果显示：与传统的NetFlow算法相比,该方法易于实现,测量误差可控,具有高效性和准确性,同时具有资源节约性。     

一种基于FCBF的流信息抽样测量框架及算法

基于FCBF的高效流信息抽样测量框架不仅可以抽样测量三类流参数,而且存储开销小,只需1～3MB字节左右的存储空间;同时还可以做到几乎零概率的流信息识别统计误差。分析结果表明,该算法可以支持远高于OC48的链路速率,甚至可达OC192或更高;适合于将来高速链路上细粒度的流信息抽样测量。     

流量抽样关键技术研究

网络管理和监控是网管系统和流量工程的重要组成部分.随着网络的高速发展,实时有效的流量抽样技术对网管系统和网络监控系统越来越重要.传统的网络流量测量是对链路上通过的所有报文进行都捕获和统计的方式进行的.随着网络技术的发展,传统的流量测量方法会对测量设备产生很大的开销,因而变得不再实用.为了解决上述问题文章对现有网络流量监测技术进行研究,首先对流量测量方法和流特征进行介绍,然后介绍了现有抽样技术的种类以及现有抽样技术的研究现状,最后介绍了三种具体的自适应抽样技术.     

基于滑动窗口的资源可控流量测量算法

针对高速链路中流量测量缺乏可扩展性的问题,提出一种在线挖掘频繁流的算法。通过采用“滑动窗口”机制,构造流抽样函数,自适应地设置抽样门限的方法,实现流大小的无偏估计。基于实际的互联网数据进行仿真实验,结果表明,该算法在保证准确性的同时,具有自适应性和资源可控性。     

基于语义的访问控制模型及其推理机制

针对高速链路中流量测量缺乏可扩展性的问题,提出一种在线挖掘频繁流的算法。通过采用“滑动窗口”机制,构造流抽样函数,自适应地设置抽样门限的方法,实现流大小的无偏估计。基于实际的互联网数据进行仿真实验,结果表明,该算法在保证准确性的同时,具有自适应性和资源可控性。     

基于流量信息结构的异常检测

由于人们对网络流量规律的认识还不够深入,大型高速网络流量的异常检测仍然是目前测量领域研究的一个难点问题.通过对网络流量结构和流量信息结构的研究发现,在一定范围内,正常网络流量的IP、端口等具有重尾分布和自相似特性等较为稳定的流量结构,这种结构对应的信息熵值较为稳定.异常流量和抽样流量的信息熵值以正常流量信息熵值为中心波动,构成以IP、端口和活跃IP数量为维度的空间信息结构.据此对流量进行建模,提出了基于流量信息结构的支持向量机(support vector machine,简称SVM)的二值分类算法,其核心是将流量异常检测转化为基于SVM的分类决策问题.实验结果表明,该算法具有很高的检测效率,还初步验证了该算法的抽样检测能力.因此,将该算法应用到大型高速骨干网络具有实际意义.     

基于FARIMA模型的流量抽样测量方法

目前的流量抽样测量方法主要基于传统的数学理论,并没有考虑到实际网络流量的特征,基于此,提出基于FARIMA流量预测的抽样方法,根据流量预测值动态调整抽样率,既减轻了CPU的负载,又节省了存储空间。通过对比实际使用中的流量抽样测量方法取得的数据报文样本均值和Hurst参数,表明该方法能够正确体现原始数据的流量行为统计特征。