层压缩树包分类算法研究

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

一种基于IXP2400的多维包分类引擎设计

包分类在基于策略的路由、Qos和防火墙等网络应用中至关重要,在网络中提供这些区分服务的关键机制是数据包分类功能。网络处理器是一种优化处理网络分组数据的可编程集成电路,其高并行性和可编程特点适合用来实现包分类等计算密集型任务。论文根据BV包分类算法的并行特点,提出了一种基于IXP2400的包分类引擎机制,为高速网络环境下实现网络数据的线速处理提供了借鉴价值。     

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

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

高性能网包分类理论与算法综述

随着IP网络架构的不断演进以及网络业务和安全需求的不断增长,高性能网包分类在下一代交换机、路由器、防火墙等网络基础设备中有着越来越广的应用.网包分类算法作为高性能网包分类的核心技术,具有重要的研究价值和实践意义.文中从理论分析和算法设计两方面介绍了高性能网包分类的最新研究成果.在理论分析层面,依据计算几何理论对网包分类问题的数学解法及复杂度进行了归纳,总结了网包分类算法的理论依据及性能评价方法.在算法设计层面,对具有影响力的网包分类算法按照不同的研究方向进行了归类和介绍,并结合自身研究成果对不同类别的算法设计思路行了深入分析.作者在多核网络处理器平台以及FPGA平台上实现了几类具有代表性的网包分类算法,并通过真实的网络流量测试比较了不同类型算法在不同系统平台上的实际性能.最后,作者总结并展望了高性能网包分类的下一步发展方向.     

基于维度分解的多核并行网包分类算法

为了实现高速网包分类,本文提出一种多核并行的包分类算法。该算法基于维度分解和位向量（Bit Vector, BV）的思想,将规则集分解为多个维度,在对网包进行分类时,采用包内并行方案,将多个维度的结果进行多核并行合并,缩短单个包的处理时间,提升系统吞吐能力,并且能保证输出顺序与包输入顺序一致。实验结果表明,并行算法在Cavium OCTEON CN6645多核网络处理器平台上能达到每秒92700条规则的预处理速度和5.37 Mpps的吞吐性能,当网包大于等于256 Byte时,能实现10 Gbps的线速处理,性能高于同等条件下的HiCut算法和PCIU算法。     

一种基于递归流的快速多维包分类算法

为了使用户在现有的网络上得到不同的服务类型和更好的QOS,同时满足下一代网络的需要,包分类技术受到越来越多的关注,本文在介绍RFC包分类算法的基础上,提出一种新的快速多维包分类算法。     

基于多元分层感知的移动物联网区域分割算法

为解决物联网区域分割引发的低质量数据传输、高频率网络拥塞等问题,提出一种基于多元分层感知机制的高效安全区域分割算法。根据节点间数据交换的紧密程度,将网络拓扑分割为网络层、传输层和最终汇聚层,设计多元分层感知模型,增强簇头节点的更新能力。结合机会路由连通特性,设计基于机会碰撞信息提取机制的区域分割子算法,借助拉格朗日模型进行特征挖掘,提升节点机会碰撞度并优化区域分割效果。基于簇内节点关联度,构建能量-路由双因子裁决机制,实现区域信息与簇头节点的数据交互并缓解数据拥塞。实验结果表明,与基于改进移动中继和楔形合并-能量空洞消除的区域分割算法相比,该算法具有更好的网络区域分割效果及更强的数据拥塞控制能力。     

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

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

一种基于几何区域分割的网包分类算法

网包分类算法HyperSplit采用了二分查找树结构进行查找, 其决策树深度较大, 规则复制较多, 无法保证算法的时间性能。针对以上问题, 提出了一种基于几何区域分割的网包分类算法MP^2S。该算法采用多点切分和冗余覆盖删减的方法压缩决策树深度, 引入区间二分查找并提出新的数据结构来优化算法的时间性能。仿真结果表明, MP^2S的平均决策树深度约为HyperSplit的60%, 内存访问次数比HyperSplit降低了约10%。     

基于聚合折叠向量的多维包分类算法*

