CN104410573B - 一种基于tcam的包匹配方法 - Google Patents

Abstract

本发明提供一种基于TCAM的包匹配方法，该方法包括：根据包转发速率r和TCAM芯片的时钟周期t计算空间压缩等级n；该空间压缩等级n为原TCAM芯片中可被压缩为1条表项的原表项数量；根据所述压缩等级n选择合适类型的TCAM芯片；根据压缩等级n，对原TCAM芯片进行压缩；当获取到匹配关键字时，将该匹配关键字与压缩后的TCAM芯片的规则库进行对比，执行n个时钟周期的匹配操作，得到匹配结果。该方案根据网络设备的包转发速率要求动态选择TCAM条目压缩等级，确保了在高速良好的用户体验的前提下，提高了TCAM芯片的空间利用率，并降低了能耗；且实现了TCAM芯片的动态选择，降低TCAM芯片的选购时间和费用。

Description

一种基于TCAM的包匹配方法

技术领域

本发明涉及互联网数据包分类技术领域，具体涉及一种基于TCAM的包匹配方法。

背景技术

随着互联网越来越深入人们的日常生活，网络流量不断增大，各种网络应用的数量也飞速增长，同时，随之而来的新型网络恶意攻击也不断出现，从而导致了越来越多的网络核心路由设备出现网络拥塞现象，严重降低了网络核心路由设备的转发性能。鉴于此，为识别网络中的流量类型以提供更优的服务质量和网络安全水平，数据包分类技术应运而生，且已成为现有互联网架构的核心组成部分。其中，基于三态内容寻址存储器(TCAM)的高速数据包分类机制因具有极高的包匹配速率，已成为了包分类技术的事实工业标准。

TCAM芯片规则库中的每条规则表达为严格的三态(0，1和*)格式，即TCAM中每一位比特只能取三种值：0，1和*(代表无关项)。如果一个字符串与某规则中所有的0和1位相同，则表明该字符串符合该规则。例如，字符串“110110”和“110010”都符合规则“11**10”。TCAM通过并行地将搜索关键词与规则库中的所有规则进行对比，并在固定时钟周期内返回位于TCAM较低地址位置的匹配结果，以实现高速的匹配操作。为降低能耗，现有TCAM芯片大多支持全局掩码寄存器(GMR)和局部掩码寄存器(BMR)。如图1所示,GMR决定了在包规则匹配中的参与匹配操作的纵向比特位置范围(如GMR 0和GMR 2)，而BMR决定了在匹配操作中应被启用或禁用的TCAM内存块(例如Block0)。GMR和BMR协同操作可实现降低TCAM芯片能耗的功能。

TCAM芯片规则库三态表述的固有特征，决定了在范围字段的匹配过程中将不可避免产生范围扩张问题。在典型的IPv4规则判定中，协议号和源IP地址、目的IP地址均可表述为前缀格式，即所有的无关项*均分布于三态字符串的末尾位置(例如11010***)，这使得数据包中上述三个字段信息均可直接存储于TCAM中作为一条表项。然而，数据包中的源端口号和目的端口号信息在规则判定中表征为实数范围，例如,[1,65535]的范围字段需要30个前缀格式的三态字符串来表征，而表征源端口号和目的端口号均属于[1,65535]的规则判定则需要多达30×30＝900个TCAM表项，这显然导致了严重的范围扩张问题。同时，范围扩张引起的表项剧增也加大了TCAM芯片的功耗，影响TCAM芯片的实际应用效果。

因此，如何提高TCAM芯片的空间利用率，以减轻范围扩张带来的负面影响，对基于TCAM的数据包分类技术的发展具有至关重要的推动作用。

为解决上述问题，现有技术提出了一种C-TCAM(Compressed-TCAM：压缩的TCAM)：采用二级压缩机制，将原先占据两条TCAM表项的每两个范围字段(如传输层端口号字段)压缩存储到一条TCAM表项中，以提高TCAM芯片的空间利用率。

