基于元组向量折叠的大规模规则库包分类算法

基于元组空间提出了一种适用于多维大规则库的包分类算法——元组向量折叠算法。与基本元组空间算法和基于元组的位并行包分类算击相比较,该算法在空间复杂度和时间复杂度上都取得了较好的性能。     

一种多维并行报文分类算法

位并行、位向量和聚合位向量算法通过对多个域进行并行处理加快分类速度,但三者内存占用太大,不适用于大规则集。为此,提出一种压缩位并行算法,通过报文分类压缩每个域上的重复规则并重新组织规则集,从而缩短位图中位串的长度,减少内存空间的占用。实验结果证明,该压缩位并行算法在不影响运行速度的前提下,明显减少了空间占用。     

一种快速的五元一维包分类算法

包分类算法在网络安全产品中至关重要,该文介绍常见的包分类算法,针对现有包分类算法的不足,构造了一种基于Hash函数的可快速查找、快速定位五元一维包分类算法,并给出算法准确性、快速性的理论证明。     

一种适于多维的快速包分类算法

包分类是多种网络应用的关键性技术,包分类算法的性能对网络的时延和吞吐量有决定性的影响。文章介绍一种适于多维的快速包分类算法——RFC算法,论述了算法的原理和实现算法,将RFC算法与几种常见的分类算法作仿真比较,阐述了RFC算法的优越性。     

包分类算法中规则转换方法研究

对传统包分类算法中的规则形式化进行改进,在研究包分类算法中规则转换方法的基础上,提出一种基于集合运算的非匹配规则转换算法,将该算法与其他范围规则转换算法进行性能比较,分析这些算法的时空复杂度,同时进行仿真。实验结果表明,该算法产生的规则数目小于其他算法。     

一种基于递归流的快速多维包分类算法

为了使用户在现有的网络上得到不同的服务类型和更好的QOS,同时满足下一代网络的需要,包分类技术受到越来越多的关注,本文在介绍RFC包分类算法的基础上,提出一种新的快速多维包分类算法。     

一种基于关联规则挖掘的分类规则挖掘算法

本文根据关联规则和分类规则的概念与表示形式,指出在关联规则挖掘过程中如果指定挖掘与一个确定的项相关联,那么就是分类规则挖掘了,论述了分类规则是特殊情况下的关联规则,并指出在这种特殊情况下,关联规则所具有的特征;然后根据这一论述,提出了一种在关联规则挖掘算法中利用限制条件概率分布来发现分类规则的算法。     

一种基于子元组划分的快速两维包分类算法

包分类对于支持如防火墙、攻击检测、差分服务等网络应用有着重要的意义.研究人员对此做了大量研究.其中基于Srinivasan提出的元组空间思想的算法都存在着不能够通过预查找的方法直接定位匹配规则的元组的问题,因此此类算法的平均查找性能不稳定.针对两维包分类,提出了将元组划分为子元组的准则,满足准则的子元组可以根据3个独立的一维查找结果确定是否包含匹配规则,通过消除不必要的元组查找来提高查找速度和获得稳定的查找性能.     

基于规则集压缩的高效包分类算法

研究发现快速包分类算法EGT-PC由于压缩特里树路径带来规则集的大量冗余备份降低了算法的查找时间和存储空间等性能。根据规则数据库中规则相对聚集的特性,设计出适合该算法的规则集压缩机制,提出新的包分类算法——EGT-SC。实验表明,在查找时间和存储空间上新算法的性能都有明显的提高。     

一种改进的基于规则实例多覆盖分类算法

基于规则分类算法提取的规则集通常存在3个问题:首先,提取的分类规则集中短规则过少,致使高质量的规则不多;其次,规则集中规则数量少,训练数据中几乎所有实例仅被规则覆盖一次;第三,虽然提取大量的规则,但是训练数据中存在一些小类样本的实例不能被任何一条规则覆盖。本文提出一种改进的基于规则的实例多覆盖分类算法(Rule-based classification with instances covered by multiple rules, RCIM),其特点是:(1)为了提高规则的质量,在选择生成规则的第1项时不仅考虑属性值的好坏,而且还考虑了属性值补的好坏;(2)一次产生尽量多,高质量的规则,而且当训练数据的实例至少被两条规则覆盖后才将其删除;(3)当遇上难以判断的测试数据时,对测试数据的各个属性值进行二次学习提取规则。算法RCIM不仅可以有效地提取大量的规则,而且较大程度地提高了规则的质量。通 过在大量数据上实验结果表明,RCIM比许多其他算法取得了更高的分类准确率。     

可扩展的路由器软件架构

提出了一个可扩展的路山器软件架构BVFilter,它将多个包分类集中在一个分类器中完成,实现一个包分类为多个所用,减少了包分类的分销,性能评价模拟实验显示出BVFilter架构具有良好的扩展性：采用BVFilter处理6个包分类过程的时间仅比处理1个的时间高出13%,而采用传统软件架构时则高出314%。     

一个快速的二维数据包分类算法

随着因特网的发展,主干路由器上的包输入成为网络性能的瓶颈。该文基于空间分解技术提出了一个数据包分类算法,它将数据包和过滤器的匹配用多维空间中的点的定位来实现,可用于快速的路由查找和数据包分类。     

一种新的快速报文分类算法——RC-FST*

RC-FST 算法利用IP 地址高8 比特前缀建立Hash 压缩索引表, 将分类规则集分成多个子集, 并针对每个子集建立快速搜索树, 而这些规模相对小的本地搜索树更利于实现快速建立、查找和优化。为提高搜索树性能, 在规则分割等问题上也提出了独到的解决方法。该算法查找速度快( 50Mbps) , 支持分类规则数据库大(105) , 可扩展性好, 适于硬件流水线方式实现, 具有很高的实用价值。     

路由器中的包分类算法研究

在Internet路由器中将数据包分类成流采用了散列算法的基本思想,并引入了流的局部性原理来加速散列查找的过程,用软件对该算法进行了仿真测试,并在最后从时间复杂度和空间复杂度两个方面对其进行了性能分析。实验结果表明,该算法能够快速地实现分流。     

一种改进的多维高速报文分类算法*

RFC算法是目前具有代表性的一种报文分类算法,具有匹配速度快、占用内存少、支持范围匹配等优点,但是它不能处理变长字符串域.结合多模式匹配算法的思想,对RFC算法进行了有益扩充,使新算法能够根据变长字符串域进行分类.实验结果表明,改进的算法在有效扩展KFC算法的适用范围的基础上,仍具有良好的性能.     

支持快速增量更新的包分类算法

动态数据包分类是目前新兴网络服务的基础,但现有包分类算法的更新性能不能令人满意。基于递归空间分解和解释器方法,设计和实现了一个支持快速增量更新的两阶段多维包分类算法TICS,利用局部数据结构重建替换方法允许规则集增量更新,并通过适当的内存管理允许查找和更新的并行同步进行。实验表明,算法的更新速度比目前更新最快的BRPS算法至少提升了一个数量级,且内存消耗少,具有良好的并行扩放性。     

基于网络处理器的高速包分类机制设计

三元按内容寻址寄存器(TCAM)是内容寻址存储器(CAM)的一种变形,较CAM而言可以使查找更加灵活,对其工作（如包处理）效率的提高也起着极大的优化作用。文章从TCAM的原理及结构特点出发,阐述了其适用于提高NP性能的原因,通过一个设计实例说明了采用TCAM协处理器在网络处理器中加速包处理过程的方法和技术。