Adaptive routing of messages in parallel and distributed processor systems

• US 5,170,393 A
• Filed: 12/03/1990
• Issued: 12/08/1992
• Est. Priority Date: 05/18/1989
• Status: Expired due to Term

• Current Assignee: California Institute of Technology
• Original Assignee: California Institute of Technology
• Inventors: Peterson, John C., Chow, Edward T.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): HOM, SHICK C
• Application Number:
  US07/620,735
• Time in Patent Office: 736 Days
• Field of Search: 370/60, 370/54, 370/94.1, 370/94.3
• US Class Current: 370/255
• CPC Class Codes: H04L 45/06 Deflection routing, e.g. hot-potato routing

Abstract

In a multi-node network containing a plurality of parallel and distributed nodes, this invention reduces the time to establish a through-path or make a decision that no through-path can be established at the present time. In one aspect, each node that can be an originating node contains connectivity analysis logic which performs a minimum cycle breakdown of the possible paths between the originating node and the destination node to establish a list of nodes to be tried before attempting to establish a through-path to a destination node whereby exhaustive testing of all paths is not undertaken. In another, each node that can be an intermediate node contains pruning logic for pruning a non-variable tested path and all associated paths depending therefrom from further testing whereby redundant testing of paths which will result in failure is eliminated. In yet another, each node that can be an intermediate node contains backtracking logic for not waiting at the node for a link to a busy next-adjacent further node to free up and for backtracking to a next-adjacent previous node when no next-adjacent further node is immediately non-busy. Additionally, each node contains an intelligent channel having a separate path setup mode in which the function of path establishing is performed and data transmission mode in which the function of data transfer is performed whereby transmitted data passes through the nodes without processing time being added.

Claims

1. In a multi-node network containing a plurality of parallel and distributed switching nodes, the improvement for reducing the time to establish a through-path from the originating node to the destination node or make a decision that no through-path can be established at this time when routing messages from an originating node to a destination node;

the improvement comprising;

connectivity analysis logic in each node that can be an originating node;

said connectivity analysis logic having means for performing a minimum cycle breakdown of the possible paths between the originating node and the destination node to establish a list of nodes disposed along possible paths to be tried before attempting to establish a through-path to a destination node along said possible paths whereby exhaustive testing of all paths is not undertaken before success or failure is determined.

2. The improvement to a multi-node network of claim 1 wherein said minimum cycle breakdown means comprises logic for performing the steps of:

a) assigning the destination node as a current node;

b) using the minimum number of non-overlapping minimum cycles necessary to "color" (i.e. include) all the penultimate nodes on shortest, in number of nodes, paths between the source and destination nodes of the current nodes;

c) assigning non-colored nodes included by the selected minimum cycles with the shortest distance to the source node as penultimate nodes;

d) assigning colored nodes as current nodes;

e) if the penultimate nodes on the shortest paths between the source and destination nodes is the source node, then proceeding to step (f);

otherwise, returning to step (b);

f) designating all the colored nodes as intermediate nodes that may need to be visited in any subsequent attempt to either establish a successful through-path between the source and destination nodes.

3. The improvement to a multi-node network of claim 1 additionally comprising:

each node that can be an intermediate node along a through-path containing pruning logic for pruning a non-available tested path and all associated paths depending on the non-available path from further testing during a process of finding an available path between the originating node and the destination node whereby redundant testing of paths which will result in failure is eliminated.

4. The improvement to a multi-node network of claim 3 additionally comprising:

each node that can be an intermediate node along a through-path containing backtracking logic for not waiting at the node for a link to a busy next-adjacent further node to free up and for backtracking to a next-adjacent previous node when no next-adjacent further node is immediately non-busy.

5. The improvement to a multi-node network of claim 1 additionally comprising:

each node that can be an intermediate node along a through-path containing an intelligent channel having two separate operating modes, wherein one of said two modes is a path setup mode in which the function of path establishing is performed and the other of said two modes is a data transmission mode in which the function of data transfer is performed whereby when the intelligent channel is in the data transmission mode data passes directly through the associated node and has no processing time added thereto by the associated node.