但是，C-TCAM不具备TCAM芯片类型选择功能，不能根据网络设备转发速率的不同需求而动态适配TCAM芯片类型及空间压缩等级，导致芯片空间利用率不高，且能耗较高。例如，对于IPv4分组分类而言，若TCAM芯片位宽为144比特时，因为非范围字段包括源地址、目的地址和协议字段总长度共72比特，范围字段包括源端口和目的端口总长度共32比特，因此，采用C-TCAM后，每条TCAM表项的剩余比特宽度为8比特(144-72-32×2＝8)；然而，若采用576比特位宽的TCAM芯片时，C-TCAM方法导致每条TCAM表项的剩余比特宽度多达440比特，单条TCAM表项空间利用率仅为23.6％。产生这种想象的原因是：C-TCAM算法不具备动态TCAM芯片类型选择功能，只能固定地采用范围字段二级压缩机制，而不能根据网络设备转发速率需求自适应地调整范围字段压缩等级。

发明内容

本发明的目的是提出一种基于TCAM的包匹配方法，基于网络设备转发速率来完成TCAM芯片类型动态选择及范围字段压缩等级智能核定，在保证网络设备正常转发速率的基础上，提高TCAM芯片的空间利用率。

为达上述目的，本发明提供了一种基于TCAM的包匹配方法，包括：

根据包转发速率r和TCAM芯片的时钟周期t计算空间压缩等级n；该空间压缩等级n为原TCAM芯片中可被压缩为1条表项的原表项数量；

根据所述压缩等级n选择合适类型的TCAM芯片；

根据压缩等级n，对原TCAM芯片进行压缩；所述压缩包括：将原TCAM芯片中占据n条表项中的n对源端口号和目的端口号压缩为1条表项，按照表项位置自上而下的顺序依次执行；

当获取到匹配关键字时，将该匹配关键字与压缩后的TCAM芯片的规则库进行对比，执行n个时钟周期的匹配操作，得到匹配结果。

其中，所述根据包转发速率r和TCAM芯片的时钟周期t计算空间压缩等级n包括：

根据以下公式计算包转发速率：定义网络最小包大小为x bit，如果某网络设备接口带宽为y bit/s，则TCAM-PC的包转发速率需要达到的数值可计算如下：

r＝y/x；

其中，x为网络最小包大小，单位为bit；y为网络设备接口带宽，单位为bit/s；

计算所述网络最小包的处理时延：

d＝1/r

根据以下公式计算TCAM芯片压缩等级n：

即：

其中，t为TCAM芯片的时钟周期，单位为秒。

进一步的，如TCAM芯片的最大位宽为M，则为获得尽可能大的空间压缩率，n应为：

s为源IP地址的长度、d为目的IP地址的长度、p为协议号的长度、s’为源端口号的长度、d’为目的端口号的长度。

进一步的，所述根据所述压缩等级n选择合适类型的TCAM芯片，包括：

所述合适类型的TCAM芯片的位宽z取满足如下条件的最小整数值：

(s+d+p)+(s'+d')n≤z≤M，且z∈C；

其中，C为TCAM类型的集合，C＝{c|c∈N}(N＝1,2,3,…)。

其中，所述根据压缩等级n，对原TCAM芯片进行压缩包括：

每条压缩的表项中，高优先级的规则存储于偏左侧的位置，低优先级的规则存储于偏右侧位置。

所述将该匹配关键字与压缩后的TCAM芯片的规则库进行对比，执行n个时钟周期的匹配操作，得到匹配结果，包括：

在第i个时钟周期，全局掩码寄存器GMR激活GMR0+GMRi，i∈[1,n]，禁用其它所有比特位以降低能耗；

若发现一条匹配规则存储于TCAM内存块Block m，则在下一个时钟周期内，激活编号小于或等于m的所有地址块，禁用其它的所有地址块，以进一步降低能耗；

当所有n个时钟周期的匹配操作全部完成时，从匹配到的规则中选取地址最低的规则作为最终的匹配结果。

上述技术方案具有如下有益效果：

