General memory efficient packet matching FPGA architecture for future high-speed networks

Packet classification (matching) is one of the critical operations in networking widely used in many different devices and tasks ranging from switching or routing to a variety of monitoring and security applications like firewall or IDS. To satisfy the ever-growing performance demands of current and future high-speed networks, specially designed hardware accelerated architectures implementing packet classification are necessary. These demands are now growing to such an extent, that in order to keep up with the rising throughputs of network links, the FPGA accelerated architectures are required to perform matching of multiple packets in every single clock cycle. To meet this requirement a simple replication approach can be utilized – instantiate multiple copies of a processing pipeline matching incoming packets in parallel. However, simple replication of pipelines inseparably brings a significant increase in utilization of FPGA resources of all types, which is especially costly for rather scarce on-chip memories used in matching tables.We propose and examine a unique parallel hardware architecture for hash-based exact match classification of multiple packets in each clock cycle that offers a reduction of memory replication requirements. The core idea of the proposed architecture is to exploit the basic memory organization structure present in all modern FPGAs, where hundreds of individual block or distributed memory tiles are available and can be accessed (addressed) independently. This way, we are able to maintain a rather high throughput of matching multiple packets per clock cycle even without fully replicated memory resources in matching tables. Our results show that the designed approach can use on-chip memory resources very efficiently and even scales exceptionally well with increased capacities of match tables. For example, the proposed architecture is able to achieve a throughput of more than 2 Tbps (over 3 000 Mpps) with an effective capacity of more than 40 000 IPv4 flow records at the cost of only a few hundred block memory tiles (366 BlockRAM for Xilinx or 672 M20K for Intel FPGAs) utilizing only a small fraction of available logic resources (around 68 000 LUTs for Xilinx or 95 000 ALMs for Intel).     

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.     

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.     

一种基于自适应缓存机制的报文分类算法

提出了一种高效、适用性好、易于实现的报文分类算法CSAC（classification on self-adaptive cache）．该算法通过缓存属性子空间内报文集合的分类查询路径,将查询结果复用于同一子空间后续报文的分类．而缓存命中失效时也不必从头开始查询,减少了失效的时间开销．根据通信流量上下文变化对缓存运行状态造成的影响,算法采用自适应缓存机制,通过动态调整缓存的粒度、结构和缓存项在散列桶中的位置,有效地保证了缓存命中率．此外,算法不需要预处理过程,支持多维复杂规则（如4～7层属性、逻辑匹配操作等）和规则增量更新,比较适合于网络边界安全、用户流量审计和负载均衡等报文分类比较复杂的应用．采用CSAC算法开发的高端防火墙和入侵检测设备在实际网络环境中的性能良好．     

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

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

基于网络内容的无阻塞近似流分类的并行建模

针对大字符集语言的特点,提出一种并行硬件模型实现基于网络内容的近似流分类.由于采用并行设计和流水线设计,该模型在大规则库下仍有较好的性能,并可适用于高速网络.该并行模型有如下特点:①通过采用不同的规则组合器可完成插入、删除、替代和交换错误的近似匹配;②通过配置参数,可灵活控制近似匹配的程度;③可直接应用于大字符集语言下的网络内容流分类;④针对中文环境做了概率建模,分析了并行硬件模型对网络分组的匹配概率,证明该模型在一般情况下具有较好的可应用性.     

Line segment matching for 3D computer vision using a new iteration scheme

A new iteration scheme is proposed to solve the line segment matching problem in stereo vision analysis. A match function which directly reflects the requirements of the epipolar and disparity constraints is proposed for line segment matching. The information contained in the match function is used to determine line segment correspondences indirectly. After a match network is established according to the match function values, a new iteration algorithm is employed to tune the strengths of the match links in the match network so that the match network can converge to a stable state. No explicit compatibility coefficient need be defined for computing the support function values in the iterations, resulting in a faster computation speed than those of conventional relaxation matching techniques. The inherent anti-symmetric characteristic of relaxation matching for the image correspondence problem is also avoided naturally. The experimental results show that the proposed iteration scheme is effective and suitable for matching line segments even when images are complicated.     

基于短前缀长度分割的高速二维分组分类算法

