高性能无冲突分组查找分类算法的研究

随着因特网的迅猛发展,信息安全、网络安全已经成为人们日益关注的焦点。本文提出了一种面向网络服务监控网关的基于用户的无冲突分组的报文分类算法。该算法是一种基于无冲突哈希和分组查找的多维查找算法,是在无冲突散列查找算法、Lakshman和Stiliadis提出的二维分类算法和iptables分类架构的基础上提出的,但该算法的平均空间性能和时间性能均优于无冲突散列查找算法和iptables分类算法。     

基于二分搜索Trie的IPv4/IPv6路由快速查找算法

提出了一种独特的基于前缀长度二分搜索Trie的IP路由查找算法,融合了基于前缀长度的二分查找算法和基于Trie的查找算法的优点,采用部分IP地址作为索引,避免了使用Hash函数,提高了路由查找速度和表项更新速度;支持路由表的动态更新;算法扩展性好,可满足IPV4和IPV6两种协议栈的OC-48(25Gbps)、OC-192(10Gbps)接口的线速路由查找。     

散列索引多分支Trie树快速路由查找算法

路由器的主要任务是转发IP分组,实现高速分组转发的关键是快速的路由查找算法。我们针对IPv4地址,首先建立前缀长度为8、16和24的3张hash表,在此基础上,再分别针对不同长度的前缀建立最多只涉及其余8比特的多分支Trie树。在这种结构中进行IP路由查找,其存储器访问次数最多为7次,而且还具有易于更新、易于扩展等特点。     

一种支持实时增量更新的并行包分类算法

UTM(unified threat management)技术的提出和应用要求多维包分类算法能够支持实时的增量更新.但由于以往的研究都侧重于加快算法的查找速度,这一需求已经成了目前包分类算法在实际应用中的一个瓶颈.提出一种二维trie树结构来组织分类规则,并给出了相应的查找及更新算法.利用trie结构的特性将各种长度的前缀组合进行分组,并依此将整个规则集分成多个子集.查找时将每一次查找过程分解成若干个可以独立运行的子任务,每个子任务处理一个子集.两级混合trie结构保持了规则之间的独立性,因此可以快速地对单条规则进行增量删除或添加.实验结果表明,本算法在保持高速查找的基础上,将单条规则的增量更新操作速度提高到了和单次查找操作同样的量级,同时并行查找使得算法对规则类型和规模的敏感度大大降低,具有较好的可扩展性.     

众核网络处理器下高速包转发系统设计与实现

互联网的快速发展要求网络设备能够支持每秒几百万以上分组的转发能力,实现这一功能的关键是路由表的组织结构、快速的路由查找算法和高性能的硬件平台支持。设计并实现基于众核网络处理器的高速IP包转发系统,使用Tile-Gx36众核网络处理器作为硬件平台,采用基于Hash的前缀长度和多分支Trie树的路由查找算法,借鉴基于Hash的前缀长度路由表查找算法在存储和检索上的优势,并结合基于多分支Trie树路由表查找算法的查询效率,将路由表存储于L2层缓存中,进一步提高了路由表的访问速度和查询命中率。实验结果表明,对于不同大小负载的数据包系统均能满足40 Gbps的转发速度。     

一种新的快速报文分类算法——RC-FST*

RC-FST 算法利用IP 地址高8 比特前缀建立Hash 压缩索引表, 将分类规则集分成多个子集, 并针对每个子集建立快速搜索树, 而这些规模相对小的本地搜索树更利于实现快速建立、查找和优化。为提高搜索树性能, 在规则分割等问题上也提出了独到的解决方法。该算法查找速度快( 50Mbps) , 支持分类规则数据库大(105) , 可扩展性好, 适于硬件流水线方式实现, 具有很高的实用价值。     

基于LSOT的高速IP路由查找算法

