Method and apparatus for creating a robust highly connected direct interconnection network

1. A method for creating an interconnection network, comprising:

associating an n-bit binary identifier with each node in the interconnection network;

grouping the n bits of each binary identifier into h overlapping sets a 1 , a 2 , . . . a h , wherein the sets a 1 , a 2 , . . . a h cover all of the n bits; and

for each set a i , forming fully connected clusters of nodes by creating a direct point-to-point link between any two nodes that have binary identifiers that differ in bits of the set a i but are the same in other bit positions;

wherein for each set a i , forming fully connected clusters involves generating 2 n−∥a i ∥ fully connected clusters of 2 ∥a i ∥ nodes, wherein ∥a i ∥ is the number of bits in the set a i ; and

wherein the symbols “n”, and “h” represent non-negative integer values.

2. The method of claim 1 , wherein each of the sets a 1 , a 2 , . . . a h includes the same number of bits.

3. The method of claim 2 , wherein each set a i includes at least one unique bit that does not belong to another set.

4. The method of claim 1 , further comprising determining a minimal path between a first node and a second node by:

identifying a minimal subset of the sets a 1 , a 2 , . . . a h which includes all of the bits that are different between the binary identifier for the first node and the binary identifier for the second node; and

for each set a i in the minimal subset, selecting a link from the fully connected cluster associated with a i , such that the selected links form a minimal path between the first node and the second node.

5. The method of claim 4 , wherein if one or more failures make it impossible to form a minimal path between the first node and the second node, the method further comprises generating a non-minimal path between the first node and the second node, if possible, wherein the non-minimal path includes more than the minimal number of links (in the absence of failures) between the first node and the second node.

6. The method of claim 1 , wherein each node in the interconnection network has degree

D

=

∑

i

=

1

h

⁢

⁢

(

2



a

i



-

1

)

,

wherein ∥a i ∥ is the number of bits in the set a i , and wherein the symbol “D” represents a non-negative integer value that denotes the total number of links to a node.

7. The method of claim 1 , wherein the total number of links in the interconnection network is

N

2

⁢

∑

i

=

1

h

⁢

⁢

(

2



a

i



-

1

)

,

wherein ∥a i ∥ is the number of bits in the set a i , and wherein the symbol “N” represents a non-negative integer value that denotes the total number of links in the interconnection network.

8. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for creating an interconnection network, the method comprising:

associating an n-bit binary identifier with each node in the interconnection network;

grouping the n bits of each binary identifier into h overlapping sets a 1 , a 2 , . . . a h , wherein the sets a 1 , a 2 , . . . a h cover all of the n bits; and

for each set a i , forming fully connected clusters of nodes by creating a direct point-to-point link between any two nodes that have binary identifiers that differ in bits of the set a i but are the same in other bit positions;

wherein for each set a i , forming fully connected clusters involves generating 2 n−∥a i ∥ fully connected clusters of 2 ∥a i ∥ nodes wherein ∥a i ∥ is the number of bits in the set a i ; and

wherein the symbols “n”, and “h” represent non-negative integer values.

9. The computer-readable storage medium of claim 8 , wherein each of the sets a 1 , a 2 , . . . a h includes the same number of bits.

10. The computer-readable storage medium of claim 9 , wherein each set a i includes at least one unique bit that does not belong to another set.

11. The computer-readable storage medium of claim 8 , wherein the method further comprises determining a minimal path between a first node and a second node by:

identifying a minimal subset of the sets a 1 , a 2 , . . . a h which includes all of the bits that are different between the binary identifier for the first node and the binary identifier for the second node; and

for each set a i in the minimal subset, selecting a link from the fully connected cluster associated with a i , such that the selected links form a minimal path between the first node and the second node.

12. The computer-readable storage medium of claim 11 , wherein if one or more failures make it impossible to form a minimal path between the first node and the second node, the method further comprises generating a non-minimal path between the first node and the second node, if possible, wherein the non-minimal path includes more than the minimal number of links (in the absence of failures) between the first node and the second node.

13. The computer-readable storage medium of claim 8 , wherein each node in the interconnection network has degree

D

=

∑

i

=

1

h

⁢

⁢

(

2



a

i



-

1

)

,

wherein ∥a i ∥ is the number of bits in the set a i , and wherein the symbol “D” represents a non-negative integer value that denotes the total number of links to a node.

14. The computer-readable storage medium of claim 8 , wherein the total number of links in the interconnection network is

