一种基于tcam连续数值匹配方法和装置的制造方法
一种基于tcam连续数值匹配方法和装置的制造方法
【技术领域】
[0001] 本发明设及数据包处理技术领域，特别设及一种基于TCAM连续数值匹配方法和 装置。
【背景技术】
[0002] 高速数据包分类算法，在很多的网络应用领域中，变得越来越重要，例如，网络安 全应用、QoS服务过滤和网络负载均衡应用等。为了进行高速包分类，网络设备通常采用分 类数据库，其中包含多条A化(Access Control List,访问控制列表），每一条A化可能由多 条用于输入或者输出数据流的规则组成。
[0003] A化规则的数目在逐渐增多，可能要求上百万的规则；对A化规则的捜索速度也要 求越来越高，要求达到每秒上百万次的捜索能力。为满足该些要求，有很多的基于RAM的高 速数据包分类算法，例如，RFC算法、Hyper化ts算法等。然而，对于各种高速数据包分类算 法来说，毫无疑问地W基于TCAM的高速数据包分类算法的捜索速度最快。
[0004]CAM的英文全称为ContentAcMress油leMemo巧，即内容寻址内存。与普通的 SRAM、DDR等内存不同；普通内存通过输入地址得到数据；而CAM相反，通过输入数据得到数 据所在的地址。TCAM(即TernaryCAM)为S态CAM,不仅可W匹配二进制数"0"和"1"，还 可W通过掩码匹配任意值，也称为可匹配"X"。CAM的数据宽度通常可配置，如9字节、18字 节、36字节或72字节等。
[0005] 高速数据包的分类过程中需要对连续数值规则进行匹配，连续数值规则是指对 于某个匹配的域指定一个连续数值区域，例如W太网数据包的TCP端口连续数值为80~ 8000,然而使用TCAM直接进行匹配连续数值规则时，一条连续数值规则往往需要多条TCAM 表项才能存储，特别是当一条连续数值规则中有多个连续数值区域时，需要更多的TCAM表 项才能存储，使得TCAM存储的连续数值规则条数有限，使得降低了TCAM的利用率。
【发明内容】
[0006] 本发明实施例提供了一种基于TCAM连续数值匹配方法，W提高内容寻址内存器 的利用率。该方法包括：在连续数值区域内确定两个分界点数值，根据分界点数值将所述 连续数值区域划分为=个数值段，在该=个数值段中至少有一个数值段的两个端点数值符 合预设=态编码规则，在端点数值不符合预设=态编码规则的数值段内继续确定分界点数 值进行数据分段，直到每个数值段的端点数值都符合预设=态编码规则，形成多个数值段， 其中，所述预设=态编码规则使得对所述连续数值区域进行=态编码的结果与对所述连续 数值区域划分的多个数值段分别进行=态编码后相加的结果等效；对于符合所述预设=态 编码规则的两个端点数值，则将该两个端点数值之间的数值段中数值的二进制编码的宽度 比特分别分成多个比特段，分别对每个比特段的二进制编码对应的十进制数据进行=态编 码，生成该两个端点数值之间的数值段的=态内容寻址内存器记录，并将形成的=态内容 寻址内存器记录存入S态内容寻址内存器中；将待匹配数值的二进制编码的宽度比特划分 为所述多个比特段，对每个比特段的二进制编码对应的十进制数据进行=态编码，生成所 述待匹配数值的=态内容寻址内存器记录，将所述待匹配数值的=态内容寻址内存器记录 输入到所述=态内容寻址内存器中和数值段的=态内容寻址内存器记录进行匹配。
[0007]在一个实施例中，所述预设=态编码规则是将两个端点数值的二进制编码的宽度 比特分别分成所述多个比特段，对每个比特段的二进制编码对应的十进制数值进行=态编 码，所述两个端点数值中一个端点数值的第i个比特段的=态编码与另一个端点数值的第 i个比特段的=态编码不相同，且第i个比特段之前的比特段的=态编码对应相同，i是指 一个比特段在多个比特段中的序数，第i个比特段之前是指由i至序数减小的方向。
[000引在一个实施例中，在连续数值区域内确定两个分界点数值，根据分界点数值将所 述连续数值区域划分为=个数值段，包括：将所述连续数值区域的两个端点数值的二进制 编码的宽度比特分别分成所述多个比特段，分别对每个比特段的二进制编码对应的十进制 数据进行=态编码；按照比特位由高至低的顺序，对两个端点数值的多个比特段中序数对 应的比特段的=态编码进行比较，找到=态编码不相同的第i个比特段，且第i个比特段 之前的比特段的=态编码对应相同；对于两个端点数值中较小的端点数值，将第i个比特 段对应的十进制数值加1，对加1后的十进制数值进行=态编码，将第i个比特段之后的比 特段的=态编码均用掩码表示，将第i个比特段的=态编码和第i个比特段之前比特段的 =态编码还原为二进制编码，将第i个比特段之后比特段的=态编码还原的二进制编码的 0比特，将多个比特段的二进制编码相加得到一个二进制编码，确定该二进制编码对应的十 进制数值为两个分界点数值中较小的分界点数值；对于两个端点数值中较大的端点数值， 将第i个比特段对应的十进制数值减1，对减1后的十进制数值进行=态编码，将第i个比 特段之后的比特段的=态编码均用掩码表示，将第i个比特段的=态编码和第i个比特段 之前比特段的=态编码还原为二进制编码，将第i个比特段之后比特段的=态编码还原的 二进制编码的0比特，将多个比特段的二进制编码相加得到一个二进制编码，确定该二进 制编码对应的十进制数值为两个分界点数值中较大的分界点数值；根据确定的两个分界点 数值将所述连续数值区域划分为=个数值段，其中，所述两个分界点数值符合预设=态编 码规则，在所述=个数值段中允许对两个分界点数值之间形成的数据段进行=态编码，形 成内容寻址内存器记录。
[0009] 在一个实施例中，每个比特段的比特位数小于等于4。
[0010] 本发明实施例还提供了一种基于TCAM连续数值匹配装置，W提高内容寻址内存 器的利用率。该装置包括；数值划分模块，用于在连续数值区域内确定两个分界点数值，根 据分界点数值将所述连续数值区域划分为=个数值段，在该=个数值段中至少有一个数值 段的两个端点数值符合预设=态编码规则，在端点数值不符合预设=态编码规则的数值段 内继续确定分界点数值进行数据分段，直到每个数值段的端点数值都符合预设=态编码规 贝1J，形成多个数值段，其中，所述预设=态编码规则使得对所述连续数值区域进行=态编码 的结果与对所述连续数值区域划分的多个数值段分别进行=态编码后相加的结果等效；= 态编码模块，用于对于符合所述预设S态编码规则的两个端点数值，则将该两个端点数值 之间的数值段中数值的二进制编码的宽度比特分别分成多个比特段，分别对每个比特段的 二进制编码对应的十进制数据进行=态编码，生成该两个端点数值之间的数值段的=态内 容寻址内存器记录，并将形成的=态内容寻址内存器记录存入=态内容寻址内存器中；匹 配模块，用于将待匹配数值的二进制编码的宽度比特划分为所述多个比特段，对每个比特 段的二进制编码对应的十进制数据进行=态编码，生成所述待匹配数值的=态内容寻址内 存器记录，将所述待匹配数值的=态内容寻址内存器记录输入到所述=态内容寻址内存器 中和数值段的S态内容寻址内存器记录进行匹配。
[0011] 在一个实施例中，所述预设=态编码规则是将两个端点数值的二进制编码的宽度 比特分别分成所述多个比特段，对每个比特段的二进制编码对应的十进制数值进行=态编 码，所述两个端点数值中一个端点数值的第i个比特段的=态编码与另一个端点数值的第 i个比特段的=态编码不相同，且第i个比特段之前的比特段的=态编码对应相同，i是指 一个比特段在多个比特段中的序数，第i个比特段之前是指由i至序数减小的方向。
[0012] 在一个实施例中，所述数值划分模块，包括：比特段划分单元，用于将所述连续数 值区域的两个端点数值的二进制编码的宽度比特分别分成所述多个比特段，分别对每个比 特段的二进制编码对应的十进制数据进行=态编码；比较单元，用于按照比特位由高至低 的顺序，对两个端点数值的多个比特段中序数对应的比特段的=态编码进行比较，找到= 态编码不相同的第i个比特段，且第i个比特段之前的比特段的=态编码对应相同；第一分 界点数值确定单元，用于对于两个端点数值中较小的端点数值，将第i个比特段对应的十 进制数值加1，对加1后的十进制数值进行=态编码，将第i个比特段之后的比特段的=态 编码均用掩码表示，将第i个比特段的=态编码和第i个比特段之前比特段的=态编码还 原为二进制编码，将第i个比特段之后比特段的S态编码还原的二进制编码的0比特，将多 个比特段的二进制编码相加得到一个二进制编码，确定该二进制编码对应的十进制数值为 两个分界点数值中较小的分界点数值；第二分界点数值确定单元，用于对于两个端点数值 中较大的端点数值，将第i个比特段对应的十进制数值减1，对减1后的十进制数值进行= 态编码，将第i个比特段之后的比特段的=态编码均用掩码表示，将第i个比特段的=态编 码和第i个比特段之前比特段的=态编码还 原为二进制编码，将第i个比特段之后比特段 的=态编码还原的二进制编码的0比特，将多个比特段的二进制编码相加得到一个二进制 编码，确定该二进制编码对应的十进制数值为两个分界点数值中较大的分界点数值；数值 划分单元，用于根据确定的两个分界点数值将所述连续数值区域划分为=个数值段，其中， 所述两个分界点数值符合预设=态编码规则，在所述=个数值段中允许对两个分界点数值 之间形成的数据段进行=态编码，形成内容寻址内存器记录。
[0013] 在一个实施例中，每个比特段的比特位数小于等于4。
[0014] 在本发明实施例中，通过将连续数值区域划分为多个数值段，并分别对多个数值 段进行=态编码，来实现对连续数值区域进行=态编码，实现了W更多的TCAM记录来换取 更小的编码位宽，使得有利于充分利用=态内容寻址内存器中表项的空闲比特，可W存储 更多的连续数值区域编码，再通过将编码后的待匹配数值输入到所述=态内容寻址内存器 中与=态内容寻址内存器记录进行匹配，在确保容寻址内存器快速捜索速度的同时，还可 W提高内容寻址内存器的利用率。
【附图说明】
[0015] 此处所说明的附图用来提供对本发明的进一步理解，构成本申请的一部分，并不 构成对本发明的限定。在附图中：
[0016] 图1是本发明实施例提供的一种基于TCAM连续数值匹配方法的流程图；
[0017]图2是本发明实施例提供的一种基于TCAM连续数值匹配装置的结构框图。
【具体实施方式】
[0018] 为使本发明的目的、技术方案和优点更加清楚明白，下面结合实施方式和附图，对 本发明做进一步详细说明。在此，本发明的示意性实施方式及其说明用于解释本发明，但并 不作为对本发明的限定。
[0019] 在本发明实施例中，提供了一种基于TCAM连续数值匹配方法，如图1所示，该方法 包括：
[0020] 步骤101 ;在连续数值区域内确定两个分界点数值，根据分界点数值将所述连续 数值区域划分为=个数值段，在该=个数值段中至少有一个数值段的两个端点数值符合预 设=态编码规则，在端点数值不符合预设=态编码规则的数值段内继续确定分界点数值进 行数据分段，直到每个数值段的端点数值都符合预设=态编码规则，形成多个数值段，其 中，所述预设=态编码规则使得对所述连续数值区域进行=态编码的结果与对所述连续数 值区域划分的多个数值段分别进行=态编码后相加的结果等效；
[002U 步骤102 ;对于符合所述预设S态编码规则的两个端点数值，则将该两个端点数 值之间的数值段中数值的二进制编码的宽度比特分别分成多个比特段，分别对每个比特段 的二进制编码对应的十进制数据进行=态编码，生成该两个端点数值之间的数值段的=态 内容寻址内存器记录，并将形成的=态内容寻址内存器记录存入=态内容寻址内存器TCAM 中；
[0022] 步骤103;将待匹配数值的二进制编码的宽度比特划分为所述多个比特段，对每 个比特段的二进制编码对应的十进制数据进行=态编码，生成所述待匹配数值的=态内容 寻址内存器记录，将所述待匹配数值的=态内容寻址内存器记录输入到所述TCAM中和数 值段的S态内容寻址内存器记录进行匹配。
[0023] 由图1所示的流程可知，在本发明实施例中，通过将连续数值区域划分为多个数 值段，并分别对多个数值段进行=态编码，来实现对连续数值区域进行=态编码，实现了W 更多的TCAM记录来换取更小的编码位宽，使得有利于充分利用=态内容寻址内存器中表 项的空闲比特，可W存储更多的连续数值区域编码，再通过将编码后的待匹配数值输入到 所述=态内容寻址内存器中与=态内容寻址内存器记录进行匹配，在确保容寻址内存器快 速捜索速度的同时，还可W提高内容寻址内存器的利用率。
[0024] 具体实施时，为了使得直接对所述连续数值区域进行=态编码的结果与对多个数 值段分别进行=态编码的结果等效，在本实施例中，所述预设=态编码规则是将两个端点 数值的二进制编码的宽度比特分别分成所述多个比特段，对每个比特段的二进制编码对应 的十进制数值进行=态编码，所述两个端点数值中一个端点数值的第i个比特段的=态编 码与另一个端点数值的第i个比特段的=态编码不相同，且第i个比特段之前的比特段的 =态编码对应相同，i是指一个比特段在多个比特段中的序数，第i个比特段之前是指由i 至序数减小的方向。
[0025] 具体的，为了尽量减少编码位宽，上述比特段的比特位数小于等于4,例如，对于连 续数值区域的位宽为16时，可W将16划分为7个比特段，各比特段的比特数分别是；3、3、 2、2、2、2、2 ;还可W将16划分为5个比特段，各比特段的比特数分别是；3、3、4、2、4。具体 的，基于通过TCAM的=态编码，可W将一个位宽为k的连续数值区域，编码为一条位宽为 化-1的TCAM记录。具体的编码方法如下表1所示；
[0026] 表 1
[0027]
[002引其中，0{2k-i-l}表示有连续化-i-1个0，l{i}表示有连续i个1，x{2k-i-l}表 示有连续化-i-1个X，其它表示方法类似；k为连续数值区域的比特宽度，i和j是连续数 值区域中的任意数值。例如W端口号为例，宽度为16比特，则k的值为16。具体的，一个位 宽为4的连续数值区域=态编码后变为15位，具体的编码结果如下表2所示：
[0029] 表2
[0030]
[003。 在具体实施时I，为了将连续数值区域划分为多个数值段，分别对数值段进行=态 编码W减少编码位宽，在本实施例中，在连续数值区域内确定两个分界点数值，根据分界点 数值将所述连续数值区域划分为=个数值段，包括：将所述连续数值区域的两个端点数值 的二进制编码的宽度比特分别分成多个比特段，分别对每个比特段的二进制编码对应的十 进制数据进行=态编码；按照比特位由高至低的顺序，对两个端点数值的多个比特段中序 数对应的比特段的=态编码进行比较，找到=态编码不相同的第i个比特段，且第i个比特 段之前的比特段的=态编码对应相同；对于两个端点数值中较小的端点数值，将第i个比 特段对应的十进制数值加1，对加1后的十进制数值进行=态编码，将第i个比特段之后的 比特段的=态编码均用掩码表示，将第i个比特段的=态编码和第i个比特段之前比特段 的=态编码还原为二进制编码，将第i个比特段之后比特段的=态编码还原的二进制编码 的0比特，将多个比特段的二进制编码相加得到一个二进制编码，确定该二进制编码对应 的十进制数值为两个分界点数值中较小的分界点数值；对于两个端点数值中较大的端点数 值，将第i个比特段对应的十进制数值减1，对减1后的十进制数值进行=态编码，将第i个 比特段之后的比特段的=态编码均用掩码表示，将第i个比特段的=态编码和第i个比特 段之前比特段的=态编码还原为二进制编码，将第i个比特段之后比特段的=态编码还原 的二进制编码的0比特，将多个比特段的二进制编码相加得到一个二进制编码，确定该二 进制编码对应的十进制数值为两个分界点数值中较大的分界点数值；根据确定的两个分界 点数值将所述连续数值区域划分为=个数值段，其中，所述两个分界点数值符合预设=态 编码规则，在所述=个数值段中允许对两个分界点数值之间形成的数据段进行=态编码， 形成=态内容寻址内存器记录。
[003引具体的，W连续数值区域R= [12, 241]，宽度为8位为例，具体的划分数值段和数 值匹配过程如下：
[003引首先，位宽8的分段方式为2、3、3,分成3个比特段，则3个比特段的S态编码宽度 分别为；3、7、7 ;
[0034] 即将两个端点数值12和241的二进制编码位宽划分为比特段表示为：
[0035] 8=12={00,001，100}，其中，3个比特段分别为00、001和100;
[0036] 6 = 241={11，110,001}，其中，3个比特段分别为11、110和001;
[0037] 对S和e的比特段分别进行S态编码，变为：
[003引S，= {000,0000001，0001111}
[0039] e' =山1，0111111，0011111}
[0040] 其次，按照比特位由高至低的顺序，对两个端点数值的多个比特段中序数对应的 比特段的=态编码进行比较，即对s'和e'的对应比特段编码进行比较，s'和e'对应的 第1个比特段编码不相等，则将s'的第1个比特段对应的十进制数值加1后进行S态编 码，第1个比特段之后的比特段的立态编码用掩码表示，即{001，XXXXXXX,xxxxxxx}，该 (001,xxxxxxx,xxxxxxx}还原为二进制编码后为{01，000,000}，该{01，000,000}对应的十 进制数为64,因此，64是两个分界点数值中较小的分界点数值，则将e'的第1个比特段对 应的十进制数值减 1后进行=态编码，第1个比特段之后的比特段的=态编码用掩码表示， 良P(011,XXXXXXX,xxxxxxx}，该（011,XXXXXXX,xxxxxxx}还原为二进制编码后为（10,000， 000}，该{10,000,000}对应的十进制数为128,因此，128是两个分界点数值中较大的分界 点数值，因此，上述连续数值区域R被分界点数值64和128划分为=个数值段，该=个数值 段的=态编码形式如下：
[0041] R1 = [ {001, xxxxxxx, xxxxxxx}, {Oil, xxxxxxx, xxxxxxx}]
[0042] Rii=[{000,0000001，0001111}，{000, 1111111，mini}]
[0043] R12 = [{111, 0000000, 0000000}，{000,0111111，0011111}]
[0044] R1即是两个分界点数值之间形成的数值段，可W编码为一条TCAM记录：
[0045] R1，= (0x1, xxxxxxx, xxxxxxx}
[0046] 进行第2次划分，Rll可W分为如下两段：
[0047] R2s=[{000,0000011,xxxxxxx},{000, 1111111,xxxxxxx}]
[0048] R21 =[{000, 0000001，0001111}，{000, 0000001，mini}]
[0049] R2s可W编码为一条TCAM记录；
[0化0] R2s，= {OOO'xxxxxll, xxxxxxx}
[0化1] R12可w分为如下两段：
[0052] R2e =[{111, 0000000, xxxxxxx} ,{000, 0011111, xxxxxxx}]
[0053] R22 = [{111,0111111，0000000}，{000,0111111，0011111}]
[0054] R2e可W编码为一条TCAM记录；
[0化5] R2e，= (111, OOxxxxx, xxxxxxx}
[0化6] 进行第3次划分，由于已经是最后一次划分，直接对最后的R21和R22编码即可。
[0化7] R21可W编码为一条TCAM记录；
[005引 R21' = {000,0000001，xxxllll}
[0059] R22可W编码为一条TCAM记录；
[0060] R22, = {000,0111111，OOxxxxx}
[0061] 分段编码完成，上述连续数值区域R的TCAM记录如下表3所示为：
[0062]表3
[0063]
[0064] 最后，假设待匹配数值key= 30,按照分段方式2、3、3对key的位宽比特进行分 段：
[00化]K巧=30 = {00,011，110}
[0066] 对key的各个比特段进S态编码；
[0067] Key，= {000,0000111，0111111}
[0068] 将编码后的key送入TCAM表中进行匹配，匹配结果会命中连续数值区域R的TCAM 记录中R2s的TCAM记录，因而匹配成功。即编码后的key与连续数值区域R的TCAM记录 中任意一条记录匹配成功，即数值匹配成功。
[0069] 基于同一发明构思，本发明实施例中还提供了一种基于TCAM连续数值匹配装置， 如下面的实施例所述。由于基于TCAM连续数值匹配装置解决问题的原理与基于TCAM连续 数值匹配方法相似，因此基于TCAM连续数值匹配装置的实施可W参见基于TCAM连续数值 匹配方法的实施，重复之处不再寶述。W下所使用的，术语"单元"或者"模块"可W实现预 定功能的软件和/或硬件的组合。尽管W下实施例所描述的装置较佳地W软件来实现，但 是硬件，或者软件和硬件的组合的实现也是可能并被构想的。
[0070] 图2是本发明实施例的基于TCAM连续数值匹配装置的一种结构框图，如图2所 示，包括；数值划分模块201、=态编码模块202和匹配模块203,下面对该结构进行说明。
[0071] 数值划分模块201，用于在连续数值区域内确定两个分界点数值，根据分界点数值 将所述连续数值区域划分为=个数值段，在该=个数值段中至少有一个数值段的两个端点 数值符合预设=态编码规则，在端点数值不符合预设=态编码规则的数值段内继续确定分 界点数值进行数据分段，直到每个数值段的端点数值都符合预设=态编码规则，形成多个 数值段，其中，所述预设=态编码规则使得对所述连续数值区域进行=态编码的结果与对 所述连续数值区域划分的多个数值段分别进行=态编码后相加的结果等效；
[0072]=态编码模块202,与数值划分模块201连接，用于对于符合所述预设=态编码规 则的两个端点数值，则将该两个端点数值之间的数值段中数值的二进制编码的宽度比特分 别分成多个比特段，分别对每个比特段的二进制编码对应的十进制数据进行=态编码，生 成该两个端点数值之间的数值段的=态内容寻址内存器记录，并将形成的=态内容寻址内 存器记录存入=态内容寻址内存器中；
[0073] 匹配模块203,与S态编码模块202连接，用于将待匹配数值的二进制编码的宽 度比特划分为所述多个比特段，对每个比特段的二进制编码对应的十进制数据进行=态编 码，生成所述待匹配数值的=态内容寻址内存器记录，将所述待匹配数值的=态内容寻址 内存器记录输入到所述=态内容寻址内存器中和数值段的=态内容寻址内存器记录进行 匹配。
[0074] 在一个实施例中，所述数值划分模块201，包括；比特段划分单元，用于将所述连 续数值区域的两个端点数值的二进制编码的宽度比特分别分成所述多个比特段，分别对每 个比特段的二进制编码对应的十进制数据进行=态编码；比较单元，与比特段划分单元连 接，用于按照比特位由高至低的顺序，对两个端点数值的多个比特段中序数对应的比特段 的=态编码进行比较，找到=态编码不相同的第i个比特段，且第i个比特段之前的比特段 的=态编码对应相同；第一分界点数值确定单元，与比较单元连接，用于对于两个端点数值 中较小的端点数值，将第i个比特段对应的十进制数值加1，对加1后的十进制数值进行= 态编码，将第i个比特段之后的比特段的=态编码均用掩码表示，将第i个比特段的=态编 码和第i个比特段之前比特段的=态编码还原为二进制编码，将第i个比特段之后比特段 的=态编码还原的二进制编码的0比特，将多个比特段的二进制编码相加得到一个二进制 编码，确定该二进制编码对应的十进制数值为两个分界点数值中较小的分界点数值；第二 分界点数值确定单元，与第一分界点数值确定单元连接，用于对于两个端点数值中较大的 端点数值，将第i个比特段对应的十进制数值减1，对减1后的十进制数值进行=态编码， 将第i个比特段之后的比特段的=态编码均用掩码表示，将第i个比特段的=态编码和第 i个比特段之前比特段的=态编码还原为二进制编码，将第i个比特段之后比特段的=态 编码还原的二进制编码的0比特，将多个比特段的二进制编码相加得到一个二进制编码， 确定该二进制编码对应的十进制数值为两个分界点数值中较大的分界点数值；数值划分单 元，与第二分界点数值确定单元连接，用于根据确定的两个分界点数值将所述连续数值区 域划分为=个数值段，其中，所述两个分界点数值符合预设=态编码规则，在所述=个数值 段中允许对两个分界点数值之间形成的数据段进行=态编码，形成=态内容寻址内存器记 录。
[0075] 在一个实施例中，每个比特段的比特位数小于等于4。
[0076] 在本发明实施例中，通过将连续数值区域划分为多个数值段，并分别对多个数值 段进行=态编码，来实现对连续数值区域进行=态编码，实现了W更多的TCAM记录来换取 更小的编码位宽，使得有利于充分利用=态内容寻址内存器中表项的空闲比特，可W存储 更多的连续数值区域编码，再通过将编码后的待匹配数值输入到所述=态内容寻址内存器 中与=态内容寻址内存器记录进行匹配，在确保容寻址内存器快速捜索速度的同时，还可 W提高内容寻址内存器的利用率。
[0077]显然，本领域的技术人员应该明白，上述的本发明实施例的各模块或各步骤可W 用通用的计算装置来实现，它们可W集中在单个的计算装置上，或者分布在多个计算装置 所组成的网络上，可选地，它们可W用计算装置可执行的程序代码来实现，从而，可W将它 们存储在存储装置中由计算装置来执行，并且在某些情况下，可WW不同于此处的顺序执 行所示出或描述的步骤，或者将它们分别制作成各个集成电路模块，或者将它们中的多个 模块或步骤制作成单个集成电路模块来实现。该样，本发明实施例不限制于任何特定的硬 件和软件结合。
[007引W上所述仅为本发明的优选实 施例而已，并不用于限制本发明，对于本领域的技 术人员来说，本发明实施例可W有各种更改和变化。凡在本发明的精神和原则之内，所作的 任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。
【主权项】
1. 一种基于TCAM连续数值匹配方法，其特征在于，包括： 在连续数值区域内确定两个分界点数值，根据分界点数值将所述连续数值区域划分 为三个数值段，在该三个数值段中至少有一个数值段的两个端点数值符合预设三态编码规 贝1J，在端点数值不符合预设三态编码规则的数值段内继续确定分界点数值进行数据分段， 直到每个数值段的端点数值都符合预设三态编码规则，形成多个数值段，其中，所述预设三 态编码规则使得对所述连续数值区域进行三态编码的结果与对所述连续数值区域划分的 多个数值段分别进行三态编码后相加的结果等效； 对于符合所述预设三态编码规则的两个端点数值，则将该两个端点数值之间的数值段 中数值的二进制编码的宽度比特分别分成多个比特段，分别对每个比特段的二进制编码对 应的十进制数据进行三态编码，生成该两个端点数值之间的数值段的三态内容寻址内存器 记录，并将形成的三态内容寻址内存器记录存入三态内容寻址内存器TCAM中； 将待匹配数值的二进制编码的宽度比特划分为所述多个比特段，对每个比特段的二 进制编码对应的十进制数据进行三态编码，生成所述待匹配数值的三态内容寻址内存器记 录，将所述待匹配数值的三态内容寻址内存器记录输入到所述TCAM中和数值段的三态内 容寻址内存器记录进行匹配。2. 如权利要求1所述的方法，其特征在于，所述预设三态编码规则是将两个端点数值 的二进制编码的宽度比特分别分成所述多个比特段，对每个比特段的二进制编码对应的十 进制数值进行三态编码，所述两个端点数值中一个端点数值的第i个比特段的三态编码与 另一个端点数值的第i个比特段的三态编码不相同，且第i个比特段之前的比特段的三态 编码对应相同，i是指一个比特段在多个比特段中的序数，第i个比特段之前是指由i至序 数减小的方向。3. 如权利要求2所述的方法，其特征在于，在连续数值区域内确定两个分界点数值，根 据分界点数值将所述连续数值区域划分为三个数值段，包括： 将所述连续数值区域的两个端点数值的二进制编码的宽度比特分别分成所述多个比 特段，分别对每个比特段的二进制编码对应的十进制数据进行三态编码； 按照比特位由高至低的顺序，对两个端点数值的多个比特段中序数对应的比特段的三 态编码进行比较，找到三态编码不相同的第i个比特段，且第i个比特段之前的比特段的三 态编码对应相同； 对于两个端点数值中较小的端点数值，将第i个比特段对应的十进制数值加1，对加1 后的十进制数值进行三态编码，将第i个比特段之后的比特段的三态编码均用掩码表示， 将第i个比特段的三态编码和第i个比特段之前比特段的三态编码还原为二进制编码，将 第i个比特段之后比特段的三态编码还原的二进制编码的O比特，将多个比特段的二进制 编码相加得到一个二进制编码，确定该二进制编码对应的十进制数值为两个分界点数值中 较小的分界点数值； 对于两个端点数值中较大的端点数值，将第i个比特段对应的十进制数值减1，对减1 后的十进制数值进行三态编码，将第i个比特段之后的比特段的三态编码均用掩码表示， 将第i个比特段的三态编码和第i个比特段之前比特段的三态编码还原为二进制编码，将 第i个比特段之后比特段的三态编码还原的二进制编码的O比特，将多个比特段的二进制 编码相加得到一个二进制编码，确定该二进制编码对应的十进制数值为两个分界点数值中 较大的分界点数值； 根据确定的两个分界点数值将所述连续数值区域划分为三个数值段，其中，所述两个 分界点数值符合预设三态编码规则，在所述三个数值段中允许对两个分界点数值之间形成 的数据段进行三态编码，形成三态内容寻址内存器记录。4. 如权利要求1至3中任一项所述的方法，其特征在于，每个比特段的比特位数小于等 于4。5. -种基于TCAM连续数值匹配装置，其特征在于，包括： 数值划分模块，用于在连续数值区域内确定两个分界点数值，根据分界点数值将所述 连续数值区域划分为三个数值段，在该三个数值段中至少有一个数值段的两个端点数值符 合预设三态编码规则，在端点数值不符合预设三态编码规则的数值段内继续确定分界点数 值进行数据分段，直到每个数值段的端点数值都符合预设三态编码规则，形成多个数值段， 其中，所述预设三态编码规则使得对所述连续数值区域进行三态编码的结果与对所述连续 数值区域划分的多个数值段分别进行三态编码后相加的结果等效； 三态编码模块，用于对于符合所述预设三态编码规则的两个端点数值，则将该两个端 点数值之间的数值段中数值的二进制编码的宽度比特分别分成多个比特段，分别对每个比 特段的二进制编码对应的十进制数据进行三态编码，生成该两个端点数值之间的数值段的 三态内容寻址内存器记录，并将形成的三态内容寻址内存器记录存入三态内容寻址内存器 TCAM中； 匹配模块，用于将待匹配数值的二进制编码的宽度比特划分为所述多个比特段，对每 个比特段的二进制编码对应的十进制数据进行三态编码，生成所述待匹配数值的三态内容 寻址内存器记录，将所述待匹配数值的三态内容寻址内存器记录输入到所述TCAM中和数 值段的三态内容寻址内存器记录进行匹配。6. 如权利要求5所述的装置，其特征在于，所述预设三态编码规则是将两个端点数值 的二进制编码的宽度比特分别分成所述多个比特段，对每个比特段的二进制编码对应的十 进制数值进行三态编码，所述两个端点数值中一个端点数值的第i个比特段的三态编码与 另一个端点数值的第i个比特段的三态编码不相同，且第i个比特段之前的比特段的三态 编码对应相同，i是指一个比特段在多个比特段中的序数，第i个比特段之前是指由i至序 数减小的方向。7. 如权利要求6所述的装置，其特征在于，所述数值划分模块，包括： 比特段划分单元，用于将所述连续数值区域的两个端点数值的二进制编码的宽度比特 分别分成所述多个比特段，分别对每个比特段的二进制编码对应的十进制数据进行三态编 码； 比较单元，用于按照比特位由高至低的顺序，对两个端点数值的多个比特段中序数对 应的比特段的三态编码进行比较，找到三态编码不相同的第i个比特段，且第i个比特段之 前的比特段的三态编码对应相同； 第一分界点数值确定单元，用于对于两个端点数值中较小的端点数值，将第i个比特 段对应的十进制数值加1，对加1后的十进制数值进行三态编码，将第i个比特段之后的比 特段的三态编码均用掩码表示，将第i个比特段的三态编码和第i个比特段之前比特段的 三态编码还原为二进制编码，将第i个比特段之后比特段的三态编码还原的二进制编码的 O比特，将多个比特段的二进制编码相加得到一个二进制编码，确定该二进制编码对应的十 进制数值为两个分界点数值中较小的分界点数值； 第二分界点数值确定单元，用于对于两个端点数值中较大的端点数值，将第i个比特 段对应的十进制数值减1，对减1后的十进制数值进行三态编码，将第i个比特段之后的比 特段的三态编码均用掩码表示，将第i个比特段的三态编码和第i个比特段之前比特段的 三态编码还原为二进制编码，将第i个比特段之后比特段的三态编码还原的二进制编码的 O比特，将多个比特段的二进制编码相加得到一个二进制编码，确定该二进制编码对应的十 进制数值为两个分界点数值中较大的分界点数值； 数值划分单元，用于根据确定的两个分界点数值将所述连续数值区域划分为三个数值 段，其中，所述两个分界点数值符合预设三态编码规则，在所述三个数值段中允许对两个分 界点数值之间形成的数据段进行三态编码，形成三态内容寻址内存器记录。8.如权利要求5至7中任一项所述的装置，其特征在于，每个比特段的比特位数小于等 于4。
【专利摘要】本发明实施例提供一种基于TCAM连续数值匹配方法和装置，该方法包括：根据分界点数值将连续数值区域划分为三个数值段，在该三个数值段中至少有一个数值段的两个端点数值符合预设三态编码规则，在端点数值不符合预设三态编码规则的数值段内继续确定分界点数值进行数据分段；对于符合预设三态编码规则的两个端点数值，将该两个端点数值之间的数值段中数值的二进制编码的宽度比特分别分成多个比特段，对每个比特段进行三态编码，生成该数值段的三态内容寻址内存器记录；对待匹配数值进行与数据段相同形式的三态编码，生成待匹配数值的三态内容寻址内存器记录，将待匹配数值的三态内容寻址内存器记录和数值段的三态内容寻址内存器记录进行匹配。
【IPC分类】H04L1/00, H04L29/06
【公开号】CN104901947
【申请号】CN201510172733
【发明人】彭义刚, 周志雄, 邹昕, 王锟, 李锐光, 汪锐, 孙昊良, 王子厚, 李晓倩, 张露晨
【申请人】国家计算机网络与信息安全管理中心, 北京恒光信息技术有限公司
【公开日】2015年9月9日
【申请日】2015年4月13日
【技术领域】
[0001] 本发明设及数据包处理技术领域，特别设及一种基于TCAM连续数值匹配方法和 装置。
【背景技术】
[0002] 高速数据包分类算法，在很多的网络应用领域中，变得越来越重要，例如，网络安 全应用、QoS服务过滤和网络负载均衡应用等。为了进行高速包分类，网络设备通常采用分 类数据库，其中包含多条A化(Access Control List,访问控制列表），每一条A化可能由多 条用于输入或者输出数据流的规则组成。
[0003] A化规则的数目在逐渐增多，可能要求上百万的规则；对A化规则的捜索速度也要 求越来越高，要求达到每秒上百万次的捜索能力。为满足该些要求，有很多的基于RAM的高 速数据包分类算法，例如，RFC算法、Hyper化ts算法等。然而，对于各种高速数据包分类算 法来说，毫无疑问地W基于TCAM的高速数据包分类算法的捜索速度最快。
[0004]CAM的英文全称为ContentAcMress油leMemo巧，即内容寻址内存。与普通的 SRAM、DDR等内存不同；普通内存通过输入地址得到数据；而CAM相反，通过输入数据得到数 据所在的地址。TCAM(即TernaryCAM)为S态CAM,不仅可W匹配二进制数"0"和"1"，还 可W通过掩码匹配任意值，也称为可匹配"X"。CAM的数据宽度通常可配置，如9字节、18字 节、36字节或72字节等。
[0005] 高速数据包的分类过程中需要对连续数值规则进行匹配，连续数值规则是指对 于某个匹配的域指定一个连续数值区域，例如W太网数据包的TCP端口连续数值为80~ 8000,然而使用TCAM直接进行匹配连续数值规则时，一条连续数值规则往往需要多条TCAM 表项才能存储，特别是当一条连续数值规则中有多个连续数值区域时，需要更多的TCAM表 项才能存储，使得TCAM存储的连续数值规则条数有限，使得降低了TCAM的利用率。
【发明内容】
[0006] 本发明实施例提供了一种基于TCAM连续数值匹配方法，W提高内容寻址内存器 的利用率。该方法包括：在连续数值区域内确定两个分界点数值，根据分界点数值将所述 连续数值区域划分为=个数值段，在该=个数值段中至少有一个数值段的两个端点数值符 合预设=态编码规则，在端点数值不符合预设=态编码规则的数值段内继续确定分界点数 值进行数据分段，直到每个数值段的端点数值都符合预设=态编码规则，形成多个数值段， 其中，所述预设=态编码规则使得对所述连续数值区域进行=态编码的结果与对所述连续 数值区域划分的多个数值段分别进行=态编码后相加的结果等效；对于符合所述预设=态 编码规则的两个端点数值，则将该两个端点数值之间的数值段中数值的二进制编码的宽度 比特分别分成多个比特段，分别对每个比特段的二进制编码对应的十进制数据进行=态编 码，生成该两个端点数值之间的数值段的=态内容寻址内存器记录，并将形成的=态内容 寻址内存器记录存入S态内容寻址内存器中；将待匹配数值的二进制编码的宽度比特划分 为所述多个比特段，对每个比特段的二进制编码对应的十进制数据进行=态编码，生成所 述待匹配数值的=态内容寻址内存器记录，将所述待匹配数值的=态内容寻址内存器记录 输入到所述=态内容寻址内存器中和数值段的=态内容寻址内存器记录进行匹配。
[0007]在一个实施例中，所述预设=态编码规则是将两个端点数值的二进制编码的宽度 比特分别分成所述多个比特段，对每个比特段的二进制编码对应的十进制数值进行=态编 码，所述两个端点数值中一个端点数值的第i个比特段的=态编码与另一个端点数值的第 i个比特段的=态编码不相同，且第i个比特段之前的比特段的=态编码对应相同，i是指 一个比特段在多个比特段中的序数，第i个比特段之前是指由i至序数减小的方向。
[000引在一个实施例中，在连续数值区域内确定两个分界点数值，根据分界点数值将所 述连续数值区域划分为=个数值段，包括：将所述连续数值区域的两个端点数值的二进制 编码的宽度比特分别分成所述多个比特段，分别对每个比特段的二进制编码对应的十进制 数据进行=态编码；按照比特位由高至低的顺序，对两个端点数值的多个比特段中序数对 应的比特段的=态编码进行比较，找到=态编码不相同的第i个比特段，且第i个比特段 之前的比特段的=态编码对应相同；对于两个端点数值中较小的端点数值，将第i个比特 段对应的十进制数值加1，对加1后的十进制数值进行=态编码，将第i个比特段之后的比 特段的=态编码均用掩码表示，将第i个比特段的=态编码和第i个比特段之前比特段的 =态编码还原为二进制编码，将第i个比特段之后比特段的=态编码还原的二进制编码的 0比特，将多个比特段的二进制编码相加得到一个二进制编码，确定该二进制编码对应的十 进制数值为两个分界点数值中较小的分界点数值；对于两个端点数值中较大的端点数值， 将第i个比特段对应的十进制数值减1，对减1后的十进制数值进行=态编码，将第i个比 特段之后的比特段的=态编码均用掩码表示，将第i个比特段的=态编码和第i个比特段 之前比特段的=态编码还原为二进制编码，将第i个比特段之后比特段的=态编码还原的 二进制编码的0比特，将多个比特段的二进制编码相加得到一个二进制编码，确定该二进 制编码对应的十进制数值为两个分界点数值中较大的分界点数值；根据确定的两个分界点 数值将所述连续数值区域划分为=个数值段，其中，所述两个分界点数值符合预设=态编 码规则，在所述=个数值段中允许对两个分界点数值之间形成的数据段进行=态编码，形 成内容寻址内存器记录。
[0009] 在一个实施例中，每个比特段的比特位数小于等于4。
[0010] 本发明实施例还提供了一种基于TCAM连续数值匹配装置，W提高内容寻址内存 器的利用率。该装置包括；数值划分模块，用于在连续数值区域内确定两个分界点数值，根 据分界点数值将所述连续数值区域划分为=个数值段，在该=个数值段中至少有一个数值 段的两个端点数值符合预设=态编码规则，在端点数值不符合预设=态编码规则的数值段 内继续确定分界点数值进行数据分段，直到每个数值段的端点数值都符合预设=态编码规 贝1J，形成多个数值段，其中，所述预设=态编码规则使得对所述连续数值区域进行=态编码 的结果与对所述连续数值区域划分的多个数值段分别进行=态编码后相加的结果等效；= 态编码模块，用于对于符合所述预设S态编码规则的两个端点数值，则将该两个端点数值 之间的数值段中数值的二进制编码的宽度比特分别分成多个比特段，分别对每个比特段的 二进制编码对应的十进制数据进行=态编码，生成该两个端点数值之间的数值段的=态内 容寻址内存器记录，并将形成的=态内容寻址内存器记录存入=态内容寻址内存器中；匹 配模块，用于将待匹配数值的二进制编码的宽度比特划分为所述多个比特段，对每个比特 段的二进制编码对应的十进制数据进行=态编码，生成所述待匹配数值的=态内容寻址内 存器记录，将所述待匹配数值的=态内容寻址内存器记录输入到所述=态内容寻址内存器 中和数值段的S态内容寻址内存器记录进行匹配。
[0011] 在一个实施例中，所述预设=态编码规则是将两个端点数值的二进制编码的宽度 比特分别分成所述多个比特段，对每个比特段的二进制编码对应的十进制数值进行=态编 码，所述两个端点数值中一个端点数值的第i个比特段的=态编码与另一个端点数值的第 i个比特段的=态编码不相同，且第i个比特段之前的比特段的=态编码对应相同，i是指 一个比特段在多个比特段中的序数，第i个比特段之前是指由i至序数减小的方向。
[0012] 在一个实施例中，所述数值划分模块，包括：比特段划分单元，用于将所述连续数 值区域的两个端点数值的二进制编码的宽度比特分别分成所述多个比特段，分别对每个比 特段的二进制编码对应的十进制数据进行=态编码；比较单元，用于按照比特位由高至低 的顺序，对两个端点数值的多个比特段中序数对应的比特段的=态编码进行比较，找到= 态编码不相同的第i个比特段，且第i个比特段之前的比特段的=态编码对应相同；第一分 界点数值确定单元，用于对于两个端点数值中较小的端点数值，将第i个比特段对应的十 进制数值加1，对加1后的十进制数值进行=态编码，将第i个比特段之后的比特段的=态 编码均用掩码表示，将第i个比特段的=态编码和第i个比特段之前比特段的=态编码还 原为二进制编码，将第i个比特段之后比特段的S态编码还原的二进制编码的0比特，将多 个比特段的二进制编码相加得到一个二进制编码，确定该二进制编码对应的十进制数值为 两个分界点数值中较小的分界点数值；第二分界点数值确定单元，用于对于两个端点数值 中较大的端点数值，将第i个比特段对应的十进制数值减1，对减1后的十进制数值进行= 态编码，将第i个比特段之后的比特段的=态编码均用掩码表示，将第i个比特段的=态编 码和第i个比特段之前比特段的=态编码还 原为二进制编码，将第i个比特段之后比特段 的=态编码还原的二进制编码的0比特，将多个比特段的二进制编码相加得到一个二进制 编码，确定该二进制编码对应的十进制数值为两个分界点数值中较大的分界点数值；数值 划分单元，用于根据确定的两个分界点数值将所述连续数值区域划分为=个数值段，其中， 所述两个分界点数值符合预设=态编码规则，在所述=个数值段中允许对两个分界点数值 之间形成的数据段进行=态编码，形成内容寻址内存器记录。
[0013] 在一个实施例中，每个比特段的比特位数小于等于4。
[0014] 在本发明实施例中，通过将连续数值区域划分为多个数值段，并分别对多个数值 段进行=态编码，来实现对连续数值区域进行=态编码，实现了W更多的TCAM记录来换取 更小的编码位宽，使得有利于充分利用=态内容寻址内存器中表项的空闲比特，可W存储 更多的连续数值区域编码，再通过将编码后的待匹配数值输入到所述=态内容寻址内存器 中与=态内容寻址内存器记录进行匹配，在确保容寻址内存器快速捜索速度的同时，还可 W提高内容寻址内存器的利用率。
【附图说明】
[0015] 此处所说明的附图用来提供对本发明的进一步理解，构成本申请的一部分，并不 构成对本发明的限定。在附图中：
[0016] 图1是本发明实施例提供的一种基于TCAM连续数值匹配方法的流程图；
[0017]图2是本发明实施例提供的一种基于TCAM连续数值匹配装置的结构框图。
【具体实施方式】
[0018] 为使本发明的目的、技术方案和优点更加清楚明白，下面结合实施方式和附图，对 本发明做进一步详细说明。在此，本发明的示意性实施方式及其说明用于解释本发明，但并 不作为对本发明的限定。
[0019] 在本发明实施例中，提供了一种基于TCAM连续数值匹配方法，如图1所示，该方法 包括：
[0020] 步骤101 ;在连续数值区域内确定两个分界点数值，根据分界点数值将所述连续 数值区域划分为=个数值段，在该=个数值段中至少有一个数值段的两个端点数值符合预 设=态编码规则，在端点数值不符合预设=态编码规则的数值段内继续确定分界点数值进 行数据分段，直到每个数值段的端点数值都符合预设=态编码规则，形成多个数值段，其 中，所述预设=态编码规则使得对所述连续数值区域进行=态编码的结果与对所述连续数 值区域划分的多个数值段分别进行=态编码后相加的结果等效；
[002U 步骤102 ;对于符合所述预设S态编码规则的两个端点数值，则将该两个端点数 值之间的数值段中数值的二进制编码的宽度比特分别分成多个比特段，分别对每个比特段 的二进制编码对应的十进制数据进行=态编码，生成该两个端点数值之间的数值段的=态 内容寻址内存器记录，并将形成的=态内容寻址内存器记录存入=态内容寻址内存器TCAM 中；
[0022] 步骤103;将待匹配数值的二进制编码的宽度比特划分为所述多个比特段，对每 个比特段的二进制编码对应的十进制数据进行=态编码，生成所述待匹配数值的=态内容 寻址内存器记录，将所述待匹配数值的=态内容寻址内存器记录输入到所述TCAM中和数 值段的S态内容寻址内存器记录进行匹配。
[0023] 由图1所示的流程可知，在本发明实施例中，通过将连续数值区域划分为多个数 值段，并分别对多个数值段进行=态编码，来实现对连续数值区域进行=态编码，实现了W 更多的TCAM记录来换取更小的编码位宽，使得有利于充分利用=态内容寻址内存器中表 项的空闲比特，可W存储更多的连续数值区域编码，再通过将编码后的待匹配数值输入到 所述=态内容寻址内存器中与=态内容寻址内存器记录进行匹配，在确保容寻址内存器快 速捜索速度的同时，还可W提高内容寻址内存器的利用率。
[0024] 具体实施时，为了使得直接对所述连续数值区域进行=态编码的结果与对多个数 值段分别进行=态编码的结果等效，在本实施例中，所述预设=态编码规则是将两个端点 数值的二进制编码的宽度比特分别分成所述多个比特段，对每个比特段的二进制编码对应 的十进制数值进行=态编码，所述两个端点数值中一个端点数值的第i个比特段的=态编 码与另一个端点数值的第i个比特段的=态编码不相同，且第i个比特段之前的比特段的 =态编码对应相同，i是指一个比特段在多个比特段中的序数，第i个比特段之前是指由i 至序数减小的方向。
[0025] 具体的，为了尽量减少编码位宽，上述比特段的比特位数小于等于4,例如，对于连 续数值区域的位宽为16时，可W将16划分为7个比特段，各比特段的比特数分别是；3、3、 2、2、2、2、2 ;还可W将16划分为5个比特段，各比特段的比特数分别是；3、3、4、2、4。具体 的，基于通过TCAM的=态编码，可W将一个位宽为k的连续数值区域，编码为一条位宽为 化-1的TCAM记录。具体的编码方法如下表1所示；
[0026] 表 1
[0027]
[002引其中，0{2k-i-l}表示有连续化-i-1个0，l{i}表示有连续i个1，x{2k-i-l}表 示有连续化-i-1个X，其它表示方法类似；k为连续数值区域的比特宽度，i和j是连续数 值区域中的任意数值。例如W端口号为例，宽度为16比特，则k的值为16。具体的，一个位 宽为4的连续数值区域=态编码后变为15位，具体的编码结果如下表2所示：
[0029] 表2
[0030]
[003。 在具体实施时I，为了将连续数值区域划分为多个数值段，分别对数值段进行=态 编码W减少编码位宽，在本实施例中，在连续数值区域内确定两个分界点数值，根据分界点 数值将所述连续数值区域划分为=个数值段，包括：将所述连续数值区域的两个端点数值 的二进制编码的宽度比特分别分成多个比特段，分别对每个比特段的二进制编码对应的十 进制数据进行=态编码；按照比特位由高至低的顺序，对两个端点数值的多个比特段中序 数对应的比特段的=态编码进行比较，找到=态编码不相同的第i个比特段，且第i个比特 段之前的比特段的=态编码对应相同；对于两个端点数值中较小的端点数值，将第i个比 特段对应的十进制数值加1，对加1后的十进制数值进行=态编码，将第i个比特段之后的 比特段的=态编码均用掩码表示，将第i个比特段的=态编码和第i个比特段之前比特段 的=态编码还原为二进制编码，将第i个比特段之后比特段的=态编码还原的二进制编码 的0比特，将多个比特段的二进制编码相加得到一个二进制编码，确定该二进制编码对应 的十进制数值为两个分界点数值中较小的分界点数值；对于两个端点数值中较大的端点数 值，将第i个比特段对应的十进制数值减1，对减1后的十进制数值进行=态编码，将第i个 比特段之后的比特段的=态编码均用掩码表示，将第i个比特段的=态编码和第i个比特 段之前比特段的=态编码还原为二进制编码，将第i个比特段之后比特段的=态编码还原 的二进制编码的0比特，将多个比特段的二进制编码相加得到一个二进制编码，确定该二 进制编码对应的十进制数值为两个分界点数值中较大的分界点数值；根据确定的两个分界 点数值将所述连续数值区域划分为=个数值段，其中，所述两个分界点数值符合预设=态 编码规则，在所述=个数值段中允许对两个分界点数值之间形成的数据段进行=态编码， 形成=态内容寻址内存器记录。
[003引具体的，W连续数值区域R= [12, 241]，宽度为8位为例，具体的划分数值段和数 值匹配过程如下：
[003引首先，位宽8的分段方式为2、3、3,分成3个比特段，则3个比特段的S态编码宽度 分别为；3、7、7 ;
[0034] 即将两个端点数值12和241的二进制编码位宽划分为比特段表示为：
[0035] 8=12={00,001，100}，其中，3个比特段分别为00、001和100;
[0036] 6 = 241={11，110,001}，其中，3个比特段分别为11、110和001;
[0037] 对S和e的比特段分别进行S态编码，变为：
[003引S，= {000,0000001，0001111}
[0039] e' =山1，0111111，0011111}
[0040] 其次，按照比特位由高至低的顺序，对两个端点数值的多个比特段中序数对应的 比特段的=态编码进行比较，即对s'和e'的对应比特段编码进行比较，s'和e'对应的 第1个比特段编码不相等，则将s'的第1个比特段对应的十进制数值加1后进行S态编 码，第1个比特段之后的比特段的立态编码用掩码表示，即{001，XXXXXXX,xxxxxxx}，该 (001,xxxxxxx,xxxxxxx}还原为二进制编码后为{01，000,000}，该{01，000,000}对应的十 进制数为64,因此，64是两个分界点数值中较小的分界点数值，则将e'的第1个比特段对 应的十进制数值减 1后进行=态编码，第1个比特段之后的比特段的=态编码用掩码表示， 良P(011,XXXXXXX,xxxxxxx}，该（011,XXXXXXX,xxxxxxx}还原为二进制编码后为（10,000， 000}，该{10,000,000}对应的十进制数为128,因此，128是两个分界点数值中较大的分界 点数值，因此，上述连续数值区域R被分界点数值64和128划分为=个数值段，该=个数值 段的=态编码形式如下：
[0041] R1 = [ {001, xxxxxxx, xxxxxxx}, {Oil, xxxxxxx, xxxxxxx}]
[0042] Rii=[{000,0000001，0001111}，{000, 1111111，mini}]
[0043] R12 = [{111, 0000000, 0000000}，{000,0111111，0011111}]
[0044] R1即是两个分界点数值之间形成的数值段，可W编码为一条TCAM记录：
[0045] R1，= (0x1, xxxxxxx, xxxxxxx}
[0046] 进行第2次划分，Rll可W分为如下两段：
[0047] R2s=[{000,0000011,xxxxxxx},{000, 1111111,xxxxxxx}]
[0048] R21 =[{000, 0000001，0001111}，{000, 0000001，mini}]
[0049] R2s可W编码为一条TCAM记录；
[0化0] R2s，= {OOO'xxxxxll, xxxxxxx}
[0化1] R12可w分为如下两段：
[0052] R2e =[{111, 0000000, xxxxxxx} ,{000, 0011111, xxxxxxx}]
[0053] R22 = [{111,0111111，0000000}，{000,0111111，0011111}]
[0054] R2e可W编码为一条TCAM记录；
[0化5] R2e，= (111, OOxxxxx, xxxxxxx}
[0化6] 进行第3次划分，由于已经是最后一次划分，直接对最后的R21和R22编码即可。
[0化7] R21可W编码为一条TCAM记录；
[005引 R21' = {000,0000001，xxxllll}
[0059] R22可W编码为一条TCAM记录；
[0060] R22, = {000,0111111，OOxxxxx}
[0061] 分段编码完成，上述连续数值区域R的TCAM记录如下表3所示为：
[0062]表3
[0063]
[0064] 最后，假设待匹配数值key= 30,按照分段方式2、3、3对key的位宽比特进行分 段：
[00化]K巧=30 = {00,011，110}
[0066] 对key的各个比特段进S态编码；
[0067] Key，= {000,0000111，0111111}
[0068] 将编码后的key送入TCAM表中进行匹配，匹配结果会命中连续数值区域R的TCAM 记录中R2s的TCAM记录，因而匹配成功。即编码后的key与连续数值区域R的TCAM记录 中任意一条记录匹配成功，即数值匹配成功。
[0069] 基于同一发明构思，本发明实施例中还提供了一种基于TCAM连续数值匹配装置， 如下面的实施例所述。由于基于TCAM连续数值匹配装置解决问题的原理与基于TCAM连续 数值匹配方法相似，因此基于TCAM连续数值匹配装置的实施可W参见基于TCAM连续数值 匹配方法的实施，重复之处不再寶述。W下所使用的，术语"单元"或者"模块"可W实现预 定功能的软件和/或硬件的组合。尽管W下实施例所描述的装置较佳地W软件来实现，但 是硬件，或者软件和硬件的组合的实现也是可能并被构想的。
[0070] 图2是本发明实施例的基于TCAM连续数值匹配装置的一种结构框图，如图2所 示，包括；数值划分模块201、=态编码模块202和匹配模块203,下面对该结构进行说明。
[0071] 数值划分模块201，用于在连续数值区域内确定两个分界点数值，根据分界点数值 将所述连续数值区域划分为=个数值段，在该=个数值段中至少有一个数值段的两个端点 数值符合预设=态编码规则，在端点数值不符合预设=态编码规则的数值段内继续确定分 界点数值进行数据分段，直到每个数值段的端点数值都符合预设=态编码规则，形成多个 数值段，其中，所述预设=态编码规则使得对所述连续数值区域进行=态编码的结果与对 所述连续数值区域划分的多个数值段分别进行=态编码后相加的结果等效；
[0072]=态编码模块202,与数值划分模块201连接，用于对于符合所述预设=态编码规 则的两个端点数值，则将该两个端点数值之间的数值段中数值的二进制编码的宽度比特分 别分成多个比特段，分别对每个比特段的二进制编码对应的十进制数据进行=态编码，生 成该两个端点数值之间的数值段的=态内容寻址内存器记录，并将形成的=态内容寻址内 存器记录存入=态内容寻址内存器中；
[0073] 匹配模块203,与S态编码模块202连接，用于将待匹配数值的二进制编码的宽 度比特划分为所述多个比特段，对每个比特段的二进制编码对应的十进制数据进行=态编 码，生成所述待匹配数值的=态内容寻址内存器记录，将所述待匹配数值的=态内容寻址 内存器记录输入到所述=态内容寻址内存器中和数值段的=态内容寻址内存器记录进行 匹配。
[0074] 在一个实施例中，所述数值划分模块201，包括；比特段划分单元，用于将所述连 续数值区域的两个端点数值的二进制编码的宽度比特分别分成所述多个比特段，分别对每 个比特段的二进制编码对应的十进制数据进行=态编码；比较单元，与比特段划分单元连 接，用于按照比特位由高至低的顺序，对两个端点数值的多个比特段中序数对应的比特段 的=态编码进行比较，找到=态编码不相同的第i个比特段，且第i个比特段之前的比特段 的=态编码对应相同；第一分界点数值确定单元，与比较单元连接，用于对于两个端点数值 中较小的端点数值，将第i个比特段对应的十进制数值加1，对加1后的十进制数值进行= 态编码，将第i个比特段之后的比特段的=态编码均用掩码表示，将第i个比特段的=态编 码和第i个比特段之前比特段的=态编码还原为二进制编码，将第i个比特段之后比特段 的=态编码还原的二进制编码的0比特，将多个比特段的二进制编码相加得到一个二进制 编码，确定该二进制编码对应的十进制数值为两个分界点数值中较小的分界点数值；第二 分界点数值确定单元，与第一分界点数值确定单元连接，用于对于两个端点数值中较大的 端点数值，将第i个比特段对应的十进制数值减1，对减1后的十进制数值进行=态编码， 将第i个比特段之后的比特段的=态编码均用掩码表示，将第i个比特段的=态编码和第 i个比特段之前比特段的=态编码还原为二进制编码，将第i个比特段之后比特段的=态 编码还原的二进制编码的0比特，将多个比特段的二进制编码相加得到一个二进制编码， 确定该二进制编码对应的十进制数值为两个分界点数值中较大的分界点数值；数值划分单 元，与第二分界点数值确定单元连接，用于根据确定的两个分界点数值将所述连续数值区 域划分为=个数值段，其中，所述两个分界点数值符合预设=态编码规则，在所述=个数值 段中允许对两个分界点数值之间形成的数据段进行=态编码，形成=态内容寻址内存器记 录。
[0075] 在一个实施例中，每个比特段的比特位数小于等于4。
[0076] 在本发明实施例中，通过将连续数值区域划分为多个数值段，并分别对多个数值 段进行=态编码，来实现对连续数值区域进行=态编码，实现了W更多的TCAM记录来换取 更小的编码位宽，使得有利于充分利用=态内容寻址内存器中表项的空闲比特，可W存储 更多的连续数值区域编码，再通过将编码后的待匹配数值输入到所述=态内容寻址内存器 中与=态内容寻址内存器记录进行匹配，在确保容寻址内存器快速捜索速度的同时，还可 W提高内容寻址内存器的利用率。
[0077]显然，本领域的技术人员应该明白，上述的本发明实施例的各模块或各步骤可W 用通用的计算装置来实现，它们可W集中在单个的计算装置上，或者分布在多个计算装置 所组成的网络上，可选地，它们可W用计算装置可执行的程序代码来实现，从而，可W将它 们存储在存储装置中由计算装置来执行，并且在某些情况下，可WW不同于此处的顺序执 行所示出或描述的步骤，或者将它们分别制作成各个集成电路模块，或者将它们中的多个 模块或步骤制作成单个集成电路模块来实现。该样，本发明实施例不限制于任何特定的硬 件和软件结合。
[007引W上所述仅为本发明的优选实 施例而已，并不用于限制本发明，对于本领域的技 术人员来说，本发明实施例可W有各种更改和变化。凡在本发明的精神和原则之内，所作的 任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。
【主权项】
1. 一种基于TCAM连续数值匹配方法，其特征在于，包括： 在连续数值区域内确定两个分界点数值，根据分界点数值将所述连续数值区域划分 为三个数值段，在该三个数值段中至少有一个数值段的两个端点数值符合预设三态编码规 贝1J，在端点数值不符合预设三态编码规则的数值段内继续确定分界点数值进行数据分段， 直到每个数值段的端点数值都符合预设三态编码规则，形成多个数值段，其中，所述预设三 态编码规则使得对所述连续数值区域进行三态编码的结果与对所述连续数值区域划分的 多个数值段分别进行三态编码后相加的结果等效； 对于符合所述预设三态编码规则的两个端点数值，则将该两个端点数值之间的数值段 中数值的二进制编码的宽度比特分别分成多个比特段，分别对每个比特段的二进制编码对 应的十进制数据进行三态编码，生成该两个端点数值之间的数值段的三态内容寻址内存器 记录，并将形成的三态内容寻址内存器记录存入三态内容寻址内存器TCAM中； 将待匹配数值的二进制编码的宽度比特划分为所述多个比特段，对每个比特段的二 进制编码对应的十进制数据进行三态编码，生成所述待匹配数值的三态内容寻址内存器记 录，将所述待匹配数值的三态内容寻址内存器记录输入到所述TCAM中和数值段的三态内 容寻址内存器记录进行匹配。2. 如权利要求1所述的方法，其特征在于，所述预设三态编码规则是将两个端点数值 的二进制编码的宽度比特分别分成所述多个比特段，对每个比特段的二进制编码对应的十 进制数值进行三态编码，所述两个端点数值中一个端点数值的第i个比特段的三态编码与 另一个端点数值的第i个比特段的三态编码不相同，且第i个比特段之前的比特段的三态 编码对应相同，i是指一个比特段在多个比特段中的序数，第i个比特段之前是指由i至序 数减小的方向。3. 如权利要求2所述的方法，其特征在于，在连续数值区域内确定两个分界点数值，根 据分界点数值将所述连续数值区域划分为三个数值段，包括： 将所述连续数值区域的两个端点数值的二进制编码的宽度比特分别分成所述多个比 特段，分别对每个比特段的二进制编码对应的十进制数据进行三态编码； 按照比特位由高至低的顺序，对两个端点数值的多个比特段中序数对应的比特段的三 态编码进行比较，找到三态编码不相同的第i个比特段，且第i个比特段之前的比特段的三 态编码对应相同； 对于两个端点数值中较小的端点数值，将第i个比特段对应的十进制数值加1，对加1 后的十进制数值进行三态编码，将第i个比特段之后的比特段的三态编码均用掩码表示， 将第i个比特段的三态编码和第i个比特段之前比特段的三态编码还原为二进制编码，将 第i个比特段之后比特段的三态编码还原的二进制编码的O比特，将多个比特段的二进制 编码相加得到一个二进制编码，确定该二进制编码对应的十进制数值为两个分界点数值中 较小的分界点数值； 对于两个端点数值中较大的端点数值，将第i个比特段对应的十进制数值减1，对减1 后的十进制数值进行三态编码，将第i个比特段之后的比特段的三态编码均用掩码表示， 将第i个比特段的三态编码和第i个比特段之前比特段的三态编码还原为二进制编码，将 第i个比特段之后比特段的三态编码还原的二进制编码的O比特，将多个比特段的二进制 编码相加得到一个二进制编码，确定该二进制编码对应的十进制数值为两个分界点数值中 较大的分界点数值； 根据确定的两个分界点数值将所述连续数值区域划分为三个数值段，其中，所述两个 分界点数值符合预设三态编码规则，在所述三个数值段中允许对两个分界点数值之间形成 的数据段进行三态编码，形成三态内容寻址内存器记录。4. 如权利要求1至3中任一项所述的方法，其特征在于，每个比特段的比特位数小于等 于4。5. -种基于TCAM连续数值匹配装置，其特征在于，包括： 数值划分模块，用于在连续数值区域内确定两个分界点数值，根据分界点数值将所述 连续数值区域划分为三个数值段，在该三个数值段中至少有一个数值段的两个端点数值符 合预设三态编码规则，在端点数值不符合预设三态编码规则的数值段内继续确定分界点数 值进行数据分段，直到每个数值段的端点数值都符合预设三态编码规则，形成多个数值段， 其中，所述预设三态编码规则使得对所述连续数值区域进行三态编码的结果与对所述连续 数值区域划分的多个数值段分别进行三态编码后相加的结果等效； 三态编码模块，用于对于符合所述预设三态编码规则的两个端点数值，则将该两个端 点数值之间的数值段中数值的二进制编码的宽度比特分别分成多个比特段，分别对每个比 特段的二进制编码对应的十进制数据进行三态编码，生成该两个端点数值之间的数值段的 三态内容寻址内存器记录，并将形成的三态内容寻址内存器记录存入三态内容寻址内存器 TCAM中； 匹配模块，用于将待匹配数值的二进制编码的宽度比特划分为所述多个比特段，对每 个比特段的二进制编码对应的十进制数据进行三态编码，生成所述待匹配数值的三态内容 寻址内存器记录，将所述待匹配数值的三态内容寻址内存器记录输入到所述TCAM中和数 值段的三态内容寻址内存器记录进行匹配。6. 如权利要求5所述的装置，其特征在于，所述预设三态编码规则是将两个端点数值 的二进制编码的宽度比特分别分成所述多个比特段，对每个比特段的二进制编码对应的十 进制数值进行三态编码，所述两个端点数值中一个端点数值的第i个比特段的三态编码与 另一个端点数值的第i个比特段的三态编码不相同，且第i个比特段之前的比特段的三态 编码对应相同，i是指一个比特段在多个比特段中的序数，第i个比特段之前是指由i至序 数减小的方向。7. 如权利要求6所述的装置，其特征在于，所述数值划分模块，包括： 比特段划分单元，用于将所述连续数值区域的两个端点数值的二进制编码的宽度比特 分别分成所述多个比特段，分别对每个比特段的二进制编码对应的十进制数据进行三态编 码； 比较单元，用于按照比特位由高至低的顺序，对两个端点数值的多个比特段中序数对 应的比特段的三态编码进行比较，找到三态编码不相同的第i个比特段，且第i个比特段之 前的比特段的三态编码对应相同； 第一分界点数值确定单元，用于对于两个端点数值中较小的端点数值，将第i个比特 段对应的十进制数值加1，对加1后的十进制数值进行三态编码，将第i个比特段之后的比 特段的三态编码均用掩码表示，将第i个比特段的三态编码和第i个比特段之前比特段的 三态编码还原为二进制编码，将第i个比特段之后比特段的三态编码还原的二进制编码的 O比特，将多个比特段的二进制编码相加得到一个二进制编码，确定该二进制编码对应的十 进制数值为两个分界点数值中较小的分界点数值； 第二分界点数值确定单元，用于对于两个端点数值中较大的端点数值，将第i个比特 段对应的十进制数值减1，对减1后的十进制数值进行三态编码，将第i个比特段之后的比 特段的三态编码均用掩码表示，将第i个比特段的三态编码和第i个比特段之前比特段的 三态编码还原为二进制编码，将第i个比特段之后比特段的三态编码还原的二进制编码的 O比特，将多个比特段的二进制编码相加得到一个二进制编码，确定该二进制编码对应的十 进制数值为两个分界点数值中较大的分界点数值； 数值划分单元，用于根据确定的两个分界点数值将所述连续数值区域划分为三个数值 段，其中，所述两个分界点数值符合预设三态编码规则，在所述三个数值段中允许对两个分 界点数值之间形成的数据段进行三态编码，形成三态内容寻址内存器记录。8.如权利要求5至7中任一项所述的装置，其特征在于，每个比特段的比特位数小于等 于4。
【专利摘要】本发明实施例提供一种基于TCAM连续数值匹配方法和装置，该方法包括：根据分界点数值将连续数值区域划分为三个数值段，在该三个数值段中至少有一个数值段的两个端点数值符合预设三态编码规则，在端点数值不符合预设三态编码规则的数值段内继续确定分界点数值进行数据分段；对于符合预设三态编码规则的两个端点数值，将该两个端点数值之间的数值段中数值的二进制编码的宽度比特分别分成多个比特段，对每个比特段进行三态编码，生成该数值段的三态内容寻址内存器记录；对待匹配数值进行与数据段相同形式的三态编码，生成待匹配数值的三态内容寻址内存器记录，将待匹配数值的三态内容寻址内存器记录和数值段的三态内容寻址内存器记录进行匹配。
【IPC分类】H04L1/00, H04L29/06
【公开号】CN104901947
【申请号】CN201510172733
【发明人】彭义刚, 周志雄, 邹昕, 王锟, 李锐光, 汪锐, 孙昊良, 王子厚, 李晓倩, 张露晨
【申请人】国家计算机网络与信息安全管理中心, 北京恒光信息技术有限公司
【公开日】2015年9月9日
【申请日】2015年4月13日
最新回复(0)