由于因特网速度不断提高、网络流量不断增加、路由表规模不断扩大，IP路由查找已经成为制约路由器性能的重要原因，因而受到广泛重视。目前人们已经提出几种算法用于解决IP路由查找问题，但均不能完全满足核心路由器的要求。该文提出一种基于LSOT的IP路由查找方法，它使用可变大小段表和偏移量表，能适应SRAM和FPGA芯片内存储器容量的变化，具有查找速度高、更新时间快、存储代价低、易于实现等特点，使用FPGA设计能满足10Gbps端口速率核心路由器环境的要求，使用ASIC设计能满足40Gbps端口速率核心路由器环境的要求。     

一种高效的网络安全设备IP数据包转发机制

通过对IP数据包转发机制研究,针对网络安全设备对数据包转发的特殊需求,提出了一种基于(IFPLUT TCAM)的IP数据包转发机制。该机制将查找表根据输出端口分割为若干个小查找表,并允许查找引擎对每个小查找表进行并行处理,有效地将寻找“最长前缀匹配”的复杂问题简化为“第一前缀匹配”问题。     

一种前缀长度二分查找的改进算法

在研究路由表地址前缀分布特点的基础上，提出了前缀长度二分查找方案。该方案采用前缀扩展技术，将前缀数量相对稀少的若干种前缀合并成一种，降低了查找树的高度，减少了存储器访问次数，提高了查找速度，分析了一种实用的Marker存储算法，探讨了IPv6的路由查找问题。     

基于多处理机结构的IP路由搜索技术

随着因特网的飞速发展以及128位地址的IPV6的出现,路由表变得日益庞大,这给IP目标地址的查找速度提出了更高的要求。IP地址查询使用的不是精确匹配,而是最长前缀匹配,因查询极其复杂。论文针对现有的IP查询技术的缺点和不足,提出了一种基于多处理器结构的搜索技术,这种技术减少了查找的比较次数和存储空间。     

A longest prefix first search tree for IP lookup

The IP lookup mechanism is a key issue, in the design of IP routers. IP lookup is an important action in a router, which finds the next hop of each incoming packet with a longest-prefix-match address in the routing table. This work places the routing table on a longest prefix first search tree, which is constructed as a heap-like structure by the prefix length. A router using this scheme has fewer memory accesses when executing IP lookup than a router designed according to the Trie [E. Fredkin, Trie Memory, Communication of the ACM 3 (1960) 490–500], Patricia [K. Sklower, A tree-based routing table for Berkeley Unix, in: Proceedings of the USENIX Conference, 1991, pp. 93–99] or Prefix tree [M. Berger, IP lookup with low memory requirement and fast update, in: Proceedings of IEEE High Performance Switching and Routing, 2003, pp. 287–291]. Some nodes of the proposed tree can include two entries of the routing table to decrease the number of tree nodes. For instance, a routing table with 163,695 entries can be held in the proposed tree with 156,191 nodes. Furthermore, an improved scheme is presented to partition a tree into several smaller trees. The simulation reveals that the scheme not only lowers the tree height effectively but also scales well to IPv6 addresses.     

IP报文分类算法概述

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

DMP-tree: A dynamic M-way prefix tree data structure for strings matching

We propose DMP-tree, a dynamic M-way prefix tree, data structure for the string matching problem in general and prefix matching in particular. DMP-tree has been initially devised for fast and efficiently handling prefix matching which constitutes the building block of some applications in the computer realm and related area. It is assumed there are strings of an alphabet Σ which are ordered. The data strings can have different lengths and some of them can be prefixes of others. Two well known applications of prefix matching are layers 3 and 4 switching in TCP/IP protocols. In layer 3 switching, routers forward an IP packet by checking its destination address and finding the longest matching prefix from a database. In layer 4 switching, the source and destination addresses are used to classify packets for differentiated service and Quality of Services (QoS). DMP-tree is a superset of B-tree. When none of the data strings are a prefix of each other, DMP-tree is the same as B-tree. In DMP-tree, no data string can be in a higher level than another data string which is its prefix. This requires a special procedure for node splitting. Indeed, node splitting differentiates DMP-tree from B-tree. The proposed data structure is simple, well defined, easy to implement in hardware or software and efficient in terms of memory usages and search time compared to other data structures proposed for prefix matching. We have implemented DMP-tree and the experimental results for simulated IP prefixes from the {0, 1} character set show an average search time of for a large number of N, number of data elements, when the internal node branching factor M is big enough (?5).     

