基于TCAM的包分类算法研究综述

包分类技术作为网络交换业务的核心技术,在保证网络的高带宽和低延迟方面发挥着重要作用。在核心网与承载网领域,高性能网络对交换、路由、QoS(Quality of Service)等业务提出了更高的要求。目前高端交换芯片的主流技术仍以基于硬件的包分类算法为主,其中又以TCAM技术的应用最为成熟。本文分析了当前TCAM算法应用现状和研究进展,系统性地介绍了TCAM中的范围匹配和多匹配两大核心问题及其解决方案,对比阐述了现有算法的优点和缺点,最后给出了未来TCAM包分类算法的研究趋势。

ISCP-TCAM:一种低功耗高速路由查找引擎结构

提出一种高速、低功耗路由查找引擎结构ISCP TCAM(ImprovedStage ControlPipeline TernaryContentAddressableMemory),这种结构不但具有传统内容可寻址寄存器(TCAM)管理简单、 更新容易、查找快速等优点,而且功耗要比同等容量的TCAM小得多。同时为进一步评估其性能利 用ALTERA公司的逻辑可编程门阵列(FPGA)实现了这一结构。该结构在低功耗高速路由查找引擎 的设计中是一个较好的选择。

TCAM快更新高速路由查找算法与实现

常用的单步TCAM路由查找方案要求转发表的存储必须按前缀长度相对地址降序排列,这种与地址关联的排序操作影响表项的更新速度和路由查找流程的连续性。本文提出并实现了一种独特的对前缀范围对分搜索的IPv4五步TCAM流水查找方法。突出特点是转发表不需排序,查找速率高,表项更新快,查表连续性好,可满足IPv4核心路由器双OC-768(40Gbps)端口、48B包的线速转发。

一种支持TCAM规则更新与压缩方法

提出了一种TCAM空间划分和规则压缩相结合的方法,使得OpenFlow网络在支持实时更新的同时能采用小容量的TCAM芯片来存储网络中的规则.所提方法将TCAM芯片空间划分为实时更新区和压缩存储区,实时更新区处在TCAM芯片的前部,用于存放中央控制器发送过来的实时更新规则.后台服务器以一定的时间周期将TCAM芯片中的实时更新区的规则以及压缩存储区中的规则进行压缩,并将压缩后的规则存入TCAM的压缩区,保持实时更新区具有空间接收实时更新规则.分析了区间划分的比率问题,并利用ClassBench工具产生原始规则集进行了仿真实验,实验结果验证了本文方法的有效性.

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

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

基于TCAM的快速更新算法

目前用于实现线速数据包处理的硬件设备主要是TCAM。对于如何保持TCAM列表的排序这个问题，通常的解决方案提高了平均性能，但是浪费了TCAM空间。论述了一种改进的算法来管理TCAM使得其在最差情况下递增式更新时间保持较小，通过分析使其也能够用于解决数据包分类问题。

TCAM在高速路由查找中的应用及其FPGA实现

当前随着网络带宽的不断增加,对路由器转发速度的要求也越来越高。如何进行路由的快速查找目前成为限制报文快速转发的瓶颈,为了解决这一问题比较流行的方式是采用TCAM器件进行路由的快速查找。本文详细介绍了TCAM器件在高速路由查找中的应用及其管理算法,同时重点给出了TCAM器件的FPGA实现。

改进的TCAM路由更新方法与实现

基于TCAM的硬件路由查找算法能够在一个时钟周期内完成最长前缀匹配,实现快速路由查找和分组转发。但路由表表项的有序性使得更新过程比较复杂从而成为TCAM路由技术发展的瓶颈。根据不同长度前缀表项的分布特性及路由表稳态时的更新规律,优化了路由表的空间分配,并引入了缓冲池的思想,提出了一种改进的路由表更新方法,从而提高路由表更新效率。

基于Trie树分割路由表降低TCAM功耗的方法

TCAM已成为在路由器设计中实现路由查找的硬件方案,具有速度快、实现简单的优点,但其功耗较高。该文提出了一种基于trie树的结构进行路由表分割、降低TCAM功耗的方法,同传统的TCAM相比,前缀数量达到200时降低大约80%的功耗,前缀数量越多,相对降低的比例越大。

基于CAM/TCAM分组的Multi-Gigabit速率模式匹配引擎

为了提高NIDS中模式匹配模块的处理性能,在分析相关研究的基础上,提出了一种具有multi-gigabit线速度处理能力的模式匹配引擎.该引擎采用按模式串长度和数目不同,在CAM或TCAM中均衡分组存储的方法,以及待测串切换等技术实现了multi-gigabit速率的处理性能和有效的存储空间利用.通过采用多个匹配模块并行处理的方式可以进一步提高引擎的处理能力.在200MHz的时钟工作频率下,系统输出的性能可以达到6Gbit/s以上.

