Methods of managing dynamic decision trees
AssigneeHewlett-Packard Company
InventorsAled Justin Edwards, Costas Calamvokis
Life of this patent
Estimating the term…
Abstract
A data packet switch includes a decision tree for classifying data packets, which can be dynamically modified. To conserve memory resources nodes which are found during modification to have matching effects are combined. If only a subset of paths to a node are relevant to a modification, the node is split. Prior to implementation of the modifications, temporary nodes are inserted before modified nodes to preserve existing paths. These temporary nodes are controlled by a single memory value which can be changed to effect all the modifications to the decision tree simultaneously.
Claims19
A method of managing a dynamic decision tree containing a plurality of branches, each branch containing a plurality of nodes, after addition of a plurality of new nodes depending from a first existing node to a branch, comprising the steps of:
- (a) identifying a new node at the end of the branch;
- (b) seeking a matching existing node and identifying every node on the branch that points to said new node and redirecting it to said matching existing node.
Apparatus including a memory for holding a dynamic decision tree that is to be used in course of the operation of the apparatus and contains a plurality of nodes including branch nodes;
- the apparatus further including an arrangement for managing the decision tree, this arrangement comprising:
- means for adding one or more nodes to the decision tree in at least one chain each of at least one node;
- means for identifying an added node that is furthest down the tree along the chain containing it;
- and
- means for seeking, for the identified node, a matching existing node in the tree and upon locating one, identifying every branch node that points to said added node and redirecting it to said matching existing node.
A method of managing a dynamic decision tree that is stored in apparatus memory and contains a plurality of nodes including branch nodes, the method comprising the steps of:
- (a) adding one or more nodes to the decision tree in at least one chain each of at least one node;
- (b) identifying an added node that is furthest down the tree along the chain containing it;
- and
- (c) for the identified node, seeking a matching existing node and upon locating one, identifying every branch node that points to said added node and redirecting it to said matching existing node.
Dependencies are inferred from the claim text.