Patent US5602839A successfully refreshed from Google Patents.
US5602839A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Adaptive and dynamic message routing system for multinode wormhole networks
Assignee: International Business Machines Corp
•
Filing: 1995-11-09
•
Granted: 1997-02-11
•
Expires: 2015-11-09
Abstract
Abstract In a multinode communication or multiprocessor network, messages are communicated from one node to another using an adaptive and dynamic routing scheme. The routing scheme includes two-level multi-path routing tables at each node to ensure efficient delivery of the messages. An entry in the level-1 table identifies a group of nodes and entry in the level-2 table identifies the address for each node within that group. The routing scheme also includes a deflection counter in each message header to avoid endless rerouting of messages and an exponential backoff and retry policy to avoid deadlocks.
Inventors
- 👤 Narasimhareddy Annapareddy
- 👤 James T. Brady
- 👤 Damon W. Finney
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 06:18
CPC Classifications
H; H04; H04W; H04W40/00; H04W40/02; H04Q; H04Q3/00; H04Q3/64; H04Q3/66; H04Q3/665; H04L; H04L45/00; H04L45/02; H04L45/04; H04L45/18; H04L45/20; H04L45/40; H04W40/24; H04W84/00; H04W84/02; H04W84/04
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
115 words
A wormhole network, comprising: a plurality of nodes interconnected by communication links, said nodes divided into groups where each of said groups includes a predetermined number of said nodes not included in the other groups, each node having a local node address and a group address and further having access to a processor and memory; each node including a level-1 table, said level-1 table comprising message delivery directions for delivering a message from a node of a group to another group in the network; and each node including a level-2 table, said level-2 table comprising message delivery directions for delivering said message from a node of a group to the other nodes within said group.
Claim 2
Dependent Claim
115 words
A wormhole network, comprising: a plurality of nodes interconnected by communication links, said nodes divided into groups where each of said groups includes a predetermined number of said nodes not included in the other groups, each node having a local node address and a group address and further having access to a processor and memory; each node including a level-1 table, said level-1 table comprising message delivery directions for delivering a message from a node of a group to another group in the network; and each node including a level-2 table, said level-2 table comprising message delivery directions for delivering said message from a node of a group to the other nodes within said group.
Claim 3
Dependent Claim
41 words
A wormhole network according to claim 1 wherein each of said message delivery directions in said level-1 table includes the most preferred message delivery direction for delivering a message from a node of a group to another group in the network.
Claim 4
Dependent Claim
39 words
A wormhole network according to claim 2 wherein said message delivery directions in said level-2 table include most preferred message delivery directions for delivering a message from a node of a group to the other nodes within said group.
Claim 5
Dependent Claim
35 words
A wormhole network according to claim 3 wherein said message comprises a message header, said message header including a destination address, said destination address having a destination group address and a destination local node address.
Claim 6
Dependent Claim
45 words
A wormhole network according to claim 4 wherein said destination group address is used as an index into a level-1 table of a node receiving said message to select a message delivery direction if said destination group address does not match the node group address.
Claim 7
Dependent Claim
44 words
A wormhole network according to claim 5 wherein said destination local node address is used as an index into a level-2 table of a node receiving said message to select a message delivery direction if said destination group address matches the node group address.
Claim 8
Dependent Claim
55 words
A wormhole network according to claim 6 wherein said message header further comprises a deflection counter, said deflection counter is decremented by a node receiving said message if the node is not the destination node and the most preferred message delivery direction for delivering the message in the level-1 table of said node is unavailable.
Claim 9
Dependent Claim
20 words
A wormhole network according to claim 7 further comprising a backup and retry means for resending an unsuccessfully terminated message.
Claim 10
Independent Claim
127 words
A method of delivering messages in a wormhole network from a source node to a destination node where each message includes a group address and a local node address for the destination node, comprising the steps of: dividing nodes in said network into groups where each group comprises a plurality of the nodes not included in the other groups; storing a level-1 routing table at each node for providing message delivery directions from a node to every other group in the network; storing a level-2 routing table at each node for providing message delivery directions from a node of a group to the other nodes of said group; and routing said message from the source node to the destination node using the level-1 table and level-2 table.
Claim 11
Independent Claim
127 words
A method of delivering messages in a wormhole network from a source node to a destination node where each message includes a group address and a local node address for the destination node, comprising the steps of: dividing nodes in said network into groups where each group comprises a plurality of the nodes not included in the other groups; storing a level-1 routing table at each node for providing message delivery directions from a node to every other group in the network; storing a level-2 routing table at each node for providing message delivery directions from a node of a group to the other nodes of said group; and routing said message from the source node to the destination node using the level-1 table and level-2 table.
Claim 12
Dependent Claim
45 words
A method of delivering messages in a wormhole network according to claim 9 wherein said message delivery directions in said level-1 table includes the most preferred message delivery directions for delivering a message from a node of a group to other groups in the network.
Claim 13
Dependent Claim
46 words
A method of delivering messages in a wormhole network according to claim 10 wherein said message delivery directions in said level-2 table includes the most preferred message delivery directions for delivering a message from a node of a group to the other nodes within said group.
Claim 14
Dependent Claim
41 words
A method of delivering messages in a wormhole network according to claim 11 wherein said message comprises a message header, said message header including a destination address, said destination address having a destination group address and a destination local node address.
Claim 15
Dependent Claim
45 words
A method of delivering messages in a wormhole network according to claim 12 wherein said destination group address is used as an index into a level-1 table of a node receiving said message if said destination group address does not match the node group address.
Claim 16
Dependent Claim
44 words
A method of delivering messages in a wormhole network according to claim 13 wherein said destination local node address is used as an index into a level-2 table of a node receiving said message if said destination group address matches the node group address.
Claim 17
Dependent Claim
54 words
A method of delivering messages in a wormhole network according to claim 14 wherein said message header further comprises a deflection counter, said deflection counter is decremented by a node receiving said message if the node is not the destination node and the most preferred message delivery direction in the level-1 table is unavailable.
Claim 18
Dependent Claim
24 words
A method of delivering messages in a wormhole network according to claim 15 further comprising a backoff-and-retry means for resending an unsuccessfully terminated message.
Claim 19
Dependent Claim
219 words
A wormhole network comprising: a plurality of nodes interconnected by communication links, said nodes divided into gateway nodes and local nodes where each of said gateway nodes controls message delivery to a predetermined number of said local nodes, each gateway node is identified by a gateway node address and each local node is identified by a local node address and a gateway node address, each of said nodes further having access to a processor and memory; a level-1 table stored at each gateway node, said level-1 table comprising message delivery directions, including the most preferred message delivery directions, for delivering a message from a gateway node to other gateway nodes in the network, said message comprising a message header, said message header including a destination address, said destination address having a destination gateway node address and a destination local node address; a level-2 table stored at each local node, said level-2 table comprising message delivery directions, including the most preferred message delivery directions, for delivering said message among the local nodes controlled by a gateway node; and wherein said destination gateway node address is used as an index into a level-1 table of a gateway node receiving said message if said destination gateway node address does not match the gateway node address of the gateway node receiving said message.
Claim 20
Dependent Claim
219 words
A wormhole network comprising: a plurality of nodes interconnected by communication links, said nodes divided into gateway nodes and local nodes where each of said gateway nodes controls message delivery to a predetermined number of said local nodes, each gateway node is identified by a gateway node address and each local node is identified by a local node address and a gateway node address, each of said nodes further having access to a processor and memory; a level-1 table stored at each gateway node, said level-1 table comprising message delivery directions, including the most preferred message delivery directions, for delivering a message from a gateway node to other gateway nodes in the network, said message comprising a message header, said message header including a destination address, said destination address having a destination gateway node address and a destination local node address; a level-2 table stored at each local node, said level-2 table comprising message delivery directions, including the most preferred message delivery directions, for delivering said message among the local nodes controlled by a gateway node; and wherein said destination gateway node address is used as an index into a level-1 table of a gateway node receiving said message if said destination gateway node address does not match the gateway node address of the gateway node receiving said message.
Claim 21
Dependent Claim
46 words
A wormhole network according to claim 17 wherein said destination local node address is used as an index into a level-2 table of a node receiving said message if said destination gateway node address matches the gateway node address of the gateway node receiving said message.
Claim 22
Dependent Claim
51 words
A wormhole network according to claim 18 wherein said message header further comprises a deflection counter, said deflection counter is decremented by a gateway node receiving said message if the gateway node is not the destination gateway node and the most preferred message delivery direction in the level-1 table is unavailable.
Claim 23
Dependent Claim
20 words
A wormhole network according to claim 19 further comprising a backup and retry means for resending an unsuccessfully terminated message.
Claim 24
Independent Claim
235 words
A method of delivering messages in a wormhole network from a source node to a destination node where each message comprises a message header, said message header including a destination address, said destination address having a destination gateway node address and a destination local node address comprising the steps of: dividing nodes in said network into gateway nodes and local nodes where each gateway node controls message delivery to a predetermined number of local nodes; storing a level-1 routing table at each gateway node for providing message delivery directions, including the most preferred message delivery directions, from a gateway node to the other gateway nodes in the network: storing a level-2 routing table at each local node for providing message delivery directions, including the most preferred message delivery directions, from a local node of a gateway node to the other local nodes of said gateway node; routing said message from the source node to the destination gateway node using the level-1 table at each gateway node used in the network for message delivery; routing said message from the destination gateway node to the destination local node using the level-2 table at each local node used in the network for message delivery; and wherein said destination gateway address is used as an index into a level-1 table of a gateway node receiving said message if said destination gateway address does not match the gateway node address.
Claim 25
Independent Claim
235 words
A method of delivering messages in a wormhole network from a source node to a destination node where each message comprises a message header, said message header including a destination address, said destination address having a destination gateway node address and a destination local node address comprising the steps of: dividing nodes in said network into gateway nodes and local nodes where each gateway node controls message delivery to a predetermined number of local nodes; storing a level-1 routing table at each gateway node for providing message delivery directions, including the most preferred message delivery directions, from a gateway node to the other gateway nodes in the network: storing a level-2 routing table at each local node for providing message delivery directions, including the most preferred message delivery directions, from a local node of a gateway node to the other local nodes of said gateway node; routing said message from the source node to the destination gateway node using the level-1 table at each gateway node used in the network for message delivery; routing said message from the destination gateway node to the destination local node using the level-2 table at each local node used in the network for message delivery; and wherein said destination gateway address is used as an index into a level-1 table of a gateway node receiving said message if said destination gateway address does not match the gateway node address.
Claim 26
Dependent Claim
45 words
A method of delivering messages in a wormhole network according to claim 21 wherein said destination local node address is used as an index into a level-2 table of a local node receiving said message if said destination gateway address matches the gateway node address.
Claim 27
Dependent Claim
57 words
A method of delivering messages in a wormhole network according to claim 22 wherein said message header further comprises a deflection counter, said deflection counter is decremented by a node receiving said message if the node is not the destination node and the most preferred message delivery direction from that node to the next node is unavailable.
Claim 28
Dependent Claim
26 words
A method of delivering messages in a wormhole network according to claim 23 further comprising a backup and retry means for resending an unsuccessfully terminated message.
References Cited (Backward Citations)
DE3626870A1
Cited
US5079767A
Cited
US5142531A
Cited
US5206856A
Cited
US5365520A
Cited
US5351237A
Cited
US5353283A
Cited
US5495479A
Cited
US5497368A
Cited
US5519705A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-02-11 | 2000-08-12 | 2001-02-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-02-11 | 2004-08-12 | 2005-02-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-02-11 | 2008-08-12 | 2009-02-11 | $7700.00 | Window Closed / Lapsed |