报文分类算法可扩展性标准评测系统

针对报丈分类算法没有标准可扩展性评测工具的问题,基于计算机体系结构测试领域的benchmark方法开发出基于benchmark的报文分类算法可扩展性评测系统.该系统利用benchmark参数文件引导生成规则库,允许用户利用高层输入参数控制规则库和Trace的产生,并能够实现对被测算法可扩展性能指标的实时监测.最后利用该评测系统对典型报文分类算法在不同模拟场景下进行仿真评测.仿真结果表明,该系统能够准确评测算法的可扩展性,为研究报丈分类算法的可扩展性提供了标准评测工具.     

报文分类算法研究

阐述了互联网络中报文分类问题的定义、几何意义和最新研究进展.从报文分类算法的实现特征出发,对报文分类问题的各种经典算法进行了分类并逐类地详细介绍.通过对几种典型算法在虚拟环境下进行评测,总结了各种报文分类算法的优缺点和适用环境,并就报文分类问题的研究方向作出展望.     

基于IXP1200的快速报文分类算法的设计与实现

通过对现有报文分类算法的分析和性能比较,并结合分类规则所具有的特性提出了一种新的基于IXP1200网络处理器的多维报文分类算法,称为PCBNP(packet classification based on network processor),并达到了报文的线速转发.算法除了通过减少分类的规则数和分类的域宽来加快分类的速度外,还采用重定向排序索引、位向量表示匹配规则等技术来加快分类的速度,特别是利用了规则的动态分布规律来确定查找报文字段的顺序,通过先查找“分布最均匀的字段”来达到在所有的字段被查找之前提前找到报文匹配的过滤规则的目的.算法具有高速、多维和可扩展的特性,与现有的算法比较,该算法在综合性能上优于已有的报文分类算法.     

基于IXPl200的快速报文分类算法的设计与实现

通过对现有报文分类算法的分析和性能比较，并结合分类规则所具有的特性提出了一种新的基于IXP1200网络处理器的多维报文分类算法，称为PCBNP(packet classification based on network processor)，并达到了报文的线速转发．算法除了通过减少分类的规则数和分类的域宽来加快分类的速度外，还采用重定向排序索引、位向量表示匹配规则等技术来加快分类的速度，特别是利用了规则的动态分布规律来确定查找报文字段的顺序，通过先查找“分布最均匀的字段”来达到在所有的字段被查找之前提前找到报文匹配的过滤规则的目的．算法具有高速、多维和可扩展的特性，与现有的算法比较，该算法在综合性能上优于已有的报文分类算法．     

报文分类算法研究

该文首先对报文分类问题进行了形式化描述,陈述了解决该问题的几种思路并对其进行了性能的边界分析;同时给出了设计高效报文分类算法需要关注的关键问题;对目前常见的报文分类算法作了介绍,分析了这些算法的时间、空间和更新复杂度;并结合常见的报文分类算法的应用指出了各算法的适用范围;最后介绍了其它领域的分类算法的应用,展望了报文分类算法的两个发展方向。     

基于GPU的并行报文分类方法

 报文分类是网络设备的基本处理模式,通常采用报文过滤系统对每个报文进行分类。传统报文分类难以适应当今越来越高的网络流量,分类处理速度低于报文到达网络接口的速度,无法实现实时分析。因此,本文提出使用GPU对大规模报文集进行并行分类的方法,利用GPU的线程级并行处理能力加速报文分类吞吐率,并对其性能及优化方法进行详细分析。实验结果表明,GPU加速的Linear Search和RFC报文分类算法与纯CPU系统执行相比可达到4.4~132.5倍的加速比。     

基于OpenFlow的报文分类算法研究与实现

随着软件定义网络、OpenFlow等技术的兴起,传统的基于5元组的报文分类技术已不能满足OpenFlow基于多元组的细粒度流量控制需求。因此,以分析已有的报文分类算法为基础,采用分而治之的思想,针对OpenFlow报文分类的精确匹配需求,设计实现了一种基于Hash的计数型链表Bloom Filter算法--OF_CBF算法。针对OpenFlow报文分类的通配匹配需求,借鉴正则表达式匹配算法思想,设计实现了基于有限自动机的报文匹配算法--OF_FSMP算法。对两种算法进行分析验证,并初步对两种算法进行了性能分析。     

IP报文分类算法概述

Internet的高速发展要求提供高性能的P流分类算法以更好地为防火墙、QoS、流量工程、资源预留、网络地址转换等提供服务。由于IP报文分类算法的多域特征,因此其具有相当的难度。研究者提出了很多报文分类算法,本文将这些算法概括为5类：基于Trie树的算法、基于空间分割的算法、启发式算法、基于硬件实现的算法和其他算法,并对IP报文分类算法的思想、原理和过程进行了介绍和分析,说明了这些算法之间的联系,并对这些算法在搜索和更新的时间性能、空间性能、适用性范围和优缺点等进行了分析和比较。作为总结,本文还对IP报文分类算法研究的方法和趋势进行了分析和总结。     

