包分类算法中规则转换方法研究

对传统包分类算法中的规则形式化进行改进,在研究包分类算法中规则转换方法的基础上,提出一种基于集合运算的非匹配规则转换算法,将该算法与其他范围规则转换算法进行性能比较,分析这些算法的时空复杂度,同时进行仿真。实验结果表明,该算法产生的规则数目小于其他算法。     

Linux下基于Netfilter的包过滤算法

通过对Linux操作系统下Netfilter防火墙中包过滤技术的分析,发现Netfilter包过滤使用简单的线性分级算法,当防火墙需要匹配的规则越来越多时,防火墙的性能会急剧下降,造成系统瓶颈。因此,提出一种基于二叉树和Hash函数的包过滤算法B—H。通过测试证明,该算法在大量规则的情况下能够达到快速匹配,有效地提高了包过滤的性能。     

运用差分演化算法实现多维包匹配的研究

互联网的发展已经使网速的瓶颈由链路速度转移到核心网络设备的包处理速度上,而包处理的核心工作是包匹配。传统方法难以做到包匹配速度适应核心网络设备数据包线速转发。提出了一种新的包匹配算法,该算法对差分演化算法进行了改进,并结合了改进算法和传统的包匹配算法。在适应值处理上运用统计学方法,从而增加了分析问题的客观性。数值实验表明,新算法与传统算法相比,在速度、存储空间以及更新时间等性能上得到了有效改善,另外新算法的包匹配的时间性能与规则数目只有很弱的相关性,从而适合处理多维和大规模问题。新算法把演化算法运用于多域大规模规则库的网络数据包的转发,并且数据包还能做到线速转发。新算法具有普适性,适用于防火墙、差别服务路由器等网络设备。     

基于多层迭代的递归数据流匹配改进算法

递归数据流匹配算法(RFC)是一种高性能包匹配算法.但随着规则库中规则维数的增长以及规模的增加,必将使系统内存消耗殆尽.对RFC进行改进以减少内存消耗,把规则库分成几个子集,每个规则存储在一个独立的子集中.采用多种方法对RFC数据结构进行精简,进一步改善算法的速度和内存性能.实验结果表明,该改进算法大大降低了RFC总体内存消耗,极大提高了包匹配的计算性能.     

运用差分演化算法实现包匹配多层核心基的提取

针对网络防火墙、路由器等设备中包匹配的速度问题,提出运用差分演化算法实现包匹配多层核心基的提取。该算法运用多层基础基描述包的多层特征,在每层中分别运用差分演化算法进行比特基和实体基的提取,运用平均自信息和平均互信息量衡量基础基选择的优劣。这种方法可以根据规则库实际规模选择提取比特实体基的层数,非常适应规则库的增长。实验结果表明,所提算法在时间效率、空间效率方面相对于已有的递归数据流匹配算法和基于实数编码的差分演化的包匹配算法,综合性能最优。     

基于规则的防火墙匹配算法研究

传统防火墙包过滤过程是通过数据包与过滤规则顺序匹配,直到有一条规则匹配后即可停止。当过滤规则日益增多时,防火墙的吞吐量也不断下降,严重影响了网络的性能。该文提出并设计了快速的规则匹配算法,改变了以往的顺序匹配,极大地提高了防火墙的吞吐量和性能。     

一种基于Linux内核的高效包分类算法

针对iptables核心包分类算法的低效问题,提出一种符合Linux内核限制条件并充分利用已有内核机制的高效包分类算法。该算法具备动态更新、多维匹配、实施速度快等主流包分类算法的特点,适合实际应用。实验结果表明在规则库较大的情况下,算法性能有很大提高。     

基于规则集压缩的高效包分类算法

研究发现快速包分类算法EGT-PC由于压缩特里树路径带来规则集的大量冗余备份降低了算法的查找时间和存储空间等性能。根据规则数据库中规则相对聚集的特性,设计出适合该算法的规则集压缩机制,提出新的包分类算法——EGT-SC。实验表明,在查找时间和存储空间上新算法的性能都有明显的提高。     

网络安全系统中的快速规则匹配

