Method and apparatus for eliminating unsuccessful tries in a search tree

• US 5,008,882 A
• Filed: 08/17/1987
• Issued: 04/16/1991
• Est. Priority Date: 08/17/1987
• Status: Expired due to Fees

• Current Assignee: California Institute of Technology
• Original Assignee: California Institute of Technology
• Inventors: Chow, Edward, Madan, Herb S., Peterson, John C.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Chin, Wellington
• Application Number:
  US07/086,722
• Time in Patent Office: 1,338 Days
• Field of Search: 370/60, 370/94, 370/85, 370/86, 370/88, 370/89, 370/54, 370/95, 370/60.1, 370/94.1, 370/85.1, 370/85.12, 370/85.13, 370/85.7, 370/85.15, 370/95.1, 370/94.3
• US Class Current: 370/406
• CPC Class Codes: G06F 15/17368 non hierarchical topologies
• CPC Class Codes: H04L 45/06 Deflection routing, e.g. hot-potato routing
• CPC Class Codes: H04L 45/36 Backward learning

Abstract

A circuit switching system in an M-ary, n-cube connected network completes a best-first path from an originating node to a destination node by latching valid legs of the path as the path is being sought out. Each network node is provided with a routing hyperswitch sub-network, ("HSN") connected between that node and bidirectional high capacity communication channels of the n-cube network. The sub-networks are all controlled by routing algorithms which respond to message identification headings ("headers") on messages to be routed along one or more routing legs. The header includes information embedded therein which is interpreted by each sub-network to route and historically update the header. A logic circuit, available at every node, implements the algorithm and automatically forwards or back-tracks the header in the network legs of various paths until a completed path is latched.

Claims

1. A method of searching for a best-first path from an originating computer ("node") through any number of intermediate node(s) to a destination node, when said nodes are connected in a cube-configured network having a plurality of path sections interconnecting the originating, intermediate and destination nodes, comprising the steps of:

trying individual path sections of the network in a preferred order of paths which lead from the originating to the destination node;

eliminating from the order of paths to be tried, those path sections terminating at a destination node and found busy; and

latching the first non-busy terminal path section of the preferred order which completes a path from the originating to said destination node.

2. A method in accordance with claim 1 wherein the eliminating step further comprises the step of:

considering as eliminated from further tries all path sections located between the originating node and the node where the busy path section is found.

3. A method in accordance with claim 1 and further comprising the additional step of:

reserving as a partially completed path, each successfully tried path section in any given one of said preferred order, until said first non-busy terminal path is latched to fully complete said path.

4. A method in accordance with claim 1 and further comprising:

storing information at the busy nodes reached during any given try to eliminate any retry of such node(s) during any one complete search cycle through said network.

5. A method in accordance with claim 1 wherein said trying step comprises:

originating a message header at said originating node; and

forwarding said header over the paths in said preferred order.

6. A method in accordance with claim 5 and further comprising:

embedding, in said header, information reflecting path sections which have been eliminated from any further tries.

7. A method in accordance with claim 6 and further comprising:

embedding, in said header, routing information which controls the path sections over which the header is routed.

8. A method in accordance with claim 1 and further comprising:

establishing a system-wide routing alogrithm at every node; and

performing said steps of trying, eliminating, and latching in accordance with said routing algorithm.

9. A method in accordance with claim 8 and further comprising:

dynamically changing the order of paths to be tried during any one search cycle based upon the busy and non-busy conditions of path sections tried during said search cycle.

10. A method in accordance with claim 1 wherein the destination node in said network is connected to a plurality of penultimate nodes, and wherein said trying step further comprises:

searching for a complete path using a search criteria where at most one attempt will be made to reach all given penultimate nodes.

11. A method in accordance with claim 1 wherein the destination node in said network is connected to a plurality of penultimate nodes and wherein said trying step further comprises:

searching for a complete path using a search criteria where every possible attempt will be made to reach all of the penultimate nodes.

12. A method in accordance with claim 10 wherein an intermediate node comprises a plurality of input lines and at least an equal number of output lines and comprising the further steps of:

searching for a non-busy path at every one of the output lines from said intermediate node.

13. A method in accordance with claim 12 and further comprising:

sending over the input line that requested a search of the output lines, a signal indicative of a busy condition at all of said output lines at said intermediate node.

14. A method in accordance with claim 11 wherein an intermediate node comprises a plurality of input lines and at least an equal number of output lines and comprising the further steps of:

searching for a non-busy path at every one of the output lines from said intermediate node.

15. A method in accordance with claim 14 and further comprising:

sending over the input line that requested a search of the output lines, a signal indicative of a busy condition at all of said output lines at said intermediate node.

16. A method in accordance with claim 8 and further comprising:

implementing the routing algorithm in logic circuitry; and

