Dynamic routing system for a multinode communications network

• US 5,218,676 A
• Filed: 01/08/1990
• Issued: 06/08/1993
• Est. Priority Date: 01/08/1990
• Status: Expired due to Fees

• Current Assignee: University of Rochester The A Not-For-Profit Corporation
• Original Assignee: University of Rochester
• Inventors: Merriam, Charles W., Ben-Ayed, Mondher
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Chavis, John Q.
• Application Number:
  US07/561,538
• Time in Patent Office: 1,247 Days
• Field of Search: 364/200, 364/900
• US Class Current: 709/240
• CPC Class Codes: G06F 13/37 using a physical-position-dependent priority, e.g. daisy chain, round robin or token passing

Abstract

A communication network having a multiplicity of nodes provides efficient exchange of messages between the nodes. The messages may be originated and received by the computers of a parallel computer system, the processors and associated memories of which are connected to each node. Each node includes a routing system which results in efficient system performance for the parallel computer system associated with the nodes. The messages have control information (a message tag) to which the routing system at each node is responsive. The tag contains data identifying the destination node of the message in the network and prioritization data which, when the message is generated, is initialized to have a value (weight) corresponding to the length (number of links) of the minimal path from the source node where the message originates to the destination node of the message. The routing system utilizes the weights to establish message priority. The routing system receives and sends messages not exceeding the number of links connected thereto on each cycle such that messages flow in and flow out of each routing node on each cycle without being held or stored in queues in the node. Messages of lesser priority are switched by the router to alternate links in accordance with their weights thereby dynamically routing and resolving conflicts among messages.

Claims

1. In a multiprocessor in which messages are exchanged between processors interconnected for message communication by a multinode network wherein each node is connected to other nodes of said network by a plurality of message communication links, a system for transferring messages from nodes associated with processors which are the sources of said messages to nodes associated with processors which are the destinations for said messages so that said messages which are assigned priorities based on the topology of the network are passed continually among nodes without being blocked at any node and while minimizing the average time spent by messages in traveling between their source and destination nodes regardless of the distance in number of said links between said source and destination nodes, said system comprising non-blocking routing means for routing said messages at each node along links of minimal length to reach their destination nodes and along other links with priority given to the messages having longest distance between their source and destination nodes, said routing means including means based upon the present topology of the network, means at each node for increasing the priority of messages each time they are routed on links which are along paths of more than minimal length, and means at each node for receiving and then sending a number of said messages not exceeding the number of said plurality of links connected thereto.

2. The system according to claim 1 wherein said messages are generated by said processors with message weight data representing their priority and data representing their destinations and wherein said increasing means includes means in each node responsive to said message being transmitted from said node on a link which is along a path greater than of minimal length to its destination node for increasing the value of said message weight data.

3. The system according to claim 2 wherein said increasing means includes means for increasing the message weight thereof by two in numerical value.

4. The system according to claim 1 wherein said routing means includes means operative continually in consecutive cycles, and means for operating said transmitting and sending means so that said number of messages flow into and out of each of said nodes on each of said cycles.

5. The system according to claim 2 wherein said routing means comprises means for routing said messages in order of the value of their respective message weight data so that at each of said nodes the message of said number of messages having the highest message weight is routed for sending on a link along a minimal length path.

6. The system according to claim 5 wherein said routing means provides said routing in said weighting data value order with means for sorting and storing said number of data messages in accordance with their respective weighting data values.

7. The system according to claim 6 wherein said messages also contain data corresponding to the node in said network which is the destination thereof and said routing means includes means for allocating each of said messages to a different one of said links for sending said messages to other nodes of said network from said storing means in said weighting data order in accordance with said destination data thereof.

8. The system according to claim 7 wherein said allocating means comprises means responsive to said destination data for assigning each of said number of messages to be transmitted to (a) main links which are along paths of minimal length, (b) alternate links which are also along Paths of minimal length and (c) remaining ones of said lines which are available such that messages of highest weight order are assigned to said main link, and remaining messages are assigned to alternate and remaining available links respectively in accordance with their said weight data order.

9. The system according to claim 8 wherein said increasing means includes means responsive to the link to which said messages are assigned for increasing the value of the weighting order data only in those messages which are assigned to remaining available links.

11. The system according to claim 9 wherein said message contains a first control data field representing their destination nodes and a second control data field representing the priority thereof.

13. The network according to claim 11 wherein said routing means comprises means for incrementing the weight of each message which is routed to said free link.

18. The system according to claim 1 wherein means are provided for routing said messages along those of said minimal length and other links which are not faulty.

10. A digital multinode message communication network which comprises a multiplicity of nodes, each having a plurality of message communication links which are not necessarily equal in number, said communication links connecting each of said nodes to a plurality of other nodes of said network, a routing system in each node which comprises means for receiving a plurality of messages which are assigned priorities based on the topology of the network and which is equal or less than the number of said links and sending said messages out along the links of each said node on successive routing cycles so that all said messages flow into and out of each said node on said successive cycles, non-blocking routing means for transferring messages which are received first on one of said plurality of links along a main path of minimum length in number of links, from said node to another of said plurality of nodes which is the destination thereof, then to another of said plurality of links along an alternate path which is also of said minimum length, and then to any of said plurality of links which is free in order according to the length of the path to said destination node of said message so that the messages having longer path lengths are given priority over messages of shorter path lengths to their respective destination nodes, said routing means including means based upon the present topology of the network.

12. The network according to claim 10 wherein said control data field is a weight which has an initial value when said message one of said nodes which is the source of said message in said network which represents the minimal path from said source node to another of said multiplicity of nodes which is the destination of said message.

14. The network according to claim 12 wherein said incrementing means includes means for incrementing said weight by a value of at least two.

15. The network according to claim 12 wherein said router means comprises means for sorting and storing said messages in order accordance with their weights, means for mapping said messages for routing on links of minimal length according to their first data fields representing the destinations thereof, and means for assigning said messages to said main, alternate and free links according to the weight thereof.

16. The network according to claim 14 wherein said means are provided for successively transferring said messages from said storing means to said mapping and assigning means in the order stored in said storing means.

17. The network according to claim 15 further comprising means associated with each of said nodes (a local node) for storing messages for which said node in the source node where said messages are injected with said network in send queues and for storing messages for which said local node is the destination of said messages in receive queues, and means for transferring said message into said routing system of said node in lieu of a message from another of said multiplicity of nodes when the destination of said message is said local node and when a message is not sent along to said local node along one of its plurality of links.

19. The system according to claim 10 wherein said routing means include means for selecting links along said main, and alternate paths only if they are not faulty.