Packet preclassification using search tree algorithms

• US 20080279205A1
• Filed: 05/11/2007
• Published: 11/13/2008
• Est. Priority Date: 05/11/2007
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Applied Micro Circuits Corporation (MACOM Technology Solutions Holdings, Inc.)
• Inventors: Sgouros, Alexander, Chakrabroty, Sourav, Bergen, Christopher Dean, Bush, Leonard
• Granted Patent: US 7,720,100 B2
• Time in Patent Office: Days
• US Class Current: 370/408
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

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.

Claims

1. An information packet preclassification method comprising:

receiving a packet of information;

differentiating the packet into segments;

using a decision tree with multiple levels, comparing segments in the packet to a node at a tree level, where each node includes a plurality of node reference segments and corresponding node comparison operators;

in response to comparing segments, accessing a classification attribute; and

,

assigning the classification attribute to the packet.

2. The method of claim 1 further comprising:

processing the packet in response to the classification attribute.

3. 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.

4. 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.

5. 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.

6. The method of claim 5 wherein branching to the node in the second tree level includes branching to a last decision node;

wherein comparing segments further includes branching to a key node in response to comparing the second segment in the packet to the last decision node; and

,

wherein accessing the classification attribute in response to the decision tree comparisons includes accessing classification pointers in the key node.

7. The method of claim 6 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 2 further comprising:

hashing 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.

9. The method of claim 1 further comprising:

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.

10. The method of claim 6 further comprising:

prior to receiving the packet, selecting classification pointers for a key node; and

,

selecting the number of classification pointers per key node.

11. The method of claim 1 further comprising:

prior to receiving the packet, selecting segments in the packet to be compared.

12. 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; and

,

a classification database having an interface to accept classification pointers from the plurality of PPEs, and an output to supply classification attributes for packets in response to receiving the classification pointers.

13. The system of claim 12 further comprising:

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.

14. The system of claim 12 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.

15. The system of claim 12 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.

16. The system of claim 12 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.

17. The system of claim 16 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.

18. The system of claim 17 wherein 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.

19. The system of claim 13 wherein the PPE controller hashes selected packet segments stored in the packet RAM in response to comparing segments in the packet to nodes in the decision tree;

and,

wherein the processor includes a plurality of processing engines, the processor managing the order of packets to the processing engines, in response hashed segment values associated with the packets.

20. The system of claim 12 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.

21. The system of claim 17 further comprising:

a UI connected to the packet RAM for selecting segments in a packet to be written.