providing identical logic circuitry at every node.

17. A method in accordance with claim 16 wherein said trying step further comprises:

originating a message header at said originating node; and

forwarding said header over the paths in said preferred order.

18. A method in accordance with claim 17 and further comprising;

embedding, in said header, information reflecting path sections which have been eliminated from any further tries.

19. A method in accordance with claim 18 and further comprising:

embedding, in said header, routing information which controls the path sections over which the header is routed.

20. A method in accordance with claim 17 and further comprising:

establishing a system-wide routing algorithm at every node; and

performing said steps of trying, eliminating, and latching in accordance with said routing algorithm.

21. A circuit switching system for completing a plurality of data-handling sections of a communication link between connected in a cube-configured network, with any node being capable of originating a message header having embedded therein an identifier of a destination node so that data may be sent from said originating to said destination node after a connected communication link has been completed therebetween, said system comprising:

means at every node receiving said header for completing, a best-first section of said communication link, if available, between an originating, intermediate and destination nodes, or if said best-first output sections at any node(s) receiving said header are busy, delivering a congestion signal to the last successful forwardly node; and

means at every node including the last successful forwarding node responsive to said congestion signal for automatically rerouting said header along other sections of the communication link in said cube-configured network until a completed high speed data communication link is established between the originating and destination nodes.

22. A circuit switching system having a best-first message routing algorithm for a plurality of cube-connected nodes, said system comprising:

means at any node for originating a message having embedded therein a destination node identifier and a channel history flag reflecting the message'"'"'s progress through the network as it moves toward said destination node;

means at every node for executing said best-first routing algorithm in accordance with the channel history flag of a message arriving at any given node to seek the best-first route for said message through said network; and

means at each node transversed by said message for latching a completed circuit through said cube-connected network in accordance with an executed channel history portion of said message routing algorithm.

23. A circuit switching system in accordance with claim 22 and further comprising:

means at every node receiving a message to be routed for checking the availability or busy status of outgoing channels from the receiving node; and

means at said receiving node responsive to said checking means for altering said channel history flag of said message in order to reflect the status as checked by said status checking means

24. A circuit switching system in accordance with claim 23 and further comprising:

means at said receiving node for determining from said channel history flag of said message, the routing for said message along one of a plurality of outgoing channels from said node; and

further wherein

said status checking means is responsive to said determining means for checking the status of said one outgoing channel.

25. A circuit switching system in accordance with claim 23 wherein said receiving node is positionally located between said originating and said destination node, and further wherein:

said routing algorithm presumes that all network connections between said intermediate node and said destination node are blocked if all outgoing channels from said intermediate node are blocked.

26. A circuit switching system in accordance with claim 25 and further comprising:

means assigning a unique numerical node identifier to every node in said cube-connected network; and

said best-first routing algorithm routes each given message through the nodes, if available, which results in the lowest accumulated total of the numerical identifiers for said nodes.

27. A circuit switching system in accordance with claim 26 and wherein in said system is further characterized by:

said best-first routing algorithm routes each given message through the nodes having said lowest accumulated total of said numerical identifiers and if said nodes are not available through the next lowest accumulated total.

28. A circuit switching system in accordance with claim 22 and further characterized as:

each message-receiving node having means available thereat for ascertaining for said message;

a current node identifier ("ID"), the number of hops ("H") in the cube-connected network between the current node and the destination node ("D"), and the originating, or source, node identifier; and

where the number of hops (H) are the number of possibilities for linking together circuit sections for a desired communication link, and a hop is a movement from one node to another.

29. A circuit switching system in accordance with claim 28 and further comprising:

a routing logic at every node in said cube-connected network for routing said messages in accordance with said routing algorithm.

30. A circuit switching system in accordance with claim 29 wherein said node identifiers are accumulated to form a sum for each of several available paths between the originating and the destination nodes, and wherein said system further comprises:

means at every intermediate node, i, for locating the lowest available channel (based upon said node identifier values) equal to the first available channel, where the term i designates a node that is i hops away from the destination node.

31. A circuit switching system in accordance with claim 30 wherein a completed path requires hops from node to node and wherein said system is characterized by further comprising:

means at node, i, which is a node i hops away from a destination node, for performing the following steps;

(a) if first available channel is not busy then latch said first available channel;

(b) transmit header to node i-1; and

(c) change hop to hop+1.

32. A circuit switching system in accordance with claim 30 and further comprising:

means at node i for performing the additional steps of;

(a) if first available channel is busy then at node (i) where (i) is less than or equal to (n-1);

(b) backtrack header to node i+1, where backtrack means to start the steps from the node that forwarded the header to node i;

(c) set channel history flag (b_n-1, . . . b_i . . . b₀)=(O_n-1 . . . O_i+1 . . . l_i . . . l₀);

