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

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.

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.