Methods of altering dynamic decision trees

• US 6,320,848 B1
• Filed: 04/30/1999
• Issued: 11/20/2001
• Est. Priority Date: 05/01/1998
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Edwards, Aled Justin, Calamvokis, Costas
• Primary Examiner(s): Olms, Douglas
• Assistant Examiner(s): VANDERPUYE, KENNETH N
• Application Number:
  US09/302,871
• Time in Patent Office: 935 Days
• Field of Search: 370/255, 370/256, 370/389, 370/395, 370/401, 370/392, 709/239, 709/242, 709/252
• US Class Current: 370/255
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/0817 by checking functioning
• CPC Class Codes: H04L 43/12 Network monitoring probes
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04Q 2213/13056 Routines, finite state machines
• CPC Class Codes: H04Q 2213/13109 Initializing, personal profile
• CPC Class Codes: H04Q 2213/13196 Connection circuit/link/trunk/junction, bridge, router, gateway
• CPC Class Codes: H04Q 3/66 Traffic distributors

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.

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.

2. The method of claim 1, including the step of:

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