Method and apparatus for eliminating unsuccessful tries in a search tree
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
51 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
-
-
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. - View Dependent Claims (23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 39)
-
-
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. - View Dependent Claims (37, 38, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51)
-
Specification