US5533198A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Direction order priority routing of packets between nodes in a networked system
Assignee: Morgan Stanley and Co LLC
•
Filing: 1992-11-30
•
Granted: 1996-07-02
•
Expires: 2012-11-30
Abstract
Abstract A method of routing messages within an n-dimensional network topology. Two directions are associated with each dimension in the n-dimensional network, for a total of 2n directions. A direction order is assigned which prioritizes the order in which a packet is routed across the 2n possible directions. Such an approach provides deadlock-free, fault tolerant wormhole routing in networks without wrap-around channels. For networks with wrap-around channels, the above method of wormhole routing is enhanced by placing a first direction from each of the n dimensions within a first group of directions. The second direction from each dimension is placed within a second group of directions. A packet to be routed from a source node to a destination node is routed in all relevant directions in the first group of directions in any order before being routed in the second group of directions. If, while traveling in a direction within the first group of directions, the packet is routed across a wrap-around channel, all further routing in that direction must be completed before moving in another direction. Routing then proceeds, if necessary, in the other directions of that first group of directions. Likewise, if, while traveling in a direction within the second group of directions, the packet is routed across a wrap-around channel, all further routing in that direction must be completed before moving in another of the second group of directions. A free hop mechanism is also taught for increase flexibility.
Inventors
- 👤 Gregory M. Thorson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 05:03
CPC Classifications
H; H04; H04Q; H04Q3/00; H04Q3/0016; H04Q3/0062; H04Q3/0075; H04Q3/0079; G; G06; G06F; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17356; G06F15/17368; G06F15/17381; H04L; H04L45/00; H04L45/02; H04L45/06; H04L45/22; H04L45/40; G06F11/00; G06F11/07; G06F11/16; G06F11/20; G06F11/202
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
208 words
A method of routing a packet between a source and a destination node in a networked system having a plurality of nodes connected in an n-dimensional topology, wherein the topology comprises n dimensions, including a first and a second dimension, wherein the system comprises two or more nodes connected in 2n directions to other nodes in the system and wherein the 2n directions comprise first and second directions in each of the n dimensions, the system performing the method comprising the steps of: defining a direction order for routing packets, wherein the direction order defines a priority for packet routing in each of the 2n directions, wherein the first direction of the first dimension, the second direction of the first dimension, the first direction of the second dimension, and the second direction of the second dimension all have different defined priorities for packet routing; generating a header comprising routing information, wherein the routing information comprises information needed for routing in each dimension based on the direction order; attaching the header to information to be transferred in order to form a packet; and transferring the packet from the source node to the destination node, wherein the step of transferring the packet comprises routing the packet in the direction order.
Claim 2
Independent Claim
208 words
A method of routing a packet between a source and a destination node in a networked system having a plurality of nodes connected in an n-dimensional topology, wherein the topology comprises n dimensions, including a first and a second dimension, wherein the system comprises two or more nodes connected in 2n directions to other nodes in the system and wherein the 2n directions comprise first and second directions in each of the n dimensions, the system performing the method comprising the steps of: defining a direction order for routing packets, wherein the direction order defines a priority for packet routing in each of the 2n directions, wherein the first direction of the first dimension, the second direction of the first dimension, the first direction of the second dimension, and the second direction of the second dimension all have different defined priorities for packet routing; generating a header comprising routing information, wherein the routing information comprises information needed for routing in each dimension based on the direction order; attaching the header to information to be transferred in order to form a packet; and transferring the packet from the source node to the destination node, wherein the step of transferring the packet comprises routing the packet in the direction order.
Claim 3
Dependent Claim
49 words
The method of routing according to claim 1 wherein the step of transferring the packet further comprises sending the packet in a free hop from the source node to an adjacent node to avoid a route in which multiple links between ones of the plurality of nodes are missing.
Claim 4
Dependent Claim
64 words
The method of routing according to claim 1 wherein the step of defining a direction order comprises assigning the first and second directions of the first dimension to a higher priority than the first and second directions of the second dimension in order to ensure that routing of a packet is completed in the first dimension before it is initiated in the second dimension.
Claim 5
Dependent Claim
48 words
The method of routing according to claim 1 wherein the step of defining a direction order comprises assigning all first directions to higher priorities than any second directions such that routing of a packet is completed in all first directions before it is initiated in any second direction.
Claim 6
Dependent Claim
49 words
The method of routing according to claim 4 wherein the step of transferring the packet further comprises sending the packet in a free hop from the source node to an adjacent node to avoid a route in which multiple links between ones of the plurality of nodes are missing.
Claim 7
Dependent Claim
38 words
The method of routing according to claim 5 wherein the step of sending the packet in a free hop from the source node to an adjacent node comprises sending the packet in any one of the first directions.
Claim 8
Dependent Claim
62 words
The method of claim 1 further comprising the steps of: recognizing a network fault in the networked system between two of the plurality of nodes; and redefining the direction order for routing packets, wherein the redefined direction order redefines the priority for packet routing in at least two of the 2n directions to permit routing of the packet around the network fault.
Claim 9
Independent Claim
434 words
A method of routing a packet between a source and a destination node in a networked system having a plurality of nodes connected in an n-dimensional topology having wrap-around channels, wherein the topology comprises n dimensions, including a first and a second dimension, wherein the system comprises two or more nodes connected in 2n directions to other nodes in the system and wherein the 2n directions comprise first and second directions in each of the n dimensions, the system performing the method comprising the steps of: defining a direction order for routing packets, wherein the direction order defines a priority for packet routing in each of the 2n directions, wherein the first direction of the first dimension, the second direction of the first dimension, the first direction of the second dimension, and the second direction of the second dimension all have different defined priorities for packet routing; generating a header comprising routing information, wherein the routing information comprises information for routing in at least one of the directions in each dimension based on the direction order; attaching the header to information to be transferred in order to form a packet; transferring the packet from the source node to the destination node, wherein the step of transferring the packet comprises: routing the packet in the first directions defined in the routing information according to the direction order, wherein the step of routing the packet in the first directions comprises: a) routing the packet in one of the first directions defined in the routing information; b) determining if the packet has crossed one of the wrap-around channels; c) if the packet has crossed a wrap-around channel in a particular one of the first directions, continuing to route in the particular first direction until all transfers in that particular first direction are completed; and d) if one or more first directions defined in the routing information have not been routed, going to step a; and routing the packet in the second directions defined in the routing information according to the direction order, wherein the step of routing the packet in the second directions comprises: e) routing the packet in one of the second directions defined in the routing information; f) determining if the packet has crossed one of the wrap-around channels; g) if the packet has crossed a wrap-around channel in a particular one of the second directions, continuing to route in the particular second direction until all transfers in that particular second direction are completed; and h) if one or more second directions defined in the routing information have not been routed, going to step e.
Claim 10
Independent Claim
434 words
A method of routing a packet between a source and a destination node in a networked system having a plurality of nodes connected in an n-dimensional topology having wrap-around channels, wherein the topology comprises n dimensions, including a first and a second dimension, wherein the system comprises two or more nodes connected in 2n directions to other nodes in the system and wherein the 2n directions comprise first and second directions in each of the n dimensions, the system performing the method comprising the steps of: defining a direction order for routing packets, wherein the direction order defines a priority for packet routing in each of the 2n directions, wherein the first direction of the first dimension, the second direction of the first dimension, the first direction of the second dimension, and the second direction of the second dimension all have different defined priorities for packet routing; generating a header comprising routing information, wherein the routing information comprises information for routing in at least one of the directions in each dimension based on the direction order; attaching the header to information to be transferred in order to form a packet; transferring the packet from the source node to the destination node, wherein the step of transferring the packet comprises: routing the packet in the first directions defined in the routing information according to the direction order, wherein the step of routing the packet in the first directions comprises: a) routing the packet in one of the first directions defined in the routing information; b) determining if the packet has crossed one of the wrap-around channels; c) if the packet has crossed a wrap-around channel in a particular one of the first directions, continuing to route in the particular first direction until all transfers in that particular first direction are completed; and d) if one or more first directions defined in the routing information have not been routed, going to step a; and routing the packet in the second directions defined in the routing information according to the direction order, wherein the step of routing the packet in the second directions comprises: e) routing the packet in one of the second directions defined in the routing information; f) determining if the packet has crossed one of the wrap-around channels; g) if the packet has crossed a wrap-around channel in a particular one of the second directions, continuing to route in the particular second direction until all transfers in that particular second direction are completed; and h) if one or more second directions defined in the routing information have not been routed, going to step e.
Claim 11
Dependent Claim
49 words
The method of routing according to claim 8 wherein the step of transferring the packet further comprises sending the packet in a free hop from the source node to an adjacent node to avoid a route in which multiple links between ones of the plurality of nodes are missing.
Claim 12
Dependent Claim
38 words
The method of routing according to claim 9 wherein the step of sending the packet in a free hop from the source node to an adjacent node comprises sending the packet in any one of the first directions.
Claim 13
Dependent Claim
188 words
A networked system comprising: a plurality of nodes; an interconnect network interconnecting the nodes in an n-dimensional topology having n dimensions, including a first and a second dimension, the interconnect network connecting two or more nodes in 2n directions to other nodes in the system, the 2n directions including first and second directions in each of the n dimensions; means for defining a direction order for routing from a source node to a destination node according to a priority in each of the 2n directions, wherein the first direction of the first dimension, the second direction of the first dimension, the first direction of the second dimension, and the second direction of the second dimension all have different defined priorities for packet routing; means for generating a header having routing information needed for routing in each dimension based on the direction order; means for forming a packet by attaching the header to information provided by the source node; and means responsive to the routing information in the header to transfer the packet from the source node to the destination node by routing the packet in the direction order.
Claim 14
Dependent Claim
188 words
A networked system comprising: a plurality of nodes; an interconnect network interconnecting the nodes in an n-dimensional topology having n dimensions, including a first and a second dimension, the interconnect network connecting two or more nodes in 2n directions to other nodes in the system, the 2n directions including first and second directions in each of the n dimensions; means for defining a direction order for routing from a source node to a destination node according to a priority in each of the 2n directions, wherein the first direction of the first dimension, the second direction of the first dimension, the first direction of the second dimension, and the second direction of the second dimension all have different defined priorities for packet routing; means for generating a header having routing information needed for routing in each dimension based on the direction order; means for forming a packet by attaching the header to information provided by the source node; and means responsive to the routing information in the header to transfer the packet from the source node to the destination node by routing the packet in the direction order.
Claim 15
Dependent Claim
48 words
The networked system of claim 11 wherein the means for transferring the packet includes means for sending the packet in a free hop from the source node to an adjacent node to avoid a route in which multiple links between ones of the plurality of nodes are missing.
Claim 16
Dependent Claim
64 words
The networked system of claim 11 wherein the means for defining a direction order includes means for assigning the first and second directions of the first dimension to a higher priority than the first and second directions of the second dimension in order to ensure that routing of a packet is completed in the first dimension before it is initiated in the second dimension.
Claim 17
Dependent Claim
48 words
The networked system of claim 11 wherein the means for defining a direction order includes means for assigning all first directions to higher priorities than any second directions such that routing of a packet is completed in all first directions before it is initiated in any second direction.
Claim 18
Dependent Claim
47 words
The networked system of claim 14 wherein means for transferring the packet includes means for sending the packet in a free hop from the source node to an adjacent node to avoid a route in which multiple links between ones of the plurality of nodes are missing.
Claim 19
Dependent Claim
38 words
The networked system of claim 15 wherein the means for sending the packet in a free hop from the source node to an adjacent node includes means for sending the packet in any one of the first directions.
Claim 20
Dependent Claim
64 words
The networked system of claim 11 further comprising: means for recognizing a network fault in the networked system between two of the plurality of nodes; and means for redefining the direction order for routing packets, wherein the redefined direction order redefines the priority for packet routing in at least two of the 2n directions to permit routing of the packet around the network fault.
Claim 21
Dependent Claim
277 words
A networked system, controlled by an operating system and comprising: a plurality of nodes, each node including a look-up table having entries corresponding to each of the plurality of nodes, the entries defining, for each node, a path to be taken to each node from the other nodes; an interconnect network interconnecting the nodes in an n-dimensional topology having n dimensions, including a first and a second dimension, the interconnect network connecting two or more nodes in 2n directions to other nodes in the system, the 2n directions including first and second directions in each of the n dimensions; means for generating a header having routing information needed for routing in each dimension from a source node to a destination node by accessing an entry corresponding to the destination node in the source node's look-up table, wherein said entry defines a direction order for routing from the source node to the destination node according to a priority in each of the 2n directions, wherein the first direction of the first dimension, the second direction of the first dimension, the first direction of the second dimension, and the second direction of the second dimension all have different defined priorities for packet routing; means for forming a packet by attaching the header to information provided by the source node; means responsive to the routing information in the header for transferring the packet from the source node to the destination node by routing the packet in the direction order; and a network control path connected to each node separate from the interconnect network, wherein the network control path provides a path for the operating system to load the look-up tables.
Claim 22
Dependent Claim
277 words
A networked system, controlled by an operating system and comprising: a plurality of nodes, each node including a look-up table having entries corresponding to each of the plurality of nodes, the entries defining, for each node, a path to be taken to each node from the other nodes; an interconnect network interconnecting the nodes in an n-dimensional topology having n dimensions, including a first and a second dimension, the interconnect network connecting two or more nodes in 2n directions to other nodes in the system, the 2n directions including first and second directions in each of the n dimensions; means for generating a header having routing information needed for routing in each dimension from a source node to a destination node by accessing an entry corresponding to the destination node in the source node's look-up table, wherein said entry defines a direction order for routing from the source node to the destination node according to a priority in each of the 2n directions, wherein the first direction of the first dimension, the second direction of the first dimension, the first direction of the second dimension, and the second direction of the second dimension all have different defined priorities for packet routing; means for forming a packet by attaching the header to information provided by the source node; means responsive to the routing information in the header for transferring the packet from the source node to the destination node by routing the packet in the direction order; and a network control path connected to each node separate from the interconnect network, wherein the network control path provides a path for the operating system to load the look-up tables.
Claim 23
Dependent Claim
34 words
The networked system of claim 18 wherein the look-up table entries corresponding to each node include both an absolute location of the corresponding node and a selected path in each of the n dimensions.
Claim 24
Dependent Claim
68 words
The networked system of claim 18 wherein the look-up table entries corresponding to each node include a relative address from each node in the networked system to all other nodes, and wherein the means for transferring the packet includes means to alter the routing information in the header prior to forwarding the packet to the next node in the path from the source node to the destination node.
References Cited (Backward Citations)
EP0501524A2
Cited
US4933933A
Cited
WO1988008652A1
Cited
US5008882A
Cited
US5105424A
Cited
US5157692A
Cited
US5280474A
Cited
US5218676A
Cited
US5175733A
Cited
US5333279A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-07-02 | 2000-01-01 | 2000-07-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-07-02 | 2004-01-01 | 2004-07-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-07-02 | 2008-01-01 | 2008-07-02 | $7700.00 | Window Closed / Lapsed |