CN112039782B - Multi-branch jump co-processing method and device - Google Patents
Multi-branch jump co-processing method and device Download PDFInfo
- Publication number
- CN112039782B CN112039782B CN202010717565.7A CN202010717565A CN112039782B CN 112039782 B CN112039782 B CN 112039782B CN 202010717565 A CN202010717565 A CN 202010717565A CN 112039782 B CN112039782 B CN 112039782B
- Authority
- CN
- China
- Prior art keywords
- tcam
- sub
- condition
- node
- branch
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Images
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/74—Address processing for routing
- H04L45/745—Address table lookup; Address filtering
- H04L45/74591—Address table lookup; Address filtering using content-addressable memories [CAM]
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/30—Arrangements for executing machine instructions, e.g. instruction decode
- G06F9/38—Concurrent instruction execution, e.g. pipeline or look ahead
- G06F9/3877—Concurrent instruction execution, e.g. pipeline or look ahead using a slave processor, e.g. coprocessor
Landscapes
- Engineering & Computer Science (AREA)
- Software Systems (AREA)
- Theoretical Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
- Multi Processors (AREA)
Abstract
本申请提供一种多分支跳转协处理方法及装置,该方法包括:第一网络处理器获取分支跳转条件,并将分支跳转条件发送给协处理器,分支跳转条件包括N条分支跳转子条件,分支跳转子条件与子TCAM一一对应;协处理器对每个子TCAM对应的分支跳转子条件和每个子TCAM中的TCAM条目进行匹配,确定匹配成功的至少一条TCAM条目;协处理器根据匹配成功的至少一条TCAM条目确定静态随机存储器SRAM地址,SRAM地址对应的SRAM单元用于存储待执行动作对应的存储地址;协处理器将SRAM地址发送给所述第二网络处理器;第二网络处理器根据SRAM地址确定待执行动作对应的存储地址,并执行存储地址对应的待执行动作。
The present application provides a multi-branch jump co-processing method and device. The method includes: a first network processor acquires a branch jump condition, and sends the branch jump condition to the coprocessor, where the branch jump condition includes N branches Jump sub-conditions, branch jump sub-conditions are in one-to-one correspondence with sub-TCAMs; the coprocessor matches the branch-jump sub-conditions corresponding to each sub-TCAM with the TCAM entries in each sub-TCAM, and determines at least one TCAM entry that matches successfully The coprocessor determines the static random access memory SRAM address according to at least one TCAM entry that matches successfully, and the SRAM unit corresponding to the SRAM address is used to store the storage address corresponding to the action to be executed; the coprocessor sends the SRAM address to the second network for processing The second network processor determines the storage address corresponding to the to-be-executed action according to the SRAM address, and executes the to-be-executed action corresponding to the storage address.
Description
技术领域technical field
本申请涉及多分支跳转协处理技术,尤其涉及一种多分支跳转协处理方法及装置。The present application relates to a multi-branch jump co-processing technology, and in particular, to a multi-branch jump co-processing method and device.
背景技术Background technique
随着互联网技术的不断发展,交换机或者路由器的应用也越来越频繁,通常交换机或者路由器中包括有网络处理器,在网络处理器上运行的软件中,会遇到多分支跳转结构。With the continuous development of Internet technology, the application of switches or routers is becoming more and more frequent. Usually, switches or routers include a network processor. In the software running on the network processor, a multi-branch jump structure will be encountered.
目前网络处理器基于三态内容寻址存储器(Ternary Content Address Memory,简称TCAM)来实现这种分支跳转。其中TCAM中存储有多条TCAM条目。网络处理器对编译后的分支跳转条件与TCAM中的TCAM条目进行匹配,当匹配成功后,则该网络处理器将匹配成功的TCAM条目对应的静态随机存储器(Static Random Access Memory,简称SRAM)地址发送给下一个网络处理器,该下一个网络处理器通过确定SRAM地址中所存储的待执行动作对应的存储地址,来执行该存储地址对应的待执行动作。At present, the network processor implements this branch jump based on a ternary content addressable memory (Ternary Content Address Memory, TCAM for short). There are multiple TCAM entries stored in the TCAM. The network processor matches the compiled branch jump condition with the TCAM entry in the TCAM. When the match is successful, the network processor will match the static random access memory (Static Random Access Memory, SRAM for short) corresponding to the successful TCAM entry. The address is sent to the next network processor, and the next network processor executes the to-be-executed action corresponding to the storage address by determining the storage address corresponding to the to-be-executed action stored in the SRAM address.
然而,目前网络处理器基于TCAM进行分支跳转条件匹配时,存在匹配数量庞大的问题。尤其当分支跳转条件较为复杂时,则TCAM条目也会存在爆炸式增长的趋势,从而造成多分支跳转条件匹配效率低的问题,同时这将对TCAM的存储空间带来进一步的挑战。However, when the network processor currently performs branch and jump condition matching based on TCAM, there is a problem of a huge number of matches. Especially when the branch and jump conditions are complex, the TCAM entries will also have an explosive growth trend, resulting in the problem of low matching efficiency of multi-branch jump conditions, and this will bring further challenges to the storage space of the TCAM.
发明内容SUMMARY OF THE INVENTION
本申请提供一种多分支跳转协处理方法及装置,从而提高多分支跳转条件匹配效率,并且可以节省TCAM的存储空间,进而降低TCAM的功耗。The present application provides a multi-branch jump co-processing method and device, thereby improving the multi-branch jump condition matching efficiency, and can save the storage space of the TCAM, thereby reducing the power consumption of the TCAM.
第一方面,本申请实施例提供一种多分支跳转协处理方法,该方法应用于交换机或者路由器,该交换机或者路由器包括:第一网络处理器、第二网络处理器、协处理器和三态内容寻址存储器TCAM,协处理器的两端分别与第一网络处理器和第二网络处理器连接,TCAM与协处理器连接,其中TCAM按照待处理业务被逻辑划分为N个子TCAM,N为大于或者等于2的正整数,前N-1个子TCAM中的每个子TCAM中包括至少一条TCAM条目,每个子TCAM中的至少一条TCAM条目存在一个收敛节点,且收敛节点为每个子TCAM的下一个子TCAM中的至少一条TCAM条目的起始节点;该方法包括:In a first aspect, an embodiment of the present application provides a multi-branch jump co-processing method, and the method is applied to a switch or router, where the switch or router includes: a first network processor, a second network processor, a co-processor, and a third network processor. The two ends of the coprocessor are connected to the first network processor and the second network processor respectively, and the TCAM is connected to the coprocessor. The TCAM is logically divided into N sub-TCAMs according to the services to be processed, and N is a positive integer greater than or equal to 2, each sub-TCAM in the first N-1 sub-TCAMs includes at least one TCAM entry, and at least one TCAM entry in each sub-TCAM has a convergence node, and the convergence node is the lower part of each sub-TCAM. the starting node of at least one TCAM entry in a sub-TCAM; the method includes:
第一网络处理器获取分支跳转条件,并将分支跳转条件发送给协处理器,其中分支跳转条件包括N条分支跳转子条件,分支跳转子条件与子TCAM一一对应。The first network processor acquires the branch jump condition, and sends the branch jump condition to the coprocessor, wherein the branch jump condition includes N branch jump subconditions, and the branch jump subconditions correspond to the sub-TCAMs one-to-one.
协处理器对每个子TCAM对应的分支跳转子条件和每个子TCAM中的TCAM条目进行匹配,确定匹配成功的至少一条TCAM条目。The coprocessor matches the branch and jump subconditions corresponding to each sub-TCAM with the TCAM entries in each sub-TCAM, and determines at least one TCAM entry that is successfully matched.
协处理器根据匹配成功的至少一条TCAM条目确定静态随机存储器SRAM地址,SRAM地址对应的SRAM单元用于存储待执行动作对应的存储地址。The coprocessor determines the SRAM address of the static random access memory according to at least one TCAM entry that is successfully matched, and the SRAM unit corresponding to the SRAM address is used to store the storage address corresponding to the action to be executed.
协处理器将SRAM地址发送给第二网络处理器。The coprocessor sends the SRAM address to the second network processor.
第二网络处理器根据SRAM地址确定待执行动作对应的存储地址,并执行存储地址对应的待执行动作。The second network processor determines a storage address corresponding to the to-be-executed action according to the SRAM address, and executes the to-be-executed action corresponding to the storage address.
本申请实施例的有益效果是:由于TCAM被逻辑划分为N个子TCAM,使得TCAM条目数量降低,从而提高了分支跳转条件的匹配效率,并且可以节省TCAM的存储空间,进而降低TCAM的功耗。The beneficial effects of the embodiments of the present application are: since the TCAM is logically divided into N sub-TCAMs, the number of TCAM entries is reduced, thereby improving the matching efficiency of branch jump conditions, and saving the storage space of the TCAM, thereby reducing the power consumption of the TCAM .
可选地,若分支跳转条件最多包括M个条件节点,每个条件节点可以取值为第一数值或者第二数值,M为大于或者等于2的正整数,则每条TCAM条目也包括M项数值,每项数值可以为第一数值、第二数值和第三数值中的任一项。Optionally, if the branch jump condition includes at most M condition nodes, each condition node can take a value of the first value or the second value, and M is a positive integer greater than or equal to 2, then each TCAM entry also includes M. Item value, each item value can be any one of the first value, the second value and the third value.
当任一分支跳转子条件中的条件节点取所述第一数值,且任一分支跳转子条件对应的子TCAM中存在至少一条TCAM条目对应位置的数值为第一数值或者第三数值时,则表示任一分支跳转子条件中的条件节点匹配成功。When the condition node in any branch jump sub-condition takes the first value, and there is at least one TCAM entry in the sub-TCAM corresponding to any branch jump sub-condition, the value corresponding to the position of the first value or the third value , it means that the conditional node in any branch jump subcondition is successfully matched.
当任一分支跳转子条件中的条件节点取第二数值,且任一分支跳转子条件对应的子TCAM中存在至少一条TCAM条目对应位置的数值为第二数值或者第三数值时,则表示任一分支跳转子条件中的条件节点匹配成功。When the condition node in any branch jump sub-condition takes the second value, and there is at least one TCAM entry corresponding to the second value or the third value in the sub-TCAM corresponding to any branch jump sub-condition, then Indicates that the conditional node in any branch jump subcondition is successfully matched.
当任一分支跳转子条件中的每个条件节点和任一条TCAM条目对应位置的数值匹配成功,则表示任一分支跳转子条件和任一条TCAM条目匹配成功。When each condition node in any branch jump sub-condition and the value of the corresponding position of any TCAM entry successfully match, it means that any branch jump sub-condition and any TCAM entry match successfully.
通过该方法可以有效确定分支跳转子条件和任一条TCAM条目是否匹配成功。This method can effectively determine whether the branch jump subcondition and any TCAM entry match successfully.
可选地,协处理器根据匹配成功的至少一条TCAM条目确定静态随机存储器SRAM地址,包括:Optionally, the coprocessor determines the SRAM address of the static random access memory according to at least one TCAM entry that is successfully matched, including:
协处理器在至少一条TCAM条目中,确定与每个子TCAM对应的分支跳转子条件中的每个条件节点取值相同的TCAM条目。The coprocessor determines, in at least one TCAM entry, a TCAM entry with the same value as each condition node in the branch and jump subconditions corresponding to each sub-TCAM.
协处理器确定取值相同的TCAM条目对应的SRAM地址为SRAM地址。The coprocessor determines that the SRAM address corresponding to the TCAM entry with the same value is the SRAM address.
通过该方法可以有效SRAM地址,从而可以根据SRAM地址确定待执行动作对应的存储地址,并执行存储地址对应的待执行动作。Through this method, the SRAM address can be effectively used, so that the storage address corresponding to the action to be executed can be determined according to the SRAM address, and the action to be executed corresponding to the storage address can be executed.
可选地,还包括:协处理器获取子TCAM的划分信息,划分信息包括:收敛节点的个数和收敛节点的位置信息。Optionally, the method further includes: the coprocessor obtains the division information of the sub-TCAM, and the division information includes: the number of the convergent nodes and the location information of the convergent nodes.
协处理器根据子TCAM的划分信息确定分支跳转条件的分割节点,并根据分割节点对分支跳转条件进行划分,获得N条分支跳转子条件。The coprocessor determines the division node of the branch jump condition according to the division information of the sub-TCAM, and divides the branch jump condition according to the division node to obtain N branch jump sub-conditions.
通过该方法协处理器可以准确的对分支跳转条件进行划分,使得TCAM条目数量降低,从而提高了分支跳转条件的匹配效率,并且可以节省TCAM的存储空间,进而降低TCAM的功耗。By this method, the coprocessor can accurately divide the branch and jump conditions, so that the number of TCAM entries is reduced, thereby improving the matching efficiency of the branch and jump conditions, and can save the storage space of the TCAM, thereby reducing the power consumption of the TCAM.
下面将提供一种多分支跳转协处理装置,该装置可以用于执行上述的多分支跳转协处理方法,其实现原理和技术效果类似,在此不再赘述。The following will provide a multi-branch jump co-processing apparatus, which can be used to execute the above-mentioned multi-branch jump co-processing method, and its implementation principle and technical effect are similar, and will not be repeated here.
第二方面,本申请实施例提供一种多分支跳转协处理装置,该装置包括:第一网络处理器、第二网络处理器、协处理器和三态内容寻址存储器TCAM,协处理器的两端分别与第一网络处理器和第二网络处理器连接,TCAM与协处理器连接,其中TCAM按照待处理业务被逻辑划分为N个子TCAM,所述N为大于或者等于2的正整数,前N-1个子TCAM中的每个子TCAM中包括至少一条TCAM条目,所述每个子TCAM中的至少一条TCAM条目存在一个收敛节点,且收敛节点为每个子TCAM的下一个子TCAM中的至少一条TCAM条目的起始节点。In a second aspect, an embodiment of the present application provides a multi-branch jump co-processing device, the device includes: a first network processor, a second network processor, a co-processor, and a tri-state content addressable memory TCAM, the co-processor The two ends of the TCAM are respectively connected to the first network processor and the second network processor, and the TCAM is connected to the coprocessor, wherein the TCAM is logically divided into N sub-TCAMs according to the business to be processed, and N is a positive integer greater than or equal to 2 , each sub-TCAM in the first N-1 sub-TCAMs includes at least one TCAM entry, at least one TCAM entry in each sub-TCAM has a convergent node, and the convergent node is at least one of the next sub-TCAMs of each sub-TCAM The starting node of a TCAM entry.
第一网络处理器用于获取分支跳转条件,并将分支跳转条件发送给协处理器,其中分支跳转条件包括N条分支跳转子条件,分支跳转子条件与子TCAM一一对应。The first network processor is configured to acquire the branch jump condition and send the branch jump condition to the coprocessor, wherein the branch jump condition includes N branch jump subconditions, and the branch jump subconditions correspond to the sub-TCAMs one-to-one.
协处理器用于对每个子TCAM对应的分支跳转子条件和每个子TCAM中的TCAM条目进行匹配,确定匹配成功的至少一条TCAM条目;根据匹配成功的至少一条TCAM条目确定静态随机存储器SRAM地址,SRAM地址对应的SRAM单元用于存储待执行动作对应的存储地址;并将SRAM地址发送给第二网络处理器。The coprocessor is used to match the branch jump subcondition corresponding to each sub-TCAM with the TCAM entry in each sub-TCAM, and determine at least one TCAM entry that matches successfully; determine the SRAM address of the static random access memory according to the at least one TCAM entry that matches successfully, The SRAM unit corresponding to the SRAM address is used to store the storage address corresponding to the action to be executed; and the SRAM address is sent to the second network processor.
第二网络处理器用于根据SRAM地址确定待执行动作对应的存储地址,并执行存储地址对应的待执行动作。The second network processor is configured to determine a storage address corresponding to the to-be-executed action according to the SRAM address, and execute the to-be-executed action corresponding to the storage address.
可选地,若分支跳转条件最多包括M个条件节点,每个条件节点可以取值为第一数值或者第二数值,M为大于或者等于2的正整数,则每条TCAM条目也包括M项数值,每项数值可以为第一数值、第二数值和第三数值中的任一项。Optionally, if the branch jump condition includes at most M condition nodes, each condition node can take a value of the first value or the second value, and M is a positive integer greater than or equal to 2, then each TCAM entry also includes M. Item value, each item value can be any one of the first value, the second value and the third value.
当任一分支跳转子条件中的条件节点取第一数值,且任一分支跳转子条件对应的子TCAM中存在至少一条TCAM条目对应位置的数值为第一数值或者第三数值时,则表示任一分支跳转子条件中的条件节点匹配成功。When the condition node in any branch jump subcondition takes the first value, and there is at least one TCAM entry corresponding to the first value or the third value in the sub-TCAM corresponding to any branch jump subcondition, then Indicates that the conditional node in any branch jump subcondition is successfully matched.
当任一分支跳转子条件中的条件节点取第二数值,且任一分支跳转子条件对应的子TCAM中存在至少一条TCAM条目对应位置的数值为第二数值或者第三数值时,则表示任一分支跳转子条件中的条件节点匹配成功。When the condition node in any branch jump sub-condition takes the second value, and there is at least one TCAM entry corresponding to the second value or the third value in the sub-TCAM corresponding to any branch jump sub-condition, then Indicates that the conditional node in any branch jump subcondition is successfully matched.
当任一分支跳转子条件中的每个条件节点和任一条TCAM条目对应位置的数值匹配成功,则表示任一分支跳转子条件和任一条TCAM条目匹配成功。When each condition node in any branch jump sub-condition and the value of the corresponding position of any TCAM entry successfully match, it means that any branch jump sub-condition and any TCAM entry match successfully.
可选地,协处理器具体用于:在至少一条TCAM条目中,确定与每个子TCAM对应的分支跳转子条件中的每个条件节点取值相同的TCAM条目。确定取值相同的TCAM条目对应的SRAM地址为所述SRAM地址。Optionally, the coprocessor is specifically configured to: in at least one TCAM entry, determine a TCAM entry with the same value as each condition node in the branch jump subcondition corresponding to each sub-TCAM. It is determined that the SRAM address corresponding to the TCAM entry with the same value is the SRAM address.
可选地,协处理器还用于:获取子TCAM的划分信息,划分信息包括:收敛节点的个数和收敛节点的位置信息。根据子TCAM的划分信息确定分支跳转条件的分割节点,并根据分割节点对分支跳转条件进行划分,获得N条分支跳转子条件。Optionally, the coprocessor is further configured to: acquire division information of the sub-TCAM, where the division information includes: the number of convergent nodes and location information of the convergent nodes. The division node of the branch jump condition is determined according to the division information of the sub-TCAM, and the branch jump condition is divided according to the division node to obtain N branch jump sub-conditions.
本申请提供一种多分支跳转协处理方法及装置,该方法包括:第一网络处理器获取分支跳转条件,并将分支跳转条件发送给协处理器,其中分支跳转条件包括N条分支跳转子条件,分支跳转子条件与子TCAM一一对应;协处理器对每个子TCAM对应的分支跳转子条件和每个子TCAM中的TCAM条目进行匹配,确定匹配成功的至少一条TCAM条目;协处理器根据匹配成功的至少一条TCAM条目确定静态随机存储器SRAM地址,SRAM地址对应的SRAM单元用于存储待执行动作对应的存储地址;协处理器将SRAM地址发送给所述第二网络处理器;第二网络处理器根据SRAM地址确定待执行动作对应的存储地址,并执行存储地址对应的待执行动作。由于TCAM被逻辑划分为N个子TCAM,使得TCAM条目数量降低,从而提高了分支跳转条件的匹配效率,并且可以节省TCAM的存储空间,进而降低TCAM的功耗。The present application provides a multi-branch jump co-processing method and device. The method includes: a first network processor acquires a branch jump condition, and sends the branch jump condition to the coprocessor, wherein the branch jump condition includes N Branch jump sub-conditions, branch jump sub-conditions are in one-to-one correspondence with sub-TCAMs; the coprocessor matches the branch-jump sub-conditions corresponding to each sub-TCAM with the TCAM entries in each sub-TCAM, and determines at least one TCAM that matches successfully entry; the coprocessor determines the SRAM address of the static random access memory according to at least one TCAM entry that is successfully matched, and the SRAM unit corresponding to the SRAM address is used to store the storage address corresponding to the action to be executed; the coprocessor sends the SRAM address to the second network a processor; the second network processor determines a storage address corresponding to the action to be executed according to the SRAM address, and executes the action to be executed corresponding to the storage address. Since the TCAM is logically divided into N sub-TCAMs, the number of TCAM entries is reduced, thereby improving the matching efficiency of branch jump conditions, saving the storage space of the TCAM, and reducing the power consumption of the TCAM.
附图说明Description of drawings
图1为本发明一实施例提供的一种多分支跳转协处理方法的流程图;1 is a flowchart of a multi-branch jump co-processing method provided by an embodiment of the present invention;
图2为本发明一实施例提供的基于交换机或者路由器所提供的多分支跳转协处理的示意图;FIG. 2 is a schematic diagram of a multi-branch jump co-processing based on a switch or a router provided by an embodiment of the present invention;
图3A为本发明一实施例提供的子TCAM与SRAM单元对应关系的示意图;3A is a schematic diagram of a corresponding relationship between a sub-TCAM and an SRAM cell provided by an embodiment of the present invention;
图3B为本发明另一实施例提供的子TCAM与SRAM单元对应关系的示意图;3B is a schematic diagram of a corresponding relationship between a sub-TCAM and an SRAM cell provided by another embodiment of the present invention;
图4A为现有技术提供的分支跳转结构的示意图;4A is a schematic diagram of a branch and jump structure provided by the prior art;
图4B为本发明一实施例提供的分支跳转结构和基于该分支跳转结构的TCAM划分的示意图;4B is a schematic diagram of a branch jump structure and TCAM division based on the branch jump structure provided by an embodiment of the present invention;
图4C为本发明一实施例提供的分支跳转结构和基于该分支跳转结构的TCAM划分的示意图;4C is a schematic diagram of a branch jump structure and TCAM division based on the branch jump structure provided by an embodiment of the present invention;
图5为本申请一实施例提供的一种多分支跳转协处理装置的结构示意图。FIG. 5 is a schematic structural diagram of a multi-branch jump co-processing apparatus according to an embodiment of the present application.
具体实施方式Detailed ways
目前,在网络处理器上运行的软件中,经常会遇到多分支跳转结构,例如网络处理器运行的多分支跳转结构如下:At present, in the software running on the network processor, the multi-branch jump structure is often encountered. For example, the multi-branch jump structure running on the network processor is as follows:
其中左侧的conditon_1,conditon_2、conditon_3以及conditon_X等为多分支跳转条件,该多分支跳转条件中的任一多分支跳转条件可以用Key={a,b,c,...}表示,右侧的TCAM entry1、TCAM entry2和TCAM entry3等为TCAM中存储的TCAM条目。The left conditon_1, conditon_2, conditon_3, and conditon_X are multi-branch jump conditions, and any multi-branch jump condition in the multi-branch jump conditions can be represented by Key={a,b,c,...} , the TCAM entry1, TCAM entry2, and TCAM entry3 on the right are TCAM entries stored in the TCAM.
现有技术中网络处理器对编译后的分支跳转条件与TCAM中的TCAM条目进行匹配,当匹配成功后,则该网络处理器将匹配成功的TCAM条目对应的SRAM地址发送给下一个网络处理器,该下一个网络处理器通过确定SRAM地址中所存储的待执行动作对应的存储地址,来执行该存储地址对应的待执行动作。In the prior art, the network processor matches the compiled branch jump condition with the TCAM entry in the TCAM, and when the matching is successful, the network processor sends the SRAM address corresponding to the successfully matched TCAM entry to the next network processing The next network processor executes the to-be-executed action corresponding to the storage address by determining the storage address corresponding to the to-be-executed action stored in the SRAM address.
然而目前网络处理器基于TCAM进行分支跳转条件匹配时,存在匹配数量庞大的问题。尤其当分支跳转条件较为复杂时,则TCAM条目也会存在爆炸式增长的趋势,从而造成多分支跳转条件匹配效率低的问题,同时这将对TCAM的存储空间带来进一步的挑战。However, when the network processor currently performs branch and jump condition matching based on TCAM, there is a problem of a huge number of matches. Especially when the branch and jump conditions are complex, the TCAM entries will also have an explosive growth trend, resulting in the problem of low matching efficiency of multi-branch jump conditions, and this will bring further challenges to the storage space of the TCAM.
为了解决上述问题,本申请提供一种多分支跳转协处理方法及装置。具体地,图1为本发明一实施例提供的一种多分支跳转协处理方法的流程图,该方法应用于交换机或者路由器,图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条目的起始节点。In order to solve the above problems, the present application provides a multi-branch jump co-processing method and apparatus. Specifically, FIG. 1 is a flowchart of a multi-branch jump co-processing method provided by an embodiment of the present invention, and the method is applied to a switch or a router, and FIG. 2 is a method provided by a switch or router based on an embodiment of the present invention. A schematic diagram of the multi-branch jump co-processing of the and the
所谓收敛节点必须满足两个条件:第一,它是子TCAM所包括的至少一条TCAM条目中的每条TCAM条目的最后一个条件节点的下一个条件节点(公共条件节点)。第二,它是该子TCAM的下一个子TCAM所包括的至少一条TCAM条目中的每条TCAM条目的起始节点。其中子TCAM所包括的至少一条TCAM条目可以是子TCAM中的全部TCAM条目,也可以是子TCAM中的部分TCAM条目。同样的,子TCAM的下一个子TCAM所包括的至少一条TCAM条目可以是子TCAM的下一个子TCAM中的全部TCAM条目,也可以是子TCAM的下一个子TCAM中的部分TCAM条目。The so-called convergent node must satisfy two conditions: first, it is the next condition node (common condition node) of the last condition node of each TCAM entry in at least one TCAM entry included in the sub-TCAM. Second, it is the starting node of each TCAM entry in at least one TCAM entry included in the next sub-TCAM of the sub-TCAM. The at least one TCAM entry included in the sub-TCAM may be all TCAM entries in the sub-TCAM, or may be part of the TCAM entries in the sub-TCAM. Similarly, at least one TCAM entry included in the next sub-TCAM of the sub-TCAM may be all TCAM entries in the next sub-TCAM of the sub-TCAM, or may be part of the TCAM entries in the next sub-TCAM of the sub-TCAM.
或者,or,
所谓收敛节点必须满足两个条件:第一,它是子TCAM所包括的至少一条TCAM条目中的每条TCAM条目的最后一个条件节点(公共条件节点)。第二,它是该子TCAM的下一个子TCAM所包括的至少一条TCAM条目中的每条TCAM条目的起始节点的前一个条件节点(公共条件节点)。The so-called convergent node must satisfy two conditions: first, it is the last condition node (common condition node) of each TCAM entry in at least one TCAM entry included in the sub-TCAM. Second, it is the previous condition node (common condition node) of the start node of each TCAM entry of at least one TCAM entry included in the next child TCAM of the child 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”等同于下面将要提到的第三数值。It is worth mentioning that in this application, the TCAM is logically divided into multiple sub-TCAMs, and correspondingly, the TCAM entries in the sub-TCAMs are also changed relative to the TCAM entries in the prior art. Assuming that the TCAM is logically divided into two sub-TCAMs, namely TCAM1 and TCAM2, a TCAM entry in the prior art is TCAM entry={10, 01, 10, 01, 10}, while a TCAM entry corresponding to TCAM1 in this application For TCAM entry1={10, 01, 00, 00, 00}, a TCAM entry corresponding to TCAM2 is TCAM entry2={00, 00, 10, 01, 10}, the symbol "00" can represent any value, in this application "00" of is equivalent to the third numerical value to be mentioned below.
具体地,如图1所示,该方法包括如下步骤:Specifically, as shown in Figure 1, the method includes the following steps:
步骤S101:第一网络处理器获取分支跳转条件,并将分支跳转条件发送给协处理器,其中分支跳转条件包括N条分支跳转子条件,分支跳转子条件与子TCAM一一对应;Step S101: the first network processor acquires the branch jump condition, and sends the branch jump condition to the coprocessor, wherein the branch jump condition includes N branch jump sub-conditions, and the branch jump sub-condition and the sub-TCAM are one-to-one correspond;
具体地,第一网络处理器可以获取一个分支跳转条件或者多个分支跳转条件,这里第一网络处理器获取的分支跳转条件即为上述分支跳转结构中的Key。由于TCAM被逻辑划分为N个子TCAM,因此分支跳转条件也自然被划分为N条分支跳转子条件,需要说明的是,一种可选方式:该分支跳转子条件可以是根据待处理业务已经被划分好的,并且该分支跳转子条件与子TCAM的对应关系也已经是配置好的。另一种可选方式,该多分支跳转协处理方法还包括:协处理器获取子TCAM的划分信息,该划分信息包括:收敛节点的个数和收敛节点的位置信息;协处理器根据子TCAM的划分信息确定分支跳转条件的分割节点,并根据分割节点对分支跳转条件进行划分,获得N条分支跳转子条件。Specifically, the first network processor may obtain one branch jump condition or multiple branch jump conditions, where the branch jump condition obtained by the first network processor is the Key in the foregoing branch jump structure. Since the TCAM is logically divided into N sub-TCAMs, the branch jump condition is also naturally divided into N branch jump sub-conditions. It should be noted that an optional way: the branch jump sub-condition can be The service has been divided, and the corresponding relationship between the branch jump sub-condition and the sub-TCAM has also been configured. In another optional manner, the multi-branch jump co-processing method further includes: the co-processor obtains the division information of the sub-TCAM, where the division information includes: the number of convergent nodes and the location information of the converged nodes; The division information of the TCAM determines the division node of the branch jump condition, and divides the branch jump condition according to the division node to obtain N branch jump sub-conditions.
步骤S102:协处理器对每个子TCAM对应的分支跳转子条件和每个子TCAM中的TCAM条目进行匹配,确定匹配成功的至少一条TCAM条目;Step S102: the coprocessor matches the branch jump subcondition corresponding to each sub-TCAM with the TCAM entry in each sub-TCAM, and determines at least one TCAM entry that matches successfully;
可选地,若分支跳转条件最多包括M个条件节点,每个条件节点可以取值为第一数值或者第二数值,该M为大于或者等于2的正整数,则每条TCAM条目也包括M项数值,每项数值可以为第一数值、第二数值和第三数值中的任一项;当任一分支跳转子条件中的条件节点取第一数值,且任一分支跳转子条件对应的子TCAM中存在至少一条TCAM条目对应位置的数值为第一数值或者第三数值时,则表示任一分支跳转子条件中的条件节点匹配成功;当任一分支跳转子条件中的条件节点取第二数值,且任一分支跳转子条件对应的子TCAM中存在至少一条TCAM条目对应位置的数值为第二数值或者第三数值时,则表示任一分支跳转子条件中的条件节点匹配成功;当任一分支跳转子条件中的每个条件节点和任一条TCAM条目对应位置的数值匹配成功,则表示所述任一分支跳转子条件和所述任一条TCAM条目匹配成功。Optionally, if the branch jump condition includes at most M condition nodes, each condition node can take a value of the first value or the second value, and M is a positive integer greater than or equal to 2, then each TCAM entry also includes M values, each value can be any one of the first value, the second value and the third value; when the condition node in any branch jump subcondition takes the first value, and any branch jump subcondition When there is at least one TCAM entry in the sub-TCAM corresponding to the condition and the value of the corresponding position is the first value or the third value, it means that the condition node in any branch jump sub-condition is successfully matched; when any branch jump sub-condition is in the The condition node takes the second value, and when there is at least one TCAM entry in the sub-TCAM corresponding to any branch jump subcondition, the value at the corresponding position of the TCAM entry is the second value or the third value, it means that any branch jump subcondition is in the The condition node matches successfully; when each condition node in any branch jump sub-condition and the value of the corresponding position of any TCAM entry match successfully, it means that any branch jump sub-condition and any TCAM entry The match was successful.
例如:第一数值为01,第二数值为10,第三数值为00,获取到的分支跳转子条件为Key={01,10},则Key={01,10}在TCAM1中匹配成功的TCAM条目包括:TCAM entry1={01,10,00,00,00},TCAM entry2={01,00,00,00,00},TCAM entry3={00,00,00,00,00},其中TCAM条目与SRAM地址一一对应。For example: the first value is 01, the second value is 10, the third value is 00, and the obtained branch jump sub-condition is Key={01, 10}, then Key={01, 10} is successfully matched in TCAM1 The TCAM entries include: TCAM entry1={01, 10, 00, 00, 00}, TCAM entry2={01, 00, 00, 00, 00}, TCAM entry3={00, 00, 00, 00, 00}, The TCAM entry corresponds to the SRAM address one-to-one.
步骤S103:协处理器根据匹配成功的至少一条TCAM条目确定SRAM地址,该SRAM地址对应的SRAM单元用于存储待执行动作对应的存储地址;Step S103: the coprocessor determines an SRAM address according to at least one TCAM entry that has been successfully matched, and the SRAM cell corresponding to the SRAM address is used to store the storage address corresponding to the action to be executed;
一种可选方式:协处理器在子TCAM所包括的至少一条TCAM条目中,确定与该子TCAM对应的分支跳转子条件中的每个条件节点取值相同的TCAM条目;协处理器确定取值相同的TCAM条目对应的SRAM地址为所述SRAM地址,该SRAM地址对应的SRAM单元用于存储待执行动作对应的存储地址。An optional way: the coprocessor determines, in at least one TCAM entry included in the sub-TCAM, a TCAM entry with the same value for each condition node in the branch jump subcondition corresponding to the sub-TCAM; the coprocessor determines The SRAM address corresponding to the TCAM entry with the same value is the SRAM address, and the SRAM unit corresponding to the SRAM address is used to store the storage address corresponding to the action to be executed.
接着上述的例子,上述分支跳转子条件Key={01,10},对于子TCAM1来讲,匹配成功的TCAM条目为:TCAM entry1={01,10,00,00,00},TCAM entry2={01,00,00,00,00},TCAM entry3={00,00,00,00,00},则协处理器在子TCAM1所包括的至少一条TCAM条目中,确定与该子TCAM1对应的分支跳转子条件中的每个条件节点取值相同的TCAM条目为TCAMentry1={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。Following the above example, the above branch jump sub-condition Key={01, 10}, for the sub-TCAM1, the successful matching TCAM entry is: TCAM entry1={01, 10, 00, 00, 00}, TCAM entry2= {01, 00, 00, 00, 00}, TCAM entry3={00, 00, 00, 00, 00}, then the coprocessor determines, in at least one TCAM entry included in the sub-TCAM1, the corresponding sub-TCAM1 The TCAM entry with the same value of each condition node in the branch jump subcondition is TCAMentry1={01, 10, 00, 00, 00}, and it is determined that the TCAM entry1={01, 10, 00, 00, 00} corresponds to The SRAM address is the final SRAM address. FIG. 3A is a schematic diagram of the correspondence between a sub-TCAM and an SRAM cell provided by an embodiment of the present invention. As shown in FIG. 3A , the sub-TCAM1 includes 3 TCAM entries with successful matching, wherein the matching success is represented by 1, and the matching failure is represented by 0 , for TCAM1, the TCAM entry with the same value as the Key is the first TCAM entry: TCAM entry1, determine that the SRAM storage unit corresponding to the SRAM address corresponding to the TCAM entry1 stores the storage address corresponding to the action to be executed is 0, and the same For TCAM2, the SRAM storage unit corresponding to the SRAM address stores the storage address corresponding to the action to be executed is 2, and for TCAM3, the SRAM storage unit corresponding to the SRAM address stores the storage address corresponding to the action to be executed is 1, For TCAMN, the SRAM storage unit corresponding to the SRAM address stores the storage address corresponding to the action to be executed as 3.
另一种可选方式:假设每个分支跳转条件都包括了5个条件节点,前两个条件节点被划分为一个分支跳转子条件,后三个被划分为另一个分支跳转子条件,并且TCAM entryX={00,00,00,00,00}为每个子TCAM中的最后一个TCAM条目,则协处理器在匹配成功的至少一条TCAM条目中确定第一条TCAM条目对应的SRAM地址为最终的SRAM地址。Another alternative: Assuming that each branch jump condition includes 5 condition nodes, the first two condition nodes are divided into one branch jump sub-condition, and the last three are divided into another branch jump sub-condition , and TCAM entryX={00, 00, 00, 00, 00} is the last TCAM entry in each sub-TCAM, then the coprocessor determines the SRAM address corresponding to the first TCAM entry in at least one TCAM entry that matches successfully is the final SRAM address.
基于此,上述分支跳转子条件Key={01,10},对于子TCAM1来讲,匹配成功的TCAM条目为:TCAM entry1={01,10,00,00,00},TCAM entry3={00,00,00,00,00}。图3B为本发明另一实施例提供的子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。Based on this, the above branch jump sub-condition Key={01, 10}, for the sub-TCAM1, the TCAM entry that matches successfully is: TCAM entry1={01, 10, 00, 00, 00}, TCAM entry3={00 , 00, 00, 00, 00}. FIG. 3B is a schematic diagram of the correspondence between the sub-TCAM and the SRAM cell provided by another embodiment of the present invention. As shown in FIG. 3B , the sub-TCAM1 includes 2 TCAM entries with successful matching, wherein the matching success is represented by 1, and the matching failure is represented by 0 Indicates that, for TCAM1, the TCAM entry with the same value as the Key is the first TCAM entry: TCAM entry1, and it is determined that the SRAM storage unit corresponding to the SRAM address corresponding to the TCAM entry1 stores the storage address corresponding to the action to be executed as 0, Similarly, for TCAM2, the SRAM storage unit corresponding to the SRAM address stores the storage address corresponding to the action to be executed is 2, and for TCAM3, the SRAM storage unit corresponding to the SRAM address stores the storage address corresponding to the action to be executed is 1 , for TCAMN, the SRAM storage unit corresponding to the SRAM address stores the storage address corresponding to the action to be executed as 3.
步骤S104:协处理器将SRAM地址发送给第二网络处理器;Step S104: the coprocessor sends the SRAM address to the second network processor;
步骤S105:第二网络处理器根据SRAM地址确定待执行动作对应的存储地址,并执行存储地址对应的待执行动作。Step S105: The second network processor determines a storage address corresponding to the action to be executed according to the SRAM address, and executes the action to be executed corresponding to the storage address.
结合步骤S104和步骤S105进行说明:第二网络处理器获取到每个子TCAM对应的SRAM地址之后,第二网络处理器可以根据每个SRAM地址确定待执行动作对应的存储地址,并执行该存储地址对应的待执行动作。也就是说,针对不同的SRAM地址,第二网络处理器独立执行存储地址对应的待执行动作。当然,也可以是,按照SRAM地址对应的存储地址有低至高的顺序依次执行该存储地址对应的待执行动作。本申请对此不做限制。Steps S104 and S105 are described in conjunction with: after the second network processor obtains the SRAM address corresponding to each sub-TCAM, the second network processor can determine the storage address corresponding to the action to be executed according to each SRAM address, and execute the storage address. The corresponding action to be executed. That is, for different SRAM addresses, the second network processor independently executes the to-be-executed actions corresponding to the storage addresses. Of course, it can also be that the actions to be executed corresponding to the storage addresses are sequentially executed according to the storage addresses corresponding to the SRAM addresses in the order from low to high. This application does not limit this.
下面对上述过程进行举例说明:The following is an example of the above process:
方案一:图4A为现有技术提供的分支跳转结构的示意图,如图4A所示,菱形表示分支跳转条件的条件节点。矩形表示待执行动作。从上至下每条路径中的菱形构成一条分支跳转条件。基于该分支跳转结构,TCAM中至少需要存储8*4*2*2=128条TCAM条目。Solution 1: FIG. 4A is a schematic diagram of a branch jump structure provided by the prior art. As shown in FIG. 4A , a diamond represents a condition node of a branch jump condition. Rectangles represent actions to be performed. The diamonds in each path from top to bottom constitute a branch jump condition. Based on the branch and jump structure, at least 8*4*2*2=128 TCAM entries need to be stored in the TCAM.
方案二:图4B为本发明一实施例提供的分支跳转结构和基于该分支跳转结构的TCAM划分的示意图,如图4B所示,菱形表示分支跳转条件的条件节点。矩形表示待执行动作。从上至下每条路径中的菱形构成一条分支跳转条件。基于该分支跳转结构,TCAM1包括至少8条TCAM条目。TCAM2包括至少4*2*2=16条TCAM条目。因此整个TCAM中至少需要存储8+4*2*2=24条TCAM条目。Scheme 2: FIG. 4B is a schematic diagram of a branch jump structure provided by an embodiment of the present invention and a TCAM division based on the branch jump structure. As shown in FIG. 4B , a diamond represents a condition node of a branch jump condition. Rectangles represent actions to be performed. The diamonds in each path from top to bottom constitute a branch jump condition. Based on the branch-jump structure, TCAM1 includes at least 8 TCAM entries. TCAM2 includes at least 4*2*2=16 TCAM entries. Therefore, at least 8+4*2*2=24 TCAM entries need to be stored in the entire TCAM.
方案三:图4C为本发明一实施例提供的分支跳转结构和基于该分支跳转结构的TCAM划分的示意图,如图4C所示,菱形表示分支跳转条件的条件节点。矩形表示待执行动作。从上至下每条路径中的菱形构成一条分支跳转条件。基于该分支跳转结构,TCAM1包括至少8条TCAM条目。TCAM2包括至少4条TCAM条目。TCAM3包括至少2*2=4条TCAM条目。因此整个TCAM中至少需要存储8+4+2*2=16条TCAM条目。Scheme 3: FIG. 4C is a schematic diagram of a branch jump structure provided by an embodiment of the present invention and a TCAM division based on the branch jump structure. As shown in FIG. 4C , a diamond represents a condition node of a branch jump condition. Rectangles represent actions to be performed. The diamonds in each path from top to bottom constitute a branch jump condition. Based on the branch-jump structure, TCAM1 includes at least 8 TCAM entries. TCAM2 includes at least 4 TCAM entries. TCAM3 includes at least 2*2=4 TCAM entries. Therefore, at least 8+4+2*2=16 TCAM entries need to be stored in the entire TCAM.
综上所述,图4A至图4C所示的三个方案对应的TCAM条目如表1:To sum up, the TCAM entries corresponding to the three schemes shown in FIG. 4A to FIG. 4C are shown in Table 1:
表1Table 1
综上,本申请提供一种多分支跳转协处理方法,包括:第一网络处理器获取分支跳转条件,并将分支跳转条件发送给协处理器,其中分支跳转条件包括N条分支跳转子条件,分支跳转子条件与子TCAM一一对应;协处理器对每个子TCAM对应的分支跳转子条件和每个子TCAM中的TCAM条目进行匹配,确定匹配成功的至少一条TCAM条目;协处理器根据匹配成功的至少一条TCAM条目确定静态随机存储器SRAM地址,SRAM地址对应的SRAM单元用于存储待执行动作对应的存储地址;协处理器将SRAM地址发送给所述第二网络处理器;第二网络处理器根据SRAM地址确定待执行动作对应的存储地址,并执行存储地址对应的待执行动作。由于TCAM被逻辑划分为N个子TCAM,使得TCAM条目数量降低,从而提高了分支跳转条件的匹配效率,并且可以节省TCAM的存储空间,进而降低TCAM的功耗。In summary, the present application provides a multi-branch jump co-processing method, including: a first network processor obtains a branch jump condition, and sends the branch jump condition to the coprocessor, wherein the branch jump condition includes N branches Jump sub-conditions, branch jump sub-conditions are in one-to-one correspondence with sub-TCAMs; the coprocessor matches the branch-jump sub-conditions corresponding to each sub-TCAM with the TCAM entries in each sub-TCAM, and determines at least one TCAM entry that matches successfully The coprocessor determines the static random access memory SRAM address according to at least one TCAM entry that matches successfully, and the SRAM unit corresponding to the SRAM address is used to store the storage address corresponding to the action to be executed; the coprocessor sends the SRAM address to the second network for processing The second network processor determines the storage address corresponding to the to-be-executed action according to the SRAM address, and executes the to-be-executed action corresponding to the storage address. Since the TCAM is logically divided into N sub-TCAMs, the number of TCAM entries is reduced, thereby improving the matching efficiency of branch jump conditions, saving the storage space of the TCAM, and reducing the power consumption of the TCAM.
图5为本申请一实施例提供的一种多分支跳转协处理装置的结构示意图,如图5所示,该装置50包括:第一网络处理器51、第二网络处理器52、协处理器53和三态内容寻址存储器TCAM54,所述协处理器53的两端分别与所述第一网络处理器51和所述第二网络处理器52连接,所述TCAM54与所述协处理器53连接,其中所述TCAM54按照待处理业务被逻辑划分为N个子TCAM,所述N为大于或者等于2的正整数,前N-1个子TCAM中的每个子TCAM中包括至少一条TCAM条目,所述每个子TCAM中的至少一条TCAM条目存在一个收敛节点,且所述收敛节点为所述每个子TCAM的下一个子TCAM中的至少一条TCAM条目的起始节点。FIG. 5 is a schematic structural diagram of a multi-branch jump co-processing apparatus according to an embodiment of the present application. As shown in FIG. 5 , the
所述第一网络处理器51用于获取分支跳转条件,并将所述分支跳转条件发送给所述协处理器,其中所述分支跳转条件包括N条分支跳转子条件,所述分支跳转子条件与所述子TCAM一一对应。The
所述协处理器53用于对每个子TCAM对应的分支跳转子条件和每个子TCAM中的TCAM条目进行匹配,确定匹配成功的至少一条TCAM条目;根据所述匹配成功的至少一条TCAM条目确定静态随机存储器SRAM地址,所述SRAM地址对应的SRAM单元用于存储待执行动作对应的存储地址;并将所述SRAM地址发送给所述第二网络处理器。The
所述第二网络处理器52用于根据所述SRAM地址确定所述待执行动作对应的存储地址,并执行所述存储地址对应的所述待执行动作。The
本申请实施例提供的多分支跳转协处理装置可以用于执行上述的多分支跳转协处理方法,其实现原理和技术效果类似,在此不再赘述。The multi-branch jump co-processing apparatus provided in the embodiment of the present application can be used to execute the above-mentioned multi-branch jump co-processing method, and the implementation principle and technical effect thereof are similar, and details are not described herein again.
可选地,若所述分支跳转条件最多包括M个条件节点,每个条件节点可以取值为第一数值或者第二数值,所述M为大于或者等于2的正整数,则每条TCAM条目也包括M项数值,每项数值可以为所述第一数值、所述第二数值和第三数值中的任一项。Optionally, if the branch jump condition includes at most M condition nodes, each condition node can take a value of a first value or a second value, and the M is a positive integer greater than or equal to 2, then each TCAM The entry also includes M values, each of which may be any of the first value, the second value, and the third value.
当任一分支跳转子条件中的条件节点取所述第一数值,且所述任一分支跳转子条件对应的子TCAM中存在至少一条TCAM条目对应位置的数值为所述第一数值或者所述第三数值时,则表示所述任一分支跳转子条件中的条件节点匹配成功。When the condition node in any branch jump sub-condition takes the first value, and the value corresponding to at least one TCAM entry in the sub-TCAM corresponding to any branch jump sub-condition is the first value or When the third numerical value is present, it indicates that the conditional nodes in any of the branch jump subconditions are successfully matched.
当所述任一分支跳转子条件中的条件节点取所述第二数值,且所述任一分支跳转子条件对应的子TCAM中存在至少一条TCAM条目对应位置的数值为所述第二数值或者所述第三数值时,则表示所述任一分支跳转子条件中的条件节点匹配成功。When the condition node in any branch jump sub-condition takes the second value, and the value corresponding to the position of at least one TCAM entry in the sub-TCAM corresponding to any branch jump sub-condition is the second value If the value is equal to or the third value, it means that the conditional node in any of the branch jump subconditions is successfully matched.
当所述任一分支跳转子条件中的每个条件节点和任一条TCAM条目对应位置的数值匹配成功,则表示所述任一分支跳转子条件和所述任一条TCAM条目匹配成功。When each condition node in the any branch jump sub-condition and the numerical value of the corresponding position of any TCAM entry successfully match, it means that the any branch jump sub-condition and any TCAM entry match successfully.
可选地,所述协处理器53具体用于:在所述至少一条TCAM条目中,确定与每个子TCAM对应的分支跳转子条件中的每个条件节点取值相同的TCAM条目;确定所述取值相同的TCAM条目对应的SRAM地址为所述SRAM地址。Optionally, the
可选地,所述协处理器53还用于:获取所述子TCAM的划分信息,所述划分信息包括:所述收敛节点的个数和所述收敛节点的位置信息;根据所述子TCAM的划分信息确定所述分支跳转条件的分割节点,并根据所述分割节点对所述分支跳转条件进行划分,获得所述N条分支跳转子条件。Optionally, the
本申请实施例提供的多分支跳转协处理装置可以用于执行上述的多分支跳转协处理方法,其实现原理和技术效果类似,在此不再赘述。The multi-branch jump co-processing apparatus provided in the embodiment of the present application can be used to execute the above-mentioned multi-branch jump co-processing method, and the implementation principle and technical effect thereof are similar, and details are not described herein again.
本领域普通技术人员可以理解:实现上述各方法实施例的全部或部分步骤可以通过程序指令相关的硬件来完成。前述的程序可以存储于一计算机可读取存储介质中。该程序在执行时,执行包括上述各方法实施例的步骤;而前述的存储介质包括:ROM、RAM、磁碟或者光盘等各种可以存储程序代码的介质。Those of ordinary skill in the art can understand that all or part of the steps of implementing the above method embodiments may be completed by program instructions related to hardware. The aforementioned program can be stored in a computer-readable storage medium. When the program is executed, the steps including the above method embodiments are executed; and the foregoing storage medium includes: ROM, RAM, magnetic disk or optical disk and other media that can store program codes.
Claims (8)
Priority Applications (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
CN202010717565.7A CN112039782B (en) | 2017-01-25 | 2017-01-25 | Multi-branch jump co-processing method and device |
Applications Claiming Priority (2)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
CN201710061332.4A CN107018078B (en) | 2017-01-25 | 2017-01-25 | Multi-branch jump co-processing method and device |
CN202010717565.7A CN112039782B (en) | 2017-01-25 | 2017-01-25 | Multi-branch jump co-processing method and device |
Related Parent Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
CN201710061332.4A Division CN107018078B (en) | 2017-01-25 | 2017-01-25 | Multi-branch jump co-processing method and device |
Publications (2)
Publication Number | Publication Date |
---|---|
CN112039782A CN112039782A (en) | 2020-12-04 |
CN112039782B true CN112039782B (en) | 2022-01-18 |
Family
ID=59440064
Family Applications (2)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
CN201710061332.4A Active CN107018078B (en) | 2017-01-25 | 2017-01-25 | Multi-branch jump co-processing method and device |
CN202010717565.7A Active CN112039782B (en) | 2017-01-25 | 2017-01-25 | Multi-branch jump co-processing method and device |
Family Applications Before (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
CN201710061332.4A Active CN107018078B (en) | 2017-01-25 | 2017-01-25 | Multi-branch jump co-processing method and device |
Country Status (1)
Country | Link |
---|---|
CN (2) | CN107018078B (en) |
Families Citing this family (2)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
WO2020124400A1 (en) * | 2018-12-19 | 2020-06-25 | 华为技术有限公司 | Multi-branch skip processing apparatus and method, and processor |
CN112822112B (en) * | 2020-12-31 | 2022-08-19 | 苏州盛科通信股份有限公司 | Routing address storage method and device |
Citations (4)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN101039215A (en) * | 2006-08-10 | 2007-09-19 | 华为技术有限公司 | Method and system for maintaining ternary content addressable memory items |
CN102957617A (en) * | 2011-08-18 | 2013-03-06 | 盛科网络(苏州)有限公司 | Method and device for superimposing multiple services |
WO2014041451A1 (en) * | 2012-09-14 | 2014-03-20 | International Business Machines Corporation | Using special-case hardware units for facilitating access control lists on networking element |
US9413662B1 (en) * | 2009-01-13 | 2016-08-09 | Juniper Networks, Inc. | Intra-term logical or operation in a network filter |
Family Cites Families (8)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US7356033B2 (en) * | 2002-11-21 | 2008-04-08 | Lucent Technologies Inc. | Method and apparatus for performing network routing with use of power efficient TCAM-based forwarding engine architectures |
US8089961B2 (en) * | 2007-12-07 | 2012-01-03 | University Of Florida Research Foundation, Inc. | Low power ternary content-addressable memory (TCAMs) for very large forwarding tables |
CN101350771B (en) * | 2008-07-07 | 2010-12-29 | 中国人民解放军国防科学技术大学 | Method and system for storing elements of tri-state content addressable memory without ordering |
US9049157B1 (en) * | 2009-08-16 | 2015-06-02 | Compass Electro-Optical Systems Ltd | Method and device for improving scalability of longest prefix match |
CN102571494B (en) * | 2012-01-12 | 2014-11-05 | 东北大学 | Field programmable gate array-based (FPGA-based) intrusion detection system and method |
CN102663051B (en) * | 2012-03-29 | 2014-12-10 | 浪潮(北京)电子信息产业有限公司 | Method and system for searching content addressable memory |
US9098601B2 (en) * | 2012-06-27 | 2015-08-04 | Futurewei Technologies, Inc. | Ternary content-addressable memory assisted packet classification |
CN104284346B (en) * | 2014-10-14 | 2017-11-10 | 国家电网公司 | Wireless optical broadband access network Optimization deployment method based on survivability heavy-route |
-
2017
- 2017-01-25 CN CN201710061332.4A patent/CN107018078B/en active Active
- 2017-01-25 CN CN202010717565.7A patent/CN112039782B/en active Active
Patent Citations (4)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN101039215A (en) * | 2006-08-10 | 2007-09-19 | 华为技术有限公司 | Method and system for maintaining ternary content addressable memory items |
US9413662B1 (en) * | 2009-01-13 | 2016-08-09 | Juniper Networks, Inc. | Intra-term logical or operation in a network filter |
CN102957617A (en) * | 2011-08-18 | 2013-03-06 | 盛科网络(苏州)有限公司 | Method and device for superimposing multiple services |
WO2014041451A1 (en) * | 2012-09-14 | 2014-03-20 | International Business Machines Corporation | Using special-case hardware units for facilitating access control lists on networking element |
Also Published As
Publication number | Publication date |
---|---|
CN107018078B (en) | 2020-08-07 |
CN107018078A (en) | 2017-08-04 |
CN112039782A (en) | 2020-12-04 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
CN109639579B (en) | Multicast message processing method and device, storage medium and processor | |
CN103019884B (en) | Memory page de-weight method and memory page de-weight device based on virtual machine snapshot | |
US20160337247A1 (en) | Network controller security monitor | |
US9294390B2 (en) | Hash table storage and search methods and devices | |
CN108011823B (en) | Multi-stage method and device for multi-domain flow table and multi-stage flow table searching method and device | |
WO2018068524A1 (en) | Routing-table establishment and ip routing lookup method, device, and storage medium | |
JP2004023450A (en) | Router device | |
WO2016184029A1 (en) | Storage and lookup methods and apparatuses supporting hash lookup and routing lookup, and storage medium | |
WO2015127721A1 (en) | Data matching method and apparatus and computer storage medium | |
CN102232219A (en) | Method and device for storing and searching keyword | |
CN115695014B (en) | Access control list construction and data message processing method, device and system | |
CN112039782B (en) | Multi-branch jump co-processing method and device | |
CN115987888B (en) | Routing address storage method, device, network equipment and storage medium | |
JP2017537566A (en) | Routing table maintenance method, apparatus and storage medium | |
CN107276916B (en) | Switch flow table management method based on protocol-aware forwarding technology | |
CN112087389B (en) | A method, system, storage medium and terminal for message matching look-up table | |
CN112187743B (en) | Network policy matching method and system based on IP address longest prefix | |
CN107483238A (en) | A log management method, cluster management node and system | |
CN114448890B (en) | Addressing methods, devices, electronic equipment and storage media | |
Ha et al. | Efficient flow table management scheme in SDN-based cloud computing networks | |
CN118282943A (en) | Method and device for searching route table item | |
WO2016091027A1 (en) | Rule aggregation method and device for network address translation and access control list | |
CN104301227B (en) | High-speed low-power-consumption IP route table lookup method based on TCAM | |
WO2022267018A1 (en) | Packet matching method and apparatus, network device, and medium | |
WO2016173196A1 (en) | Method and apparatus for learning address mapping relationship |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
PB01 | Publication | ||
PB01 | Publication | ||
SE01 | Entry into force of request for substantive examination | ||
SE01 | Entry into force of request for substantive examination | ||
GR01 | Patent grant | ||
GR01 | Patent grant |