上述技术方案根据网络设备的包转发速率要求动态选择TCAM条目压缩等级，即，TCAM-PC(TCAM with Packet-forwarding-rate Constraints，满足网络设备转发速率的基于TCAM的包匹配方法)可在保证网络设备高速数据包转发速率的前提下实现合理的空间压缩率，确保了在高速良好的用户体验的前提下，降低了TCAM芯片的空间占用程度，提高了TCAM芯片的空间利用率，并降低了能耗；且实现了TCAM芯片的动态选择，可根据网络应用的不同性能需求选择合理的芯片类型，在实现网络应用功能的同时，降低TCAM芯片的选购时间和费用。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1是现有技术TCAM结构示意图；

图2是本发明实施例一的基于TCAM的包匹配方法的具体流程图；

图3是本发明TCAM-PC的体系结构示意图；

图4是本发明TCAM-PC的工作流程图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

TCAM范围匹配过程导致的范围扩张问题的特征是：在扩张后形成的每条新TCAM表项中，数据包源地址、目的地址和协议字段等非范围字段信息是相同的，而只有范围字段如源端口号和目的端口号是不同的。基于上述特征，本发明提出一种提高TCAM空间利用率的TCAM芯片选择方法——TCAM-PC。TCAM-PC通过将n(n＝1,2…)条包含不同范围字段信息(但同时包含相同的非范围字段信息)的TCAM表项压缩为一条，且在压缩后的新表项中仅保留一份非范围字段的信息，以达到节省TCAM芯片存储空间、提高空间利用率的目的。上述n是由配置TCAM芯片的网络设备的数据包转发速率决定的，本发明中数据包转发速率定义为rpacket/s(每秒转发r个数据包)。

实施例一

如图2所示，为本实施例一种基于TCAM的包匹配方法的流程图，包括以下步骤：

步骤201，根据包转发速率r和TCAM芯片的时钟周期t计算空间压缩等级n；该空间压缩等级n为原TCAM芯片中可被压缩为1条表项的原表项数量；

步骤202，根据所述压缩等级n选择合适类型的TCAM芯片；

步骤203，根据压缩等级n，对原TCAM芯片进行压缩；所述压缩包括：将原TCAM芯片中占据n条表项中的n对源端口号和目的端口号压缩为1条表项，按照表项位置自上而下的顺序依次执行；

步骤204，当获取到匹配关键字时，将该匹配关键字与压缩后的TCAM芯片的规则库进行对比，执行n个时钟周期的匹配操作，得到匹配结果。

其中，所述根据包转发速率r和TCAM芯片的时钟周期t计算空间压缩等级n包括：

根据以下公式计算包转发速率：定义网络最小包大小为x bit，如果某网络设备接口带宽为y bit/s，则TCAM-PC的包转发速率需要达到的数值可计算如下：

r＝y/x；

其中，x为网络最小包大小，单位为bit；y为网络设备接口带宽，单位为bit/s；

计算所述网络最小包的处理时延：

d＝1/r

根据以下公式计算TCAM芯片压缩等级n：

即：

其中，t为TCAM芯片的时钟周期，单位为秒。

进一步的，如TCAM芯片的最大位宽为M，则为获得尽可能大的空间压缩率，n应为：

s为源IP地址的长度、d为目的IP地址的长度、p为协议号的长度、s’为源端口号的长度、d’为目的端口号的长度。

进一步的，根据所述压缩等级n选择合适类型的TCAM芯片，包括：

所述合适类型的TCAM芯片的位宽z取满足如下条件的最小整数值：

(s+d+p)+(s'+d')n≤z≤M，且z∈C；

其中，C为TCAM类型的集合，C＝{c|c∈N}(N＝1,2,3,…)。

其中，所述根据压缩等级n，对原TCAM芯片进行压缩包括：

每条压缩的表项中，高优先级的规则存储于偏左侧的位置，低优先级的规则存储于偏右侧位置。

优选的，所述将该匹配关键字与压缩后的TCAM芯片的规则库进行对比，执行n个时钟周期的匹配操作，得到匹配结果，包括：