N

2

⁢

∑

i

=

1

h

⁢

⁢

(

2



a

i



-

1

)

,

wherein ∥a i ∥ is the number of bits in the set a i , and wherein the symbol “N” represents a non-negative integer value that denotes the total number of links in the interconnection network.

15. An apparatus that creates an interconnection network, comprising:

an association mechanism configured to associate an n-bit binary identifier with each node in the interconnection network;

a grouping mechanism configured to group the n bits of each binary identifier into h overlapping sets a 1 , a 2 , . . . a h , wherein the sets a 1 , a 2 , . . . a h cover all of the n bits; and

a connecting mechanism, wherein for each set a i , the connecting mechanism is configured to form fully connected clusters of nodes by creating a direct point-to-point link between any two nodes that have binary identifiers that differ in bits of the set a i but are the same in other bit positions;

wherein for each set a i , forming fully connected clusters involves generating 2 n−∥a i ∥ fully connected clusters of 2 ∥a i ∥ nodes, wherein ∥a i ∥ is the number of bits in the set a i ; and

wherein the symbols “n”, and “h” represent non-negative integer values.

16. The apparatus of claim 15 , wherein each of the sets a 1 , a 2 , . . . a h includes the same number of bits.

17. The apparatus of claim 16 , wherein each set a i includes at least one unique bit that does not belong to another set.

18. The apparatus of claim 15 , further comprising path generator configured to determine a minimal path between a first node and a second node by:

identifying a minimal subset of the sets a 1 , a 2 , . . . a h which includes all of the bits that are different between the binary identifier for the first node and the binary identifier for the second node; and

for each set a i in the minimal subset, selecting a link from the fully connected cluster associated with a i , such that the selected links form a minimal path between the first node and the second node.

19. The apparatus of claim 18 , wherein if one or more failures make it impossible to form a minimal path between the first node and the second node, the path generator is additionally configured to generate a non-minimal path between the first node and the second node, if possible, wherein the non-minimal path includes more than the minimal number of links (in the absence of failures) between the first node and the second node.

20. The apparatus of claim 15 , wherein each node in the interconnection network has degree

D

=

∑

i

=

1

h

⁢

⁢

(

2



a

i



-

1

)

,

wherein ∥a i ∥ is the number of bits in the set a i , and wherein the symbol “D” represents a non-negative integer value that denotes the total number of links to a node.

21. The apparatus of claim 15 , wherein the total number of links in the interconnection network is

N

2

⁢

∑

i

=

1

h

⁢

⁢

(

2



a

i



-

1

)

,

wherein ∥a i ∥ is the number of bits in the set a i , and wherein the symbol “N” represents a non-negative integer value that denotes the total number of links in the interconnection network.

22. An interconnection network, comprising:

a plurality of nodes, wherein each node is associated with a unique an n-bit binary identifier;

wherein the n bits of each binary identifier are grouped into h overlapping sets a 1 , a 2 , . . . a h , wherein the sets a 1 , a 2 , . . . a h cover all of the n bits; and

a plurality of direct point-to-point links that form fully connected clusters between nodes in the plurality of nodes, wherein for each set a i , there exists a link between nodes that have binary identifiers that differ in bits of the set a i but are the same in other bit positions, and wherein there do not exist other links;

wherein for each set a i , forming fully connected clusters involves generating 2 n−∥a i ∥ fully connected clusters of 2 ∥a i ∥ nodes wherein ∥a i ∥ is the number of bits in the set a i ; and

wherein the symbols “n”, and “h” represent non-negative integer values.

23. The interconnection network of claim 22 , wherein each of the sets a 1 , a 2 , . . . a h includes the same number of bits.

24. The interconnection network of claim 22 , wherein each set a i includes at least one unique bit that does not belong to another set.

25. The interconnection network of claim 22 , wherein each node in the interconnection network has degree

D

=

∑

i

=

1

h

⁢

⁢

(

2



a

i



-

1

)

,

wherein ∥a i ∥ is the number of bits in the set a i , and wherein the symbol “D” represents a non-negative integer value that denotes the total number of links to a node.

26. The interconnection network of claim 22 , wherein the total number of links in the interconnection network is

N

2

⁢

∑

i

=

1

h

⁢

⁢

(

2



a

i



-

1

)

,

wherein ∥a i ∥ is the number of bits in the set a i , and wherein the symbol “N” represents a non-negative integer value that denotes the total number of links in the interconnection network.