US5175733A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Adaptive message routing for multi-dimensional networks
Assignee: Intel Corp
•
Filing: 1990-12-27
•
Granted: 1992-12-29
•
Expires: 2010-12-27
Abstract
Abstract An adaptive routing means and method useful for transferring messages on a number of multi-dimensional network topologies that connect distributed multi-processing systems. A plurality of processing nodes comprising processing means for processing information and router means for routing messages are connected in a multi-dimensional network (A) with an identical or redundant message passing multi-dimensional network (B) of routers being connected to network A. Each router comprises four types of channels for message passing: 1) a channel to transfer information between a router and a processor coupled to the router, 2) a channel to transfer information in an X direction, 3) a channel for the Y direction, and 4) a channel for the Z direction. This connectivity allows messages to pass between nodes within network A, between routers within network B, or between network A and network B by passing through a router. Messages are routed in networks A and B by routing first in the X dimension and then in the Y dimension. The present invention transitions between A and B networks when contention is encountered in the X or Y direction, if the appropriate Z channel is available. If an X or Y channel is not immediately granted, a request is made for the Z channel. Both the request for an X or Y channel and the request for the Z channel are maintained until one request is granted. The message is then routed on the granted channel and the other request is withdrawn. The router does not commit to routing on a particular channel until one channel is available.
Inventors
- 👤 Steven F. Nugent
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 11:40
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/02; H04L45/06
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
184 words
A network for routing messages comprising: a first network having a plurality of nodes, each said node having a router, said nodes being coupled together by first network channels for routing messages between nodes of said first network; a second network having a plurality of nodes, each said node having a router, said nodes being coupled together by second network channels for routing messages between nodes of said second network, each said router in said second network being coupled to at least one router in said first network by Z channels for routing messages between nodes of each network, said first and said second networks being of equal dimension; and message routing means operably disposed within each said router of both said first network and said second network, said message routing means routing messages from a source node to a destination node via said first network channels and said second network channels, said message routing means routing messages between said first network and said second network on said Z channels if a required first network channel or a required second network channel is unavailable.
Claim 2
Dependent Claim
184 words
A network for routing messages comprising: a first network having a plurality of nodes, each said node having a router, said nodes being coupled together by first network channels for routing messages between nodes of said first network; a second network having a plurality of nodes, each said node having a router, said nodes being coupled together by second network channels for routing messages between nodes of said second network, each said router in said second network being coupled to at least one router in said first network by Z channels for routing messages between nodes of each network, said first and said second networks being of equal dimension; and message routing means operably disposed within each said router of both said first network and said second network, said message routing means routing messages from a source node to a destination node via said first network channels and said second network channels, said message routing means routing messages between said first network and said second network on said Z channels if a required first network channel or a required second network channel is unavailable.
Claim 3
Dependent Claim
25 words
The network claimed in claim 1 wherein said routers use routing information contained in each message for routing said message to its said destination node.
Claim 4
Dependent Claim
54 words
The network claimed in claim 1 wherein said first network and said second network are arranged in a two-dimensional dual mesh connection of nodes, said routers of said first network and said second network having X channels for routing messages in an X direction and Y channels for routing messages in a Y direction.
Claim 5
Dependent Claim
28 words
The network claimed in claim 1 wherein said message routing means routing messages between said first network and said second network on said Z channels in either direction.
Claim 6
Dependent Claim
35 words
The network claimed in claim 1 wherein said message routing means routing messages between said first network and said second network on said Z channels if the previous channel traversed was not a Z channel.
Claim 7
Dependent Claim
91 words
The network claimed in claim 1 wherein said message routing means further including: means for requesting the use of a primary channel in order to route a message thereon; means for determining if a requested channel is available for use; means for requesting the use of a secondary channel in order to route said message thereon if said primary channel is unavailable; and means for granting the use of a channel in order to route said message thereon, said channel granted being the first of said requested channels to become available.
Claim 8
Dependent Claim
33 words
The network claimed in claim 6 further including means for withdrawing a request for the use of a channel when a request for the use of a primary or secondary channel is granted.
Claim 9
Dependent Claim
16 words
The network claimed in claim 7 wherein said secondary channel is one of said Z channels.
Claim 10
Dependent Claim
40 words
The network claimed in claim 7 wherein said message routing means further including: means for repeatedly testing for the availability of both said primary channel and said secondary channel, until either said primary channel or said secondary channel becomes available.
Claim 11
Dependent Claim
15 words
The network claimed in claim 1 wherein said messages are routed using relative message addressing.
Claim 12
Dependent Claim
15 words
The network claimed in claim 1 wherein said messages are routed using absolute message addressing.
Claim 13
Dependent Claim
167 words
In a network having a first network including a plurality of nodes, each said node having a router, said nodes being coupled together by first network channels for routing messages between nodes of said first network and a second network including a plurality of nodes, each said node having a router, said nodes being coupled together by second network channels for routing messages between nodes of said second network, each said router in said second network being coupled to at least one router in said first network by Z channels for routing messages between nodes of each network, said first and said second networks being of equal dimension, a process for routing messages comprising the step of: routing messages from a source node to a destination node via said first network channels and said second network channels, said messages being routed between said first network and said second network on said Z channels if a required first network channel or a required second network channel is unavailable.
Claim 14
Dependent Claim
167 words
In a network having a first network including a plurality of nodes, each said node having a router, said nodes being coupled together by first network channels for routing messages between nodes of said first network and a second network including a plurality of nodes, each said node having a router, said nodes being coupled together by second network channels for routing messages between nodes of said second network, each said router in said second network being coupled to at least one router in said first network by Z channels for routing messages between nodes of each network, said first and said second networks being of equal dimension, a process for routing messages comprising the step of: routing messages from a source node to a destination node via said first network channels and said second network channels, said messages being routed between said first network and said second network on said Z channels if a required first network channel or a required second network channel is unavailable.
Claim 15
Dependent Claim
83 words
The process claimed in claim 12 wherein said message routing step further including: requesting the use of a primary channel in order to route a message thereon; determining if a requested channel is available for use; requesting the use of a secondary channel in order to route said message thereon if said primary channel is unavailable; and granting the use of a channel in order to route said message thereon, said channel granted being the first of said requested channels to become available.
Claim 16
Dependent Claim
27 words
The process claimed in claim 12 further including a step of: decoding routing information contained in each message for routing said message to its said destination node.
Claim 17
Dependent Claim
33 words
The process claimed in claim 12 further including a step of: routing messages in either an X direction or a Y direction in said first network depending upon information contained in each message.
Claim 18
Dependent Claim
32 words
The process claimed in claim 12 wherein messages may be routed on said Z channels from said first network to said second network or from said second network to said first network.
Claim 19
Dependent Claim
34 words
The process claimed in claim 13 further including a step of: withdrawing a request for the use of a channel when a request for the use of a primary or secondary channel is granted.
Claim 20
Dependent Claim
36 words
The process claimed in claim 13 further including a step of: repeatedly testing for the availability of both said primary channel and said secondary channel, until either said primary channel or said secondary channel becomes available.
Claim 21
Dependent Claim
140 words
A network routing apparatus comprising: a primary channel and a secondary channel, said primary channel and said secondary channel being used to route messages in a first network; a Z channel, said Z channel being used to route messages to a second network; and routing logic coupled to said primary channel, said secondary channel, and said Z channel, said routing logic comprising: means for requesting the use of said primary channel in order to route a message thereon; means for determining if a requested channel is available for use; means for requesting the use of said secondary channel in order to route said message thereon if said primary channel is unavailable; and means for granting the use of a channel in order to route said message thereon, said channel granted being the first of said requested channels to become available.
Claim 22
Dependent Claim
140 words
A network routing apparatus comprising: a primary channel and a secondary channel, said primary channel and said secondary channel being used to route messages in a first network; a Z channel, said Z channel being used to route messages to a second network; and routing logic coupled to said primary channel, said secondary channel, and said Z channel, said routing logic comprising: means for requesting the use of said primary channel in order to route a message thereon; means for determining if a requested channel is available for use; means for requesting the use of said secondary channel in order to route said message thereon if said primary channel is unavailable; and means for granting the use of a channel in order to route said message thereon, said channel granted being the first of said requested channels to become available.
Claim 23
Dependent Claim
27 words
The network routing apparatus claimed in claim 19 further including: means for decoding routing information contained in each message for routing said message to a destination node.
Claim 24
Dependent Claim
34 words
The network routing apparatus claimed in claim 19 further including: means for routing messages in either an X direction or a Y direction in said first network depending upon information contained in each message.
Claim 25
Dependent Claim
34 words
The network routing apparatus claimed in claim 19 wherein messages may be routed on said Z channel from said first network to said second network or from said second network to said first network.
Claim 26
Dependent Claim
39 words
The network routing apparatus claimed in claim 19 wherein said routing logic further comprises means for withdrawing a request for the use of a channel when a request for the use of a primary or secondary channel is granted.
Claim 27
Dependent Claim
41 words
The network routing apparatus claimed in claim 19 wherein said routing logic further comprises means for repeatedly testing for the availability of both said primary channel and said secondary channel, until either said primary channel or said secondary channel becomes available.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-12-29 | 1996-06-29 | 1996-12-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-12-29 | 2000-06-29 | 2000-12-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-12-29 | 2004-06-29 | 2004-12-29 | $7700.00 | Window Closed / Lapsed |