基于布鲁姆过滤器算法和三态内容寻址存储器的高效范围匹配方法

该文基于布鲁姆过滤器算法和三态内容寻址存储器(Ternary Content Addressable Memory, TCAM)技术提出一种高效范围匹配方法,解决了目前TCAM范围匹配方案存在的存储利用率低、功耗大的问题。设计基于最长共同前缀的分段匹配算法(Segmented Match on Longest Common Prefix, SMLCP)将范围匹配拆分为前缀匹配和特征区间比对两步,TCAM空间利用率达到100%。根据SMLCP算法设计了BF-TCAM模型,使用布鲁姆过滤器对关键字过滤,屏蔽无关项参与比较,大幅降低功耗。使用流水线缩短关键路径长度,使查找操作在一个时钟周期内完成。研究结果表明,所提方法实现了零范围扩张,工作功耗较传统TCAM降低50%以上。     

基于TCAM的范围匹配方法——C-TCAM

提出一种基于TCAM的范围匹配方法——C-TCAM(compressed TCAM)。空间方面,通过二级压缩存储,C-TCAM可以将2个扩展后的TCAM表项压缩成一个,最坏情况下范围扩张因子为W 1或者W 2,提高了空间利用率;功耗方面,通过一种新的TCAM查找算法来避免无效表项参与比较从而降低了功耗;分析和仿真显示C-TCAM方法在实现性能分组分类的同时在空间利用率、功耗等方面具有优势。     

基于TCAM的深部包检测技术研究与实现

深度包检测技术(DPI)已成为网络信息安全的研究重点。基于硬件实现模式匹配的DPI技术凭借其更强的处理能力受到广泛关注。本文提出一种基于TCAM模式匹配的方法实现DPI,规则表项按字节分别存储在TCAM(三态内容寻址存储器)中,输入字符按不同字节与TCAM中内容进行匹配,提高了DPI中模式匹配的处理速度。针对该技术功耗大的缺点,提出BF(Bloom Filter)和TCAM相结合的两级模式匹配技术,BF可将较少可疑包转发给TCAM处理模块,从而降低了系统功耗,大大提高了系统处理速度。     

基于多域并行编码的高速IPv6流分类

IPv6的多域流分类是高速路由器设计中的一个难点.本文提出了一种使用TCAM的高速IPv6流分类方案,其核心思想是:(1)区分IPv6包头5个域字段的不同特征,根据IPv6地址的特征及其分配信息对其进行压缩,对TCP端口域实施扩展的层次编码,根据统计数据对协议域进行压缩,最终结果是把原始域的296比特转换成280比特的查找关键字,与TCAM的表项宽度相匹配;(2)使用嵌入SSRAM表查找技术,对5个域并行进行独立编码,消除瓶颈编码环节,达到线速处理要求;(3)分类规则数据库按照本文预设计的编码方式存储在TCAM中,使用流水线技术让域的编码操作和查找操作并行执行,每个TCAM访存周期完成一次查找操作.同时,为解决范围匹配问题,本文设计了一种预定义位宽的动态范围编码算法,既节省了TCAM的存储空间,又提高了硬件规则库的更新速度.分析和仿真表明,当路由查找和流分类共用一个TCAM时,使用较低的工作频率(66MHz),流分类和路由查找速度均可达到22Mpps,满足高速OC-192接口的线速查找与流分类要求.     

基于网络处理器外扩TCAM的研究与实现

传统交换芯片只能将内存固化于芯片内部,无法扩展外部存储器。针对这一问题,提出了一种基于网络处理器的外扩TCAM的方案。在此基础之上,对TCAM内存管理进行了分析,研究了网络处理器与外扩TCAM的通信原理,并详细描述了TCAM模块的初始化实现过程。经测试表明,该硬件运行稳定,为微引擎表项查找提供了存储空间。     

基于TCAM的低能耗正则表达式匹配算法

提出一种基于字符索引的正则表达式匹配算法,对确定型有限自动机（DFA, deterministic finite automaton）的字母表和状态进行分离存储,构建字符索引,减少匹配时激活的TCAM块数,显著降低TCAM能耗。实验结果表明：与DFA相比,基于字符索引的DFA（CIDFA, character-indexed DFA）在能耗上平均减少了92.7%,在存储空间开销上平均减少了32.0%,在吞吐量上平均提高了57.9%。     

一种大容量模式匹配算法