随着网络攻击的增多,各类安全系统被广泛应用,其关键和核心是规则匹配.加速规则匹配可以提高系统性能,使其适应更高速网络和更严格环境.介绍和分析了现有的两种主要规则匹配算法:布尔表达式树和有向无环控制流图,提出了一种快速规则匹配算法.该算法先对有向无环控制流图进行等价变换,再在此基础上进行概率优化和改进,通过调整规则内部的逻辑表示结构,使得规则的结构转换速度和计算速度都得到明显的提高.经过测试比较,该算法能有效缩短匹配时间,改善系统性能.     

一种性能优化的防火墙规则匹配算法

设计了一种防火墙规则匹配算法,该算法基于分治思想将规则集按照协议类型分割为多个子集,并根据规则之间的关系,将各子集分为无序组和有序组,通过设计哈希函数和索引算法对两组规则进行分别匹配。分析表明,该算法的效率远优于同类算法,大大提高了防火墙的工作性能。     

基于混合模式匹配算法的网络入侵检测

为了提升中央处理单元(CPU)和图形处理单元(GPU)协同检测网络入侵的性能,本文提出了一种具有数据包有效载荷长度约束的CPU/GPU混合模式匹配算法(LHPMA)。在分析CPU/GPU混合模式匹配算法(HPMA)的基础上,设计了长度约束分离算法(LBSA)对传入数据包进行提前分类。利用CPU中的预过滤缓冲区对较长数据包进行快速预过滤,结合全匹配缓冲区将较短数据包直接分配给GPU进行全模式匹配,通过减少有效载荷长度的多样性,提升了CPU/GPU协同检测网络入侵的性能。实验结果表明,LHPMA增强了HPMA的处理性能,充分发挥了GPU并行处理较短数据包的优势,并且LHPMA提高了网络入侵检测的吞吐量。     

Non-preemptive buffer management for latency sensitive packets

The delivery of latency sensitive packets is a crucial issue in real-time applications of communication networks. Such packets often have a firm deadline and a packet becomes useless if it arrives after its deadline. The deadline, however, applies only to the packet’s journey through the entire network; individual routers along the packet’s route face a more flexible deadline. We study policies for admitting latency sensitive packets at a router. Each packet is tagged with a value. A packet waiting at a router loses value over time as its probability of arriving at its destination on time decreases. The router is modeled as a non-preemptive queue, and its objective is to maximize the total value of the forwarded packets. When a router receives a packet, it must either accept it (and delay future packets), or reject it immediately. The best policy depends on the set of values that a packet can take. We consider three natural sets: an unrestricted model, a real-valued model, where any value over 1 is allowed, and an integral-valued model. For the unrestricted model, we prove that there is no constant competitive ratio algorithm. For the real-valued model, we give a randomized 4-competitive algorithm and a matching lower bound (up to low order terms). We also provide a deterministic lower bound of \(\phi ^3 - {\varepsilon }\approx 4.236\), almost matching the previously known 4.24-competitive algorithm. For the integral-valued model, we describe a deterministic 4-competitive algorithm, and prove that this is tight even for randomized algorithms (up to low order terms).     

Hierarchical multi-pattern matching algorithm for network content inspection

Inspection engines that can inspect network content for application-layer information are urgently required. In-depth packet inspection engines, which search the whole packet payload, can identify the interested packets that contain certain patterns. Network equipment then utilizes the searching results from the inspection engines for application-oriented management. The most important technology for fast packet inspection is an efficient multi-pattern matching algorithm to perform exact string matching between packets and a large set of patterns. This paper proposes a novel hierarchical multi-pattern matching algorithm (HMA) for packet inspection. HMA builds hierarchical index tables from the most frequent common-codes, and efficiently reduces the amount of external memory accesses and memory space by two-tier and cluster-wise matching. Analysis and simulation results reveal that HMA performs much better than state-of-the-art matching algorithms. In particular, HMA can update patterns incrementally, thus creating a reliable network system.     

基于正则表达式的DFA拆分算法研究