系统地论述了目前包分类研究的相关领域:分类器的种类、分类算法的评价准则、设计分类算法的原则和现实规则库的特点等.通过对各分类算法和现实规则库的特点进行分析,采用聚合折叠向量法,提出了一种适用于多维大规则库的多域分解查找算法及其硬件实现模型,解决了高性能五维包分类问题.算法采用并行与流水相结合来实现,进一步提高了包分类的性能.     

支持快速增量更新的包分类算法

动态数据包分类是目前新兴网络服务的基础,但现有包分类算法的更新性能不能令人满意。基于递归空间分解和解释器方法,设计和实现了一个支持快速增量更新的两阶段多维包分类算法TICS,利用局部数据结构重建替换方法允许规则集增量更新,并通过适当的内存管理允许查找和更新的并行同步进行。实验表明,算法的更新速度比目前更新最快的BRPS算法至少提升了一个数量级,且内存消耗少,具有良好的并行扩放性。     

A space- and power-efficient multi-match packet classification technique combining TCAMs and SRAMs

Packet classification is implemented in modern network routers for providing differentiated services based on packet header information. Traditional packet classification only reports a single matched rule with the highest priority for an incoming packet and takes an action accordingly. With the emergence of new Internet applications such as network intrusion detection system, all matched rules need to be reported. This multi-match problem is more challenging and is attracting attentions in recent years. Because of the stringent time budget on classification, architectural solutions using ternary content addressable memory (TCAM) are the preferred choice for backbone network routers. However, despite its advantage on search speed, TCAM is much more expensive than SRAM, and is notorious for its extraordinarily high power consumption. These problems limit the application and scalability of TCAM-based solutions. This paper presents a tree-based multi-match packet classification technique combining the benefits of both TCAMs and SRAMs. The experiments show that the proposed solution achieves significantly more savings on both memory space and power consumption on packet matching compared to existing solutions.     

一种多维并行报文分类算法

位并行、位向量和聚合位向量算法通过对多个域进行并行处理加快分类速度,但三者内存占用太大,不适用于大规则集。为此,提出一种压缩位并行算法,通过报文分类压缩每个域上的重复规则并重新组织规则集,从而缩短位图中位串的长度,减少内存空间的占用。实验结果证明,该压缩位并行算法在不影响运行速度的前提下,明显减少了空间占用。     

并行编译中数据分布的线性划分模式计算

由于计算机访问本地存储器的速度远远快于通过网络访问异地计算机存储器的速度，因此，在分布式存储环境中，如何对程序中引用的数据进行合理的分布，从而达到在本地进行计算时只需访问存储在本地的数据（即无通信的数据分布）的目的，已成为提高并行计算速度的关键问题，本文主要讨论如何在数组下标表达式为线性的条件下，对一种种锘于线性代数中超平面概念的数组线性划分技术进行扩充，并给出了完整的数据划式计算算法。     

一种基于范围搜索的并行多维分类算法PRSMC

针对高速网络应用对基于范围查找的分组分类算法的要求以及高性能并行计算环境的特点,提出了一种高速多维分组分类算法——PRSMC(基于范围搜索的并行多维分类)算法。该算法具有较快的搜索速度和较强的并行性,特别适合在多CPU多核高性能计算机上实现。同时提出了算法的双缓冲并行实现技术,使得在软件环境中具有良好空间和时间性能。性能实验表明该算法具有良好的可扩展性,算法速度较同类基于区域划分的算法有较大提升,平均分类速率能达到1Mpkt/s左右。     

基于规则集划分的多决策树报文分类算法

为克服决策树算法处理高速网络、大容量规则集下的报文分类问题时内存使用量大的弊端,提出一种基于规则集划分的多决策树报文分类算法。在保证规则子集数量可控的前提下,采用启发式算法将规则集划分为有限个规则子集,最大限度分离交叠规则;提出两级级联决策树结构,降低决策树深度以减少规则查找时间。理论分析表明,该算法空间复杂度较传统单决策树算法大幅降低。仿真结果表明,该算法的内存使用量比目前空间性能最好的EffiCuts算法减少了30%,且维度可扩展性更好。     

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

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

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

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

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.