6. The improvement to a multi-node network of claim 5 wherein each said intelligent channel includes switching logic for performing the steps of:

a) when the associated node is an originating node, originating and sending a header with the destination node'"'"'s address embedded in the header to a selected next neighboring node'"'"'s intelligent channel and reserving the path through which the header travels; and

b) when the associated node is an intermediate node;

b1) evaluating a received header and the header to a selected next neighboring node intelligent channel which is not busy and then switching a local crossbar switch of the intermediate node'"'"'s to connect an inbound channel thereof to an outbound channel thereof whereby the intermediate node is placed in said data transmission mode; and

b2) repeating step (b1) until the header reaches the destination node; and

c) when the associated node is a destination node, sending an acknowledgment back to the source node'"'"'s intelligent channel through the intermediate nodes to establish a network connection pipeline communication path in the data transmission mode so that messages can start to be transmitted by the originating node.

7. The improvement to a multi-node network of claim 6 wherein each said switching logic at an intermediate node includes logic for performing the step of:

if all the selected next neighboring nodes'"'"' intelligent channels are busy, then sending a backtrack status to the previous node'"'"'s said intelligent channel

8. The improvement to a multi-node network of claim 6 wherein:

each of said intelligent channels includes a status signal link connected to said status signal link of next adjacent nodes to which it is connected.

9. The improvement to a multi-node network of claim 8 wherein:

each of said status signal links is a link bi-directionally transmitting a 2-bit status word which is interpreted differently in said path setup mode and in said data transmission mode.

10. The improvement to a multi-node network of claim 9 wherein:

a) in said path setup mode, the bits of said status word are interpreted as;

00--ready to receive header

01--ready to receive data

10--header backtracked to the previous node

11--header error, retransmit header; and

b) in said data transmission mode, the bits of said status word are interpreted as;

00--break pipeline to source

01--ready to receive data

10--wait for next data packet

11--data error, retransmit data packet.

11. Switching apparatus for use in a network containing a plurality of parallel and distributed nodes for routing messages from an originating node to a destination node while reducing the time to establish a through-path from the originating node to the destination node or make a decision that no through-path can be established at this time comprising:

a) a separate node processor disposed in association with each node, each said node processor containing computing means and associated logic for execution thereby for making switching decisions from header information associated with messages being routed thereby; and

b) an intelligent channel connected to said node processor to be controlled thereby, each intelligent channel having two separate operating modes, wherein one of said two modes is a path setup mode in which a function of establishing a path from an originating node to a destination node from said header information preceding data associated with a said message is performed and the other of said two modes is a data transmission mode in which a function of transferring data associated with a said message is performed, each intelligent channel having a plurality of input lines for connecting to said intelligent channels of next adjacent nodes to receive inputs therefrom and a plurality of output lines for connecting to said intelligent channels of next adjacent node to transmit outputs thereto, said input lines of a node being connected directly to said output lines when said intelligent channel of a node is in said data transmission mode whereby when a said intelligent channel is in said data transmission mode said data passes directly through the associated node and has no processing time added thereto by the associated node;

each said node processor of each node that can be an originating node contains connectivity analysis logic which performs a minimum cycle breakdown of the possible paths between the originating node and the destination node to establish a list of nodes disposed along possible paths to be tried before attempting to establish a through-path to a destination node along said possible paths whereby exhaustive testing of all paths is not undertaken before success or failure is determined.

12. The switching apparatus of claim 11 wherein said connectivity analysis logic includes logic for performing the steps of:

a) assigning the destination node as a current node;

b) using the minimum number of non-overlapping minimum cycles necessary to "color" (i.e. include) all the penultimate nodes on shortest, in number of nodes, paths between the source and destination nodes of the current nodes;

c) assigning non-colored nodes included by the selected minimum cycles with the shortest distance to the source node a penultimate nodes;

d) assigning colored nodes as current nodes;

e) if the penultimate nodes on the shortest paths between the source and destination nodes is the source node, then proceeding to step (f);

otherwise, returning to step (b);

