多分支跳转协处理方法及装置转让专利
申请号 : CN202010717565.7
文献号 : CN112039782B
文献日 : 2022-01-18
发明人 : 钟汝刚 , 李顺方 , 亚里夫·布里马 , 尤尼·比克
申请人 : 华为技术有限公司
摘要 :
权利要求 :
1.一种多分支跳转协处理方法,所述方法应用于交换机或者路由器,所述交换机或者所述路由器包括:第一网络处理器、第二网络处理器、协处理器和三态内容寻址存储器TCAM,其中所述TCAM按照待处理业务被逻辑划分为N个子TCAM,所述N为大于或者等于2的正整数,前N‑1个子TCAM中的每个子TCAM中包括至少一条TCAM条目,所述每个子TCAM中的至少一条TCAM条目存在一个收敛节点,且所述收敛节点为所述每个子TCAM的下一个子TCAM中的至少一条TCAM条目的起始节点,以及所述收敛节点为所述每个子TCAM中的至少一条TCAM条目中的每条TCAM条目的最后一个条件节点的下一个条件节点;或者,所述收敛节点为所述每个子TCAM中的至少一条TCAM条目中的每条TCAM条目的最后一个条件节点,以及所述收敛节点为所述每个子TCAM的下一个子TCAM中的至少一条TCAM条目的起始节点的前一个条件节点;所述方法包括:
所述第一网络处理器获取分支跳转条件,并将所述分支跳转条件发送给所述协处理器,其中所述分支跳转条件包括N条分支跳转子条件,所述分支跳转子条件与所述子TCAM一一对应;
所述协处理器对每个子TCAM对应的分支跳转子条件和每个子TCAM中的TCAM条目进行匹配,确定匹配成功的至少一条TCAM条目;
所述协处理器根据所述匹配成功的至少一条TCAM条目确定静态随机存储器SRAM地址;
所述协处理器将所述SRAM地址发送给所述第二网络处理器;
所述第二网络处理器根据所述SRAM地址确定待执行动作对应的存储地址,并执行所述存储地址对应的所述待执行动作。
2.根据权利要求1所述的方法,其特征在于,若所述分支跳转条件最多包括M个条件节点,每个条件节点取值为第一数值或者第二数值,所述M为大于或者等于2的正整数,则每条TCAM条目也包括M项数值,每项数值为所述第一数值、所述第二数值和第三数值中的任一项;
当任一分支跳转子条件中的条件节点取所述第一数值,且所述任一分支跳转子条件对应的子TCAM中存在至少一条TCAM条目对应位置的数值为所述第一数值或者所述第三数值时,则表示所述任一分支跳转子条件中的条件节点匹配成功;
当所述任一分支跳转子条件中的条件节点取所述第二数值,且所述任一分支跳转子条件对应的子TCAM中存在至少一条TCAM条目对应位置的数值为所述第二数值或者所述第三数值时,则表示所述任一分支跳转子条件中的条件节点匹配成功;
当所述任一分支跳转子条件中的每个条件节点和任一条TCAM条目对应位置的数值匹配成功,则表示所述任一分支跳转子条件和所述任一条TCAM条目匹配成功。
3.根据权利要求2所述的方法,其特征在于,所述协处理器根据所述匹配成功的至少一条TCAM条目确定静态随机存储器SRAM地址,包括:所述协处理器在所述至少一条TCAM条目中,确定与每个子TCAM对应的分支跳转子条件中的每个条件节点取值相同的TCAM条目;
所述协处理器确定所述取值相同的TCAM条目对应的SRAM地址为所述SRAM地址。
4.根据权利要求1或2所述的方法,其特征在于,还包括:所述协处理器获取所述子TCAM的划分信息,所述划分信息包括:所述收敛节点的个数和所述收敛节点的位置信息;
所述协处理器根据所述子TCAM的划分信息确定所述分支跳转条件的分割节点,并根据所述分割节点对所述分支跳转条件进行划分,获得所述N条分支跳转子条件。
5.一种多分支跳转协处理装置,所述装置包括:第一网络处理器、第二网络处理器、协处理器和三态内容寻址存储器TCAM,其中所述TCAM按照待处理业务被逻辑划分为N个子TCAM,所述N为大于或者等于2的正整数,前N‑1个子TCAM中的每个子TCAM中包括至少一条TCAM条目,所述每个子TCAM中的至少一条TCAM条目存在一个收敛节点,且所述收敛节点为所述每个子TCAM的下一个子TCAM中的至少一条TCAM条目的起始节点,以及所述收敛节点为所述每个子TCAM中的至少一条TCAM条目中的每条TCAM条目的最后一个条件节点的下一个条件节点;或者,所述收敛节点为所述每个子TCAM中的至少一条TCAM条目中的每条TCAM条目的最后一个条件节点,以及所述收敛节点为所述每个子TCAM的下一个子TCAM中的至少一条TCAM条目的起始节点的前一个条件节点;
所述第一网络处理器用于获取分支跳转条件,并将所述分支跳转条件发送给所述协处理器,其中所述分支跳转条件包括N条分支跳转子条件,所述分支跳转子条件与所述子TCAM一一对应;
所述协处理器用于对每个子TCAM对应的分支跳转子条件和每个子TCAM中的TCAM条目进行匹配,确定匹配成功的至少一条TCAM条目;根据所述匹配成功的至少一条TCAM条目确定静态随机存储器SRAM地址;所述协处理器将所述SRAM地址发送给所述第二网络处理器;
所述第二网络处理器根据所述SRAM地址确定待执行动作对应的存储地址,并执行所述存储地址对应的所述待执行动作。
6.根据权利要求5所述的装置,其特征在于,若所述分支跳转条件最多包括M个条件节点,每个条件节点取值为第一数值或者第二数值,所述M为大于或者等于2的正整数,则每条TCAM条目也包括M项数值,每项数值为所述第一数值、所述第二数值和第三数值中的任一项;
当任一分支跳转子条件中的条件节点取所述第一数值,且所述任一分支跳转子条件对应的子TCAM中存在至少一条TCAM条目对应位置的数值为所述第一数值或者所述第三数值时,则表示所述任一分支跳转子条件中的条件节点匹配成功;
当所述任一分支跳转子条件中的条件节点取所述第二数值,且所述任一分支跳转子条件对应的子TCAM中存在至少一条TCAM条目对应位置的数值为所述第二数值或者所述第三数值时,则表示所述任一分支跳转子条件中的条件节点匹配成功;
当所述任一分支跳转子条件中的每个条件节点和任一条TCAM条目对应位置的数值匹配成功,则表示所述任一分支跳转子条件和所述任一条TCAM条目匹配成功。
7.根据权利要求6所述的装置,其特征在于,所述协处理器具体用于:在所述至少一条TCAM条目中,确定与每个子TCAM对应的分支跳转子条件中的每个条件节点取值相同的TCAM条目;
确定所述取值相同的TCAM条目对应的SRAM地址为所述SRAM地址。
8.根据权利要求6或7所述的装置,其特征在于,所述协处理器还用于:获取所述子TCAM的划分信息,所述划分信息包括:所述收敛节点的个数和所述收敛节点的位置信息;
根据所述子TCAM的划分信息确定所述分支跳转条件的分割节点,并根据所述分割节点对所述分支跳转条件进行划分,获得所述N条分支跳转子条件。
说明书 :
多分支跳转协处理方法及装置
技术领域
背景技术
构。
分支跳转条件与TCAM中的TCAM条目进行匹配,当匹配成功后,则该网络处理器将匹配成功
的TCAM条目对应的静态随机存储器(Static Random Access Memory,简称SRAM)地址发送
给下一个网络处理器,该下一个网络处理器通过确定SRAM地址中所存储的待执行动作对应
的存储地址,来执行该存储地址对应的待执行动作。
多分支跳转条件匹配效率低的问题,同时这将对TCAM的存储空间带来进一步的挑战。
发明内容
态内容寻址存储器TCAM,协处理器的两端分别与第一网络处理器和第二网络处理器连接,
TCAM与协处理器连接,其中TCAM按照待处理业务被逻辑划分为N个子TCAM,N为大于或者等
于2的正整数,前N‑1个子TCAM中的每个子TCAM中包括至少一条TCAM条目,每个子TCAM中的
至少一条TCAM条目存在一个收敛节点,且收敛节点为每个子TCAM的下一个子TCAM中的至少
一条TCAM条目的起始节点;该方法包括:
TCAM的功耗。
可以为第一数值、第二数值和第三数值中的任一项。
任一分支跳转子条件中的条件节点匹配成功。
分支跳转子条件中的条件节点匹配成功。
功耗。
一网络处理器和第二网络处理器连接,TCAM与协处理器连接,其中TCAM按照待处理业务被
逻辑划分为N个子TCAM,所述N为大于或者等于2的正整数,前N‑1个子TCAM中的每个子TCAM
中包括至少一条TCAM条目,所述每个子TCAM中的至少一条TCAM条目存在一个收敛节点,且
收敛节点为每个子TCAM的下一个子TCAM中的至少一条TCAM条目的起始节点。
态随机存储器SRAM地址,SRAM地址对应的SRAM单元用于存储待执行动作对应的存储地址;
并将SRAM地址发送给第二网络处理器。
可以为第一数值、第二数值和第三数值中的任一项。
分支跳转子条件中的条件节点匹配成功。
分支跳转子条件中的条件节点匹配成功。
SRAM地址为所述SRAM地址。
分割节点对分支跳转条件进行划分,获得N条分支跳转子条件。
子条件,分支跳转子条件与子TCAM一一对应;协处理器对每个子TCAM对应的分支跳转子条
件和每个子TCAM中的TCAM条目进行匹配,确定匹配成功的至少一条TCAM条目;协处理器根
据匹配成功的至少一条TCAM条目确定静态随机存储器SRAM地址,SRAM地址对应的SRAM单元
用于存储待执行动作对应的存储地址;协处理器将SRAM地址发送给所述第二网络处理器;
第二网络处理器根据SRAM地址确定待执行动作对应的存储地址,并执行存储地址对应的待
执行动作。由于TCAM被逻辑划分为N个子TCAM,使得TCAM条目数量降低,从而提高了分支跳
转条件的匹配效率,并且可以节省TCAM的存储空间,进而降低TCAM的功耗。
附图说明
具体实施方式
的TCAM entry1、TCAM entry2和TCAM entry3等为TCAM中存储的TCAM条目。
处理器,该下一个网络处理器通过确定SRAM地址中所存储的待执行动作对应的存储地址,
来执行该存储地址对应的待执行动作。
分支跳转条件匹配效率低的问题,同时这将对TCAM的存储空间带来进一步的挑战。
路由器,图2为本发明一实施例提供的基于交换机或者路由器所提供的多分支跳转协处理
的示意图,如图2所示,该交换机或者路由器包括:第一网络处理器21、第二网络处理器22、
协处理器23和TCAM24,该第一网络处理器21和第二网络处理器22可以是交换机或者路由器
中不同的核。协处理器23的两端分别与第一网络处理器21和第二网络处理器22连接,
TCAM24与协处理器23连接,如图2所示,其中TCAM(物理TCAM)按照待处理业务被逻辑划分为
N个子TCAM,所述N为大于或者等于2的正整数,每个子TCAM包括至少一条TCAM条目,前N‑1个
子TCAM中的每个子TCAM中的至少一条TCAM条目存在一个收敛节点,且收敛节点为每个子
TCAM的下一个子TCAM中的至少一条TCAM条目的起始节点。
子TCAM的下一个子TCAM所包括的至少一条TCAM条目中的每条TCAM条目的起始节点。其中子
TCAM所包括的至少一条TCAM条目可以是子TCAM中的全部TCAM条目,也可以是子TCAM中的部
分TCAM条目。同样的,子TCAM的下一个子TCAM所包括的至少一条TCAM条目可以是子TCAM的
下一个子TCAM中的全部TCAM条目,也可以是子TCAM的下一个子TCAM中的部分TCAM条目。
TCAM所包括的至少一条TCAM条目中的每条TCAM条目的起始节点的前一个条件节点(公共条
件节点)。
为TCAM1和TCAM2,现有技术中的一条TCAM条目为TCAM entry={10,01,10,01,10},而本申
请中TCAM1对应的一条TCAM条目为TCAM entry1={10,01,00,00,00},TCAM2对应的一条
TCAM条目为TCAM entry2={00,00,10,01,10},符号“00”可以表示任何数值,本申请中的
“00”等同于下面将要提到的第三数值。
划分为N个子TCAM,因此分支跳转条件也自然被划分为N条分支跳转子条件,需要说明的是,
一种可选方式:该分支跳转子条件可以是根据待处理业务已经被划分好的,并且该分支跳
转子条件与子TCAM的对应关系也已经是配置好的。另一种可选方式,该多分支跳转协处理
方法还包括:协处理器获取子TCAM的划分信息,该划分信息包括:收敛节点的个数和收敛节
点的位置信息;协处理器根据子TCAM的划分信息确定分支跳转条件的分割节点,并根据分
割节点对分支跳转条件进行划分,获得N条分支跳转子条件。
值可以为第一数值、第二数值和第三数值中的任一项;当任一分支跳转子条件中的条件节
点取第一数值,且任一分支跳转子条件对应的子TCAM中存在至少一条TCAM条目对应位置的
数值为第一数值或者第三数值时,则表示任一分支跳转子条件中的条件节点匹配成功;当
任一分支跳转子条件中的条件节点取第二数值,且任一分支跳转子条件对应的子TCAM中存
在至少一条TCAM条目对应位置的数值为第二数值或者第三数值时,则表示任一分支跳转子
条件中的条件节点匹配成功;当任一分支跳转子条件中的每个条件节点和任一条TCAM条目
对应位置的数值匹配成功,则表示所述任一分支跳转子条件和所述任一条TCAM条目匹配成
功。
10,00,00,00},TCAM entry2={01,00,00,00,00},TCAM entry3={00,00,00,00,00},其中
TCAM条目与SRAM地址一一对应。
同的TCAM条目对应的SRAM地址为所述SRAM地址,该SRAM地址对应的SRAM单元用于存储待执
行动作对应的存储地址。
TCAM entry3={00,00,00,00,00},则协处理器在子TCAM1所包括的至少一条TCAM条目中,
确定与该子TCAM1对应的分支跳转子条件中的每个条件节点取值相同的TCAM条目为TCAM
entry1={01,10,00,00,00},并确定该TCAM entry1={01,10,00,00,00}对应的SRAM地址
为最终的SRAM地址。图3A为本发明一实施例提供的子TCAM与SRAM单元对应关系的示意图,
如图3A所示,对于子TCAM1包括3条匹配成功的TCAM条目,其中匹配成功用1表示,匹配失败
用0表示,对于TCAM1来讲,与Key取值相同的TCAM条目为第一条TCAM条目:TCAM entry1,确
定该TCAM entry1对应的SRAM地址所对应的SRAM存储单元存储待执行动作对应的存储地址
为0,同样的,对于TCAM2来讲,SRAM地址所对应的SRAM存储单元存储待执行动作对应的存储
地址为2,对于TCAM3来讲,SRAM地址所对应的SRAM存储单元存储待执行动作对应的存储地
址为1,对于TCAMN来讲,SRAM地址所对应的SRAM存储单元存储待执行动作对应的存储地址
为3。
={00,00,00,00,00}为每个子TCAM中的最后一个TCAM条目,则协处理器在匹配成功的至少
一条TCAM条目中确定第一条TCAM条目对应的SRAM地址为最终的SRAM地址。
明另一实施例提供的子TCAM与SRAM单元对应关系的示意图,如图3B所示,对于子TCAM1包括
2条匹配成功的TCAM条目,其中匹配成功用1表示,匹配失败用0表示,对于TCAM1来讲,与Key
取值相同的TCAM条目为第一条TCAM条目:TCAM entry1,确定该TCAM entry1对应的SRAM地
址所对应的SRAM存储单元存储待执行动作对应的存储地址为0,同样的,对于TCAM2来讲,
SRAM地址所对应的SRAM存储单元存储待执行动作对应的存储地址为2,对于TCAM3来讲,
SRAM地址所对应的SRAM存储单元存储待执行动作对应的存储地址为1,对于TCAMN来讲,
SRAM地址所对应的SRAM存储单元存储待执行动作对应的存储地址为3。
并执行该存储地址对应的待执行动作。也就是说,针对不同的SRAM地址,第二网络处理器独
立执行存储地址对应的待执行动作。当然,也可以是,按照SRAM地址对应的存储地址有低至
高的顺序依次执行该存储地址对应的待执行动作。本申请对此不做限制。
跳转条件。基于该分支跳转结构,TCAM中至少需要存储8*4*2*2=128条TCAM条目。
作。从上至下每条路径中的菱形构成一条分支跳转条件。基于该分支跳转结构,TCAM1包括
至少8条TCAM条目。TCAM2包括至少4*2*2=16条TCAM条目。因此整个TCAM中至少需要存储8+
4*2*2=24条TCAM条目。
作。从上至下每条路径中的菱形构成一条分支跳转条件。基于该分支跳转结构,TCAM1包括
至少8条TCAM条目。TCAM2包括至少4条TCAM条目。TCAM3包括至少2*2=4条TCAM条目。因此整
个TCAM中至少需要存储8+4+2*2=16条TCAM条目。
分支跳转子条件与子TCAM一一对应;协处理器对每个子TCAM对应的分支跳转子条件和每个
子TCAM中的TCAM条目进行匹配,确定匹配成功的至少一条TCAM条目;协处理器根据匹配成
功的至少一条TCAM条目确定静态随机存储器SRAM地址,SRAM地址对应的SRAM单元用于存储
待执行动作对应的存储地址;协处理器将SRAM地址发送给所述第二网络处理器;第二网络
处理器根据SRAM地址确定待执行动作对应的存储地址,并执行存储地址对应的待执行动
作。由于TCAM被逻辑划分为N个子TCAM,使得TCAM条目数量降低,从而提高了分支跳转条件
的匹配效率,并且可以节省TCAM的存储空间,进而降低TCAM的功耗。
储器TCAM54,所述协处理器53的两端分别与所述第一网络处理器51和所述第二网络处理器
52连接,所述TCAM54与所述协处理器53连接,其中所述TCAM54按照待处理业务被逻辑划分
为N个子TCAM,所述N为大于或者等于2的正整数,前N‑1个子TCAM中的每个子TCAM中包括至
少一条TCAM条目,所述每个子TCAM中的至少一条TCAM条目存在一个收敛节点,且所述收敛
节点为所述每个子TCAM的下一个子TCAM中的至少一条TCAM条目的起始节点。
子TCAM一一对应。
TCAM条目确定静态随机存储器SRAM地址,所述SRAM地址对应的SRAM单元用于存储待执行动
作对应的存储地址;并将所述SRAM地址发送给所述第二网络处理器。
每项数值可以为所述第一数值、所述第二数值和第三数值中的任一项。
数值时,则表示所述任一分支跳转子条件中的条件节点匹配成功。
第三数值时,则表示所述任一分支跳转子条件中的条件节点匹配成功。
TCAM条目对应的SRAM地址为所述SRAM地址。
述分支跳转条件的分割节点,并根据所述分割节点对所述分支跳转条件进行划分,获得所
述N条分支跳转子条件。
序在执行时,执行包括上述各方法实施例的步骤;而前述的存储介质包括:ROM、RAM、磁碟或
者光盘等各种可以存储程序代码的介质。