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

Patent metadata

Field	Value
Publication number	US-9432284-B2
Application number	US-201414150572-A
Country	US
Kind code	B2
Filing date	Jan 8, 2014
Priority date	Jan 8, 2014
Publication date	Aug 30, 2016
Grant date	Aug 30, 2016

Abstract

A packet classification system, methods, and apparatus are provided for packet classification. A processor of a router coupled to a network compiles at least one search tree based on a rules set. The processor determines an x number of search phases needed to process an incoming key corresponding to the rules set, wherein the 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. The processor generates an x set of search trees, where each of the x set of search trees corresponds to a respective one of the x number of search phases. Also, the processor provides the x set of search trees to a search processor, where each of the x set of search trees is configured to process respective portions of the incoming key.

First claim

The invention claimed is:

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

Assignees

• Cavium Inc

Inventors

• Goyal Rajan
• Bullis Kenneth

Classifications

• H04L45/48 Primary

  Routing tree calculation · CPC title

• H04L45/484 Primary

  using multiple routing trees · CPC title

• H04L47/2441

  relying on flow classification, e.g. using integrated services [IntServ] · CPC title

• H04L45/74

  Address processing for routing · CPC title

• H04L45/08

  Learning-based routing, e.g. using neural networks or artificial intelligence · CPC title