基于Hash和AQT的类决策树包分类算法研究

多维包分类算法是网络安全、网络测量、服务质量、流路由等技术的重要组成部分,然而设计一种在时间上和空间上均占优的包分类算法却十分困难。在研究现有的经典IP包分类算法的基础上,根据协议类型域有限取值的特点提出了一种基于Hash函数和AQT的决策树的新型IP包分类算法。仿真结果表明：相比传统包分类算法,该算法具有更低的时空复杂度。     

高速路由器中TCP/IP数据流的分类技术

文章介绍了几种实用化的快速IP流分类技术，如三重内容寻址、基于比特向量的多维范围匹配、有向非循环图、交叉乘积和递归流分类算法等流分类技术，并根据各种流分类技术的不同应用场合，给出了设计分类算法的原则。     

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

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

基于AdaBoost的组合网络流量分类方法

针对单一分类方法在训练样本不足的情况下对于小样本网络流分类效果差的特点,通过自适应增强(Adaptive Boosting,AdaBoost)算法进行流量分类。算法首先使用CFS(Correlation-based Feature Selection)特征选择方法从大量网络流特征中提取出少量高效的分类特征,在此基础上,通过AdaBoost算法组合决策树、关联规则和贝叶斯等5种单一分类方法实现流量分类。实际网络流量数据测试表明,基于AdaBoost的组合分类方法的准确率在所选的几种算法中是最高的,其能够达到98192%,且相对于单一的分类算法,组合流量分类方法对于小样本网络流的分类效果具有明显提升。     

基于半监督学习的应用流分类方法

将半监督学习应用到应用流分类问题中,提出了一种基于半监督聚类的应用流分类算法(PSOSC).首先采用粒子群优化的K均值聚类方法对大量的无标记数据和少量的标记数据进行聚类,利用少量标记数据确定簇与应用类型的映射关系,实现应用流分类.实验表明PSOSC算法有较高的流准确率,同时,降低了对标记数据的需求.     

多决策树包分类算法

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

基于NetFlow流记录的高速应用流量分类方法

针对目前应用流量分类算法效率不高的现状,提出一种以NetFlow统计的IP流记录信息作为输入的高速应用流量分类(FATC,fast application-level traffic classification)算法。该算法采用基于简单相关系数的测度选择算法衡量测度变量间的相关关系,删除对分类无用或相互冗余的测度,而后使用基于Bayes判别法的分类算法将网络流量分至误判损失最小的应用类别中。理论分析及实验表明,FATC算法在具有超过95%的分类准确率基础上,极大降低了当前应用流量分类方法在训练和分类过程的时空复杂度,满足实时准确分类当前10Gbit/s主干信道网络流量的需求。     

激光主动成像结合距离选通技术的零时信号测量方法

针对火箭起飞过程中零时信号难以准确测量问题,提出了激光主动成像与距离选通技术相结合的测量方式,并通过求取光流的变化进而求取位移移动量获得火箭起飞的零时信号。对现有的零时信号测量方式进行了分析,确定了基于距离选通的ICCD成像方式,结合目标垂直上升的特性,提出目标轮廓与HS光流结合的抗光照干扰算法。实验结果表明:在模拟目标匀速上升过程中,在光照变化不大情况下,单独的边缘检测及单独的HS光流检测算法均能检测出目标的上升趋势;在光照变化剧烈情况下,边缘检测及HS光流检测算法均出现严重的误差,目标轮廓与HS光流结合算法排除了目标内部的干扰,得到的目标像素点位移量与真实的上升量基本一致,误差在亚像素量级,若图像帧频为25 fps,则时间精度为80 ms,完全符合零时信号提取的要求。     

基于多位域的等概率随机IP流抽样算法

对IP流信息的全方位提取有助于实现网络实时监控,精细管理,有利于网络安全性能的提升。已有的等概率随机IP流抽样算法将大量的IP流重复抽样,浪费了宝贵的计算和存储资源。针对这个问题,在原有算法的基础上设计了一种新的等概率随机IP流抽样算法,该算法在Bloom Filter的基础上采用三层位域,两层同时测量,结果取交集的方法,便于实际使用并且有效减少了已被抽样的IP流被重复抽样。实验结果表明:新方法能够大幅度提高测量精度,节约了系统资源,可以适用于10 Gb/s左右的高速网络之中。     

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

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

Algorithms for packet classification

The process of categorizing packets into “flows” in an Internet router is called packet classification. All packets belonging to the same flow obey a predefined rule and are processed in a similar manner by the router. For example, all packets with the same source and destination IP addresses may be defined to form a flow. Packet classification is needed for non-best-effort services, such as firewalls and quality of service; services that require the capability to distinguish and isolate traffic in different flows for suitable processing. In general, packet classification on multiple fields is a difficult problem. Hence, researchers have proposed a variety of algorithms which, broadly speaking, can be categorized as basic search algorithms, geometric algorithms, heuristic algorithms, or hardware-specific search algorithms. In this tutorial we describe algorithms that are representative of each category, and discuss which type of algorithm might be suitable for different applications     