Online NetFPGA decision tree statistical traffic classifier

Classifying online network traffic is becoming critical in network management and security. Recently, new classification methods based on analysis of statistical features of transport layer traffic have been proposed. While these new methods address the limitations of the port based and payload based traffic classification, the current software-based solutions are not fast enough to deal with the traffic of today’s high-speed networks. In this paper, we propose an online statistical traffic classifier using the C4.5 machine learning algorithm running on the NetFPGA platform. Our NetFPGA classifier is constructed by adding three main modules to the NetFPGA reference switch design; a Netflow module, a feature extractor module, and a C4.5 search tree classifier. The proposed classifier is able to classify the input traffics at the maximum line speed of the NetFPGA platform, i.e. 8 Gbps without any packet loss. Our method is based on the statistical features of the first few packets of a flow. The flow is classified just a few micro seconds after receiving the desired number of packets.     

建立高效的网络安全设备IP数据包转发机制

因为网络安全设备对数据包转发的特殊需求，需要比一般设备更高效稳定的数据包转发机制。通过对IP数据包转发机制研究，针对特殊需求，提出了一种基于（IFPLUT＋TCAM）的IP数据包转发机制。该机制将查找表根据输出端口分割为若干个小查找表，并允许查找引擎对每个小查找表进行并行处理，有效地将寻找“最长前缀匹配”的复杂问题简化为“第1前缀匹配”问题。     

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

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

An efficient IP address lookup algorithm based on a small balanced tree using entry reduction

Due to a tremendous increase in internet traffic, backbone routers must have the capability to forward massive incoming packets at several gigabits per second. IP address lookup is one of the most challenging tasks for high-speed packet forwarding. Some high-end routers have been implemented with hardware parallelism using ternary content addressable memory (TCAM). However, TCAM is much more expensive in terms of circuit complexity as well as power consumption. Therefore, efficient algorithmic solutions are essentially required to be implemented using network processors as low cost solutions.Among the state-of-the-art algorithms for IP address lookup, a binary search based on a balanced tree is effective in providing a low-cost solution. In order to construct a balanced search tree, the prefixes with the nesting relationship should be converted into completely disjointed prefixes. A leaf-pushing technique is very useful to eliminate the nesting relationship among prefixes [V. Srinivasan, G. Varghese, Fast address lookups using controlled prefix expansion, ACM Transactions on Computer Systems 17 (1) (1999) 1-40]. However, it creates duplicate prefixes, thus expanding the search tree.This paper proposes an efficient IP address lookup algorithm based on a small balanced tree using entry reduction. The leaf-pushing technique is used for creating the completely disjointed entries. In the leaf-pushed prefixes, there are numerous pairs of adjacent prefixes with similarities in prefix strings and output ports. The number of entries can be significantly reduced by the use of a new entry reduction method which merges pairs with these similar prefixes. After sorting the reduced disjointed entries, a small balanced tree is constructed with a very small node size. Based on this small balanced tree, a native binary search can be effectively used in address lookup issue. In addition, we propose a new multi-way search algorithm to improve a binary search for IPv4 address lookup. As a result, the proposed algorithms offer excellent lookup performance along with reduced memory requirements. Besides, these provide good scalability for large amounts of routing data and for the address migration toward IPv6. Using both various IPv4 and IPv6 routing data, the performance evaluation results demonstrate that the proposed algorithms have better performance in terms of lookup speed, memory requirement and scalability for the growth of entries and IPv6, as compared with other algorithms based on a binary search.     

路由查找算法研究综述

随着Internet的迅猛发展,用于主干网络互联的核心路由器的接口速率已经达到了2.5Gbps～10Gbps.这一速率要求核心路由器每秒能够转发几百万乃至上千万个以上的分组.分组转发的重要一步就是查找路由表,因此快速的路由查找算法是实现高速分组转发的关键.路由查找需要实现最长前缀匹配.近年来,研究人员提出了多种路由查找算法,以提高查找性能.分析了路由查找问题及其难点,全面综述了各种查找算法,并对它们进行了详细的分析和比较,最后指出了进一步的研究方向.