Methods of altering dynamic decision trees

Details Methods of altering dynamic decision trees Methods of altering dynamic decision trees

1999-04-30

2001-11-20

Olms, Douglas (Department: 2661)

Multiplex communications

Network configuration determination

Using a particular learning algorithm or technique

C370S401000

Reexamination Certificate

active

06320848

ABSTRACT:

TECHNICAL FIELD
This invention relates to methods of altering 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 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.


REFERENCES:
patent: 4499596 (1985-02-01), Casey et al.
patent: 5509006 (1996-04-01), Wilford et al.
patent: 5574910 (1996-11-01), Bialkowski
patent: 5666481 (1997-09-01), Lewis
patent: 6018524 (2000-01-01), Turner et al.
patent: 6192051 (2001-02-01), Lipman et al.
patent: WO 94/15305 (1994-07-01), None

Affiliated with

Also associated with

Rating

Methods of altering 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 altering dynamic decision trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods of altering dynamic decision trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2611606