深度包检测采用简单的字符串匹配技术将报文内容与一组固定字符串进行匹配,基于正则表达式匹配算法能提供更强的表达能力和灵活性,而复杂的正则表达式结构可能引起DFA的状态数膨胀,导致存储代价巨大;DFA拆分算法将DFA转换表拆分为三个表：间接索引表,转换输出表,直接转换表,实验结果表明DFA所占空间大大减小,实现了DFA的压缩存储。     

一种提供延迟保证的多级FIFS队列包调度算法

包调度算法是提供服务质量保证的一个重要部分.传统的每流区分的包调度方法通常不能支持较好的扩展性,不适应当前网络带宽的迅速增长.而非每流区分的方法又不能提供每流的服务保证.动态包状态(dynamic packet state,简称DPS)方法提供了一种在无须维护每流状态下提供保证服务的方法,该方法在保证服务质量的同时大大提高了扩展性.但是它仍然需要每包的调度,其复杂度和包的数量有关.在DPS的基础上提出了一种用多级FIFS队列提供延迟保证的包调度算法,并给出了该算法实现服务保证的约束条件.理论分析和仿真实验结果都表明:该算法可以实现常数时间的包调度复杂性,同时具有和DPS同样的延迟性能.     

最长前缀匹配查找的索引分离trie树结构及其算法

Internet的飞速发展要求核心路由器每秒能转发几百万个以上的分组,实现高速分组转发的关键是路由表的组织和快速的路由查找算法。索引分离trie树结构建立了具有k比特的一级索引,m比特的二级索引和步宽为s、最大深度为m/s的多分支trie树结构。在这种数据结构中进行最长前缀匹配查找的算法复杂度为:O(m/s+2)。它具有算法简单、查找速度快、易于更新、便于向IPv6过渡等特点,是一种综合性能较好的快速最长前缀匹配查找算法。     

基于RTT自适应的无线TCP改进算法

针对TCP Reno在无线环境下的性能恶化问题,在研究分析TCP Reno拥塞控制算法问题的基础上,提出一种基于RTT自适应的改进算法.该算法实现了丢包区分的拥塞窗口与慢启动门限调整,减轻了传统TCP由于无法区分拥塞丢包与误码丢包、盲目将拥塞窗口减半带来的性能下降.分析了该算法的可行性,并通过NS仿真对其吞吐量、带宽利用率、公平性等指标进行评估.仿真结果表明,相对TCP Reno,改进算法实现了无线环境下的TCP性能改善,同时具有一定的友好性与公平性.     

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

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

Port partitioning and dynamic queueing for IP forwarding

With the increase of internet protocol (IP) packets the performance of routers became an important issue in internet/working. In this paper we examine the matching algorithm in gigabit router which has input queue with virtual output queueing. Dynamic queue scheduling is also proposed to reduce the packet delay and packet loss probability. Port partitioning is employed to reduce the computational burden of the scheduler in a switch which matches the input and output ports for fast packet switching. Each port is divided into two groups such that the matching algorithm is implemented within each pair of groups in parallel. The matching is performed by exchanging the pair of groups at every time slot. Two algorithms, maximal weight matching by port partitioning (MPP) and modified maximal weight matching by port partitioning (MMPP) are presented. In dynamic queue scheduling, a popup decision rule for each delay critical packet is made to reduce both the delay of the delay critical packet and the loss probability of loss critical packet. Computational results show that MMPP has the lowest delay and requires the least buffer size. The throughput is illustrated to be linear to the packet arrival rate, which can be achieved under highly efficient matching algorithm. The dynamic queue scheduling is illustrated to be highly effective when the occupancy of the input buffer is relatively high.Scope and purposeTo cope with the increasing internet traffic, it is necessary to improve the performance of routers. To accelerate the switching from input ports to output in the router partitioning of ports and dynamic queueing are proposed. Input and output ports are partitioned into two groups A/B and a/b, respectively. The matching for the packet switching is performed between group pairs (A, a) and (B, b) in parallel at one time slot and (A, b) and (B, a) at the next time slot. Dynamic queueing is proposed at each input port to reduce the packet delay and packet loss probability by employing the popup decision rule and applying it to each delay critical packet.The partitioning of ports is illustrated to be highly effective in view of delay, required buffer size and throughput. The dynamic queueing also demonstrates good performance when the traffic volume is high.