Near-optimal path apparatus and method

• US 5,870,564 A
• Filed: 11/07/1996
• Issued: 02/09/1999
• Est. Priority Date: 03/01/1996
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Carter, Stephen R., Jensen, Delos Clark
• Primary Examiner(s): Donaghue, Larry D.
• Application Number:
  US08/744,961
• Time in Patent Office: 824 Days
• Field of Search: 395/200.71, 395/200.69, 395/200.72, 395/200.73, 395/311, 370/351, 370/400, 370/426, 370/360
• US Class Current: 709/241
• CPC Class Codes: H04Q 3/66 Traffic distributors

Abstract

A method and apparatus for dynamically providing a path through a network of nodes or granules may use a limited, advanced look at potential steps along a plurality of available paths. Given an initial position, at an initial node or granule within a network, and some destination node or granule in the network, all nodes or granules may be represented in a connected graph. An apparatus and method may evaluate current potential paths, or edges between nodes still considered to lie in potential paths, according to some cost or distance function associated therewith. Each next edge may lie ahead across the advancing "partial" wavefront, toward a new candidate node being considered for the path. With each advancement of the wavefront, one or more potential paths, previously considered, may be dropped from consideration. Thus, a "partial" wavefront, limited in size (number of nodes and connecting edges) continues to evaluate some number of the best paths "so far." The method deletes worst paths, backs out of cul-de-sacs, and penalizes turning around. The method and apparatus may be implemented to manage a computer network, a computer internetwork, parallel processors, parallel processes in a multi-processing operating system, a smart scissor for a drawing application, and other systems of nodes.

Claims

1. An apparatus for providing a near-optimal path through a plurality of nodes interconnected by edges, each edge associated with a unique connection between two nodes, each node comprising a component, and the nodes configured in granules, the apparatus comprising:

granules interconnected in a topology, each granule comprising one or more nodes operably interconnected by an edge, each edge having associated therewith a connection state selectable from an unloaded state and at least one loaded state, and having associated therewith an edge state comprising data corresponding to the connection state;

a memory device comprising;

a vacuum space containing vacuum data corresponding to the topology of the granules, the topology corresponding to the unloaded state corresponding to each granule and each edge connecting each granule to a proximate granule;

a load space containing data corresponding to a topology of the granules in a loaded state comprising the granule states corresponding to a loaded state of the plurality of loaded states for each granule; and

a processor operably connected to the memory device and programmed to execute an executable application comprising;

a granule manager effective to provide definitions of the granules,

load manager effective to create and update load data stored in the load space,

a granule event manager effective to provide data reflecting updated loads associated with edges between granules, and

a vacuum space manager effective to receive data corresponding to events associated with changes in loading of the granules, and to update the load space with the load data corresponding to the events.

2. The apparatus of claim 1 wherein the loaded state is an incremental alteration of the unloaded state.

3. The apparatus of claim 1 wherein the number of loaded states corresponds to a finite number.

4. The apparatus of claim 1 wherein a metric is derived from the topology to define a metric space representing the connections and metrics associated with the granules and physical connections between the granules.

5. The apparatus of claim 1 wherein the granules are interconnected so as to provide for each granule an edge connecting the granule to a proximate granule.

6. The apparatus of claim 5 in which the edge connecting the granule to the proximate granule represents a binary relation.

7. The apparatus of claim 1 wherein a first node is connected to a proximal node by an edge.

8. The apparatus of claim 7 wherein a granule comprising the first node is connected to a proximal granule comprising the proximal node by the edge between the first node and the second node.

9. The apparatus of claim 1 wherein the load space is a dynamically changing load space.

10. A method for providing an improved path from a source node to a destination node through a network comprising a plurality of nodes interconnected between the source node and the destination node, the method comprising:

defining a connected graph corresponding to the network, the connected graph comprising mathematical nodes connected by edges;

defining a metric space associated with the connected graph, the metric space having associated therewith a metric effective to define a cost associated with each edge;

providing a measure associated with each edge; and

determining a first cost associated with advancing from the source to each of a plurality of edges connecting the source to a corresponding plurality of first intermediate nodes;

determining a second cost associated with advancing from a first intermediate node to each of a plurality of second intermediate nodes; and

selecting a trial set of nodes from the plurality of first intermediate nodes, based on an evaluation corresponding to a distribution function and related to the second cost;

deleting a deletable first intermediate node not included in the trial set, and corresponding to a less-preferable cost function associated with the deletable first intermediate node.

11. The method of claim 10 further comprising a backing step comprising selecting an exit node connected between the source and a terminal node, the terminal node being selected from the plurality of second intermediate nodes based on a non-preferred cost selected from the second costs.

12. The method of claim 11 further comprising an abandoning step comprising deleting from consideration all nodes between the terminal node and the exit node.

13. The method of claim 10 further comprising repeating the determining step and selection steps until a preferred path is determined between the source and the destination.

14. The method of claim 10 further comprising:

providing an inertial step effective to provide an undesirable cost associated with any edge between a first intermediate node and a second intermediate node where the second intermediate node has been designated previously as a previous first intermediate node with respect to the first intermediate node as a previous second intermediate node.

15. A method for finding a path between a source node and a destination node connected in a network of nodes, the method comprising:

defining a plurality of granules, each granule comprising at least one node;

interconnecting the granules with a plurality of edges;

providing a capacity associated with each edge;

implementing a steering function for guiding advancement along a path segment comprised of edges, the path segment comprising a candidate path to be evaluated for consideration as a permanent segment of a satisfactory path between the source node and the destination node;

deleting from consideration all unsatisfactory edges by a process of superposition and reduction.

16. The method of claim 15 wherein superposition and reduction include:

providing a first partial expanding wavefront for testing a capacity of first edges passing through the first partial expanding wavefront at a first position to provide first results;

defining a second partial expanding wavefront for testing a capacity of second edges passing through the second partial expanding wavefront at a second position to provide second results;

deleting an unsatisfactory first edge selected from the first edges and corresponding to unsatisfactory second results, the unsatisfactory second results corresponding to second edges associated with the unsatisfactory first edges;

substituting the second partial expanding wavefront as a new first partial expanding wavefront; and

substituting a third partial expanding wavefront as a new second partial expanding wavefront.

17. The method of claim 15 further comprising implementing an inertia function effective to provide stability to the direction of the first partial expanding wavefront.

18. The method of claim 15 further comprising deleting a plurality of unsatisfactory first edges.

19. The method of claim 16 wherein reduction further comprises reducing the second partial expanding wavefront to a level of support corresponding to a maximum level of support.

20. The method of claim 19 further comprising establishing a maximum number of nodes associated with the maximum level of support.

21. The method of claim 20 wherein reducing further comprises deleting selected nodes that may serve in a new second partial expanding wavefront to a number no greater than the maximum number of nodes.

22. The method of claim 21 wherein superposition further comprises establishing a plurality of position states available to the second partial expanding wavefront, each position state having a probability corresponding thereto.

23. The method of claim 22 wherein reduction further comprises selecting a set of position states for inclusion in the new first partial expanding wavefront, based on the probabilities.

24. The method of claim 23 further comprising selecting the set of position states using the random selector operating under an envelope of a distribution function corresponding the probabilities.

25. The method of claim 23 further comprising selecting edges to complete the new first partial expanding wavefront by evaluating a capacity of edges associated with the plurality of selected position states.