Methods of managing dynamic decision trees

Details Methods of managing dynamic decision trees Methods of managing dynamic decision trees

1999-04-30

2003-04-15

Chin, Wellington (Department: 2664)

Multiplex communications

Network configuration determination

Using a particular learning algorithm or technique

C370S351000

Reexamination Certificate

active

06549521

ABSTRACT:

TECHNICAL FIELD
This invention relates to methods of managing dynamic decision trees, for example for use in switches (e.g. hubs and routers) used for directing data packets in packet-based data communication networks, or in monitoring probes for collecting data about operation of such networks.
BACKGROUND ART
Large, high-capacity data communication networks, such as the Internet, are typically based on packet-switched techniques. In such techniques data to be communicated are divided into blocks each of which is combined with a header to form a data packet. The header includes, for example, information identifying the particular communications transaction to which the packet relates, and routing information identifying the sender and intended recipient of the data. Each packet is transmitted through the network between packet switching devices, such as hubs and routers, which examine the packet's header and use the routing information, in conjunction with data about the current operating status of the network, to choose a transmission path along which to route the packet towards its final destination.
As the demand for new and better quality data transmission increases, so does the need for faster yet more flexible packet switching devices. One technique used within packet switches for examining packet headers and making routing decisions relies upon the use of data structures often referred to as decision trees (though more formally described as directed acyclic graphs). Current implementations of decision trees suffer from various disadvantages. For example, typically a complete tree is developed in a single operation from a set of rules defining how packets are to be routed; thus even a single, trivial change to the rules involves generation of a complete new tree. If this tree is to replace an existing tree in a packet switch, the switch must be temporarily disabled (or at the very least incoming packets must be buffered) while the tree substitution takes place, in order to avoid the substitution affecting a packet for which routing decisions using the tree are already in progress. This both reduces the throughput of the packet switch, and increases its complexity and cost. Alternatively, two copies of the entire decision tree may be maintained, an active one for routing packets, and an inactive one which may safely be modified; when the modifications are complete, the active tree is made inactive and vice versa. Although such “double-buffering” avoids reducing the throughput of the switch, it involves expensive duplication of high-speed memory typically used to store decision trees.
It would be highly desirable to have a decision tree system which permitted incremental changes to be made to the decision tree in response to changes in the associated routing rules. It is also desirable that such changes be made without interrupting operation of the packet switch more than momentarily, and without any need to buffer incoming packets. It is an object of this invention to provide a method which facilitates the use of decision trees.
DISCLOSURE OF INVENTION
According to one aspect of this invention there is provided a method of managing a dynamic decision tree containing a plurality of nodes, after addition of at least one node depending from a first existing node, comprising the steps of:
(a) identifying an added node at which node addition terminated; and
(b) seeking a matching existing node and upon locating one, identifying every added branch node that points to said added node and redirecting it to said matching existing node.
In one embodiment a node which can be reached along a plurality of paths in the decision tree is duplicated to enable functionality to be added in respect of a subset only of said paths. In this case counts may be maintained in respect of the number of paths along which each node in the tree can be reached, and in respect of the number of paths in the subset for which functionality is to be added, and a node is duplicated when said counts are unequal.


REFERENCES:
patent: 4499596 (1985-02-01), Casey et al.
patent: 4853851 (1989-08-01), Horsch
patent: 4912656 (1990-03-01), Cain et al.
patent: 5323452 (1994-06-01), Dickman et al.
patent: 5509006 (1996-04-01), Wilford et al.
patent: 5574910 (1996-11-01), Bialkowski
patent: 5666481 (1997-09-01), Lewis
patent: 5787163 (1998-07-01), Taylor et al.
patent: 6018524 (2000-01-01), Turner et al.
patent: 6192051 (2001-02-01), Lipman et al.
patent: 0 684 716 (1995-11-01), None
patent: WO 94/15305 (1994-07-01), None
Rudiger Reischuk et al., “Reliable Computation with Noisy Circuits and Decision Trees . . . ”, Jul. 1991, Foundaton of Computer Science Proceedings, 32nd Annual Symposium, pp. 602-611.*
Technique for Performing Generalized Prefix Matches IBM Technical Disclosure Bulletin, vol. 40, No. 3, Mar. 1997, pp. 189-200, XP000694555 *p. 189, paragraph 2* *p. 190, paragraph 7 -p. 197 paragraph 1*.

Affiliated with

Also associated with

Rating

Methods of managing dynamic decision trees does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Methods of managing dynamic decision trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods of managing dynamic decision trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3075650