Method and apparatus for compiling search trees for processing request keys based on a key size supported by underlying processing elements

1. A method, executed by one or more processors of a router, for compiling at least one search tree based on an original rules set, the method comprising:

determining an x number of search phases needed to process an incoming key corresponding to the original rules set, wherein the original rules set includes a plurality of rules, where each of the plurality of rules includes an n number of rule fields and where the incoming key includes an n number of processing fields and wherein each of the x number of search phases corresponds to a respective portion of a plurality of portions of the incoming key;

generating y sets of search trees, where each of the y sets of search trees corresponds to a respective one of the x number of search phases;

providing the y sets of search trees to a search processor of the router, where each of the y sets of search trees is configured to process the respective portion of the incoming key;

generating a subject set of search trees of the y sets of search trees using a subject rule field subset of a plurality of rule field subsets assigned to the respective one of the x number of search phases associated with the subject set of search trees;

receiving a current search phase rule set from which to generate the subject set of search trees, wherein the current search phase rule set is at least one of: the original rule set or a rule set received from generating a previous set of search trees;

compiling nodes of the subject set of search trees, wherein the nodes include at least one of: a root node, at least one intermediate node, and at least one leaf node;

identifying intersections of a leaf node rule set, wherein the leaf node rule set are a subset of the rule set that are in the at least one leaf node; and

processing, by the router, the leaf node rule set and the identified intersections, to process received packets.

2. The method of claim 1 wherein determining the x number of search phases needed includes determining a processing capability of a processing system for processing the incoming key.

3. The method of claim 1 further comprising:

partitioning the n rule fields into a plurality of rule field subsets; and

assigning each of the plurality of rule field subsets to a respective one of the x number of search phases.

4. The method of claim 3 wherein no two of the plurality of rule field subsets are assigned to a same search phase of the x number of search phases.

5. The method of claim 3 wherein a rule field of the n rule fields is partitioned into only one of the plurality of rule field subsets.

6. The method of claim 1 further comprising:

for each node of the subject set of search trees:

identifying lower priority rules that are completely overlapped by a higher priority rule, where an overlap of rules is based on a subset of the n number of rule fields corresponding to a subset of the x number of search phases that includes a current search phase and remaining subsequent search phases; and

removing each of the identified lower priority rules.

7. The method of claim 6 further comprising:

for each rule in a subject segment of the identified at least one segment, generating a rule for subsequent search phases of the x number of search phases, wherein the rule includes: i) remaining unprocessed rule fields out of the n number of rule fields corresponding to the subsequent search phases of the x number of search phases, and ii) a new field for the unique cookie value associated with the subject segment; and

for each of the generated rules from the subject segment, assigning a relative priority equivalent to a relative priority of the corresponding rule of the subject segment.

8. The method of claim 1 further comprising:

identifying at least one segment of the leaf node rule set, wherein the at least one segment is a region of the leaf node rule set that intersects a same subset of rules of the leaf node rule set;

assigning a unique cookie value to each of the identified at least one segment;

for a subject segment of the identified at least one segment:

defining a new rule including fields that describe the subject segment;

storing the assigned unique cookie value as associated with the subject segment as associated data of the new rule; and

replacing the leaf node rule set with each new rule of each of the identified at least one segment.

9. The method of claim 8 wherein each of the identified at least one segment associated with the same subset of rules of the leaf node rule set is assigned a same cookie value.

10. The method of claim further comprising:

for a subject leaf node of the subject set of search trees:

identifying subsets of rules in the leaf node rule set that include intersecting regions;

for each one of the intersecting regions, adding a rule to the leaf node rule set, wherein fields of the added rule describe the corresponding intersecting region;

prioritizing a subject added rule based on a number of intersecting rules of a subject intersecting region of the intersecting regions for which the added rule is associated; and

assigning a unique cookie value to each rule in the subject leaf node.

11. The method of claim 10 wherein each new rule added to the leaf node rule set has a higher priority than each original rule of the leaf node rule set.

12. The method of claim 10 further comprising:

for a subject original rule of each original rule in the subject leaf node, generating a rule for subsequent search phases of the x number of search phases, wherein the rule includes: i) remaining rule fields of the n number of rule fields corresponding to the subsequent search phases of the x number of search phases, and ii) a new field for the unique cookie value associated with the subject rule;

for each rule in a subject subset of the identified subsets, generating a rule for the subsequent search phases of the x number of search phases, wherein the rule includes: i) remaining rule fields of the n number of rule fields corresponding to the subsequent search phases of the x number of search phases, and ii) a new field for the unique cookie value associated with the subject subset; and

for each of the generated rules for the subject subset, assigning a relative priority equivalent to a relative priority of a corresponding intersecting rule of the subject subset.

13. The method of claim 1 further comprising:

for the at least one leaf node:

determining if a number of rules in the leaf node exceeds a predetermined threshold in response to adding the new rules to the rules in the leaf node; and

if the number of rules exceeds the predetermined threshold, expanding the search tree at the subject leaf node.

14. An apparatus for compiling at least one search tree based on an original rules set, the apparatus comprising:

