Packet preclassification search tree algorithms
View Patent ↗An information packet preclassification system and method are provided. The method receives a packet of information and differentiates the packet into segments. Using a decision tree with multiple levels, segments in the packet are compared to a node at a tree level, where each node includes a plurality of node reference segments and corresponding node comparison operators. The reference segment may be a different segment from the packet, or a predetermined segment value stored in memory. One, or more classification attributes are accessed in response to comparing segments, and the classification attributes are assigned to the packet. Then, the packet is processed in response to the classification attributes.
1. An information packet preclassification method comprising:
an input interface port receiving a packet of information;
a packet parsing engine (PPE) differentiating the packet into segments;
using a PPE decision tree random access memory (RAM) including a logic decision tree with multiple levels, comparing segments in the packet to a node at a tree level, where branching to the node in the second tree level includes branching to a last decision node and where each node includes a plurality of node reference segments and corresponding node comparison operators, the comparing further including branching to a key node in response to the comparing of segments in the packet to a last decision node;
in response to comparing segments, the PPE accessing a classification attribute in a classification database in response to the decision tree comparisons that include accessing classification pointers in the key node; and,
the PPE assigning the classification attribute to the packet.
2. The method of claim 1 further comprising:
a processor processing the packet in response to the classification attribute.
3. The method of claim 2 wherein the PPE controller hashes selected segments in the packet, and, wherein processing the packet in response to the classification attribute includes managing a flow of packets to a plurality of processors in response hashed segment values in the packet.
4. The method of claim 1 wherein accessing the classification attribute includes accessing a plurality of classification attributes; and,
wherein assigning the classification attribute to the packet includes assigning a plurality of classification attributes to the packet.
5. The method of claim 1 wherein comparing segments includes making a comparison between a first reference segment in the packet and node reference segments selected from a group consisting of a second reference segment in the packet and a predetermined segment value stored in memory.
6. The method of claim 1 wherein comparing segments includes:
at a first tree level, comparing a first segment in the packet to reference segments in an intermediate node,
in response to the comparisons, branching to a node in a second tree level, and, comparing a second segment in the packet to a plurality of reference segments in the second tree level node.
7. The method of claim 1 wherein comparing segments includes:
selecting a group of packet segments, creating a chained packet segment from the group of packet segments, and,
comparing the chained packet segment to a node including a plurality of chained reference segments.
8. The method of claim 1 further comprising:
a user interface (UI), the UI, prior to receiving the packet:
selecting reference segments for a node;
selecting comparison operators for a node;
selecting branches between nodes on different tree levels; and,
selecting the number of tree levels.
9. The method of claim 1 further comprising:
a UI, the UI, prior to receiving the packet:
selecting classification pointers for a key node; and,
selecting the number of classification pointers per key node.
10. The method of claim 1 further comprising:
a UI, the UI, prior to receiving the packet, selecting segments in the packet to be compared.
11. A system for preclassifying information packets, the system comprising:
an input interface with a plurality of ports to accept information packets;
a plurality of packet parsing engines (PPEs), each PPE connected to a corresponding port
to receive a packet and differentiate the packet into segments, the PPE including: a packet random access memory (RAM) for storing packet segments; a decision tree RAM for storing a logic decision tree with multiple tree levels, where each node includes a plurality of node reference segments and corresponding node comparison operators; and,
a controller having an interface for accessing the packet RAM and decision tree RAM, for comparing segments in the packet to nodes in the decision tree, and deriving classification pointers for the packet, the controller further hashing selected packet segments stored in the packet RAM in response to comparing segments in the packet to nodes in the decision tree; and,
a classification database having an interface to accept classification pointers from the plurality of PP Es, and an output to supply classification attributes for packets in response to receiving the classification pointers; and,
a processor having an interface to receive packets and classification attributes associated with the packets, the processor supplying processed packets responsive to their respective classification attributes and further including a plurality of processing engines for managing the order of packets in response to hashed segment values associated therewith.
12. The system of claim 11 wherein the PPE controller derives a plurality of classification pointers for a packet; and,
wherein the classification database assigns a plurality of classification attributes to the packet, in response to receiving the plurality of classification pointers.
13. The system of claim 11 wherein the PPE controller makes a comparison between a first reference segment in the packet and node reference segments selected from a group consisting of a second reference segment in the packet and a predetermined segment value stored in the logic tree RAM.
14. The system of claim 11 wherein the logic tree RAM includes:
a first tree level with a node for comparing a first segment in the packet to reference segments in an intermediate node;
inter-tree level branches, responsive to comparisons made in the first tree level node; and,
a second tree level with a node connected to the first tree level node via the inter-tree level branches, for comparing a second segment in the packet to a plurality of reference segments.
15. The system of claim 14 wherein the second tree level node is a last decision node; and,
wherein the logic tree RAM includes a key node connected to the last decision node via the inter-tree level branches, for accessing classification pointers.
16. The system of claim 15 wherein the PPE controller selects a group of packet segments from the packet RAM, creates a chained packet segment from the group of packet segments, accesses a plurality of chained reference segments from the decision tree RAM, and compares the chained packet segment to the plurality of chained reference segments at a tree level node.
17. The system of claim 15 further comprising:
a UI connected to the packet RAM for selecting segments in a packet to be written.
18. The system of claim 11 further comprising:
a user interface (UI) connected to the decision tree RAM for writing reference segments and comparison operators into a tree level node, selecting the number of tree levels, selecting inter-tree levels branches between nodes on different tree levels, selecting classification pointers for key nodes, and selecting the number of classification pointers per key node.