基于三态位分割的低功耗TCAM报文分类算法

针对传统基于TCAM的报文分类算法存在功耗较大的问题, 提出了一种基于三态位分割的低功耗TCAM报文分类算法——TSP-PR(tri-state-based partition for power reduction)。利用TCAM支持三态位的特点, 设计标志位选取函数动态选取标志位划分规则集, 报文查找时只选取与待匹配报文相关的子集参与比较, 减少了参与匹配的表项数目, 从而达到了降低功耗的目的。实验表明, 相对于传统基于TCAM的报文分类算法, TSP-PR算法在付出较小存储代价的情况下功耗减少了60%以上。     

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

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

基于Bloom Filter的报文分类算法

针对传统报文分类算法在实际运行中存在的问题,提出一种基于Bloom Filter的报文分类算法。将该算法的思想应用于入侵防护系统硬件模型,建立相应的流信息预处理引擎,并介绍具体的实现方法。实验结果表明,该算法是有效实用的。     

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

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

IP报文分类算法概述

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

报文分类算法研究

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

基于FPGA实现的报文分类智能网卡

一般的网络安全应用软件,只对网络中的某类报文进行处理,基于通用的网卡采集网络数据,会收到大量的无用报文,降低系统效率。本文基于FPGA和零拷贝技术,设计并实现了一种智能网卡,将报文分类过滤工作下移到网卡硬件中实现,智能网卡完成了网络数据包报文捕获、报文分析、规则匹配等工作,可以过滤掉无用报文,只把应用关心的报文提交给到主机系统。与普通网卡相比,智能网卡可以有效提升网络数据采集的效率。     

基于分类规则信息熵的报文处理算法

针对分类规则的预处理问题,提出离群属性检测分类算法。在报文分类规则属性域上计算离群属性子集,利用规则属性加权矢量计算加权距离,分析规则加权邻域的子空间离群影响因子,通过与离群因子阈值比较生成频繁匹配子集对规则进行预处理。实验结果表明,该算法能缩小后续报文的匹配范围,提高报文转发的匹配精度与速度。     

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

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

可扩展报文分类算法研究与评测

针对报文分类算法的可扩展性,深入分析了典型可扩展报文分类算法的时间、空间复杂度;基于ClassBench工具集开发出可扩展报文分类算法评测系统,利用该系统对典型算法在不同模拟场景下进行评测,并对各算法的性能差异和适用条件进行了系统分析。最后,对今后可扩展报文分类算法的发展趋势作出了展望。     

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

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

DAFT:一种OpenFlow大规模流表区分存储与加速查找架构

软件定义网络作为一种数据转发与逻辑控制相解耦的创新网络范式,当采用OpenFlow协议进行大规模部署时,其数据平面的流表规模急剧增大,对OpenFlow交换机的流表存储资源和分组转发性能提出了严峻的挑战.对此,本文构建了一种OpenFlow大规模流表区分存储与加速查找架构DAFT.该架构根据流量分布特性将OpenFlow网络流区分为重要流和次要流,进而采用TCAM和SRAM分别存储其标识字段,并采用DRAM单独存储其内容字段,有效缓解OpenFlow流表存储资源紧张问题.针对重要流/次要流区分问题,在分析传统大象流/老鼠流区分方法的基础上,基于OpenFlow网络流的包成批特性,提出活跃流/空闲流区分方法,以提高TCAM命中率.针对SRAM流表查找性能瓶颈,利用掩码访问不均匀的特点,采用"往前移1"启发法自适应调整掩码顺序,以减少后续数据包的掩码失败探测次数;利用掩码探测多数会失败的特点,借助计数型布鲁姆过滤器预测元组查找失败结果,从而绕过对应的子流表遍历过程.最后,借助骨干网络流量样本,对本文所提DAFT流表架构的查找性能进行实验评估.实验结果表明:DAFT流表架构的TCAM命中率、SRAM平均查找长度和平均流表访问时间均明显优于传统的大象流/老鼠流架构,且稳定性强,有效提升了OpenFlow交换机的分组转发性能.     

基于OpenFlow的软件定义网络虚拟化方案

软件定义网络(SDN)可以将网络控制平面与数据平面分离开来,为网络虚拟化提供了良好的平台。为了解决SDN中多租户下的虚拟化,提出了一种基于OpenFlow的网络虚拟化方案。通过一个中间代理来转换并匹配物理MAC地址与虚拟MAC地址,以及物理流表项和虚拟流表项,以此实现流量空间的虚拟化。其中,根据实际数据包的惰性计算,使用前缀或通配符来精确匹配流表项。另外,为了保障物理OpenFlow网络上不同租户之间的隔离,将单个虚拟MAC-通配符流表项映射为多个具有精确MAC地址的物理流表项。实验结果表明,该方案成功的实现了网络虚拟化,且虚拟化开销较小,具有可行性。     

基于匹配动作表模型的可编程数据平面流表归并

与传统网络技术相比,SDN技术将网络的控制平面与数据平面分离,使网络具有一定的可编程能力。以OpenFlow、POF、P4等为代表,领域内常见的SDN交换机大多基于匹配动作表模型实现。与协议相关的OpenFlow等技术不同,协议无感知的SDN技术使用{偏移,长度}等结构表示协议字段,从而实现对任意协议字段的解析和处理。然而,待处理的数据包可能带有不同长度的数据包头,所以这些数据包中特定协议字段的偏移也会不同,需要多个匹配域偏移不同的流表去完成数据流的解析,从而造成流表和流水线结构复杂。针对上述问题,本文提出一种基于MAT模型的可编程数据平面流表归并方案,扩展MAT模型中的动作集,在数据包查询流表时使用特定的动作动态地调整数据包的起始偏移,使不同数据包同一协议字段的偏移保持一致,实现匹配域相同的流表的归并。本文方案在兼容VLAN、QinQ的POF Switch实验场景下,以跳转流表时多执行一条动作为代价,缩减了约69%的流表内存消耗。     