在第i个时钟周期，全局掩码寄存器GMR激活GMR0+GMRi，i∈[1,n]，禁用其它所有比特位以降低能耗；

若发现一条匹配规则存储于TCAM内存块Block m，则在下一个时钟周期内，激活编号小于或等于m的所有地址块，禁用其它的所有地址块，以进一步降低能耗；

当所有n个时钟周期的匹配操作全部完成时，从匹配到的规则中选取地址最低的规则作为最终的匹配结果。

本实施例具有如下有益效果：

本实施例根据网络设备的包转发速率要求动态选择TCAM条目压缩等级，即，TCAM-PC可在保证网络设备高速数据包转发速率的前提下实现合理的空间压缩率，确保了在高速良好的用户体验的前提下，降低了TCAM芯片的空间占用程度，提高了TCAM芯片的空间利用率，并降低了能耗；且实现了TCAM芯片的动态选择，可根据网络应用的不同性能需求选择合理的芯片类型，在实现网络应用功能的同时，降低TCAM芯片的选购时间和费用。

实施例二

TCAM-PC包含至少三个功能部分，阐述如下：

1、TCAM芯片空间压缩等级计算方法：

定义网络最小包大小为x bit，如果某网络设备接口带宽为y bit/s，则TCAM-PC的包转发速率需要达到的数值可计算如下：

r＝y/x (1)

TCAM-PC中每个数据包的包处理时延为：

d＝1/r (2)

定义TCAM芯片的时钟周期为t秒,TCAM-PC中可被压缩为一条规则的原总规则数量(定义为压缩等级n)可推断如下：

基于公式(1)至公式(3)，可得出：

对于典型的IPv4网络而言，在每个数据包包头中，源IP地址和目的IP地址的长度均为32bits,协议号的长度为8bits，源端口号和目的端口号的长度均为16bits。若TCAM芯片的最大位宽为M，则为获得尽可能大的空间压缩率，n应为：

2、TCAM芯片选择方法：

定义TCAM类型为具有不同TCAM位宽(如位宽为72比特或144比特)的种类，且现有TCAM类型的集合为C＝{c|c∈N}(N＝1,2,3,…)，则TCAM-PC机制应选用的TCAM芯片类型z(代表TCAM芯片的位宽)，可依据如下不等式计算得出：

(32×2+8)+(16×2)n＝72+32n≤z≤M且z∈C (6)

注意，为获得尽可能的TCAM芯片功耗，z应取满足条件不等式(6)的最小整数值。

3、TCAM-PC工作流程：

图3为TCAM-PC的体系结构示意图，其中，S_IP为源地址、D_IP为目的地址、Prot为协议号、S_Port为源端口、D_Port为目的端口。

如图4所示，TCAM-PC的工作过程如下：

步骤401：TCAM-PC基于TCAM芯片空间压缩等级计算方法(公式(1)至公式(5))计算出TCAM存储空间的压缩等级n；然后基于TCAM芯片选择方法(公式(6))选择合适的TCAM芯片类型；

步骤402：TCAM-PC按照将原先占据n条TCAM表项的每n对源端口号和目的端口号压缩为1条表项，并按照表项位置自上而下的顺序依次执行(例如自Block 0的表项开始压缩，直到压缩至Block m)；且每条压缩后的表项中，高优先级的规则存储于偏左侧位置，低优先级的规则存储于偏右侧位置；

步骤403：当一个匹配关键字到来时，TCAM-PC将关键字与规则库进行对比，执行n个时钟周期的匹配操作：在第i个时钟周期，GMR激活GMR0+GMRi，i∈[1,n]，其余所有比特位均禁用以降低能耗；另外，若发现一条匹配规则存储于Block m，则在下一个时钟周期内，仅仅激活编号小于或等于m的所有地址块(例如Block l，l≤m)，其余的地址块均禁用，以进一步降低能耗；当所有n个时钟周期的匹配操作全部完成时，TCAM-PC从匹配到的规则中选取地址最低的规则作为最终的匹配结果。