模式匹配技术是入侵检测与信息监管等网络应用的重要手段。针对现有模式匹配算法在大规模模式集下无法支持高速处理的情况,提出了一种两级三态内容可寻址寄存器（TCAM）的模式匹配算法。利用TCAM特性,提出一种子串编码方法压缩表项空间,提高空间利用率。通过性能分析和实验仿真表明,算法在支持大容量模式库的同时,可以获得较高的搜索速率。     

星地双基合成孔径雷达聚束模式快速BP算法

该文提出了一种应用于双基合成孔径雷达聚束模式的快速反向投影(FBP)算法,该算法在距离向压缩上使用地面接收器的同步信道作为回波信号的距离向匹配滤波器,在方位向压缩上采用2 次相位校正降低快速BP 算法中的近似误差对成像造成的影响,算法的计算复杂度为O(N2.5)。最后利用仿真数据和实测数据在图形处理器(GPU)上对该算法进行了验证。      

线速硬件网络入侵检测系统的范围匹配研究

为解决硬件入侵检测系统的规则匹配问题，提出了一种降低存储资源的范围匹配算法LRC—RM，将规则中的端口范围映射成压缩位向量，并将位向量组织成扩展平衡二叉树，然后对实现的系统进行了评估。采用该技术的网络入侵检测系统，使用的存储空间只有已有算法的1％，有利于硬件在片内完成查找过程，可实现端13范围在OC192链路的线速匹配。     

基于TCAM的K步长多模式匹配算法及硬件实现

对K步长状态机进行改进,消除了各状态的失效链,节省了存储资源,提高了匹配效率;根据TCAM(Ternary Content Addressable Memory)的并行查找和精确查找的特性,设计了一种用FPGA实现TCAM的方法,并以此作为基本匹配单元;最后结合改进的K步长状态机和基本匹配单元设计了一个快速多模式匹配系统.接收网络数据流进行实验,结果证明设计的匹配系统能达到数千兆位的吞吐率.     

A TCAM-based distributed parallel IP lookup scheme and performance analysis

Using ternary content addressable memory (TCAM) for high-speed IP address lookup has been gaining popularity due to its deterministic high performance. However, restricted by the slow improvement of memory accessing speed, the route lookup engines for next-generation terabit routers demand exploiting parallelism among multiple TCAM chips. Traditional parallel methods always incur excessive redundancy and high power consumption. We propose in this paper an original TCAM-based IP lookup scheme that achieves both ultra-high lookup throughput and optimal utilization of the memory while being power-efficient. In our multi-chip scheme, we devise a load-balanced TCAM table construction algorithm together with an adaptive load balancing mechanism. The power efficiency is well controlled by decreasing the number of TCAM entries triggered in each lookup operation. Using four 133 MHz TCAM chips and given 25% more TCAM entries than the original route table, the proposed scheme achieves a lookup throughput of up to 533 MPPS while remains simple for ASIC implementation.     

高速低功耗深度报文检测方法

针对基于三态内容寻址存储器(TCAM,ternary content addressable memory)的深度报文检测(DPI,deep packet inspection)存在的高功耗问题,提出一种分级DPI方法BF-TCAM。第一级采用低功耗的并行布鲁姆过滤器(bloom fliter)排除无需检测的正常报文;第二级采用TCAM对真正需要检测的攻击报文和第一级的假阳性误判报文做进一步的检测。由于网络流量中大部分报文是正常报文,攻击报文在其中只占很少的部分,布鲁姆过滤器的假阴性(false negative)概率为0,可以保证不会产生漏检,假阳性概率很低,可以保证高速DPI检测的同时大大地降低功耗。     

Effective cache replacement policy for packet processing cache

Owing to the explosive increase in Internet traffic, increasing the throughput and energy efficiency of core routers is an important issue for future internet. Accessing the ternary content addressable memory (TCAM) in a core router can significantly degrade its throughput and energy efficiency owing to its low operating frequency and power consuming operations. To improve the throughput and energy‐efficiency of core routers, packet processing caches (PPCs) can be potentially used. PPCs can reduce the number of TCAM accesses by storing the TCAM lookup results in a fast and low‐energy cache memory and reusing them to process subsequent packets. To enhance the PPC performance, it is important to reduce the number of PPC misses. However, the PPC miss rate of the state‐of‐the‐art PPC is still high owing to its small capacity. In this study, we propose an effective cache replacement policy, called elevator cache (ELC) to improve the PPC miss rate. Our simulation results showed that the 8‐way ELC, which can be implementable at low hardware cost, reduced the number of PPC misses by 17.1% and 5.67% in comparison to the 4‐way least recently used (LRU) and the 4‐way ELC, respectively. Consequently, it was found that the 8‐way ELC can achieve a 1.21 times higher throughput (560 Gbps) while consuming 83% energy in comparison to conventional PPCs.     

