Method and apparatus for pattern matching

Patent metadata

Field	Value
Publication number	US-9704574-B1
Application number	US-201414331472-A
Country	US
Kind code	B1
Filing date	Jul 15, 2014
Priority date	Jul 26, 2013
Publication date	Jul 11, 2017
Grant date	Jul 11, 2017

Abstract

Aspects of the disclosure provide an apparatus that includes a key generator, a first memory, a second memory, and a controller. The key generator is configured to generate a first search key, and one or more second search keys in response to a pattern. The first memory is configured to compare the first search key to a plurality of entries populated in the first memory, and determine an index of a matching entry to the first search key. The second memory is configured to respectively retrieve one or more exact match indexes of the one or more second search keys from one or more exact match pattern groups populated in the second memory. The controller is configured to select a search result for the pattern from among the index output from the first memory and the one or more exact match indexes output from the second memory.

First claim

What is claimed is:

1. An apparatus, comprising:
a key generator configured to generate a first search key, and one or more second search keys in response to a pattern;
a first memory configured to compare the first search key to a plurality of entries populated in the first memory, and determine an index of a matching entry to the first search key;
a second memory configured to respectively retrieve one or more exact match indexes of the one or more second search keys from one or more exact match pattern groups populated in the second memory; and
a controller configured to select a search result for the pattern from among the index output from the first memory and the one or more exact match indexes output from the second memory.

2. The apparatus of claim 1 , wherein the first memory is a content addressable memory (CAM).

3. The apparatus of claim 1 , wherein the second memory is configured to store the one or more exact match pattern groups in the form of at least one of hash tables, multi-hash tables and a binary content addressable memory (BCAM).

4. The apparatus of claim 1 , wherein the first memory and the second memory are configured to operate in parallel to respectively output the index of the matching entry to the first search key and the one or more exact match indexes of the one or more second search keys.

5. The apparatus of claim 1 , wherein the controller is configured to select the search result according to priority information of the matching entry and the one or more exact match indexes.

6. The apparatus of claim 1 , wherein an exact match pattern group includes a plurality of entries, and each entry is configured to store an entry key with associated priority information.

7. The apparatus of claim 6 , wherein the exact match pattern group is configured to output an index of an entry and priority information of the entry when an entry key of the entry matches a second search key for the exact match pattern group.

8. The apparatus of claim 1 , wherein an exact match pattern group includes random access memory that is accessed based on a hash look-up of a second key.

9. The apparatus of claim 1 , further comprising:
a driver configured to receive a rule with one or more classifiers, and to select one of the first memory and the second memory to populate the rule to maximize a usage of the second memory.

10. The apparatus of claim 9 , wherein the driver is configured to add a new exact match pattern group in the second memory to fit the classifiers of the rule, and move entries in the first memory with the same classifiers as the rule to the new exact match pattern group in the second memory.

11. The apparatus of claim 9 , wherein the driver is configured to move a smallest exact match pattern group to the first memory in order to have enough space to add a new exact match pattern group in the second memory for the rule.

12. A method, comprising:
generating a first search key, and one or more second search keys in response to a pattern;
comparing the first search key to a plurality of entries populated in a first memory to determine an index of a matching entry to the first search key;
respectively retrieving one or more exact match indexes of the one or more second search keys from one or more exact match pattern groups populated in a second memory; and
selecting a search result for the pattern from among the index output from among the first memory and the one or more exact match indexes output from the second memory.

13. The method of claim 12 , wherein comparing the first search key to the plurality of entries populated in the first memory to determine the index of the matching entry to the search key further comprises:
comparing the search first key to the plurality of entries populated in a content addressable memory (CAM) to determine the index of the matching entry to the first search key.

14. The method of claim 12 , wherein respectively retrieving the one or more exact match indexes of the one or more second search keys from the one or more exact match pattern groups populated in the second memory further comprises:
respectively retrieving the one or more exact match indexes of the one or more second search keys from the one or more exact match pattern groups populated in the second memory in the form of at least one of hash tables, multi-hash tables and a binary content addressable memory (BCAM).

15. The method of claim 12 , wherein the comparing operation in the first memory and the retrieving operation in the second memory from the one or more exact match pattern groups are executed in parallel.

16. The method of claim 12 , wherein selecting the search result for the pattern from among the index output from the first memory and the one or more exact match indexes output from the second memory further comprises:
selecting the search result according to priority information of the matching entry and the one or more exact matches.

17. The method of claim 12 , further comprising:
storing an entry key with associated priority information in an entry of an exact match pattern group; and
outputting an index of the entry and the priority information of the entry when the entry key matches a second search key for the exact match pattern group.

18. The method of claim 12 , further comprising:
receiving a new rule with one or more classifiers, and
selecting one of the first memory and the second memory to populate the new rule to maximize a usage of the second memory.

19. The method of claim 18 , further comprising:
adding a new exact match pattern group in the second memory to fit the classifiers of the new rule; and
moving entries in the first memory with the same classifiers as the new rule to the new exact match pattern group in the second memory.

20. The method of claim 18 , further comprising:
moving a smallest exact match pattern group to the first memory in order to have enough space to add a new exact match pattern group in the second memory for the new rule.

Assignees

• Marvell Int Ltd

Inventors

• Shamis Michael

Classifications

• G11C15/04 Primary

  using semiconductor elements · CPC title

• G06F2212/00

  Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures · CPC title

• G06F17/30982

  Physics · mapped topic

• 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

• G06F16/90339

  by using parallel associative memories or content-addressable memories · CPC title