利用流量特征的GIDS报文分类优化算法

 本文结合流量的动态特征和入侵检测系统规则库的静态特征生成高性能报文分类树,提出了一个新的面向骨干网高速入侵检测的报文分类算法FlowCopySearch(FCS).改进在于:①从流量的新角度提出了最优分类树定义并引入分类域熵衡量每个分类域对于流量的分类能力;②将传统分类算法中每个报文都必须频繁执行的内存拷贝操作简化为每个流只执行一次内存拷贝操作,克服了报文分类算法的瓶颈.实验结果表明FCS更适用于骨干网大流量trace的报文分类,较之两种经典分类算法,分类速度提高了10.1%~45.1%,同时存储消耗降低了11.1%~36.6%.     

Optimization study of a packet classification algorithm

Packet classification is a central function in filtering systems such as firewalls or intrusion detection mechanisms. Several mechanisms for fast packet classification have been proposed. But, existing algorithms are not always scalable to large filters databases in terms of search time and memory storage requirements. In this paper, we present a novel multifields packet classification algorithm based on an existing algorithm called Pacars and we show its advantages compared to previously proposed algorithms. We give performance measurements using a publicly available benchmark developed at Washington University. We show how our algorithm offers improved search times without any limitation in terms of incremental updates.     

基于流标签的新型可降维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.     

Voice Activity Detection Algorithm Using Spectral-Correlation and Wavelet-Packet Transformation

It is developed the voice activity detection algorithm using noise classification technique. It is proposed the spectral-correlation and wavelet-packet (WP) features of frames for voice activity estimation. There are tested three WP trees for effective representing of audio segments: mel-scaled wavelet packet tree, bark-scaled wavelet packet tree and ERB-scaled (equivalent rectangular bandwidth) wavelet packet tree. Application only two principal components of WP features allows to classify accurately the environment noise. The using wavelet-packet tree design which follows the concept of equivalent rectangular bandwidth for acoustic feature extraction allows to increase the voice/silence segments classification accuracy by at least 4% in compare to other classification based voice activity detection algorithms for different noise.     

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

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

基于统计的高效决策树分组分类算法

基于决策树的分组分类算法因易于实现和高效性,在快速分组分类中广泛使用。决策树算法的基本目标是构造一棵存储高效且查找时间复杂度低的决策树。设计了一种基于规则集统计特性和评价指标的决策树算法——HyperEC 算法。HyperEC算法避免了在构建决策树过程中决策树高度过高和存储空间膨胀的问题。HyperEC算法对IP地址长度不敏感,同样适用于IPv6的多维分组分类。实验证明,HyperEC算法当规则数量较少时,与HyperCuts基本相同,但随着规则数量的增加,该算法在决策树高度、存储空间占用和查找性能方面都明显优于经典的决策树算法。     

面向轻载深包检测的应用负载特征自动挖掘(英文)

Automatic signature generation approaches have been widely applied in recent traffic classification.However,they are not suitable for LightWeight Deep Packet Inspection(LW_DPI) since their generated signatures are matched through a search of the entire application data.On the basis of LW_DPI schemes,we present two Hierarchical Clustering(HC) algorithms:HC_TCP and HC_UDP,which can generate byte signatures from TCP and UDP packet payloads respectively.In particular,HC_TCP and HC_ UDP can extract the positions of byte signatures in packet payloads.Further,in order to deal with the case in which byte signatures cannot be derived,we develop an algorithm for generating bit signatures.Compared with the LASER algorithm and Suffix Tree(ST)-based algorithm,the proposed algorithms are better in terms of both classification accuracy and speed.Moreover,the experimental results indicate that,as long as the application-protocol header exists,it is possible to automatically derive reliable and accurate signatures combined with their positions in packet payloads.     

Wavelet feature selection for image classification

Energy distribution over wavelet subbands is a widely used feature for wavelet packet based texture classification. Due to the overcomplete nature of the wavelet packet decomposition, feature selection is usually applied for a better classification accuracy and a compact feature representation. The majority of wavelet feature selection algorithms conduct feature selection based on the evaluation of each subband separately, which implicitly assumes that the wavelet features from different subbands are independent. In this paper, the dependence between features from different subbands is investigated theoretically and simulated for a given image model. Based on the analysis and simulation, a wavelet feature selection algorithm based on statistical dependence is proposed. This algorithm is further improved by combining the dependence between wavelet feature and the evaluation of individual feature component. Experimental results show the effectiveness of the proposed algorithms in incorporating dependence into wavelet feature selection.     

Learn more, sample less: control of volume and variance in network measurement

This paper deals with sampling objects from a large stream. Each object possesses a size, and the aim is to be able to estimate the total size of an arbitrary subset of objects whose composition is not known at the time of sampling. This problem is motivated from network measurements in which the objects are flow records exported by routers and the sizes are the number of packet or bytes reported in the record. Subsets of interest could be flows from a certain customer or flows from a worm attack. This paper introduces threshold sampling as a sampling scheme that optimally controls the expected volume of samples and the variance of estimators over any classification of flows. It provides algorithms for dynamic control of sample volumes and evaluates them on flow data gathered from a commercial Internet Protocol (IP) network. The algorithms are simple to implement and robust to variation in network conditions. The work reported here has been applied in the measurement infrastructure of the commercial IP network. To not have employed sampling would have entailed an order of magnitude greater capital expenditure to accommodate the measurement traffic and its processing.