OpenFlow网络数据流路径建立开销的量化分析

OpenFlow采用数据平面与控制平面分离的架构,以软件实现的OpenFlow控制器作为控制平面对网络进行集中控制。在这种分离架构中,由于交换机需要与控制器进行交互,因此必然会产生一定的时间开销。经实验,数据流建立过程中的信息交互导致数据包传输时延至少增长2倍,严重降低了网络性能。因此,量化分析OpenFlow网络中流建立开销具有重要意义。分析流建立开销产生的原因,对导致数据包传输时延增长的影响因素进行量化分析。 评估流建立开销对网络性能的影响是量化分析数据流路径建立开销的重点。     

基于软件定义网络的网络故障诊断方法研究

基于软件定义网络环境下故障诊断方法的研究现状,提出了一种在软件定义网络下故障诊断定位的方法。通过发送具有匹配识别标志字段的TCP测试数据分组,利用软件定义网络环境下控制器的可编程和流表可扩展匹配的特性,设计匹配流表和指令,匹配并按特定格式写入具备定位作用的转发信息到测试数据分组。监听分析模块根据返回数据分组中的历史转发信息,提取数据并据此诊断和定位网络故障。在模拟环境下,实验结果证明了该方法的有效性,具备一定的应用价值。     

一种基于优先级的分组丢弃算法PRED

针对实时业务如语音，分析了现有的Internet的缓冲管理算法——Drop Tail算法的缺陷，提出了一种基于优先级的分组丢弃算法——PRED算法。PRED算法体现了分组的相对优先级，并能自适应地对分组的服务级别进行平滑地升级或降级，因而很适于作为DiffServ网络中的分组丢弃算法。仿真结果证明了理论分析的正确性。     

SDN数据安全处理机制关键模块的研究与实现

针对软件定义网络（SDN）的数据平面数据泄露问题、提出一种新的基于OpenFlow协议的数据安全处理机制。首先,重构OpenFlow协议的流表结构,设计实现包括安全匹配字段、安全动作在内的OpenFlow数据安全策略;然后,设计中心化管理控制器,通过开发的多个功能模块使控制器及时感知网络变化,有效管控全局网络,维护和下发数据加（解）密密钥、数据安全策略;其次,深度重构开放虚拟交换机OVS架构,设计实现数据安全策略匹配和数据安全处理的完整流程,编写数据净载信息提取接口,通过开发的多个功能模块使OVS能够根据数据安全策略细粒度匹配数据包,并对匹配成功的数据包进行完整数据安全处理操作;最后,搭建软硬件平台,对该机制的加解密处理结果和延时、吞吐量以及CPU使用率进行测试。实验结果表明：该机制可以准确对数据进行加解密操作,延时和吞吐量均处于正常水平;但CPU使用率在45%~60%浮动,开销较大,有待后续优化。     

High-speed packet classification for differentiated services in next-generation networks

In next-generation networks, packet classification is important in fulfilling the requirements of multimedia services, including VoIP and VoD. Using pre-defined filters, the incoming packets can be categorized that determines to which forwarding class a packet belongs. Packet classification is essentially a problem of multidimensional range matching. The tuple space search is a well-known solution based on multiple hash accesses for various filter length combinations. The tuple-based algorithm, a rectangle search, is highly scalable with respect to the number of filters; however, it suffers from the memory-explosion problem. Besides, the lookup performance of the rectangle search is not sufficiently fast to accomplish high-speed packet classification. This work proposes an improved scheme to reduce the required storage and realize OC-192 wire-speed forwarding. The scheme consists of two parts. The "Tuple Reduction Algorithm" drastically reduces the number of tuples by duplicating filters. Dynamic programming is used to optimize the tuple reduction and two heuristic approaches are introduced to simplify the optimization process. Furthermore, the "Look-ahead Caching" scheme is presented to improve the lookup performance. The basic idea is to prevent unnecessary tuple probing by filtering out the "un-matched" situation of the incoming packet. The experimental results show that combining the tuple reduction algorithm with look-ahead caching increases the lookup speed by a factor of six while requiring only around one third of the storage. Additionally, an extension of multiple fields to more general filters is addressed.     

A parallel computing approach to genetic sequence comparison: the master-worker paradigm with interworker communication

We have implemented a parallel version of a dynamic programming biological sequence comparison algorithm to study the potential applicability of using parallel computers for genetic sequence comparisons. Our parallel program is built using C-Linda, a machine-independent parallel programming language, and was tested on both a 10 CPU Sequent Symmetry and a 64 CPU Intel Hypercube. C-Linda implements a shared associative memory model, "tuple space," through which multiple processes can communicate and coordinate control. In our master-worker (MW) parallel implementation, a master process creates several worker processes, extracts a test sequence and multiple library sequences from a database and stores them in tuple space. Each worker reads the test sequence and then repeatedly extracts library strings from tuple space, performs pairwise sequence comparison using a local comparison algorithm to generate a similarity score, and returns the similarity scores to tuple space. The master collects the scores from tuple space and identifies the best match over all library sequences. We also implemented a method of global interworker communication to reduce the total search time by stopping those string comparisons that had no chance of improving on the current best match. Comparisons of the total run time, speedup, and efficiency were made for parallel and sequential versions of a basic MW implementation as well as versions with the global abort threshold.