基于计数布鲁姆过滤器的快速多维包分类算法

本文从数据包匹配规则的聚集特性出发,将计数布鲁姆过滤器和哈希表相结合,设计并实现了一种高效的多维包分类算法CBHT(Counting Bloom filter and Hash Table).基于包匹配规则的聚集特性,对于五维包分类问题,CBHT算法首先利用计数布鲁姆过滤器的过滤功能结合单域匹配获得与前两维匹配的小规模规则集,而后在此有限规则集中对后三维进行匹配.利用计数布鲁姆过滤器提高了包匹配速度并有效支持规则库的动态更新.实验结果表明CBHT算法比现有的B2PC算法节省60%的硬件资源,包匹配访问内存次数平均低于B2PC算法22.8%.     

哈希算法与递归流分类算法在包分类应用中的比较

包分类是多种网络应用的关键性技术,包分类算法的性能对网络的时延和吞吐量有决定性的影响。本文通过介绍包分类应用中常用的哈希算法和递归流分类算法的原理,比较它们的性能特点和应用范围,阐述在应用中各自的优缺点。     

包分类算法在防火墙中的应用研究

包分类算法的性能直接影响数据包的收发速度,决定了网络的时延和吞吐量。防火墙中使用分类算法进行过滤规则的匹配查找,能有效降低规则匹配搜索时间,极大地提升防火墙的性能。递归流分类（RFC,Recursive Flow Classification）算法查找速度快,但预处理时间长,存储开销大。现在RFC算法的基础上,结合哈希树算法对数据包各字段分开处理。将两种算法结合,综合考虑了空间和时间性能,不仅减少了存储开销,而且能保持相对快的查找速度。     

一种多维IP包分类算法

IP分类算法是应用在高性能路由器中的一种重要算法，研究IP分类算法对于提高路由器综合性能具有重要意义。基于无冲突哈希函数和AQT算法提出了一种新的IP分类算法NCHAQT（Non—Collision Hash AQT）。NCHAQT解决了AQT算法只能应用于二维的情况，使AQT可以应用于五维分类，增强了它的可扩展性。理论分析与仿真实验表明，NCHAQT在时间性能上算法优于经典算法Modular，是一个综合性能较高的包分类算法．     

一种采用启发式分割点计算的包分类算法

针对区域分割包分类算法存在的规则分布差异较大的缺陷,该文提出一种基于启发式分割点计算的区域分割包分类算法。首先依据规则集的分布规律进行分割点计算,然后再进行结构化建树。规则检索时间主要包括分割点匹配时间和分割点内规则的线性查找时间。该算法能够尽量将规则平分到各分割点,减少了规则分布的差异。仿真实验结果表明该算法降低了规则数增加对算法性能的影响,支持规则集的实时更新。     

一种基于索引指针的可扩展IP包分类算法

设计并实现了一种基于索引指针的可扩展IP包分类算法.该算法通过分析源/目的端口号和协议类型字段在实际应用中的分布特性,将这3个字段映射到一个8比特元组上,压缩了分类维数;算法依据压缩后的8比特元组将分类规则集划分为256个子集,并为每个子集建立一个索引指针,指向该子集的存贮起始地址;算法通过计算IP包中"源/目的IP地址联合字段"中各个比特的信息熵值,找出最优的比特序列作为根和子节点,为每个规则子集建立一棵Tries查找树,既保证了存贮空间和查找时间最小,而且不存在回溯问题.实验结果证明,该算法分类效率高.     

多决策树包分类算法

网络安全、网络测量、服务质量、流路由等都离不开多维包分类算法。设计一种在时间上和空间上都很好的包分类算法非常困难。该文在分析大规模规则集的特征的基础上,根据协议类型域只有有限的几种取值的特点,提出一种多决策树包分类算法。该算法既可用软件实现,也适宜硬件实现,并且在理论上适用于IPv6的包分类。当采用硬件实现时,多棵树可以并行查找,树内查找可以采用流水结构,算法的查找复杂度为O(1)。该算法可用于改进广泛应用的HiCuts和HyperCuts算法,与之相比,多决策树算法在预处理时间、内存占用和查找时间上都有很大提高。     

一种改进的交叉组合包分类研究

本文提出一种改进的基于交叉组合的包分类方法,基于对各维空间的无重叠的划分基础上进行分类,采用等价区间的办法来降低空间需求,该方法在提高处理速度的同时,所需存储空间也降低了三分之二。使用自治系统网络前缀产生模拟的分类数据库,用非随机方式及随机方式产生不同大小的数据库来对这个算法进行了验证,证明了这个算法的有效性。     

一种快速自适应最优小波包基搜索算法

在小波包调制系统中,小波包基的选取对于系统性能有着显著的影响。针对目前BBS算法与BFA算法的缺点,分析了小波包基的构成原则与选取方法,提出了一种基于根节点逐级向下按二进分支路分解,利用度量函数决定父节点与子节点取舍的最优基搜索算法,并解决了约束条件下的最优基输出问题。最后将该算法在4径Rayleigh信道模型下进行了测试,仿真结果表明：在相同条件下,该算法比BBS算法快15%~20%,比BFA算法快10~15倍,且输出的最优基比全分解结构的ICI与ISI联合功率降低约20%。     

