Hash函数实现数据包分流算法研究

随着 Internet 规模的不断扩大与应用技术的不断进步,越来越多的业务需要对数据包进行实时、快速的分类,对数据包分类的研究具有重要的现实意义。Hash 算法采用了散列算法的基本思想,并引入了流的局部性原理加速散列查找的过程。由于时间精确度较高和面向对象的特点,选用了 C^(++)语言编程对该算法进行了仿真测试,最后对 Hash 算法分析表明,Hash 算法具有良好的时间复杂度和空间复杂度,可以实现快速的分流。

用于特定流匹配的随机矩阵映射Hash算法研究

针对常规的Hash算法用于流匹配时冲突率高且不可控制的缺点,提出了一种随机矩阵映射Hash算法。该算法通过预先优选一个随机数矩阵,然后将大集合的元素分块映射成随机矩阵中的元素,从而把一个大集合映射到一个小集合。测试结果表明,该算法运算速度快、空间利用率高、冲突率低,用于流匹配时匹配速度可以达到2Mpacket/s,支持规则数达5万条以上。

基于数据拟合法的三角形薄壁堰明渠流量测量不确定度优化

针对三角形薄壁堰明渠流量计非定点使用时测量准确度水平较低的问题,基于不确定度预评估结果,提出了以曲线拟合替代线性插值计算流量系数,采用了数字输出磁致伸缩水位传感器测量水头,显著降低了原方法中贡献较大的不确定度分项。基于弗劳德相似准则改进了频率采样方法,提升了测量结果的准确度水平。测量方法改进后不确定度由1.6%提高到0.56%。通过标准表法明渠流量流速标准装置对三角形薄壁堰明渠流量计进行了标定实验,实验结果表明:测量方法改进后标定误差(偏差)由2%降低到1%。

基于RFC算法的快速多维数据包分类算法

数据包分类技术应用于许多网络服务,其性能基本决定了服务的质量。RFC算法是具有代表性的数据包分类算法,分类速度快,但由于存储开销巨大,增加了算法实现的存储消耗,加大了成本。该文在RFC算法的基础上提出了一种利用Hash技术减少存储开销且保持相对快速的数据包分类算法。

流测量算法综述

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

高速网络流量测量方法

高速网络流量测量是目前实施实时准确地监测、管理和控制网络的基础.基于网络流量测量的应用,将网络流量测量分为抽样方法和数据流方法.从不同的层次,将抽样方法分为分组抽样和流抽样,分别介绍了两类抽样方法;从测度角度介绍了数据流方法.详细介绍了高速网络流量测量的常用数据结构,以及抽样、数据流方法在高速网络流量测量中的应用,比较了各种方法的优劣.概述了高速网络流量测量技术的研究进展.最后,就现有的网络流量测量方法的不足,对网络流量测量的发展趋势和进一步的研究方向进行了讨论.

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

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

一种改进的自适应流量采样方法

高速链路对实时网络流量监测提出挑战.由于流量采集分析设备性能的限制,采用精确、高效的采样方法进行流量监测分析已成为必然.最简单的固定概率采样能监测较大业务流,但往往忽略掉比例几乎超过80%的较小业务流.数据流算法可以实时高效采集高速链路数据,基于该算法的SGS(sketch guided sampling)采样技术可以实时准确估计流大小分布,但当采样速率增大到监测系统处理能力最大值时,该方法的准确性迅速降低.基于SGS方法,提出一种自适应实时网络流量的采样方法SRGS(sketch and resources guided sampling).该方法将监测系统处理能力作为采样概率调节的一个重要参数.实验结果显示,SRGS方法能够及时根据当前流大小和监测系统处理能力,调节数据包采样概率,准确性高于SGS方法.

一种用于小流估计的数据包公平抽样算法

现有数据包公平抽样算法通常根据到达数据包所属流大小的估计值设置包抽样率,令大流所含数据包抽样率低,小流所含数据包抽样率高,缺点是算法的优劣依赖于不同方法对流大小估计的准确性;小流估计误差较大。针对此问题,利用大流持续时间长且到达速率高的特点,提出一种基于时间分片的用于小流估计的数据包公平抽样算法(MFEPS)。该算法将测量时间分割成片,抽取每个流在每个时间片内的第一个数据包,而不需要估计数据包所属流的大小。理论分析和实验结果均表明,与已有算法相比,对于小流估计,MFEPS算法在相同的CPU资源消耗条件下,具有更高的准确性和良好的扩展性。

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

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