BFPC:一种新型的基于Bloom Filter的报文分类算法

Bloom Filter是一种支持高速数据查询的数据结构,已被广泛应用到各个领域,包括路由查找、串匹配[1]等。本文将重点研究Bloom Filter在报文分类领域中的应用,提出一种新型的报文分类算法——BFPC,阐述BFPC算法的基本思想,并通过实例对该算法进行了描述。最后,对BFPC算法与其他报文分类算法进行了性能比较。     

报文分类技术的研究及其应用

Internet网络应用的发展要求路由器支持诸如服务质量(QoS)、网络入侵检测、传输测量与记账、负载平衡、拥塞控制等多种不同的技术，虽然实现这些不同技术的细节变化可能很大，但一个公共的要求是路由器能够基于报文的头的某些字段对报文进行分类．从已有的研究表明，实现高速多维报文分类算法是非常困难的，它已成为路由器的新的瓶颈，因此吸引了许多研究人员的注意．系统论述了报文分类的相关技术，包括分类的模型、可能分类的字段，评价分类的基本标准等，通过对现有报文分类算法的比较和性能分析并结合分类规则所具有的特性，提出了设计报文分类算法所应遵循的原则和思路，同时还讨论了报文分类在网络技术领域中的应用和还需解决的一些相关问题．     

Optimizing Multi-Dimensional Packet Classification for Multi-Core Systems

Packet classification has been studied for decades; it classifies packets into specific flows based on a given rule set. As software-defined network was proposed, a recent trend of packet classification is to scale the five-tuple model to multi-tuple. In general, packet classification on multiple fields is a complex problem. Although most existing softwarebased algorithms have been proved extraordinary in practice, they are only suitable for the classic five-tuple model and difficult to be scaled up. Meanwhile, hardware-specific solutions are inflexible and expensive, and some of them are power consuming. In this paper, we propose a universal multi-dimensional packet classification approach for multi-core systems. In our approach, novel data structures and four decomposition-based algorithms are designed to optimize the classification and updating of rules. For multi-field rules, a rule set is cut into several parts according to the number of fields. Each part works independently. In this way, the fields are searched in parallel and all the partial results are merged together at last. To demonstrate the feasibility of our approach, we implement a prototype and evaluate its throughput and latency. Experimental results show that our approach achieves a 40% higher throughput than that of other decomposed-based algorithms and a 43% lower latency of rule incremental update than that of the other algorithms on average. Furthermore, our approach saves 39% memory consumption on average and has a good scalability.     

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

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

流分类算法综述

流分类问题是当前国内外研究的热点 ,流分类算法层出不穷 .首先介绍了流分类的重要意义 ,然后简单的介绍了流分类问题涉及到的一些概念性问题 ,最后着重介绍了目前流分类的最新成果 .本文对每一类详细介绍了其中典型的算法 ,并且对各算法的性能进行了分析比较     

基于层次智能切割的IP分类算法

首先对规则数据库存在冲突的情况进行处理,生成了无冲突的规则数据库。然后基于层次智能切割算法,同时构造无冲突的哈希函数,提出了一种新的IP分类算法,即基于层次智能切割和无冲突哈希算法( HICNCH),并且提出利用最小二乘法改进了层次智能切割树分割域的判定准则,使分割更加高效。通过与经典算法的各项指标的比较,论证了该算法具有较小时间复杂度和空间复杂度,综合性能有了较大提高。     

一种新的高维报文分类算法--无相交树算法

报文分类是网络交换设备的基础操作之一，它会在很大程度上影响相关硬件设备和软件系统的功能和性能．目前存在大量的报文分类算法，但大多数都是针对低维分类问题．针对网络管理和网络入侵检测等应用需求的日益增长，该文提出了一种新的高维报文分类算法NI Trie．该算法具有其它报文分类算法所不具备的强表述支持能力和低时间复杂度并存的特点，其期望时间复杂度和期望空间复杂度均达到了同类分类算法的最优或接近最优．它具备较强的软硬件通用能力，可适用于较广的应用领域，实际应用性能良好．     

DiffServ模型中的多级主动缓冲管理算法

根据DiffServ模型实现的需要，在分析现有缓冲管理算法的基础上，提出了QPRED和VPRED多级主动缓冲管理算法，这两种算法在分组分类的粒度上提供了分级的缓冲管理能力，并将每一类分组的缓冲状态（缓冲字节数或缓冲平均队列长度）引入到了分组丢弃概率的计算中，同时结合优先级因子实现了类和类之间在优先级意义上的公平性，与现有的缓冲管理算法相比，QPRED和VPRED多级主动缓冲管理算法更适合于DiffServ模型的要求。