US5243704A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Optimized interconnect networks
Assignee: Ascend Communications Inc
•
Filing: 1992-05-08
•
Granted: 1993-09-07
•
Expires: 2012-05-08
Abstract
Abstract A multinodal system is one-way interconnected, two-way interconnected or, more generally, (n)-way interconnected, where (n) is an integer. In a one-way interconnected system, only one connection element couples any two nodes. Or, put another way, only one communication path exists between every node and every other node. A two-way interconnected system, on the other hand, has two connection elements coupling each pair of nodes. Likewise, an (n)-way interconnected system provides (n) independent connection paths between each pair. Such systems are characteristic in that the relationship between the number of independent buses (b), the number of nodes (v), the number of ports (r), and the degree of interconnectedness (n) can be expressed by the equation ##EQU1## Two-way and (n)-way interconnect arrays may be adapted for use in fault-tolerant communications.
Inventors
- 👤 Kurt F. Baty
- 👤 Charles J. Horvath, Jr.
- 👤 Richard C. Clemson
- 👤 Scott J. Bleiweiss
- 👤 Kenneth T. Wolff
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 12:07
CPC Classifications
G; G06; G06F; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17337; G06F15/17343
Claims Analysis
Total Claims: 47
Claim 1
Independent Claim
217 words
In a digital data processing system having (v) nodes, where (v) is an integer greater than or equal to four, each including at least one of central processing means for processing information-representative signals, memory means for storing and/or retrieving information-representative signals, and peripheral controller means for controlling communications with a peripheral device, the improvement for efficiently coupling said nodes for communication with one another via a plurality of independent bus means, comprising A. (b) bus means, each being associated with and coupled to three or more of said nodes for communicating information-representative signals therebetween, independently of communications on each other bus means, said (b) bus means being configured so that i) each node is connected with each respective other node by at least (n) said bus means, ii) no single node is connected to all other nodes by a single bus means, and iii) at least one of said (b) bus means is connected to at least three or more of said nodes, B. each said node having (r) port means, each connected with that node and with one of associated bus means for providing a coupling interface therebetween, and C. where (n) and (r) are positive integers selected such that the mathematical relation ##EQU6## provides a positive integer (b), defining the number of said bus means.
Claim 2
Dependent Claim
217 words
In a digital data processing system having (v) nodes, where (v) is an integer greater than or equal to four, each including at least one of central processing means for processing information-representative signals, memory means for storing and/or retrieving information-representative signals, and peripheral controller means for controlling communications with a peripheral device, the improvement for efficiently coupling said nodes for communication with one another via a plurality of independent bus means, comprising A. (b) bus means, each being associated with and coupled to three or more of said nodes for communicating information-representative signals therebetween, independently of communications on each other bus means, said (b) bus means being configured so that i) each node is connected with each respective other node by at least (n) said bus means, ii) no single node is connected to all other nodes by a single bus means, and iii) at least one of said (b) bus means is connected to at least three or more of said nodes, B. each said node having (r) port means, each connected with that node and with one of associated bus means for providing a coupling interface therebetween, and C. where (n) and (r) are positive integers selected such that the mathematical relation ##EQU6## provides a positive integer (b), defining the number of said bus means.
Claim 3
Dependent Claim
33 words
In a digital data processing system according to claim 1, the further improvement wherein said (b) bus means connected with said port means in a configuration derived from an incomplete balanced block design.
Claim 4
Dependent Claim
45 words
In a digital data processing system according to claim 1, wherein a communication characteristic of information-representative signals on each of said (b) bus means is a function of the length thereof, the further improvement wherein said (b) bus means are of substantially the same length.
Claim 5
Dependent Claim
19 words
In a digital data processing system according to claim 1, the further improvement wherein (n) is equal to one.
Claim 6
Dependent Claim
29 words
In a digital data processing system according to claim 4, the further improvement wherein each of said bus means is connected with the same number of said port means.
Claim 7
Dependent Claim
19 words
In a digital data processing system according to claim 1, the further improvement wherein (n) is equal to two.
Claim 8
Dependent Claim
36 words
In a digital data processing system according to claim 6, the further improvement wherein at least one said bus means is connected with a different number of said port means than another of said bus means.
Claim 9
Dependent Claim
37 words
In a digital data processing system according to claim 6, the further improvement wherein said (b) bus means are configured so that each node is connected to each other node by at least two said bus means.
Claim 10
Dependent Claim
28 words
In a digital data processing system according to claim 8, the further improvement wherein each said node is connected to each other node by exactly two bus means.
Claim 11
Dependent Claim
24 words
In a digital data processing system according to claim 6, the further improvement wherein said (b) bus means are of substantially the same length.
Claim 12
Dependent Claim
226 words
In a digital data processing system having (v) nodes, where (v) is an integer greater than or equal to four, each including at least one of central processing means for processing information-representative signals, memory means for storing and/or retrieving information-representative signals, and peripheral controller means for controlling communications with a peripheral device, the improvement for efficiently coupling said nodes for communication with one another via a plurality of independent bus means, comprising A. (b) bus means, each being associated with and coupled to three or more of said nodes for communicating information-representative signals therebetween, independently of communications on each other bus means, said (b) bus means being configured so that i) each node is connected with each respective other node by at least (n) said bus means, ii) no single node is connected to all other nodes by a single bus means, and iii) at least one of said (b) bus means is connected to at least three or more of said nodes, B. each said node having (r) port means, each connected with that node and with one of associated bus means for providing a coupling interface therebetween, and C. where (r) is a positive integer, wherein (n) is equal to one, and wherein (r) is selected such that the mathematical relation b=r×(r-1))+1 provides a positive integer (b), defining the number of said bus means.
Claim 13
Dependent Claim
226 words
In a digital data processing system having (v) nodes, where (v) is an integer greater than or equal to four, each including at least one of central processing means for processing information-representative signals, memory means for storing and/or retrieving information-representative signals, and peripheral controller means for controlling communications with a peripheral device, the improvement for efficiently coupling said nodes for communication with one another via a plurality of independent bus means, comprising A. (b) bus means, each being associated with and coupled to three or more of said nodes for communicating information-representative signals therebetween, independently of communications on each other bus means, said (b) bus means being configured so that i) each node is connected with each respective other node by at least (n) said bus means, ii) no single node is connected to all other nodes by a single bus means, and iii) at least one of said (b) bus means is connected to at least three or more of said nodes, B. each said node having (r) port means, each connected with that node and with one of associated bus means for providing a coupling interface therebetween, and C. where (r) is a positive integer, wherein (n) is equal to one, and wherein (r) is selected such that the mathematical relation b=r×(r-1))+1 provides a positive integer (b), defining the number of said bus means.
Claim 14
Dependent Claim
28 words
In a digital data processing system according to claim 11, the further improvement wherein each said bus means is connected with the same number of said port means.
Claim 15
Dependent Claim
35 words
In a digital data processing system according to claim 11, the further improvement wherein said (b) bus means are connected with said port means in a configuration derived from a symmetric incomplete balanced block design.
Claim 16
Dependent Claim
228 words
In a digital data processing system having (v) nodes, where (v) is an integer greater than or equal to four, each including at least one of central processing means for processing information-representative signals, memory means for storing and/or retrieving information-representative signals, and peripheral controller means for controlling communications with a peripheral device, the improvement for efficiently coupling said nodes for communication with one another via a plurality of independent bus means, comprising A. (b) bus means, each being associated with and coupled to three or more of said nodes for communicating information-representative signals therebetween, independently of communications on each other bus means, said (b) bus means being configured so that i) each node is connected with each respective other node by at least (n) said bus means, ii) no single node is connected to all other nodes by a single bus means, and iii) at least one of said (b) bus means is connected to at least three or more of said nodes, B. each said node having (r) port means, each connected with that node and with one of associated bus means for providing a coupling interface therebetween, and C. where (r) is a positive integer, wherein (n) is equal to two, and wherein (n) and (r) are selected such that the mathematical relation b=(r×(r-1)/2)+1 provides a positive integer (b), defining the number of said bus means.
Claim 17
Dependent Claim
228 words
In a digital data processing system having (v) nodes, where (v) is an integer greater than or equal to four, each including at least one of central processing means for processing information-representative signals, memory means for storing and/or retrieving information-representative signals, and peripheral controller means for controlling communications with a peripheral device, the improvement for efficiently coupling said nodes for communication with one another via a plurality of independent bus means, comprising A. (b) bus means, each being associated with and coupled to three or more of said nodes for communicating information-representative signals therebetween, independently of communications on each other bus means, said (b) bus means being configured so that i) each node is connected with each respective other node by at least (n) said bus means, ii) no single node is connected to all other nodes by a single bus means, and iii) at least one of said (b) bus means is connected to at least three or more of said nodes, B. each said node having (r) port means, each connected with that node and with one of associated bus means for providing a coupling interface therebetween, and C. where (r) is a positive integer, wherein (n) is equal to two, and wherein (n) and (r) are selected such that the mathematical relation b=(r×(r-1)/2)+1 provides a positive integer (b), defining the number of said bus means.
Claim 18
Dependent Claim
36 words
In a digital data processing system according to claim 14, the further improvement wherein at least one said bus means is connected with a different number of said port means than another of said bus means.
Claim 19
Dependent Claim
37 words
In a digital data processing system according to claim 14, the further improvement wherein said (b) bus means are configured so that each node is connected to each other node by at least two said bus means.
Claim 20
Dependent Claim
51 words
In a digital data processing system according to claim 16, the further improvement wherein respective ports of at least two said nodes are coupled to one another and to said bus means so as to receive information-representative signals on said bus means from others of said nodes identically with each other.
Claim 21
Dependent Claim
28 words
In a digital data processing system according to claim 14, the further improvement wherein each said node is connected to each other node by exactly two bus means.
Claim 22
Dependent Claim
35 words
In a digital data processing system according to claim 14, the further improvement wherein said (b) bus means are connected with said port means in a configuration derived from a symmetric incomplete balanced block design.
Claim 23
Dependent Claim
193 words
In a multinodal system having (v) nodes, where (v) is an integer greater than or equal to four, each for performing a selected operation, the improvement for efficiently coupling said nodes for communication with one another via a plurality of independent connection means, comprising: A. (b) connection means, each being associated with and coupled to three or more of said nodes for placing them in communication, independently of communication on each other connection means, said (b) connection means being configured so that i) each node is connected for communication with each other node by at least (n) said connection means, ii) no single node is connected for communication to all other nodes by a single connection means, and iii) at least one of said (b) connection means is connected to at least three or more of said nodes, B. each said node having (r) port means, each connected with that node and with one of its associated connection means for providing a coupling interface therebetween, and C. where (n) and (r) are positive integers selected such that the mathematical relation ##EQU7## provides a positive integer (b), defining the number of said bus means.
Claim 24
Dependent Claim
193 words
In a multinodal system having (v) nodes, where (v) is an integer greater than or equal to four, each for performing a selected operation, the improvement for efficiently coupling said nodes for communication with one another via a plurality of independent connection means, comprising: A. (b) connection means, each being associated with and coupled to three or more of said nodes for placing them in communication, independently of communication on each other connection means, said (b) connection means being configured so that i) each node is connected for communication with each other node by at least (n) said connection means, ii) no single node is connected for communication to all other nodes by a single connection means, and iii) at least one of said (b) connection means is connected to at least three or more of said nodes, B. each said node having (r) port means, each connected with that node and with one of its associated connection means for providing a coupling interface therebetween, and C. where (n) and (r) are positive integers selected such that the mathematical relation ##EQU7## provides a positive integer (b), defining the number of said bus means.
Claim 25
Dependent Claim
28 words
A multinodal system according to claim 20, wherein said (b) connection means are connected with said port means in a configuration derived from an incomplete balanced block design.
Claim 26
Dependent Claim
24 words
A multinodal system according to claim 21, the further improvement wherein (n) is equal to two and wherein (b) is numerically equal to (r×(r-1)/2)+1.
Claim 27
Dependent Claim
27 words
A multinodal system according to claim 22, the further improvement wherein each said connection means is connected for communication with the same number of said port means.
Claim 28
Dependent Claim
36 words
A multinodal system according to claim 22, the further improvement wherein said (b) connection means are configured so that each node is connected for communication to each other node by at least two said connection means.
Claim 29
Dependent Claim
27 words
A multinodal system according to claim 24, the further improvement wherein each said node is connected for communication to each other node by exactly two connection means.
Claim 30
Dependent Claim
32 words
A multinodal system according to claim 22, the further improvement wherein said (b) connection means are connected with said port means in a configuration derived from a symmetric incomplete balanced block design.
Claim 31
Dependent Claim
13 words
A multinodal system according to claim 20, wherein (n) is equal to one.
Claim 32
Dependent Claim
30 words
A multinodal system according to claim 27, wherein at least one said connection means is connected with a different number of said port means than another of said connection means.
Claim 33
Dependent Claim
13 words
A multinodal system according to claim 20, wherein (n) is equal to two.
Claim 34
Dependent Claim
22 words
A multinodal system according to claim 29, wherein each said connection means is connected with the same number of said port means.
Claim 35
Dependent Claim
31 words
A multinodal system according to claim 29, wherein said (b) connection means are configured so that each node is connected to each other node by at least two said connection means.
Claim 36
Dependent Claim
47 words
A multinodal system according to claim 31, the further improvement wherein respective ports of at least two said nodes are coupled to one another and to said connection means so as to receive communications on said connection means from others of said nodes identically with each other.
Claim 37
Dependent Claim
22 words
A multinodal system according to claim 29, wherein each said node is connected to each other node by exactly two connection means.
Claim 38
Dependent Claim
38 words
A multinodal system according to claim 20, wherein a communication characteristic of each of said (b) connection means is a function of the length thereof, the improvement wherein said (b) connection means are of substantially the same length.
Claim 39
Dependent Claim
204 words
In a multinodal system having (v) nodes, where (v) is an integer greater than or equal to four, each for performing a selected operation, the improvement for efficiently coupling said nodes for communication with one another via a plurality of independent connection means, comprising: A. (b) connection means, each being associated with and coupled to three or more of said nodes for placing them in communication, independently of communication on each other connection means, said (b) connection means being configured so that i) each node is connected for communication with each other node by at least (n) said connection means, ii) no single node is connected for communication to all other nodes by a single connection means, and iii) at least one of said (b) connection means is connected to at least three or more of said nodes, B. each said node having (r) port means, each connected with that node and with one of its associated connection means for providing a coupling interface therebetween, and C. where (r) is a positive integer, wherein (n) is equal to one, and wherein (n) and (r) are selected such that the mathematical relation b=r×(r-1))+1 provides a positive integer (b), defining the number of said bus means.
Claim 40
Dependent Claim
204 words
In a multinodal system having (v) nodes, where (v) is an integer greater than or equal to four, each for performing a selected operation, the improvement for efficiently coupling said nodes for communication with one another via a plurality of independent connection means, comprising: A. (b) connection means, each being associated with and coupled to three or more of said nodes for placing them in communication, independently of communication on each other connection means, said (b) connection means being configured so that i) each node is connected for communication with each other node by at least (n) said connection means, ii) no single node is connected for communication to all other nodes by a single connection means, and iii) at least one of said (b) connection means is connected to at least three or more of said nodes, B. each said node having (r) port means, each connected with that node and with one of its associated connection means for providing a coupling interface therebetween, and C. where (r) is a positive integer, wherein (n) is equal to one, and wherein (n) and (r) are selected such that the mathematical relation b=r×(r-1))+1 provides a positive integer (b), defining the number of said bus means.
Claim 41
Dependent Claim
34 words
A multinodal system according to claim 35, the further improvement wherein at least one said connection means is connected for communication with a different number of said port means than another said connection means.
Claim 42
Dependent Claim
29 words
A multinodal system according to claim 35, the further improvement wherein said (b) connection means are connected with in a configuration derived from a symmetric incomplete balanced block design.
Claim 43
Dependent Claim
50 words
A multinodal system according to any of claims 20 or 35, the further improvement wherein A. each of said (b) connection means has physical characteristics affecting communication thereon, B. said (b) connection means are configured with respect to said physical characteristics so as to optimize communications on said connection means.
Claim 44
Dependent Claim
204 words
In a digital data processing system having (v) nodes, where (v) is an integer greater than or equal to four, each including at least one of central processing means for processing information-representative signals, memory means for storing and/or retrieving information-representative signals, and peripheral controller means for controlling communications with a peripheral device, the improvement comprising sparse-connect means for coupling said nodes for communication with one another, said sparse-connect means consisting essentially of A. (b) bus means, each being associated with and coupled to three or more of said nodes for communicating information-representative signals therebetween, independently of communications on each other bus means, said (b) bus means being configured so that i) each node is connected with each respective other node by (n) bus means, ii) no single node is connected to all other nodes by a single bus means, and iii) at least one of said (b) bus means is connected to at least three or more of said nodes, B. each said node having (r) port means, each connected with that node and with one of associated bus means for providing a coupling interface therebetween, and C. where (b), (n) and (r) are positive integers, and where (b) is numerically equal to ##EQU8##
Claim 45
Dependent Claim
204 words
In a digital data processing system having (v) nodes, where (v) is an integer greater than or equal to four, each including at least one of central processing means for processing information-representative signals, memory means for storing and/or retrieving information-representative signals, and peripheral controller means for controlling communications with a peripheral device, the improvement comprising sparse-connect means for coupling said nodes for communication with one another, said sparse-connect means consisting essentially of A. (b) bus means, each being associated with and coupled to three or more of said nodes for communicating information-representative signals therebetween, independently of communications on each other bus means, said (b) bus means being configured so that i) each node is connected with each respective other node by (n) bus means, ii) no single node is connected to all other nodes by a single bus means, and iii) at least one of said (b) bus means is connected to at least three or more of said nodes, B. each said node having (r) port means, each connected with that node and with one of associated bus means for providing a coupling interface therebetween, and C. where (b), (n) and (r) are positive integers, and where (b) is numerically equal to ##EQU8##
Claim 46
Dependent Claim
203 words
In a digital data processing system having (v) nodes, where (v) is an integer greater than or equal to four, each including at least one of central processing means for processing information-representative signals, memory means for storing and/or retrieving information-representative signals, and peripheral controller means for controlling communications with a peripheral device, the improvement comprising sparse-connect means for coupling said nodes for communication with one another, said sparse-connect means consisting of A. (b) bus means, each being associated with and coupled to three or more of said nodes for communicating information-representative signals therebetween, independently of communications on each other bus means, said (b) bus means being configured so that i) each node is connected with each respective other node by (n) bus means, ii) no single node is connected to all other nodes by a single bus means, and iii) at least one of said (b) bus means is connected to at least three or more of said nodes, B. each said node having (r) port means, each connected with that node and with one of associated bus means for providing a coupling interface therebetween, and C. where (b), (n) and (r) are positive integers, and where (b) is numerically equal to ##EQU9##
Claim 47
Dependent Claim
203 words
In a digital data processing system having (v) nodes, where (v) is an integer greater than or equal to four, each including at least one of central processing means for processing information-representative signals, memory means for storing and/or retrieving information-representative signals, and peripheral controller means for controlling communications with a peripheral device, the improvement comprising sparse-connect means for coupling said nodes for communication with one another, said sparse-connect means consisting of A. (b) bus means, each being associated with and coupled to three or more of said nodes for communicating information-representative signals therebetween, independently of communications on each other bus means, said (b) bus means being configured so that i) each node is connected with each respective other node by (n) bus means, ii) no single node is connected to all other nodes by a single bus means, and iii) at least one of said (b) bus means is connected to at least three or more of said nodes, B. each said node having (r) port means, each connected with that node and with one of associated bus means for providing a coupling interface therebetween, and C. where (b), (n) and (r) are positive integers, and where (b) is numerically equal to ##EQU9##
References Cited (Backward Citations)
US3641505A
Cited
US4112488A
Cited
US4032893A
Cited
GB2064839A
Cited
US4434463A
Cited
US4630193A
Cited
US4805091A
Cited
EP0301499A2
Cited
US4942517A
Cited
US4985830A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-09-06 | 1997-03-08 | 1997-09-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-09-06 | 2001-03-08 | 2001-09-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-09-06 | 2005-03-08 | 2005-09-07 | $7700.00 | Window Closed / Lapsed |