基于RAM和TCAM存储结构的高速路由查找算法

由于因特网速度的不断提高,网络流量的不断增加和路由表规模的不断扩大,IP路由查找已经成为制约核心路由器性能的主要瓶颈。文章分析了两种常用的基于硬件存储器的路由查找算法,并结合它们各自优点,提出了一种基于RAM和TCAM存储结构的路由查找算法,该算法克服了上述两种算法的不足,具有查找速率高、更新时间快、存储代价低、易于实现等特点,是一种理想的适合于高速核心路由器环境的查找机制。

Leaf-TCAM:一种并行IP路由查找方法及性能分析

分析了互联网路由表和路由更新的特征,提出了一种基于叶子节点进行路由表分区的并行IP路由查找方法Leaf-TCAM,分区子表按照流量特征在K个TCAM芯片中进行均衡分布。分析表明,该路由查找方法在引入0.1*(K-1)冗余的前提下具有K-1倍加速因子。该方法无需进行前缀扩展,90%以上的路由前缀无需排序,可以采用随机更新;同时还具有分区均匀、分区溢出代价小等特点,而功耗只有传统单片方案的12%。

基于TCAM技术的高速路由查找方案

基于TCAM技术提出一个高速路由查找方案。该方案可以达到每秒钟100M次的查找速度,满足OC48和OC192接口的线速转发要求。方案使用了索引表和映射表的二级结构存储路由的下一跳信息,大大减小了存储空间,同时对IPv6具有很好的扩展性。对TCAM的路由更新问题进行了讨论,提出一个最坏情况下O(W 2)的更新算法(W为前缀长度集合的数目),有效地提高了TCAM的更新性能。

TCAM路由表项管理算法优化研究

TCAM(Ternary Content-Addressable Memory)能够很好的完成最长前缀匹配,实现快速路由查找和分组转发,但是其对路由表项的有序性要求使得表项管理比较复杂。在讨论已有TCAM表项管理算法的基础上,通过分析前缀表项的统计分布特性.对路由表的空间分配进行了优化,同时引入新的基于前缀块指针管理策略,提出了一种改进的表项管理方法,提高了路由表更新效率。

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

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

TCAM路由查找技术应用解析

通过研究IP数据包转发对路由器的需求,分析了基于软件转发技术和TCAM方案。结论表明,采用专用硬件查找技术的TCAM方案,以硬件化的路由表查找和分组转发技术实现对各类数据包的快速分类和路由,支持ACL和MPLS的查找。高端路由设备要处理巨大的流量和多种复杂业务,只有采用硬件查表的方式才能满足要求。

双TCAM高性能IPv4路由查找算法与实现

传统二分算法完成一次IPv4最长前缀匹配需5步搜索,且因存在回溯问题难以硬件实现,而单步TCAM路由查找方案要求转发表的存储必须按前缀长度相对地址降序排列,影响表项的更新速度和路由查找流程的连续性。该文提出并以TCAM流水线硬件实现了一种独特对扩展前缀范围的四分搜索算法。仅用2步搜索完成一次IPv4路由查找、转发表不需排序、查找速率高、表项更新快、查表连续性好。满足IPv4核心路由器的双OC-768(40Gbps)端口、48B包的线速转发。

一种基于TCAM的PLO_OPT算法的改进

在最大前缀长度为L的TCAM(Ternary Content Addressable Memory)中,采用PLO_OPT算法更新路由表项仍然有很大的时间消耗,其时间复杂度为O(L/2)。为了进一步提高路由更新速度,根据路由前缀数量分布图,本文提出了一种PLO_OPT路由更新算法的改进方案,每更新一次表项只需进行一次操作即可,可以使时间复杂度达到O(1),且更有效地利用了存储空间。

高性能TCAM路由查找表研究与设计

TCAM是高性能路由器中查找性能强大的硬件查找结构,但是其价格昂贵且功耗大。为了解决这个问题,本文提出了一种实现方案,从而优化了TCAM电路结构且提高了性能。用Verilog HDL语言进行描述,采用Altera公司的FPGA开发权,基于CycloneⅢ单元库进行FPGA验证,此方案其时钟频率为100MHz,功耗降低50%。

用于TCAM的元组快速包分类

通过引入元组概念组织分类器,对TCAM上路由查寻算法CAO-OPT进行改进,实现了多维数据包的快速分类和更新。