一种线速可伸缩的多维包分类算法

包分类是第四层线速数据包输入处理的核心问题.当前包分类问题研究的重点是最差情况下、可伸缩的、多维的算法.尝试格算法的优点是规模可伸缩,缺点是仅支持两维.在尝试格的基础上,结合IP包分类的应用背景,提出了一种可伸缩的五维算法--无回溯层次尝试算法.该算法的基本数据结构是基于尝试格的层次尝试.在不降低规则定义能力的前提下,引入合理的假设.并在此基础上,进一步优化数据结构,消除了层次尝试的回溯搜索.实验证明对于百万规模的规则集,该算法在最差情况下可支持1Gbps链路,在平均情况下可支持2.5Gbps链路.     

基于量化规则格的关联规则渐进更新*

提出一种基于量化规则格的规则更新算法,重点讨论了在新增格节点的过程中规则更新的思想,实现在格的渐增生成过程中,相应的关联规则也得到渐进更新.最后给出简单实例说明规则更新算法的正确性.     

层压缩树包分类算法研究

包分类技术是下一代网络设备的关键技术之一．研究有效的包分类算法是目前网络技术领域的热门课题．层压缩树包分类算法的基本思想是：对路径压缩之后的二叉树进行层压缩，使压缩树中的节点能够按序存储在数组中．通过对数组元素跳跃式的查找快速的对包头进行分类．仿真试验结果表明该算法在较大规则数下能够实现对包头的快速分类，分类速度可以达到每秒处理接近2M个包头，具有O（d）的时间复杂度（d为域的个数）；在中等规模规则数下具有O（dN）的空间复杂度，并且其存储量优于其他算法（如Bitmap和区域分割包分类算法）．由于层压缩树算法对包头的每个域独立查找，在硬件实现上采用并行查找各个域的处理方式将使该算法的查找性能得到更大的提高．     

一种基于Linux内核的高效包分类算法

针对iptables核心包分类算法的低效问题,提出一种符合Linux内核限制条件并充分利用已有内核机制的高效包分类算法。该算法具备动态更新、多维匹配、实施速度快等主流包分类算法的特点,适合实际应用。实验结果表明在规则库较大的情况下,算法性能有很大提高。     

一种新的分类规则提取算法

约束概念格是概念格的特化结构,构造时具有较低的时空复杂度,能从中快速提取比较丰富的信息和知识.为了提取分类规则,在充分分析约束概念格结点外延与数据集等价划分之间关系的前提下,引入了分类支持度和记录支持度的概念,提出了一种面向约束概念格的分类规则提取算法(Classification Rule Acquisition Algorithm based on Constrained Concept Lattice,CRACCL),并采用UCI数据集作为实验集,验证了本算法能够提取更加实用和准确的分类规则.     

基于对象和属性交叉渐进模糊概念格生成算法

在人类的认知过程中,真实的形式背景总是模糊和不确定的,并伴随着对象和属性交叉渐增更新。在分析人类概念形成机理的基础上,提出了一种基于对象和属性交叉渐进式模糊概念格生成算法。该算法从空概念格开始,逐个地将形式背景中的对象和属性交叉插入到模糊概念格中,实现对模糊概念格的渐进式构造。实验及分析表明该算法不仅能有效地渐进式构造模糊概念格,而且解决了以往渐进式概念格生成算法,针对属性和对象交叉渐增更新需要重新构造概念格的问题。     

一种双哈希IP数据包分类算法研究

本文在无冲突哈希算法和异或哈希算法的基础上，提出了一种双哈希的IP分类算法，该算法的核心有三点：一是基于目的／源端口和协议域构造无冲突哈希，由于该三域的组合数目非常少，避免了空间爆炸；二是在异或哈希算法的基础上，将目的／源IP连成比特串后分为四块后进行异或，为了降低冲突率，将异或后的关键值再与一个随机数进行异或，获得分类索引值，并用此值生成多比特Trie树，一般情况下减小了空间和时间复杂度；三是在Trie树终点存放最终分类规则的索引值，为了保证查找到的规则的正确性，对每一个索引值的源／目的IP地址均匹配一次。通过以上三点改进一般要降低算法的时间复杂度和空问复杂度，通过仿真，当对1万条分类规则进行包分类时，该算法的包分类速度可以达到2MPps，所消耗的最大内存为4MB。     

分组映射多维流分类方法分析研究

流分类技术为多种高级网络服务提供支持,是未来宽带通信网络中的关键技术之一。RFC（Recursive Flow Classification）算法是一种具有代表性的流分类算法。分析RFC算法的特点后,针对其在空间效率和规则集更新上存在的不足,提出了一种基于分组映射的五维流分类算法。与RFC算法相比,该算法大大降低了存储空间,并支持规则集的动态更新。     

基于PC-树的关联规则挖掘方法

关联规则是数据挖掘的一种常用方法,特别是用在货篮分析中,而关联规则的经典算法Apriori及其改进算法的时间复杂度和空间复杂度都比较高,对于数据库更新、用户定义最小支持度等动态数据挖掘的成本太高。针对这种情况,提出了用PC-树寻找频繁项集的算法,实现高效的动态数据挖掘。     

基于选择度的分类规则学习算法

规则式分类器通常使用单一度量选择属性值,然而单一度量会导致很多属性值具有相同的度量值,从而无法选择出"好"的属性值。此外,规则式分类器通常提取置信度为100%的规则,致使规则提取过程比较费时,并且所得到的规则支持度较低。针对上述不足,提出新的属性值度量——选择度。选择度是基于信息熵、类支持度及偏离度3种度量的结合,能更好地区分属性值的优劣。在此基础上,提出一种基于选择度的分类规则学习算法LRSM。在LRSM算法中,当规则包含的负实例数小于给定域值时,该规则被抽取,删除被此规则覆盖的实例,抽取下一条规则。实验结果表明,与FOIL算法相比较,LRSM算法提高了分类准确率,同时明显地减少了分类所消耗的时间。     