分组分类是路由器根据IP分组的多个域，从分类器数据库中匹配每个输入分组，确定分组转发规则的技术，分类器为实现因特网新业务提供了统一的方式，这些新业务包括：防火墙，网络地址翻译等，二维分组分类问题在未来的因特网体系结构中占有十分重要的地位，目前，人们已经提出了几种分组分类算法，但没有一种是理想的，提出基于短前缀长度分割的二维分组分类算法，它使用短前缀长度分割（SPLS）技术对分类器集合进行分割，使得分割后的小分类器子集合可以使用巳有快速IP路由查找方法进行查找，实现时以多叉树作为基本数据结构，实验显示它具有存储需求小，平均查询时间快，更新时间快，适合于大的分类器等特点，是一种较好的二维分组分类算法。     

Ant Colony Optimization based approach for efficient packet filtering in firewall

A firewall is a security guard placed at the point of entry between a private network and the outside network. The function of a firewall is to accept or discard the incoming packets passing through it based on the rules in a ruleset. Approaches employing Neural networks for packet filtering in firewall and packet classification using 2D filters have been proposed in the literature. These approaches suffer from the drawbacks of acceptance of packets from the IP address or ports not specified in the firewall rule set and a restricted search in the face of multiple occurrences of the same IP address or ports respectively. In this paper we propose an Ant Colony Optimization (ACO) based approach for packet filtering in the firewall rule set. Termed Ant Colony Optimization Packet Filtering algorithm (ACO-PF), the scheme unlike its predecessors, considers all multiple occurrences of the same IP address or ports in the firewall rule set during its search process. The other parameters of the rule matching with the compared IP address or ports in the firewall ruleset are retrieved and the firewall decides whether the packet has to be accepted or rejected. Also this scheme has a search space lesser than that of binary search in a worst case scenario. It also strictly filters the packets according to the filter rules in the firewall rule set. It is shown that ACO-PF performs well when compared to other existing packet filtering methods. Experimental results comparing the performance of the ACO-PF scheme with the binary search scheme, sequential search scheme and neural network based approaches are presented.     

Towards adaptive character frequency-based exclusive signature matching scheme and its applications in distributed intrusion detection

Network intrusion detection systems (NIDSs), especially signature-based NIDSs, are being widely deployed in a distributed network environment with the purpose of defending against a variety of network attacks. However, signature matching is a key limiting factor to limit and lower the performance of a signature-based NIDS in a large-scale network environment, in which the cost is at least linear to the size of an input string. The overhead network packets can greatly reduce the effectiveness of such detection systems and heavily consume computer resources. To mitigate this issue, a more efficient signature matching algorithm is desirable. In this paper, we therefore develop an adaptive character frequency-based exclusive signature matching scheme (named ACF-EX) that can improve the process of signature matching for a signature-based NIDS. In the experiment, we implemented the ACF-EX scheme in a distributed network environment, evaluated it by comparing with the performance of Snort. In addition, we further apply this scheme to constructing a packet filter that can filter out network packets by conducting exclusive signature matching for a signature-based NIDS, which can avoid implementation issues and improve the flexibility of the scheme. The experimental results demonstrate that, in the distributed network environment, the proposed ACF-EX scheme can positively reduce the time consumption of signature matching and that our scheme is promising in constructing a packet filter to reduce the burden of a signature-based NIDS.     

A platform-based SoC design and implementation of scalable automaton matching for deep packet inspection

String matching plays a central role in packet inspection applications such as intrusion detection, anti-virus, anti-spam and Web filtering. Since they are computation and memory intensive, software matching algorithms are insufficient to meet the high-speed performance. Thus, offloading packet inspection to a dedicated hardware seems inevitable. This paper presents a scalable automaton matching (SAM) coprocessor that uses Aho-Corasick (AC) algorithm with two parallel acceleration techniques, root-indexing and pre-hashing. The root-indexing can match multiple bytes in one single matching, and the pre-hashing can be used to avoid bitmap AC matching which is a cycle-consuming operation. In the platform-based SoC implementation of the Xilinx ML310 FPGA, the proposed hardware architecture can achieve almost 10.7 Gbps and support over 10,000 patterns for virus, which is the largest pattern set from among the existing works. On the average, the performance of SAM is 7.65 times faster than the original bitmap AC. Furthermore, SAM is feasible for either internal or external memory architecture. The internal memory architecture provides high performance, while the external memory architecture provides high scalability in term of the number of patterns.     

Two stage packet classification using most specific filter matching and transport level sharing