高速网络流测量及模型研究

网络流测量是网络性能分析和网络流量建模的基础。该文分析了网络流测量的方法及特点,针对高速网络流测量中的关键问题进行了研究,并在此基础上提出了高速网络流测量模型,随后对该模型各组件及相互关系进行了分析,最后通过具体实验分析了模型架构及关键技术的可行性。

利用报文抽样和可逆的Bloom Filter实现长流识别

针对高速网络的发展和利用哈希技术在识别长流时难以还原主机信息的问题,提出了利用报文抽样和可逆的Bloom Filter识别长流的算法。采用带有部分主机信息的哈希函数,利用哈希串的重叠和数量上的一致性,能够很方便的还原出主机的信息。给每个哈希函数独立的存储空间,在很大程度上减少了哈希过程所带来的内部冲突。实验结果表明,这种算法可以精确地获得长流的标识与长度信息。

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

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

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

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

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

为提高流大小分布估计的精度,比较了运用TCP流的SYN包和TCP序列号信息的几种极大似然估计(MLE)算法.结果表明,运用TCP流中的SYN包和SEQ信息对流大小的分布估计比单纯的抽样估计具有更高的准确性,其中在样本流中同时运用SYN包和SEQ信息的估计效果最佳.在此基础上结合实际提出了一种对小流采取细粒度、对大流采取粗粒度的流大小非均匀粒度分布估计算法,并以实例验证了该方法的适用性.结果表明,该方法在减少算法计算量的情况下,提高了对大流的估计精度.

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

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

包延迟测量中泊松采样低估效应的仿真研究

采样是网络测量的基础,泊松采样是一种无偏的采样方法的观点被人们普遍接受,也使其在主动测量领域得到了广泛应用。用户流包性能测量已成为主动测量领域的一个重要问题,然而泊松采样的无偏性仅针对网络状态,目前尚无研究工作研究其对于用户流的包性能的测量效果。利用真实的Internet流量数据进行了仿真试验,系统定量地研究了该问题得到如下结论:泊松采样系统低估了用户流包延迟性能;低估程度不受泊松采样频率的影响且随着网络链路利用率的升高而下降。定性分析和解释了泊松采样测量用户流包延迟性能时的低估现象。

一种基于大小流区分计数的公平抽样算法

针对一种草图指导公平抽样(SGS)算法对小流估计误差大的问题,该文提出一种基于大小流区分计数的包公平抽样算法(DCMFS),并给出哈希冲突对SGS算法估计误差影响的定量分析结果。DCMFS采用大小流区分计数器,对小流采用逐流精确计数,对大流采用哈希计数。理论分析及实际的数据仿真结果均表明,DCMFS算法对小流能够实现逐流精确统计,对大流的估计标准差接近公平抽样估计标准差理论值上限。算法采用不等长位宽计数器结构,保证其空间复杂度较SGS和自适应非线性抽样方法(ANLS)没有增加;引入计数器置换使得算法时间复杂度略有提高,但仍能满足10 Gbps线速处理要求。

基于Linux内核高速IP网络测量器的研究

1.引言 近年来随网络规模日益庞大,拓扑结构越来越复杂,同时网络技术也出现两级化发展,出现网络行为学[1]和为行为分析提供抽样数据的网络测量技术的发展.由于网络测量环境的提速给网络测量带来更大困难,加上网络分析技术对测量的要求越来越高,因此测量技术成为当前网络技术的热点之一.

基于业务流数量自适应的资源限制分组抽样

高速网络中,流量抽样测量技术是一种重要可扩展的解决方案,其中NetFlow在流量测量中有着广泛的应用。针对Net-Flow的缺陷提出了一种基于业务流数量自适应的资源限制分组抽样算法,该算法结合"分层抽样"的思想,把"累积业务流数量"作为重要的参数,来自适应地调节抽样概率,该抽样方法简单、易于实现,平衡了资源的消耗量和准确性。并基于实际互联网数据进行了实验比较,结果显示:该方法具有简单性、自适应性、资源可控性的同时不会失去准确性。