(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211004515.X (22)申请日 2022.08.22 (71)申请人 烽火通信科技股份有限公司 地址 430000 湖北省武汉市东湖高新 技术 开发区高新四路6号 申请人 武汉飞思灵微电子技 术有限公司 (72)发明人 王婷婷　杨彦波　鲁鹏　 (74)专利代理 机构 深圳市六加知识产权代理有 限公司 4 4372 专利代理师 张甲一 (51)Int.Cl. G06F 16/2453(2019.01) G06F 16/2455(2019.01) G06F 16/22(2019.01) H04L 47/2441(2022.01) (54)发明名称 一种流分类时关键 字匹配的方法和装置 (57)摘要 本发明涉及通信技术领域， 特别是涉及一种 流分类时关键字匹配的方法和装置。 主要包括： 将需要进行匹配的关键字组成二维查表结构， 每 个表项对应一个 关键字类型且具有唯一的表号， 二维查表结构的行数和列数与关键字类型的数 量对应， 第一行为全部关键字类型的级联， 后续 每一行依次去掉前一行的第一个表项； 获取数据 包中的关键字， 每一行依次向后逐列匹配二维查 表结构中的对应表项或同时匹配对应表项和借 用表项； 当关键字对应的表项和/或借用的表项 击中时， 通过关键字对应的行为表确定后续执行 的动作， 直至完成查找。 本发明在多个关键字随 意组合匹配的场景下尽可能的加快匹配速度， 并 节省表项的存 储资源。 权利要求书2页 说明书10页 附图4页 CN 115374147 A 2022.11.22 CN 115374147 A 1.一种流分类时关键 字匹配的方法， 其特 征在于： 将需要进行匹配的关键字组成二维查表结构， 每个表项对应一个关键字类型且具有唯 一的表号， 二维查表结构的行数和列数与关键字类型 的数量对应， 第一行为全部关键字类 型的级联， 后续每一行依次去掉前一行的第一个表项； 获取数据包中的关键字， 每一行依次向后逐列匹配二维查表结构中的对应表项或同时 匹配对应表项和借用表项； 当关键字对应的表项和/或借用的表项击中时， 通过关键字对应的行为表确定后续执 行的动作， 直至 完成查找。 2.根据权利要求1所述的流分类时关键字匹配的方法， 其特征在于， 所述将需要进行匹 配的关键 字组成二维查表结构， 具体包括： 将所有需匹配的关键字级联根据位宽由小到大和优先级由高到低的顺序排列， 每组关 键字依次作为第一行的一个表项； 自第二行起， 每行依次去掉上一行的第一组关键 字， 直至最后一行仅有一组关键 字。 3.根据权利要求1所述的流分类时关键字匹配的方法， 其特征在于， 所述将需要进行匹 配的关键 字组成二维查表结构， 还 包括： 当新增关键字时， 将新增的关键字根据位宽由小到大和优先级由高到低插入每一行对 应的位置， 并按照新增关键 字的数量和位置增 加相应的行 数； 当删除关键 字时， 在每一行中删除对应的表项， 并删除相应的行 数。 4.根据权利要求1所述的流分类时关键字匹配的方法， 其特征在于， 所述每一行依次向 后逐列匹配二维查表结构中的对应表项或同时匹配对应表项和借用表项， 具体包括： 按照每一行表项对应的关键字顺序， 由每一行的第一个表项开始， 计算当前表项对应 的关键字的哈希值， 根据哈希值对表项 进行匹配查找； 根据查表结果击 中的行为表项判断下一级查找是否 需要进行表项借用， 同步查找对应 的表项和借用表项。 5.根据权利要求4所述的流分类时关键字匹配的方法， 其特征在于， 所述根据查表结果 击中的行为表项判断下一级查找是否需要 进行表项借用， 还 包括： 向比本次查找的关键字位宽大或者相等的关键字对应的表项借用， 若一个关键字的位 宽小于预设位宽下限， 对应的表项不被其它表项借用。 6.根据权利要求1所述的流分类时关键字匹配的方法， 其特征在于， 所述每一行依次向 后逐列匹配二维查表结构中的对应表项或同时匹配对应表项和借用表项， 还 包括： 对于每个表项， 需要匹配的关键字内容为： {表号， {前级击中的表号， 前级击中的槽位 编号， 前级哈希值}， 本次查找的关键 字}； 当用于匹配的表项为借用表时， 所述表号 为本次查找关键 字原本的表号。 7.根据权利要求6所述的流分类时关键字匹配的方法， 其特征在于， 所述需要 匹配的关 键字内容还 包括： 将{前级击中的表号， 前级击 中的槽位编号， 前级哈希值}进行归一化处理， 以最大需求 位宽作为归一 化处理后的位宽 。 8.根据权利要求1所述的流分类时关键字匹配的方法， 其特征在于， 所述每一行依次向 后逐列匹配二维查表结构中的对应表项和借用表项， 还 包括：权　利　要　求　书 1/2 页 2 CN 115374147 A 2每个表项被借用的最大次数为处 理一个数据包的拍数减一。 9.根据权利要求1所述的流分类时关键字匹配的方法， 其特征在于， 所述通过关键字对 应的行为表确定后续执 行的动作， 具体包括： 当关键字同时击中多个表项时， 根据行为表项中的优先级确定最终的查表结果。 10.一种流分类时关键 字匹配的装置， 其特 征在于： 包括至少一个处理器和存储器， 所述至少一个处理器和存储器之间通过数据总线连 接， 所述存储器存储能被所述至少一个处理器执行 的指令， 所述指令在被所述处理器执行 后， 用于完成权利要求1 ‑9中任一项所述的流分类时关键 字匹配的方法。权　利　要　求　书 2/2 页 3 CN 115374147 A 3