(d) set hop to equal hop-1; and

(e) try a number of alternate channels at node (i+1)=(fan out at node (i+1)-number of bits equaling one in channel history flag equal to n-hop-i-1).

33. A circuit switching system in accordance with claim 32 and further comprising:

means at node i+1 for determining if the number of possible channels at node i+1 is greater than zero, then i is equal to i+1; and

then perform the locating step identified in claim 30;

otherwise perform the steps identified in claim 32.

39. A searching system method in accordance with claim 26 and further comprising:

means for storing information at the busy nodes reached during any given status check, which information eliminates any retry of such node(s) during any one complete search cycle.

34. A circuit switching system for a plurality of cube-connected computers nodes, said system comprising:

a search tree for a cube-connected network of a 2n hypercube having nodes located at branching factors formed by communication lines, wherein the number of branches is variable, with a branching, or fan-out, factor of (N) in the first hop, (N-1) in the second hop, (N-2) in the penultimate hop, and 1 in the last hop;

a search tree algorithm means at each node for locating a completed path through said search tree from an originating to a destination node; and

means at each node responsive to execution of said search tree algorithm for latching a completed path through said search tree.

35. A circuit switching system for a cube-connected network of a plurality of concurrently-operable computers nodes, said switching system comprising:

means at an originating node for formulating a message format including a message destination portion and a circuit tranversing history portion in the message format;

means at said originating node for applying said message to said cube-connected network in accordance with a predetermined routing algorithm;

means at every node in said cube-connected network for executing said routing algorithm when said message arrives at any individual node; and

means at each node involved in the execution of said routing algorithm for storing that node'"'"'s participation of the execution of the routing algorithm in accordance with the message'"'"'s history portion.

36. A searching system for locating a best-first path from an originating computer ("node") through any number of intermediate node(s) to a destination node, when said nodes are connected in a cube-configured network having a plurality of path sections interconnecting an originating, intermediate and destination nodes, comprising:

means for checking, in a preferred order, the status of individual path sections of the network which lead from the originating to the destination node;

means for eliminating from the order of paths to be checked, those path sections which terminate at a destination node and which are found busy; and

means for latching the first non-busy terminal path section of the preferred order which completes a path from the originating to said destination node.

37. A search system in accordance with claim 36 wherein the eliminating means further comprising:

means for considering as busy all path sections located between the originating node and the node where a busy path section is found.

38. A searching system in accordance with claim 36 and further comprising:

means for reserving as a partially completed path, each successfully tried non-busy path section in any given one of said preferred order, until said latching means latches the first non-busy terminal path to fully complete said path.

40. A searching system in accordance with claim 36 wherein said status checking means further comprises:

means at said originating node for originating a message header; and

means for forwarding said header over the paths in said preferred order.

41. A searching system in accordance with claim 40 and further comprising:

means for embedding, in said header, information which diverts the header away from path sections which have a busy status.

42. A searching system in accordance with claim 40 and further comprising:

means for embedding, in said header, routing information which controls the path sections over which the header is routed.

43. A searching system in accordance with claim 36 and further comprising:

means for establishing a system-wide routing algorithm at every node; and

further wherein

said eliminating and latching means are controlled by said routing algorithm.

44. A searching system in accordance with claim 43 wherein said algorithm establishing means further comprises:

means for dynamically changing the order of paths to be checked during any one search cycle based upon the busy and non-busy status of path sections actually checked during one search cycle.

45. A searching system in accordance with claim 36 wherein the destination node in said network is connected to a plurality of penultimate nodes, and wherein said status checking means further comprises:

means responsive to a search criteria where one status check only is made at every given penultimate node.

46. A searching system in accordance with claim 36 wherein the destination node in said network is connected to a plurality of penultimate nodes and wherein said status checking means further comprises:

means responsive to a search criteria where every possible path configuration leading to all of the penultimate nodes is attempted.

47. A searching system in accordance with claim 45 wherein an intermediate node comprises a plurality of input lines and at least an equal number of output lines and comprising:

means for searching for a non-busy path at every one of the output lines from said intermediate node.

48. A searching system in accordance with claim 47 and further comprising:

means for sending back to the last forwarding node a signal indicative of a busy condition at all of said output lines at said intermediate node.

49. A searching system in accordance with claim 46 wherein an intermediate node comprises a plurality of input lines and at least an equal number of output lines and comprising:

means for searching for a non-busy path at every one of the output lines from said intermediate node.

50. A searching system in accordance with claim 49 and further comprising:

means for sending back to the last forwarding node a signal indicative of a busy condition at all of said output lines at said intermediate node.

51. A searching system in accordance with claim 43 and further comprising at every node:

for logic circuitry implementing the routing algorithm.