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

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

一种面向连接的快速多维包分类算法

为进一步提高聚合位向量(ABV)算法分类数据包的速度,该文提出一种面向连接的改进ABV(IABV)算法。该算法利用同一连接包分类查找规则相对一致的特点,建立哈希表-规则库两级优化查找结构,首先通过哈希表查找包分类规则,若未命中继续从规则库中查找。利用连接时效性特点设计哈希表冲突处理机制,根据表项最近命中时间判断是否进行覆写更新,避免规则累积导致查找时间增加;其次对ABV算法各维度进行等分处理,为各等分区间建立数组索引,从而快速缩小向量查找范围,加快查找规则库速度;最后,将规则中前缀转化为范围降低辅助查找结构复杂度,以减少内存空间占用量并加快规则查找速度。实验结果表明,将规则中前缀转化为范围后能够有效提升算法性能,相同条件下IABV算法相比ABV算法时间性能有显著提高。

     

多决策树包分类算法

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

递归算法在程序设计中的应用与分析

递归是程序设计中的一种重要机制,几乎所有的问题都可以借助递归的框架予以表达,更重要的是借助递归可以把一些貌似复杂的问题用紧凑形式表示出来,可读性好。本文阐述了递归适用范围与递归设计方法,通过案例,重点分析了递归算法的非递归化。     

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

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

快速流分类算法的研究

基于流的流量测量是网络测量的重要内容。对多种IP流分类算法及可能应用于万兆网环境的算法进行了分析和比较,提出了快速流分类算法需要解决的问题及发展思路。     

递归算法的分析与应用

随着软件应用中程序编写的复杂性和问题规模的扩大性,递归算法已被应用的越来越广泛,只有掌握递归的思想和了解递归的特点,才能将问题分析的更透彻,提取复杂问题中的核心点,最终用递归算法将问题简单化。本论文的目的是分析递归算法,同时介绍递归算法在构造树或图中搜索以及折半查找算法中的应用。     

递归算法的分析与应用

随着软件应用中程序编写的复杂性和问题规模的扩大性,递归算法已被应用的越来越广泛,只有掌握递归的思想和了解递归的特点,才能将问题分析的更透彻,提取复杂问题中的核心点,最终用递归算法将问题简单化。本论文的目的是分析递归算法,同时介绍递归算法在构造树或图中搜索以及折半查找算法中的应用。     

基于迭代主成分分析的哈希算法研究与实现

为了提高高维空间近邻搜索算法的查询性能,本文结合DSH算法和迭代PCA方法的优点提出迭代PCA哈希算法.该算法查询效果良好,充分利用数据集的分布信息、有严格的理论保证.该算法在达到相同精度的条件下较LSH算法和DSH算法查询花费时间少.该算法提供了一种解决近邻搜索问题有效方法.     

递归算法的设计模式与调试

基于递归算法的“自重复”特征,文中提出一种通用递归算法的设计模式,并结合实例说明该模式的应用方法和有效性,为研究递归算法提供了有效的解决方案,可推广性强。同时给出了递归程序在调试过程中的一些方法和技巧。     

适用于UHF RFID认证协议的Hash函数构造算法

在标签硬件资源受限情况下,为提高UHF RFID系统认证的安全性能,提出一种Hash函数构造算法.算法选择6个混沌映射组合之一来构造Hash函数,通过切换每组中的2个混沌映射生成混沌序列数组,再经过全序列取数策略,将生成的两组数值映射为最终的Hash值.结果分析表明,该算法具有很好的单向性、初值敏感性,在硬件资源和安全性能两方面满足了UHF RFID系统的安全认证要求.     

一种多维IP包分类算法

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

基于流标签的新型可降维IPv6报文分类算法

Traditional packet classification for IPv4 involves examining standard 5-tuple of a packet header, source address, destination address, source port, destination port and protocol. With introduction of IPv6 flow label field which entails labeling the packets belonging to the same flow, packet classification can be resolved based on 3 dimensions: flow label, source address and destination address. In this paper, we propose a novel approach for the 3-tuple packet classification based on flow label. Besides, by introducing a conversion engine to covert the source-destination pairs to the compound address prefixes, we put forward an algorithm called Reducing Dimension (RD) with dimension reduction capability, which combines heuristic tree search with usage of buckets. And we also provide an improved version of RD, called Improved RD (IRD), which uses two mechanisms: path compression and priority tag, to optimize the performance. To evaluate our algorithm, extensive experiments have been conducted using a number of synthetically generated databases. For the memory consumption, the two proposed new algorithms only consumes around 3% of the existing algorithms when the number of filters increases to 10 k. And for the average search time, the search time of the two proposed algorithms is more than four times faster than others when the number of filters is 10 k. The results show that the proposed algorithm works well and outperforms many typical existing algorithms with the dimension reduction capability.     

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

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

流分类算法研究综述

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

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

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

多域网分组分类算法研究

随着网络业务的不断增长,网分组分类技术成为下一代互联网的研究热点.多域网分组分类算法作为网分组分类的核心技术,具有重要的研究价值.介绍了网分组分类算法的理论基础;对典型的网分组分类算法进行了介绍和比较分析,指出了各自存在的优缺点,并针对性地提出了改进措施;最后对多域网分组分类算法加以总结,探讨了新的研究方向.     

A Wavelet Packet Algorithm for Classification and Detection of Moving Vehicles

In this paper we propose a robustalgorithm that solves two related problems: 1) Classificationof acoustic signals emitted by different moving vehicles. Therecorded signals have to be assigned to pre-existing categoriesindependently from the recording surrounding conditions. 2) Detectionof the presence of a vehicle in a certain class via analysisof its acoustic signature against the existing database of recordedand processed acoustic signals. To achieve this detection withpractically no false alarms we construct the acoustic signatureof a certain vehicle using the distribution of the energies amongblocks which consist of wavelet packet coefficients. We allowno false alarms in the detection even under severe conditions;for example when the acoustic recording of target object is asuperposition of the acoustics emitted from other vehicles thatbelong to other classes. The proposed algorithm is robust evenunder severe noise and a range of rough surrounding conditions.This technology, which has many algorithmic variations, can beused to solve a wide range of classification and detection problemswhich are based on acoustic processing which are not relatedto vehicles. These have numerous applications.