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

• US 7,333,444 B1
• Filed: 12/17/2003
• Issued: 02/19/2008
• Est. Priority Date: 12/17/2003
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Sharapov, Ilya A.
• Primary Examiner(s): Orgad; Edan
• Assistant Examiner(s): Haliyur; Venkatesh
• Application Number:
  US10/739,475
• Time in Patent Office: 1,525 Days
• Field of Search: 370254-258, 370/418, 370/389, 370/400, 370406-408
• US Class Current: 370/255
• CPC Class Codes: H04L 2101/604 Address structures or formats
• 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/14 Routing performance; Theoretical aspects

Abstract

One embodiment of the present invention provides a system for generating an interconnection network. During operation, the system associates an n-bit binary identifier with each node in the interconnection network. The system also groups the n bits of each binary identifier into h overlapping sets a₁, a₂, . . . a_h, wherein the sets a₁, a₂, . . . a_h cover all of the n bits. For each set a_i, the system forms 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₁ but are the same in other bit positions. Note that by varying the amount of overlap and the pattern of overlap between the overlapping sets, a₁, a₂, . . . a_h, the interconnection network can be configured to accommodate different redundancy requirements.

Claims

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₁, a₂, . . . a_h, wherein the sets a₁, a₂, . . . 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<sup>n−

∥

ai∥</sup>

fully connected clusters of 2<sup>∥

ai∥</sup>

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₁, a₂, . . . 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₁, a₂, . . . 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=\sum _{}^{}$

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

$\frac{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₁, a₂, . . . a_h, wherein the sets a₁, a₂, . . . 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<sup>n−

∥

ai∥</sup>

fully connected clusters of 2<sup>∥

ai∥</sup>

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₁, a₂, . . . 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₁, a₂, . . . 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=\sum _{}^{}$

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

$\frac{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₁, a₂, . . . a_h, wherein the sets a₁, a₂, . . . 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<sup>n−

∥

ai∥</sup>

fully connected clusters of 2<sup>∥

ai∥</sup>

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₁, a₂, . . . 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₁, a₂, . . . 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=\sum _{}^{}$

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

$\frac{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₁, a₂, . . . a_h, wherein the sets a₁, a₂, . . . 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<sup>n−

∥

ai∥</sup>

fully connected clusters of 2<sup>∥

ai∥</sup>

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₁, a₂, . . . 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=\sum _{}^{}$

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

$\frac{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.