Granted Patent B1

US 9,590,897 · App. 14/632,200 · Granted Mar 7, 2017

Abstract

Claims (49)

1. A machine-implemented method for processing network packets, comprising:

determining common key type sets from a plurality of network processing rules;

wherein determining the common key type sets from the plurality of network processing rules comprises:

determining a first key type set from one of the plurality of network processing rules;

comparing the first key type set to a set of known key type sets;

when the first key type set is found as a known key type set, incrementing a counter associated with the known key type set; and

when the first key type set is not found as a known key type set, adding the first key type set to the known key type set and associating a new counter value with the first key type set;

creating one or more hash data structures using the most common key type sets;

programming network processing rules that use the most common key type sets into the one or more hash data structures;

programming remaining network processing rules into a content addressable memory (CAM); and

using the one or more hash data structures and the CAM to find an appropriate network processing rule to process a network packet.

2. The method of claim 1 , further comprising:

programming at least one rule into the CAM directing matches to use an action output of an associated hash data structure of the one or more hash data structures.

3. The method of claim 2 , wherein the one or more hash data structures outputs at least one hash data structure priority value and the hash data structure priority value is used as a search key in the CAM.

4. The method of claim 1 , wherein the CAM is a ternary content addressable memory (TCAM).

5. The method of claim 1 , wherein the hash data structures are implemented in a different memory type than the CAM.

6. The method of claim 1 , wherein determining the common key type sets further comprises: processing a key type set for each of the plurality of network processing rules.

7. The method of claim 6 , wherein creating one or more hash data structures using the most common key type sets uses counters associated with the set of known key type sets to determine the most common key type sets.

8. A network device for processing network transmissions, the device comprising:

a processing module for processing the network transmission;

a content addressable memory (CAM);

a memory type different from the CAM for storing a set of one or more hash data structures, the one or more hash data structures outputting hash data structure priority values and action indications;

wherein the CAM and the one or more hash data structures share a network transmission processing rule set; and

wherein the processing module searches the set of one or more hash data structures and uses the output hash data structure priority values to search the CAM to determine how to handle the network transmission and processes the network transmission according to the determination;

wherein processing of the network transmission according to the determination comprises:

processing the network transmission according to an action output of a first hash data structure when a CAM search result indicates a first hash data structure action:

processing the network transmission according to an action output of a second hash data structure when a CAM search result indicates a second hash data structure action; and

a processing the network transmission according to a rule coded in the CAM when the CAM search result does not indicate a first hash data structure action or a second hash data structure action.

9. The network device of claim 8 , wherein the CAM is a ternary CAM (TCAM).

10. The network device of claim 8 , further comprising an optimization module, the optimization module adapted to process a set of network processing rules to create the set of one or more hash data structures and populate the CAM with the hash data structure priority values as search keys to locate a portion of the transmission processing rule set.

11. The network device of claim 10 , wherein the optimization module populates at least one of the set of one or more hash data structures based on the most common search key set in the set of network processing rules.

12. The network device of claim 10 , wherein the optimization module reprocesses the set of network processing rules to create the set of one or more hash data structures and populate the CAM with a portion of the transmission processing rule set after receiving a determined number of changes to the set of network processing rules.

13. The network device of claim 10 wherein the optimization module populates at least one of the set of one or more hash data structures based in part on a widest search key in the set of network processing rules.

14. A machine-implemented method for processing a network transmission, comprising:

accepting an incoming network transmission at a network device, the network transmission including one or more packet fields;

generating packet search keys based on the one or more packet fields;

performing a search of a first hash data structure using at least some of the packet search keys as defined by the first hash data structure and reading a match priority when there is a hash data structure match;

searching a content addressable memory (CAM) using at least the match priority as an input; and

processing the network transmission according to the result of the CAM search;

wherein processing the network transmission according to the result of the CAM search comprises:

processing the network transmission according to an action output of the first hash data structure when the CAM search result indicates a first hash data structure action;

processing the network transmission according to an action output of the second hash data structure when the CAM search result indicates a second hash data structure action; and

processing the network transmission according to a rule coded in the CAM when the CAM search result does not indicate a first hash data structure action or a second hash data structure action.

15. The method of claim 14 , further comprising:

performing a search of a second hash data structure using at least some of the packet search keys as defined by the second hash data structure and reading a second match priority when there is a second hash data structure match;

wherein the searching of the CAM further uses the second match priority as another input.

16. The method of claim 14 , wherein the CAM includes a flow data structure.

17. The method of claim 14 , wherein the CAM is a ternary content addressable memory (TCAM).

18. The method of claim 14 , wherein the hash data structures are implemented in a different memory type than the CAM.

Assignments (7)