Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Patent
1998-05-06
2000-05-23
Donaghue, Larry D.
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
39550047, 370351, 370238, 34082503, G06F 1630
Patent
active
060675721
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. In evaluating potential paths or edges, the apparatus and method may consider extrinsic data which influences the cost or distance function for a path or edge. 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.
REFERENCES:
patent: 4967345 (1950-10-01), Clarke et al.
patent: 5253161 (1993-10-01), Nemirovskj et al.
patent: 5444848 (1995-08-01), Johnson, Jr. et al.
patent: 5561790 (1996-10-01), Fusaro
patent: 5583996 (1996-12-01), Isuchiya
patent: 5596719 (1997-01-01), Kamakrishnan et al.
patent: 5596722 (1997-01-01), Rahnema
patent: 5604868 (1997-02-01), Komine et al.
patent: 5634011 (1997-05-01), Auerbach et al.
patent: 5682479 (1997-10-01), Newhall et al.
patent: 5729692 (1998-03-01), Qiu et al.
Deasington; X.25 Explained: Protocol for Packet Swithcing Network; 2986, pp. 111-125.
Benos; Blocking States in Connecting Networks Made Square Switches Arranged in Stages; Apr. 1981, pp. 511-516.
Carter Stephen R.
Jensen Delos Clark
Donaghue Larry D.
Novell Inc.
LandOfFree
Extrinsically influenced near-optimal path apparatus and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Extrinsically influenced near-optimal path apparatus and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extrinsically influenced near-optimal path apparatus and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1844176