Construction of hierarchical networks through extension

• US 5,519,694 A
• Filed: 02/04/1994
• Issued: 05/21/1996
• Est. Priority Date: 02/04/1994
• Status: Expired due to Fees

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Brewer, Eric A., Chong, Frederic T.
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US08/193,421
• Time in Patent Office: 837 Days
• Field of Search: 370/54, 370/55, 370/56, 370/58.1, 370/58.2, 370/58.3, 370/60, 370/61, 370/85.13, 370/94.1, 370/94.3, 379/219, 379/220, 379/221, 379/268, 379/269, 379/271, 379/272, 379/273, 340/825.02, 340/825.03, 340/826, 340/827, 340/825.79, 340/825.8, 395/200, 395/325
• US Class Current: 370/351
• CPC Class Codes: G06F 15/17393 having multistage networks, e.g. broadcasting scattering, gathering, hot spot contention, combining/decombining
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/40 Wormhole routing
• CPC Class Codes: H04Q 3/68 Grouping or interlacing selector groups or stages

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.

Claims

1. 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.

2. A switching network as claimed in claim 1 wherein permutations of interconnections differ within a set of channels.

3. A switching network as claimed in claim 2 wherein permutations of interconnections differ between successive sets of channels.

4. 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.

5. A switching network as claimed in claim 1 wherein the permutations of interconnections are substantially random.

6. 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.

7. A switching network as claimed in claim 1 wherein the permutations of interconnections are dynamically determined as data is transmitted through the network.

8. 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.

9. A switching network as claimed in claim 1 wherein the expander graph comprises a multibutterfly.

10. A switching network as claimed in claim 9 wherein the permutations of interconnections are substantially random.

11. 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.

12. A switching network as claimed in claim 9 wherein the routers within output metanodes form expander graphs.

13. A switching network as claimed in claim 12 wherein the routers of the output metanodes form multibutterfly networks.

14. A switching network as claimed in claim 9 wherein the permutations of interconnections are dynamically determined as data is transmitted through the network.

15. 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.

16. A switching network as claimed in claim 1 wherein routers of output metanodes form expander graphs.

17. 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.

18. 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.

19. 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.

20. A switching network as claimed in claim 18 wherein the permutations of interconnections are substantially random.

21. 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.

22. A switching network as claimed in claim 18 wherein the permutations of interconnections are dynamically determined as data is transmitted through the network.

23. 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.

24. 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.

25. 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.