a memory;

one or more processors coupled to the memory, the one or more processors configured to:

determine an x number of search phases needed to process an incoming key corresponding to the original rules set, wherein the original rules set includes a plurality of rules, where each of the plurality of rules includes an n number of rule fields and where the incoming key includes an n number of processing fields and wherein each of the x number of search phases corresponds to a respective portion of a plurality of portions of the incoming key;

generate y sets of search trees, where each of the y sets of search trees corresponds to a respective one of the x number of search phases;

providing the y sets of search trees to a search processor of a router, where each of the y sets of search trees is configured to process the respective portion of the incoming key;

generate a subject set of search trees of the y sets of search trees using a subject rule field subset of a plurality of rule field subsets assigned to the respective one of the x number of search phases associated with the subject set of search trees;

receive a current search phase rule set from which to generate the subject set of search trees, wherein the current search phase rule set is at least one of: the original rule set or a rule set received from generating a previous set of search trees;

compile nodes of the subject set of search trees, wherein the nodes include at least one of: a root node, at least one intermediate node, and at least one leaf node;

identify intersections of a leaf node rule set, wherein the leaf node rule set are a subset of the rule set that are in the at least one leaf node; and

process the leaf node rule set and the identified intersections to process received packets.

15. The apparatus of claim 14 wherein the one or more processors are further configured to determine the x number of search phases needed includes determining a processing capability of a processing system for processing the incoming key.

16. The apparatus of claim 14 wherein the one or more processors are further configured to:

partition the n rule fields into a plurality of rule field subsets; and

assign each of the plurality of rule field subsets to a respective one of the x number of search phases.

17. The apparatus of claim 16 wherein no two of the plurality of rule field subsets are assigned to a same search phase of the x number of search phases.

18. The apparatus of claim 16 wherein a rule field of the n rule fields is partitioned into only one of the plurality of rule field subsets.

19. The apparatus of claim 14 wherein the one or more processors are further configured to:

for each node of the subject set of search trees:

identify lower priority rules that are completely overlapped by a higher priority rule, where an overlap of rules is based on a subset of the n number of rule fields corresponding to a subset of the x number of search phases that includes a current search phase and remaining subsequent search phases; and

remove each of the identified lower priority rules.

20. The apparatus of claim 19 wherein the one or more processors are further configured to:

for each rule in a subject segment of the identified at least one segment, generate a rule for subsequent search phases of the x number of search phases, wherein the rule includes: i) remaining unprocessed rule fields out of the n number of rule fields corresponding to the subsequent search phases of the x number of search phases, and ii) a new field for the unique cookie value associated with the subject segment; and

for each of the generated rules from the subject segment, assign a relative priority equivalent to a relative priority of the corresponding rule of the subject segment.

21. The apparatus of claim 14 wherein the one or more processors are further configured to:

identify at least one segment of the leaf node rule set, wherein the at least one segment is a region of the leaf node rule set that intersects a same subset of rules of the leaf node rule set;

assign a unique cookie value to each of the identified at least one segment;

for a subject segment of the identified at least one segment:

define a new rule including fields that describe the subject segment;

store the assigned unique cookie value as associated with the subject segment as associated data of the new rule; and

replace the leaf node rule set with each new rule of each of the identified at least one segment.

22. The apparatus of claim 21 wherein each of the identified at least one segment associated with the same subset of rules of the leaf node rule set is assigned a same cookie value.

23. The apparatus of claim 14 wherein the one or more processors are further configured to:

for a subject leaf node of the subject set of search trees:

identify subsets of rules in the leaf node rule set that include intersecting regions;

for each one of the intersecting regions, add a rule to the leaf node rule set, wherein fields of the added rule describe the corresponding intersecting region;

prioritize a subject added rule based on a number of intersecting rules of a subject intersecting region of the intersecting regions for which the added rule is associated; and

assign a unique cookie value to each rule in the subject leaf node.

24. The apparatus of claim 23 wherein each new rule added to the leaf node rule set has a higher priority than each original rule of the leaf node rule set.

25. The apparatus of claim 23 further comprising:

for a subject original rule of each original rule in the subject leaf node, generate a rule for subsequent search phases of the x number of search phases, wherein the rule includes: i) remaining rule fields of the n number of rule fields corresponding to the subsequent search phases of the x number of search phases, and ii) a new field for the unique cookie value associated with the subject rule;

for each rule in a subject subset of the identified subsets, generate a rule for the subsequent search phases of the x number of search phases, wherein the rule includes: i) remaining rule fields of the n number of rule fields corresponding to the subsequent search phases of the x number of search phases, and ii) a new field for the unique cookie value associated with the subject subset; and

for each of the generated rules for the subject subset, assign a relative priority equivalent to a relative priority of a corresponding intersecting rule of the subject subset.

26. The apparatus of claim 14 wherein the one or more processors are further configured to:

for the at least one leaf node:

determine if a number of rules in the leaf node exceeds a predetermined threshold in response to adding the new rules to the rules in the leaf node; and

if the number of rules exceeds the predetermined threshold, expand the search tree at the subject leaf node.