A new hierarchical packet classification algorithm

Packet classification is one of the most challenging functions in Internet routers since it involves a multi-dimensional search that should be performed at wire-speed. Hierarchical packet classification is an effective solution which reduces the search space significantly whenever a field search is completed. However, the hierarchical approach using binary tries has two intrinsic problems: back-tracking and empty internal nodes. To avoid back-tracking, the hierarchical set-pruning trie applies rule copy, and the grid-of-tries uses pre-computed switch pointers. However, none of the known hierarchical algorithms simultaneously avoids empty internal nodes and back-tracking. This paper describes various packet classification algorithms and proposes a new efficient packet classification algorithm using the hierarchical approach. In the proposed algorithm, a hierarchical binary search tree, which does not involve empty internal nodes, is constructed for the pruned set of rules. Hence, both back-tracking and empty internal nodes are avoided in the proposed algorithm. Two refinement techniques are also proposed; one for reducing the rule copy caused by the set-pruning and the other for avoiding rule copy. Simulation results show that the proposed algorithm provides an improvement in search performance without increasing the memory requirement compared with other existing hierarchical algorithms.     

CARR: a scalable solution for network packet classification

Modern Internet routers have to handle a large number of packet classification rules, which requires classification schemes to be scalable both in time and space. In this paper, we present a scalable packet classification algorithm that is developed by combining two new concepts to the well‐known bit vector (BV) scheme. We propose a range search method based on a cache‐aware tree (CATree) which makes full use of processor's cache line to reduce the number of dynamic random access memory (DRAM) accesses. Theoretically, the number of DRAM accesses of CATree is about log(m+1) times lower than that of the widely used binary search algorithm, where m is the number of keys in a single cache line. Based on our computational results on a set of 1024 keys, the CATree algorithm is 36% faster than binary search algorithm and the performance is better when applied to a larger set of keys. In addition, we develop a rule re‐arrangement algorithm to reduce the bitmap space of BV. With this re‐arrangement, the rules for the same action may be assigned an identical priority. This reduces the number of priorities as well as the memory space of the bitmap. Furthermore, this also reduces the number of memory accesses and hence, increases the CPU cache utilization. With CATree and rule re‐arrangement, the cache‐aware bit vector with rule re‐arrangement algorithm achieves better performance in comparison with the regular BV scheme, both in space and time. In our experiments, the proposed algorithm reduces the bitmap memory space of a practical set of firewall rules by two orders of magnitude and is 91% faster than the regular BV.     

运用差分演化算法实现多维包匹配的研究

互联网的发展已经使网速的瓶颈由链路速度转移到核心网络设备的包处理速度上,而包处理的核心工作是包匹配。传统方法难以做到包匹配速度适应核心网络设备数据包线速转发。提出了一种新的包匹配算法,该算法对差分演化算法进行了改进,并结合了改进算法和传统的包匹配算法。在适应值处理上运用统计学方法,从而增加了分析问题的客观性。数值实验表明,新算法与传统算法相比,在速度、存储空间以及更新时间等性能上得到了有效改善,另外新算法的包匹配的时间性能与规则数目只有很弱的相关性,从而适合处理多维和大规模问题。新算法把演化算法运用于多域大规模规则库的网络数据包的转发,并且数据包还能做到线速转发。新算法具有普适性,适用于防火墙、差别服务路由器等网络设备。     

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

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

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

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

网格计算及其在进化计算中的应用

提出了一种将网格技术应用于进化算法的计算模式。这种计算模式使用规则与规则集共同演变的模式,实现了数据挖掘技术中的分类。它利用网格计算技术的优势,提高了以往复杂的数据挖掘技术的能力和效率。     

光纤通道交换机在强实时约束下的分组调度

以光纤通道交换网络强实时约束下的性能研究为背景,采用实时通信中的周期性任务模型,提出了负载匹配的加权轮循分组调度,导出了在该方法下网络消息集严格实时的充要条件,以最差情形下强实时的网络可达负载率为性能衡量指标推证了采用该算法的优越性并通过仿真进行了验证.     

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

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

Ant Colony Optimization based approach for efficient packet filtering in firewall

A firewall is a security guard placed at the point of entry between a private network and the outside network. The function of a firewall is to accept or discard the incoming packets passing through it based on the rules in a ruleset. Approaches employing Neural networks for packet filtering in firewall and packet classification using 2D filters have been proposed in the literature. These approaches suffer from the drawbacks of acceptance of packets from the IP address or ports not specified in the firewall rule set and a restricted search in the face of multiple occurrences of the same IP address or ports respectively. In this paper we propose an Ant Colony Optimization (ACO) based approach for packet filtering in the firewall rule set. Termed Ant Colony Optimization Packet Filtering algorithm (ACO-PF), the scheme unlike its predecessors, considers all multiple occurrences of the same IP address or ports in the firewall rule set during its search process. The other parameters of the rule matching with the compared IP address or ports in the firewall ruleset are retrieved and the firewall decides whether the packet has to be accepted or rejected. Also this scheme has a search space lesser than that of binary search in a worst case scenario. It also strictly filters the packets according to the filter rules in the firewall rule set. It is shown that ACO-PF performs well when compared to other existing packet filtering methods. Experimental results comparing the performance of the ACO-PF scheme with the binary search scheme, sequential search scheme and neural network based approaches are presented.