Search tree algorithms

• US 9,071,555 B1
• Filed: 10/17/2013
• Issued: 06/30/2015
• Est. Priority Date: 05/11/2007
• Status: Expired due to Fees

• Current Assignee: RPX Corporation
• Original Assignee: Net Navigation Systems LLC
• Inventors: Sgouros, Alexander, Bush, Leonard, Bergen, Christopher, Chakrobroty, Sourav
• Primary Examiner(s): Chery, Dady
• Application Number:
  US14/056,484
• Time in Patent Office: 621 Days
• Field of Search: 370/230, 370/235, 370/252, 370/363, 370/470, 370/473, 370/474, 709/245, 709/223, 709/238, 707/2, 707/3, 707/100
• US Class Current: 1/1
• 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 via an input interface port a packet of information;

differentiating the packet into segments using a packet parsing engine (PPE);

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, wherein each node includes

a plurality of node reference segments and corresponding node comparison operators, said 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;

in response to comparing the segments to the nodes, the PPE assigning a plurality of classification attributes to the packet;

packet;

forwarding the packet to a processor for processing in response to a classification attribute;

and

using a user interface (UI) to select segments in the packet to be written.

2. The method of claim 1 further comprising, prior to receiving the packet, using a user interface (UI):

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.

3. The method of claim 2 further comprising:

prior to receiving the packet, using the UI to select segments in the packet to be compared.

4. A system for preclassifying information packets, the system comprising:

an input interface with a plurality of ports to accept information packets;

a packet parsing engine (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;

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 assigning a classification to the packet;

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;

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

a user interface (UI) configured to permit selecting of segments in a packet to be written.

5. The system of claim 4 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.

6. The system of claim 4 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.

7. The system of claim 4 wherein the UI is connected to the decision tree RAM for configuring the decision tree.

8. The system of claim 7 wherein the UI permits 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.