f) designating all the colored nodes as intermediate nodes that may need to be visited in any subsequent attempt to either establish a successful through-path between the source and destination nodes.

13. In a multi-node network containing a plurality of parallel and distributed switching nodes, the method of operation for reducing the time to establish a through-path from the originating node to the destination node or make a decision that no through-path can be established at this time when routing messages from an originating node to a destination node comprising the steps of:

a) at each originating node and before attempting to establish a through-path to a destination node along possible paths, performing a connectivity analysis accomplishing a minimum cycle breakdown of the possible paths between the originating node and the destination node to establish a list of nodes disposed along possible paths to be tried whereby exhaustive testing of all paths is not undertaken before success or failure is determined; and

b) at each node that can be an intermediate node along a through-path and while attempting to establish a through-path to a destination node along possible paths;

b1) visiting the nodes on the list established in step (a); and

b2) performing backtrack logic comprising not waiting at the node for a link to a busy next-adjacent further node to free up and backtracking to a next-adjacent previous node when no next-adjacent further node is immediately non-busy.

14. The method of claim 13 and at each node that is an intermediate node along a through-path;

a) first operating in a path setup mode in which the function of path establishing is performed; and

b) after and only after a through-path has been established between an originating node and a destination node, then operating in a data transmission mode in which the function of data transfer is performed whereby when the nodes along a successful through-path are in the data transmission mode, data passes directly through the nodes and has no processing time added thereto by the nodes.

15. The method of claim 14 wherein the method includes the steps of:

a) at an originating node, originating and sending a header with the destination node'"'"'s address embedded in the header to a selected next neighboring node and reserving the path through which the header travels; and

b) at an intermediate node;

b1) evaluating a received header and re-routing the header to a selected next neighboring node which is not busy and then switching a local crossbar switch of the intermediate node to connect an inbound channel thereof to an outbound channel thereof whereby the intermediate node is placed in the data transmission mode; and

b2) repeating step (b2) until the header reaches the destination node; and

c) at a destination node, sending an acknowledgment back to the source node through the intermediate nodes to establish a network connection pipeline communication path in the data transmission mode so that messages can start to be transmitted by the originating node.

16. The method of claim 13 wherein said step of performing a connectivity analysis includes the steps of:

a) assigning the destination node as a current node;

using the minimum number of non-overlapping minimum cycles necessary to "color" (i.e. include) all the penultimate nodes on shortest, in number of nodes, paths between the source and destination nodes of the current nodes;

c) assigning non-colored nodes included by the selected minimum cycles with the shortest distance to the source node as penultimate nodes;

d) assigning colored nodes as current nodes;

e) if the penultimate nodes on the shortest paths between the source and destination nodes is the source node, then proceeding to step (f);

otherwise, returning to step (b);

f) designating all the colored nodes as intermediate nodes that may need to be visited in any subsequent attempt to either establish a successful through-path between the source and destination nodes.

17. The method of claim 13 and additionally comprising:

at each intermediate node while attempting to establish a through-path to a destination node along possible paths, pruning a non-available tested path and all associated paths depending on the non-available path from further testing whereby redundant testing of paths which will result in failure is eliminated.

18. The method of claim 13 and additionally comprising:

at each intermediate node while attempting to establish a through-path to a destination node along possible paths, if all selected next neighboring nodes are busy, then sending a backtrack status to the previous node.

19. The method of claim 18 wherein said step of sending a backtrack status to the previous node comprises the steps of:

a) connecting a status signal link between connected next adjacent nodes; and

,

b) bi-directionally transmitting a 2-bit status word which is interpreted differently in the path setup mode and in the data transmission mode over the status signal link.

20. The method of claim 19 including the steps of:

a) in the path setup mode, interpreting the bits of the status word as,

00--ready to receive header

01--ready to receive data

10--header backtracked to the previous node

11--header error, retransmit header; and

,

b) in the data transmission mode, interpreting the bits of the status word as,

00--break pipeline to source

01--ready to receive data

10--wait for next data packet

11--data error, retransmit data packet.