支持向量机的一种快速分类算法

传统支持向量机分类过程的计算量和支持向量的个数成正比,当支持向量较多时,其分类过程的计算比较耗时。该文基于支持向量的稀疏性,证明了对支持向量压缩时,收紧新的快速决策函数和原始决策函数之间的误差等价于在样本空间对原始支持向量进行K均值聚类操作,据此提出了一种约简支持向量的快速分类算法FD-SVM(Fast Decision algorithm of Support Vector Machine),该算法首先对原始的支持向量进行特定比例的K均值聚类操作,聚类的中心为约简后新的支持向量,按照分类误差最小的原则构建优化模型,用二次规划方法求解得到新的支持向量的系数。标准数据集上的实验表明,保持分类精度的损失在统计意义上不明显的前提下,FD-SVM可以有效压缩支持向量的数量,提高分类速度。     

流分类算法研究综述

流分类问题是未来宽带通信网络中的关键技术之一。对流分类算法的现状进行分析讨论，并对其今后的研究思路进行探讨。     

一种采用按值分支树的多维流分类算法

该文针对Modular算法用于流分类所存在的问题,提出一种采用按值分支树的多维流分类算法。算法支持对规则维数和数量的扩展,并能同时处理前缀匹配和范围匹配。仿真试验结果表明：该算法具有良好的扩展性,支持大容量的分类规则。     

Adaptive Packet Classification Algorithm Based on IXP2800 Network Processor

Packet classification is a critical data-plane task for modern routers to support value-added services, especially for those requiring QoS and flow based processing. However, classification at 10Gbps or higher using an algorithmic approach is still challenging. New generation of Network processor unit （NPU） provides unprecedented processing power for network applications, and it opens a new venture to explore thread-level parallelism for attacking networking performance bottlenecks. This paper studies the implementation issues of how an adaptive clas- sification algorithm can be efflciently implemented on a multi-core and multithreaded NPU architecture. Our algorithm combines best traits of Recursive flow classification （RFC） algorithm and bitmap compression technique to achieve deterministic classification performance while keeping the memory growth checked. When mapping such an algorithm onto the Intel IXP network processor, we consider the characteristic of IXP architecture early in the algorithm-design phase to eliminate the potential perfor- mance bottlenecks. The implemented algorithm is highly efflcient and it can run at 10Gbps speed or higher on a real IXP2800 chip.     

一种基于匹配域裁剪的包分类规则集压缩方法

随着以OpenFlow为代表的多匹配域包分类规则的出现,匹配域数量的不断增加、流表宽度的不断增大以及流表规模的不断膨胀,大大增加了硬件存储的压力。为提高现有三态内容可寻此存储器(TCAM)资源利用率,该文提出一种基于规则集特征分析的匹配域裁剪模型Field Trimmer。一方面基于对规则集中匹配域的逻辑关系分析,实现匹配域的合并, 从而减少匹配域的数量;另一方面基于对规则集统计规律的分析,实现匹配域的裁剪,使用部分匹配域来达到整体的匹配效果。实验结果表明,相比于其他方案,该方案在较小的时间复杂度下,能够进一步节省OpenFlow流表的TCAM存储空间需求50%左右;对于常见的包分类规则集,该方案所需的储存空间能够节省40%以上。     

一种基于Credit的变长分组并行交换网络调度算法

该文提出了一种新的并行分组交换(PPS)网络调度算法。该算法通过在解复用器处采用以变长分组为业务分配单元的方式消除了信元的乱序问题;通过采用Credit机制进行业务分配,实现了业务到各个交换平面完全公平的分配;各个并行交换单元采用组合输入输出排队,降低了对缓存和交换平面的加速要求,同时可以充分利用现有单Crossbar网络调度算法的研究成果。文中证明了该算法对业务分配的公平性,对高速缓存的需求量以及整个网络的稳定性,仿真进一步证明了该算法具有良好性能。     

一种新的贝叶斯调制分类算法

提出了一种基于马尔可夫链蒙特卡罗(MCMC)的数字调制分类方法。针对存在未知残留载波相位和频率时贝叶斯分类难以实现的问题,采用Metropolis-Hastings(M-H)算法估计边缘似然概率密度,从而在分类性能上保持了贝叶斯分类的理论最优性和稳健性。利用对比实验验证了方法的性能。     

一种基于大脑情感学习的快速分类改进算法

为了提高数据分类的快速性与准确性,本文在大脑情感学习（Brain Emotional Learning,BEL）模型的基础上,结合遗传算法（Genetic Algorithm,GA）,提出了一种基于GA-BEL的快速分类改进算法.BEL模型根据大脑中杏仁体和眶额皮质之间相互学习的神经生物学原理建立,模拟了情感刺激在大脑短反射通路中被快速处理的过程.因此,基于BEL模型的网络运算速度快.进一步采用遗传算法优化BEL网络权值,提高其分类正确率.在UCI数据集上的对比实验结果表明,无论对于小样本还是大样本数据集,较其他分类算法,GA-BEL算法均有较高的分类正确率和计算效率.