Flexible radix switch
A system and method for interconnecting nodes and routing data packets in high radix networks includes constructing or redefining a network structure to provide improved performance. Computation and data storage nodes are connected to a network of switching nodes that provide near optimum bandwidth and latency for networks of any size. Specialized interconnection patterns and addressing methods ensure reliable data delivery in very large networks with high data traffic volume.
1. A method of constructing a network for the transfer of data from a source device to a destination device the method comprising:
selecting a base symmetric network structure, wherein the topology of the base symmetric network structure substantially corresponds to a Cayley graph;
defining at least one of:
a number of source and destination devices to be connected to the network,
a number switches to be used in the network,
a number of ports per switch, and
an oversubscription characteristic of the network;
determining a generator matrix as a function of at least one of:
the number of source and destination devices to be connected to the network,
the number switches to be used in the network,
the number of ports per switch, and
the oversubscription characteristic of the network;
determining a wiring pattern for interconnecting each of the switches as a function of the generator matrix; and
interconnecting the switches of the network with interconnecting wires according to the wiring pattern.
2. The method according to claim 1 wherein the base network structure substantially corresponds to a hypercube having a dimension d.
3. The method according to claim 2 wherein the generator matrix is determined as a function of the number of interconnections between switches of the network and the dimension, d, of the hypercube.
4. The method according to claim 1 wherein the generator matrix is an error correcting code (ECC) generating matrix and the wiring pattern is determined by rotating the error correcting code generating matrix.
5. The method according to claim 4 , wherein the error correcting code generating matrix is rotated counterclockwise.
6. The method according to claim 1 wherein the oversubscription characteristic of the network is determined as a function of a number of ports defined for connection to source computers and destination computers and a bisection of the network.
7. The method according to claim 6 wherein the bisection is determined as a function of a Walsh function.
8. The method according to claim 7 wherein the bisection is determined by constructing primary equipartitions defined by patterns of 1's and 0s in a Walsh function.
9. The method according to claim 7 wherein the bisection is determined by constructing primary equipartitions defined by the sign pattern in an algebraic Walsh function.
10. The method according to claim 1 wherein the generator matrix is an error correcting code (ECC) generating matrix derived from digital (t,m,s) nets parameters and the wiring pattern is determined by rotating the error correcting code generating matrix.
11. The method according to claim 4 wherein ECC distance metrics are constructed using a Lee distance.
12. The method according to claim 4 wherein ECC distance metrics are constructed using a Hamming distance.
13. A network constructed according to the method of claim 1 .
14. A network constructed by connecting a plurality of switched, the network comprising
a defined number of switches, each switch being connected to at least one other switch by an internal switch connection and the network including a defined number of internal switch connections;
the switched being arranged in a symmetric network structure, wherein the topology of the base symmetric network structure substantially corresponds to a Cayley graph;
the switches being interconnected according to a wiring pattern, the wiring pattern being determined as a function of a generator matrix, wherein the generator matrix is determined as a function of the number of internal switch connections.
15. A network according to claim 14 wherein the base network structure substantially corresponds to a hypercube having a dimension d.
16. A network according to claim 14 wherein the generator matrix is determined as a function of the number of internal switch connections and the dimension, d, of the hypercube.
17. A network according to claim 14 wherein the generator matrix is an error correcting code generating matrix and the wiring pattern is determined by rotating the error correcting code generating matrix.
18. A network according to claim 17 , wherein the error correcting code generating matrix is rotated counterclockwise.
19. A network according to claim 14 , wherein the generator matrix is determined as a function of at least one of:
a number of source and destination devices to be connected to the network,
the number switches used in the network,
a number of ports per switch, and
an oversubscription characteristic of the network.
20. A network according to claim 19 wherein the oversubscription characteristic of the network is determined as a function of the number of ports defined for connection to source and destination devices and a bisection of the network.