Methods of altering dynamic decision trees
First Claim
Patent Images
1. A method of altering a dynamic decision tree containing nodes from a first node configuration to a second node configuration, comprising the steps of:
- (a) identifying a location in the decision tree at which at least one new node is to be inserted;
(b) inserting at that point a temporary node which has first and second states, the first state keeping the existing configuration of the tree unchanged, and the temporary node initially being in said first state;
(c) inserting said new node to depend from said temporary node and being coupled into said tree only when said temporary node is in said second state;
(d) repeating steps (a), (b) and (c) for any additional new nodes to be inserted; and
(e) simultaneously altering every temporary node from its first to its second state.
2 Assignments
0 Petitions
Accused Products
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.
-
Citations
7 Claims
-
1. A method of altering a dynamic decision tree containing nodes from a first node configuration to a second node configuration, comprising the steps of:
-
(a) identifying a location in the decision tree at which at least one new node is to be inserted;
(b) inserting at that point a temporary node which has first and second states, the first state keeping the existing configuration of the tree unchanged, and the temporary node initially being in said first state;
(c) inserting said new node to depend from said temporary node and being coupled into said tree only when said temporary node is in said second state;
(d) repeating steps (a), (b) and (c) for any additional new nodes to be inserted; and
(e) simultaneously altering every temporary node from its first to its second state. - View Dependent Claims (2, 3, 4, 5, 6, 7)
(f) removing every temporary node.
-
-
3. The method of claim 1, including the step of:
(g) removing any node contained in said first configuration which is redundant in said second configuration.
-
4. The method of claim 3, wherein a count is maintained in respect of the number of paths along which each node in the tree can be reached, and a node is considered to be redundant if its respective count is zero.
-
5. The method of claim 1, wherein the state of every temporary node is dependent upon a common control value, and the state of every temporary node is simultaneously altered by changing said common control value.
-
6. The method of claim 1, wherein the dynamic decision tree is part of a switch for switching data packets in a data communications network.
-
7. The method of claim 1, wherein the dynamic decision tree is part of a probe for passive monitoring of operation of a data communications network.
Specification