In this paper we introduce two new concepts to the design of packet classification systems. First, we propose most specific filter matching (MSFM), an improvement over the well known Cross Producting algorithm [V. Srinivasan, S. Suri, G. Varghese, M. Waldvogel, Fast and scalable layer four switching, in: Proceedings of ACM SIGCOMM, 1998] that significantly reduces the memory requirement of the earlier scheme. Second, we suggest that rules specifying the same source–destination IP prefix pair can be grouped together forming shared sets of transport level fields. This property of Transport Level Sharing (TLS), which characterizes real world classification databases is exploited for reducing a classifier’s memory requirement and for hardware acceleration.We split the classification process into two stages. First, we perform classification on source–destination IP prefix pairs using the MSFM algorithm. Second, we perform classification on transport level fields exploiting transport level sharing. It is the combination of most specific filter matching and transport level sharing which results in a scheme that requires no more than 11 dependent memory accesses in the critical path independent of the size of the classification database. The memory access bandwidth of our scheme is also bounded when our scheme is accelerated in hardware. Compared to other schemes which involve a small and predictable number of steps in the critical path (e.g., Cross Producting [V. Srinivasan, S. Suri, G. Varghese, M. Waldvogel, Fast and scalable layer four switching, in: Proceedings of ACM SIGCOMM, 1998] or Recursive Flow Classification [P. Gupta, N. McKeown, Packet classification on multiple fields, in: Proceedings of ACM SIGCOMM, 1999]) the combination of most specific filter matching and transport level sharing is associated with the least memory requirement.     

Joint source coding and packet classification for real-time video transmission over differentiated services networks

Differentiated Services (DiffServ) is one of the leading architectures for providing quality of service in the Internet. We propose a scheme for real-time video transmission over a DiffServ network that jointly considers video source coding, packet classification, and error concealment within a framework of cost-distortion optimization. The selections of encoding parameters and packet classification are both used to manage end-to-end delay variations and packet losses within the network. We present two dual formulations of the proposed scheme: the minimum distortion problem, in which the objective is to minimize the end-to-end distortion subject to cost and delay constraints, and the minimum cost problem, which minimizes the total cost subject to end-to-end distortion and delay constraints. A solution to these problems using Lagrangian relaxation and dynamic programming is given. Simulation results demonstrate the advantage of jointly adapting the source coding and packet classification in DiffServ networks.     

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

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

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

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

HAL: a faster match algorithm

Existing match algorithms treat the matching process like the querying process of relational databases. Owing to the combinatorial nature of the matching process, the match time greatly varies in different recognize-act cycles. Current match algorithms utilize local matching support networks with redundant working memory elements shared among rules involving the same classes. Since the match time is a dominant factor in the total execution time of a production system, such large match time makes production systems with existing match algorithms unsuitable for many applications. To reduce match time, we introduce the Heuristically-Annotated-Linkage (HAL) match algorithm. HAL differs from traditional match algorithms in that HAL employs a fixed-traversal-distance pseudobipartite network approach of treating rules and classes as objects, or nodes, in only one global pseudobipartite-graph-like connection and communication scheme. In addition, HAL is more efficient than other existing match algorithms because it is capable of immediate characterization of any new datum upon arrival. This paper reviews existing match algorithms, presents HAL, and analyzes the performance of HAL in comparison with existing algorithms.     

Multi-core implementation of decomposition-based packet classification algorithms

Multi-field packet classification is a network kernel function where packets are classified based on a set of predefined rules. Decomposition-based classification approaches are of major interest to the research community because of the parallel search in each packet header field. This paper presents four decomposition-based approaches on multi-core processors. We search in parallel for all the fields using linear search or range-tree search; we store the partial results in a linked list or a bit vector. The partial results are merged to produce the final packet header match. We evaluate the performance with respect to latency and throughput varying the rule set size (1–64 K). Experimental results show that our approaches can achieve 128 ns latency per packet and 11.5 Gbps throughput on state-of-the-art 16-core platforms.     

认知无线电频谱切换的高效信道选择机制

针对认知无线电系统中,频谱切换效率低这个难点,采用分组匹配的思想,基于业务类型对用户进行分组,将用户分组与一种全面可靠的信道评估机制匹配。这种先分组后分配信道的切换算法能有效提高多个用户的复杂场景中频谱切换的效率。仿真结果表明,该算法能够减少认知用户拥塞概率、频谱切换次数以及切换延迟,提高频谱切换效率,有效保证系统服务质量。     

一种优化入侵检测系统的方案

基于特征的入侵检测系统是目前的入侵检测技术的主流。文中提出了一种针对每一个网络报文,即时的创建一个单一的特征集合来进行匹配的方案,从而减少了匹配的工作量,提高了系统的效率。     

层压缩树包分类算法研究

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