Switching networks with expansive and/or dispersive logical clusters for message routing
AssigneeMassachusetts Institute of Technology
InventorsSanjeev Arora, Thomas F. Knight, Jr., Frank T. Leighton, Bruce M. Maggs, Eliezer Upfal
Life of this patent
Estimating the term…
Abstract
A class of switching networks is comprised of expansive logical clusters and/or dispersive logical clusters. These clusters are of low degree. The class of networks include multibutterfly networks as well as multi-Benes networks. These networks provide for fault tolerance and routing and for efficient routing. Moreover, routing is provided in a non-blocking fashion.
Claims19
A switching network for routing messages comprising at least one logical cluster which comprises:
- a) a first set of switches having N input switches for receiving messages and a second set of switches having approximately N output switches for outputting messages wherein the second set of switches is divided into at least two unique groups of switches;
- and
- b) connectors for connecting the first set of switches to the second set of switches wherein for every subset of input switches of size k of the first set of switches, there are at least x output switches in each group of the second set of switches that are connected to precisely one of the input switches of the subset of size k input switches, where k.ltoreq..alpha.N, x.ltoreq..delta..alpha.N, where k, x, and N are positive integers, N is equal to at least 8, where any particular subset includes any k of the N input switches, and where .delta. and .alpha. are positive constants less than one, such that the logical cluster exhibits a dispersion property.
A switching network for routing messages comprising at least one logical cluster which comprises:
- a) at least an input set of switches for receiving messages and at least one set of switches after the input set of switches, including an output set of switches for outputting messages, the output set of switches being divided into at least two unique groups of switches, each switch in the input set of switches and in the at least one set of switches after the input set of switches making local routing decisions;
- and
- b) connectors for connecting the sets of switches wherein there exists for every subset of switches of size k in the input set of switches at least .beta.k switches in each of said at least two unique groups of the output set of switches that can receive signals from the subset of k switches in the input set of switches, where .beta.>1, where k is a positive integer, and k<.alpha.N for N equal to the total number of switches in the input set of switches, N being equal to at least 8, and for 2.alpha.<1, such that the logical cluster exhibits an expansion property.
A switching network for routing messages comprising at least one logical cluster which comprises:
- an input set of switches equal in number to at least 8, having inputs for receiving messages and at least one set of switches after the input set of switches, including an output set of switches having outputs for outputting messages, wherein the output set of switches comprises at least two unique group of switches, each switch in the set of switches and in the at least one set of switches after the input set of switches making local routing decisions;
- and
- connectors for connecting switches in the logical cluster wherein for small subsets of size k of the input set of switches, there are more than k switches in each of said at least two unique groups of the output set of switches connected to the subsets of size k such that the logical cluster exhibits an expansion property.
Dependencies are inferred from the claim text.