本实施例根据网络设备的包转发速率要求动态选择TCAM条目压缩等级，即TCAM-PC可在保证网络设备高速数据包转发速率的前提下实现合理的空间压缩率，既确保了高速良好的用户体验，又降低了TCAM芯片的空间占用程度，提高了TCAM芯片的空间利用率，并降低了能耗。同时可以实现TCAM芯片的动态选择，可根据网络应用的不同性能需求选择合理的芯片类型，在实现网络应用功能的同时，降低了TCAM芯片的选购时间和费用。

本领域技术人员还可以了解到本发明实施例列出的各种说明性逻辑块(illustrative logical block)，单元，和步骤可以通过电子硬件、电脑软件，或两者的结合进行实现。为清楚展示硬件和软件的可替换性(interchangeability)，上述的各种说明性部件(illustrative components)，单元和步骤已经通用地描述了它们的功能。这样的功能是通过硬件还是软件来实现取决于特定的应用和整个系统的设计要求。本领域技术人员可以对于每种特定的应用，可以使用各种方法实现所述的功能，但这种实现不应被理解为超出本发明实施例保护的范围。

以上所述的具体实施方式，对本发明的目的、技术方案和有益效果进行了进一步详细说明，所应理解的是，以上所述仅为本发明的具体实施方式而已，并不用于限定本发明的保护范围，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

Claims (4)

1.一种基于TCAM的包匹配方法，其特征在于，包括：

根据包转发速率r和TCAM芯片的时钟周期t计算空间压缩等级n；该空间压缩等级n为原TCAM芯片中可被压缩为1条表项的原表项数量；

根据所述压缩等级n选择合适类型的TCAM芯片；

根据压缩等级n，对原TCAM芯片进行压缩；所述压缩包括：将原TCAM芯片中占据n条表项中的n对源端口号和目的端口号压缩为1条表项，按照表项位置自上而下的顺序依次执行；

当获取到匹配关键字时，将该匹配关键字与压缩后的TCAM芯片的规则库进行对比，执行n个时钟周期的匹配操作，得到匹配结果；

所述根据包转发速率r和TCAM芯片的时钟周期t计算空间压缩等级n包括：

根据以下公式计算包转发速率需要达到的数值：

r＝y/x；

其中，x为网络最小包的大小，单位为bit；y为网络设备接口带宽，单位为bit/s；

计算所述网络最小包的处理时延：

d＝1/r

根据以下公式计算TCAM芯片压缩等级n：

即：

其中，t为TCAM芯片的时钟周期，单位为秒；

如TCAM芯片的最大位宽为M，则为获得尽可能大的空间压缩率，n应为：

s为源IP地址的长度、d为目的IP地址的长度、p为协议号的长度、s’为源端口号的长度、d’为目的端口号的长度。

2.根据权利要求1所述的方法，其特征在于，所述根据所述压缩等级n选择合适类型的TCAM芯片，包括：

所述合适类型的TCAM芯片的位宽z取满足如下条件的最小整数值：

(s+d+p)+(s'+d')n≤z≤M，且z∈C；

其中，C为TCAM类型的集合，C＝{c|c∈N}(N＝1,2,3,…)。

3.根据权利要求1所述的方法，其特征在于，所述根据压缩等级n，对原TCAM芯片进行压缩包括：

每条压缩的表项中，高优先级的规则存储于偏左侧的位置，低优先级的规则存储于偏右侧位置。

4.根据权利要求1所述的方法，其特征在于，所述将该匹配关键字与压缩后的TCAM芯片的规则库进行对比，执行n个时钟周期的匹配操作，得到匹配结果，包括：

在第i个时钟周期，全局掩码寄存器GMR激活GMR0+GMRi，i∈[1,n]，禁用其它所有比特位以降低能耗；

若发现一条匹配规则存储于TCAM内存块Block m，则在下一个时钟周期内，激活编号小于或等于m的所有地址块，禁用其它的地址块，以进一步降低能耗；

当所有n个时钟周期的匹配操作全部完成时，从匹配到的规则中选取地址最低的规则作为最终的匹配结果。