Hybrid wildcard match table

Patent metadata

Field	Value
Publication number	US-11943142-B2
Application number	US-202117534294-A
Country	US
Kind code	B2
Filing date	Nov 23, 2021
Priority date	Nov 10, 2014
Publication date	Mar 26, 2024
Grant date	Mar 26, 2024

Abstract

Embodiments of the present invention are directed to a wildcard matching solution that uses a combination of static random access memories (SRAMs) and ternary content addressable memories (TCAMs) in a hybrid solution. In particular, the wildcard matching solution uses a plurality of SRAM pools for lookup and a spillover TCAM pool for unresolved hash conflicts.

First claim

We claim:

1. A network switch comprising:
a static random access memory (SRAM) entry table including a plurality of entries, wherein each of the entries comprise:
a code field including one or more codes; and
a value field including rule comparison data; and

one or more SRAM pools;
at least one spillover ternary content addressable memory (TCAM) pool; and
a non-transitory computer readable medium storing request interface control logic dispatching a search key to one or more of the SRAM pools and the at least one spillover TCAM pool and determining if the search key is a match for one or more of the entries based on which of the codes are satisfied by the search key and which of the codes are not satisfied by the search key.

2. The network switch of claim 1 , wherein each of the codes occupies either 2 bytes or 3 bytes of the code field.

3. The network switch of claim 2 , wherein at least one of the codes is an equal-match type code or a not-equal-match type code, the at least one of the codes comprising:
an identifier that distinguishes the at least one of the codes from other types of the codes;
a nibble index that identifies a location of match data to compare within both the search key and the value field; and
a bit length that indicates a number of bits after the location within both the search key and the value field to compare as the data, wherein the at least one of the codes relates to determining if the match data of the search key is the same as the match data from the value field.

4. The network switch of claim 3 , wherein at least another one of the codes is an in-range type code or a not-in-range type code, the at least another one of the codes comprising:
an identifier that distinguishes the at least another one of the codes from the other types of the codes;
a byte index that identifies a location of data relating to a lower boundary of the at least another one of the codes within the value field and a location of target data within the search key; and
an upper boundary field that includes data relating to an upper boundary of the at least another one of the codes, wherein the at least another one of the codes relates to determining if the target data is within or outside of the upper boundary and the lower boundary.

5. The network of claim 4 , wherein the at least one of the codes occupies 2 bytes of the code field and the at least another one of the codes occupies 3 bytes of the code field.

6. The network of claim 5 , wherein a priority field of each of the entries comprises combination data that indicates what combination of results of evaluating each of the codes of the rule with respect to the search key qualify as the search key matching the entry.

7. The network of claim 6 , wherein each of the at least another one of the codes is limited to a predetermined maximum bit size range that is less than a desired bit size range, and further wherein the combination data is based on an in-range type code for the desired bit size range or an out-of-range type code for the desired bit size such that the combination data indicates a logical combination of a plurality of the codes of the entry that when evaluated results in output that is equivalent to the in-range type code for the desired bit size range or the out-of-range type code for the desired bit size.

8. The network switch of claim 7 , wherein a hybrid wildcard match (WCM) table is accessible by the SRAM pools, the at least one spillover TCAM pool, and the request interface control logic.

9. The network switch of claim 8 , wherein the hybrid WCM includes configurations for the SRAM pools, the at least one spillover TCAM pool, and the request interface control logic.

10. The network switch of claim 9 , wherein the configurations identify which of the SRAM pools and the at least one spillover TCAM pool are active pools.

11. The network switch of claim 10 , wherein arbitration takes place to determine which of the one or more active pools has priority to return the results data.

12. A method of implementing a network switch that includes one or more static random access memory (SRAM) pools and at least one spillover ternary content addressable memory (TCAM) pool, the method comprising:
with the network switch:
identifying an entry;
if the entry is hashable, inserting the entry into one of the SRAM pools, wherein the entry as inserted into the one of the SRAM pools comprises:
a code field including one or more codes; and
a value field including rule comparison data; and
if the entry is not hashable, inserting the entry into the at least one spillover TCAM pool, wherein a match between at least a portion of a search key and at least a portion of the rule comparison data is based on which of the codes are satisfied by the portion of the search key and which of the codes are not satisfied by the portion of the search key.

13. The method of claim 12 , wherein each of the codes occupies either 2 bytes or 3 bytes of the code field.

14. The method of claim 13 , wherein at least one of the codes is an equal-match type code or a not-equal-match type code, the at least one of the codes comprising:
an identifier that distinguishes the at least one of the codes from other types of the codes;
a nibble index that identifies a location of match data to compare within both the search key and the value field; and
a bit length that indicates a number of bits after the location within both the search key and the value field to compare as the data, wherein the at least one of the codes relates to determining if the match data of the search key is the same as the match data from the value field.

15. The method of claim 14 , wherein at least another one of the codes is an in-range type code or a not-in-range type code, the at least another one of the codes comprising:
an identifier that distinguishes the at least another one of the codes from the other types of the codes;
a byte index that identifies a location of data relating to a lower boundary of the at least another one of the codes within the value field and a location of target data within the search key; and
an upper boundary field that includes data relating to an upper boundary of the at least another one of the codes, wherein the at least another one of the codes relates to determining if the target data is within or outside of the upper boundary and the lower boundary.

16. The method of claim 15 , wherein the at least one of the codes occupies 2 bytes of the code field and the at least another one of the codes occupies 3 bytes of the code field.

17. The method of claim 16 , wherein a priority field of each of the entries comprises combination data that indicates what combination of results of evaluating each of the codes of the rule with respect to the search key qualify as the search key matching the entry.

18. The method of claim 17 , wherein each of the at least another one of the codes is limited to a predetermined maximum bit size range that is less than a desired bit size range, and further wherein the combination data is based on an in-range type code for the desired bit size range or an out-of-range type code for the desired bit size such that the combination data indicates a logical combination of a plurality of the codes of the entry that when evaluated results in output that is equivalent to the in-range type code for the desired bit size range or the out-of-range type code for the desired bit size.

19. The method of claim 12 , further comprising determining whether or not the entry is hashable

Assignees

• Marvell Asia Pte Ltd

Inventors

• Huynh Jeffrey T
• Wang Weihuang
• Daniel Tsahi
• Atluri Srinath
• Balan Mohan

Classifications

• H04L45/74591 Primary

  using content-addressable memories [CAM] · CPC title

• G11C15/00

  Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores · CPC title

• H04L45/54

  Organization of routing tables · CPC title

• H04L69/22

  Parsing or analysis of headers · CPC title

• H04L45/7453 Primary

  using hashing · CPC title