Efficient Multimatch Packet Classification for Network Security Applications

New network applications like intrusion detection systems and packet-level accounting require multimatch packet classification, where all matching filters need to be reported. Ternary content addressable memories (TCAMs) have been adopted to solve the multimatch classification problem due to their ability to perform fast parallel matching. However, TCAMs are expensive and consume large amounts of power. None of the previously published multimatch classification schemes are both memory and power efficient. In this paper, we develop a novel scheme that meets both requirements by using a new set splitting algorithm (SSA). The main idea behind SSA is that it splits filters into multiple groups and performs separate TCAM lookups into these groups. It guarantees the removal of at least 1/2 the intersections when a filter set is split into two sets, thus resulting in low TCAM memory usage. SSA also accesses filters in the TCAM only once per packet, leading to low-power consumption. We compare SSA with two best known schemes: multimatch using discriminators (MUD) (Lakshminarayanan and Rangarajan, 2005) and geometric intersection-based solutions (Yu and Katz, 2004). Simulation results based on the SNORT filter sets show that SSA uses approximately the same amount of TCAM memory as MUD, but yields a 75%–95% reduction in power consumption. Compared with geometric intersection-based solutions, SSA uses 90% less TCAM memory and power at the cost of one additional TCAM lookup per packet. We also show that SSA can be combined with SRAM/TCAM hybrid approaches to further reduce energy consumption.     

一种实现TCAM快速增量更新的算法

三重内容可寻址存储器TCAM（ternary content-addressable memory）是执行快速路由查找的常用硬件设备。在TCAM中进行最长前缀匹配操作最糟糕情况可能需要次存储操作，这里提出了一种算法来处理TCAM，结果使增量更新时间在最糟糕情况保持较小。通过对该算法与其他算法的性能分析，证明该算法在前缀长度排序限制条件下较常用算法更优。     

Ternary CAM Power and Delay Model: Extensions and Uses

Applications in computer networks often require high throughput access to large data structures for lookup and classification. While advanced algorithms exist to speed these search primitives on network processors and even custom application-specific integrated circuits (ASICs), achieving tight bounds on worst case performance with standard memories often requires a very careful analysis of all possible access patterns. An alternative, and often times more simple solution, is possible if a ternary CAM (TCAM) is used to perform a fully parallel search across the entire data set. Unfortunately, this parallelism means that large portions of the chip are switching during each cycle, causing large amounts of power to be consumed. While researchers at all levels of design (from algorithms to circuits) have begun to explore new ways of managing the power consumption, quantifying design alternatives is difficult due to a lack of available models. In this paper, we examine the structure of a modern TCAM and present a simple, yet accurate, power and delay model. We present techniques to estimate the dynamic power consumption and leakage power of a TCAM structure and validate the model using a combination of industrial TCAM datasheets and prior published works. Such a model is a critical first step in bridging the intellectual divide between circuit-level and algorithm-level optimizations. To demonstrate the utility of our model, we present an extensive analysis of the model by varying various architectural parameters and describe how our model can be easily extended to handle several circuit optimizations in the TCAM structure. In addition, we present a comparative study of SRAM and TCAM energy consumption to directly quantify the many design options which will be very useful for network designers to explore various power management schemes.     

Performance Analysis for a New Medium Access Control Protocol in Wireless LANs

One fundamental issue in high-speed wireless local area networks (LANs) is to develop efficient medium access control (MAC) protocols. In this paper, we focus on the performance improvement in both MAC layer and transport layer by using a novel medium access control protocol for high-speed wireless LANs deploying carrier sense multiple access/collision avoidance (CSMA/CA). We first present a recently proposed distributed contention-based MAC protocol utilizing a Fast Collision Resolution (FCR) algorithm and show that the proposed FCR algorithm provides high throughput and low latency while improving the fairness performance. The performance of the FCR algorithm is compared with that of the IEEE 802.11 MAC algorithm via extensive simulation studies on both MAC layer and transport layer. The results show that the FCR algorithm achieves a significantly higher efficiency than the IEEE 802.11 MAC and can significantly improve transport layer performance.