US5151900A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Chaos router system
Assignee: University of Washington
•
Filing: 1991-06-14
•
Granted: 1992-09-29
•
Expires: 2011-06-14
Abstract
Abstract A chaos router system for routing messages between connected nodes in a multicomputer or multiprocessor system is disclosed. In such a system, a message may be routed between nodes along a preferred channel so that it is closer to its destination or derouted between nodes along a random channel so that it is further from its destination. The chaos router system explicitly randomizes message selection during derouting. In an asynchronous multicomputer system, the router system keeps the overall system chaotic. In this manner, the system is probabilistically livelock free.
Inventors
- 👤 Lawrence Snyder
- 👤 Smaragda Konstantinidou
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 22:57
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/02; H04L45/06; G; G06; G06F; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17356; G06F15/17368
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
217 words
A message router system for routing messages from a source node to a destination node in a multinode processing system, the multinode processing system includes a multiplicity of nodes connected by channels such that a message may be routed along a profitable channel so that it is closer to its destination or derouted along a random channel so that it is further from its destination, wherein each node includes a routing subsystem having a set of input frames corresponding to the channels for receiving messages from the channels, a set of output frames corresponding to the channels for sending messages to the channels, and a fixed-size message queue for storing messages at the node, the message router system comprising at each node: (a) a routing controller for identifying an empty output frame, selecting a profitable message from the message queue such that the channel corresponding to said empty output frame is a profitable channel for said message, and, if said profitable message is available, writing said profitable message to said empty output frame; and (b) a random selector for randomly selecting a message to be derouted from said message queue if said routing controller does not identify a profitable message and if said message queue is full, and writing said derouted message to said empty output frame.
Claim 2
Dependent Claim
217 words
A message router system for routing messages from a source node to a destination node in a multinode processing system, the multinode processing system includes a multiplicity of nodes connected by channels such that a message may be routed along a profitable channel so that it is closer to its destination or derouted along a random channel so that it is further from its destination, wherein each node includes a routing subsystem having a set of input frames corresponding to the channels for receiving messages from the channels, a set of output frames corresponding to the channels for sending messages to the channels, and a fixed-size message queue for storing messages at the node, the message router system comprising at each node: (a) a routing controller for identifying an empty output frame, selecting a profitable message from the message queue such that the channel corresponding to said empty output frame is a profitable channel for said message, and, if said profitable message is available, writing said profitable message to said empty output frame; and (b) a random selector for randomly selecting a message to be derouted from said message queue if said routing controller does not identify a profitable message and if said message queue is full, and writing said derouted message to said empty output frame.
Claim 3
Dependent Claim
34 words
A message router system as claimed in claim 1, wherein said random selector selects a derouted message only if an input message is available at an input frame corresponding to said empty output frame.
Claim 4
Dependent Claim
92 words
A message router system as claimed in claim 1, wherein each node includes a main node processor and each routing subsystem includes an injection buffer and a destination buffer for communicating with said main node processor such that said main node processor reads and writes messages from said destination buffer and said injection buffer, respectively, and wherein said routing controller identifies a message destined for said node and writes said message to said destination buffer, and reads an injection message from said injection buffer and writes said injection message to said queue.
Claim 5
Dependent Claim
29 words
A message router system as claimed in claim 3, wherein said routing controller writes an injection message to said message queue only if said message queue is not full.
Claim 6
Dependent Claim
42 words
A message router system as claimed in claim 3, wherein an injection token is routed through said multinode processing system as a message, and wherein said routing controller upon receipt of said injection token writes an injection message to said message queue.
Claim 7
Dependent Claim
42 words
A message router system as claimed in claim 5, wherein said routing controller marks said injection message as a tagged message, such that when said tagged message is received at its destination the routing controller at said destination regenerates said injection token.
Claim 8
Dependent Claim
41 words
A message router system as claimed in claim 6, wherein said regenerated injection token is routed in a predetermined fashion such that each node in the multinode system receives said injection token once before any node receives said injection token twice.
Claim 9
Dependent Claim
24 words
A message router system as claimed in claim 1, wherein said multinode system is an asynchronous system and each of said nodes is self-timed.
Claim 10
Independent Claim
202 words
A method for routing messages from a source node to a destination node in a multinode processing system, the multinode processing system including a multiplicity of nodes connected by channels such that a message may be routed along a profitable channel so that it is closer to its destination or derouted along a random channel so that it is further from its destination, wherein each node includes a routing subsystem having a set of input frames corresponding to the channels for receiving messages from the channels, a set of output frames corresponding to the channels for sending messages to the channels, and a fixed-size message queue for storing messages at the node, the method comprising the steps of: (a) identifying an empty output frame, selecting a profitable message from the message queue such that the channel corresponding to said empty output frame is a profitable channel for said message, and, if said profitable message is available, writing said profitable message to said empty output frame; and (b) if a profitable message cannot be identified and if said message queue is full, randomly selecting a message to be derouted from said message queue and writing said derouted message to said empty output frame.
Claim 11
Independent Claim
202 words
A method for routing messages from a source node to a destination node in a multinode processing system, the multinode processing system including a multiplicity of nodes connected by channels such that a message may be routed along a profitable channel so that it is closer to its destination or derouted along a random channel so that it is further from its destination, wherein each node includes a routing subsystem having a set of input frames corresponding to the channels for receiving messages from the channels, a set of output frames corresponding to the channels for sending messages to the channels, and a fixed-size message queue for storing messages at the node, the method comprising the steps of: (a) identifying an empty output frame, selecting a profitable message from the message queue such that the channel corresponding to said empty output frame is a profitable channel for said message, and, if said profitable message is available, writing said profitable message to said empty output frame; and (b) if a profitable message cannot be identified and if said message queue is full, randomly selecting a message to be derouted from said message queue and writing said derouted message to said empty output frame.
References Cited (Backward Citations)
US4432996A
Cited
US4543653A
Cited
US4550398A
Cited
US4484325A
Cited
US4598400A
Cited
US4814973A
Cited
US4661947A
Cited
US4999833A
Cited
US4742511A
Cited
US4797882A
Cited
US4814980A
Cited
US4868818A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-09-29 | 1996-03-30 | 1996-09-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-09-29 | 2000-03-30 | 2000-09-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-09-29 | 2004-03-30 | 2004-09-29 | $7700.00 | Window Closed / Lapsed |