US5519694A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Construction of hierarchical networks through extension
Assignee: Massachusetts Institute of Technology
•
Filing: 1994-02-04
•
Granted: 1996-05-21
•
Expires: 2014-02-04
Abstract
Abstract A switching network incorporates expander graphs such as multibutterflies but avoids the wiring complications resulting from the randomness of such graphs. The network includes metanodes, each having plural routers. Channels of multiple interconnections are connected between the metanodes according to an upper level expander graph. Interconnections within the channels are randomly connected. Interconnections on the channels may be time multiplexed and they may be dynamically assigned to routers within a metanode.
Inventors
- 👤 Eric A. Brewer
- 👤 Frederic T. Chong
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 06:06
CPC Classifications
H; H04; H04L; H04L45/00; G; G06; G06F; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17356; G06F15/17368; G06F15/17393; H04L45/40; H04Q; H04Q3/00; H04Q3/64; H04Q3/68
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
96 words
A switching network comprising: a plurality of metanodes, each metanode comprising a plurality of routers, and a plurality of channels interconnecting the metanodes as an expander graph of successive stages, each stage of plural metanodes, with a set of channels interconnecting successive stages, each channel connecting a single metanode of one stage with a single metanode of a succeeding stage and each channel comprising plural interconnections between routers of the connected metanodes such that the switching network is a joined extension of the expander graph, the channels providing different permutations of interconnections between routers of metanodes.
Claim 2
Dependent Claim
96 words
A switching network comprising: a plurality of metanodes, each metanode comprising a plurality of routers, and a plurality of channels interconnecting the metanodes as an expander graph of successive stages, each stage of plural metanodes, with a set of channels interconnecting successive stages, each channel connecting a single metanode of one stage with a single metanode of a succeeding stage and each channel comprising plural interconnections between routers of the connected metanodes such that the switching network is a joined extension of the expander graph, the channels providing different permutations of interconnections between routers of metanodes.
Claim 3
Dependent Claim
18 words
A switching network as claimed in claim 1 wherein permutations of interconnections differ within a set of channels.
Claim 4
Dependent Claim
18 words
A switching network as claimed in claim 2 wherein permutations of interconnections differ between successive sets of channels.
Claim 5
Dependent Claim
29 words
A switching network as claimed in claim 1 wherein the number of interconnections in successive sets of channels differs such that the switching network has different degrees of extension.
Claim 6
Dependent Claim
16 words
A switching network as claimed in claim 1 wherein the permutations of interconnections are substantially random.
Claim 7
Dependent Claim
39 words
A switching network as claimed in claim 5 wherein the metanodes further comprise multiplexers which multiplex plural signals from routers to common signal paths in the channels and demultiplexers which demultiplex signals from common signal paths to plural routers.
Claim 8
Dependent Claim
23 words
A switching network as claimed in claim 1 wherein the permutations of interconnections are dynamically determined as data is transmitted through the network.
Claim 9
Dependent Claim
39 words
A switching network as claimed in claim 1 wherein the metanodes further comprise multiplexers which multiplex plural signals from routers to common signal paths in the channels and demultiplexers which demultiplex signals from common signal paths to plural routers.
Claim 10
Dependent Claim
15 words
A switching network as claimed in claim 1 wherein the expander graph comprises a multibutterfly.
Claim 11
Dependent Claim
16 words
A switching network as claimed in claim 9 wherein the permutations of interconnections are substantially random.
Claim 12
Dependent Claim
39 words
A switching network as claimed in claim 10 wherein the metanodes further comprise multiplexers which multiplex plural signals from routers to common signal paths in the channels and demultiplexers which demultiplex signals from common signal paths to plural routers.
Claim 13
Dependent Claim
17 words
A switching network as claimed in claim 9 wherein the routers within output metanodes form expander graphs.
Claim 14
Dependent Claim
18 words
A switching network as claimed in claim 12 wherein the routers of the output metanodes form multibutterfly networks.
Claim 15
Dependent Claim
23 words
A switching network as claimed in claim 9 wherein the permutations of interconnections are dynamically determined as data is transmitted through the network.
Claim 16
Dependent Claim
39 words
A switching network as claimed in claim 14 wherein the metanodes further comprise multiplexers which multiplex plural signals from routers to common signal paths in the channels and demultiplexers which demultiplex signals from common signal paths to plural routers.
Claim 17
Dependent Claim
16 words
A switching network as claimed in claim 1 wherein routers of output metanodes form expander graphs.
Claim 18
Dependent Claim
47 words
A switching network as claimed in claim 1 having a two-level hierarchical extension, the channels comprising subchannels, with plural permutations of the subchannels between sets of routers within metanodes, and interconnections within the subchannels which provide plural permutations of interconnections between routers of the sets of routers.
Claim 19
Dependent Claim
96 words
A switching network comprising: a plurality of metanodes, each metanode comprising a plurality of routers, and a plurality of channels interconnecting the metanodes as a multipath graph of successive stages, each stage of plural metanodes, with a set of channels interconnecting successive stages, each channel connecting a single metanode of one stage with a single metanode of a succeeding stage and each channel comprising plural interconnections between routers of the connected metanodes such that the switching network is a joined extension of the multipath graph, the channels providing different permutations of interconnections between routers of metanodes.
Claim 20
Dependent Claim
96 words
A switching network comprising: a plurality of metanodes, each metanode comprising a plurality of routers, and a plurality of channels interconnecting the metanodes as a multipath graph of successive stages, each stage of plural metanodes, with a set of channels interconnecting successive stages, each channel connecting a single metanode of one stage with a single metanode of a succeeding stage and each channel comprising plural interconnections between routers of the connected metanodes such that the switching network is a joined extension of the multipath graph, the channels providing different permutations of interconnections between routers of metanodes.
Claim 21
Dependent Claim
29 words
A switching network as claimed in claim 18 wherein the number of interconnections in successive sets of channels differs such that the switching network has different degrees of extension.
Claim 22
Dependent Claim
16 words
A switching network as claimed in claim 18 wherein the permutations of interconnections are substantially random.
Claim 23
Dependent Claim
39 words
A switching network as claimed in claim 20 wherein the metanodes further comprise multiplexers which multiplex plural signals from routers to common signal paths in the channels and demultiplexers which demultiplex signals from common signal paths to plural routers.
Claim 24
Dependent Claim
23 words
A switching network as claimed in claim 18 wherein the permutations of interconnections are dynamically determined as data is transmitted through the network.
Claim 25
Dependent Claim
39 words
A switching network as claimed in claim 22 wherein the metanodes further comprise multiplexers which multiplex plural signals from routers to common signal paths in the channels and demultiplexers which demultiplex signals from common signal paths to plural routers.
Claim 26
Dependent Claim
39 words
A switching network as claimed in claim 18 wherein the metanodes further comprise multiplexers which multiplex plural signals from routers to common signal paths in the channels and demultiplexers which demultiplex signals from common signal paths to plural routers.
Claim 27
Dependent Claim
47 words
A switching network as claimed in claim 18 having a two-level hierarchical extension, the channels comprising subchannels, with plural permutations of the subchannels between sets of routers within metanodes, and interconnections within the subchannels which provide plural permutations of interconnections between routers of the sets of routers.
References Cited (Backward Citations)
US4905224A
Cited
US5105424A
Cited
US5125076A
Cited
US5032837A
Cited
US5175539A
Cited
US5103220A
Cited
US5088091A
Cited
US5224100A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-05-21 | 1999-11-20 | 2000-05-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-05-21 | 2003-11-20 | 2004-05-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-05-21 | 2007-11-20 | 2008-05-21 | $7700.00 | Window Closed / Lapsed |