×

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
First Claim
Patent Images

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.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×