Method and apparatus for cluster interconnection using multi-port nodes and multiple routing fabrics
View Patent ↗Interconnect networks are described that allow nodes having more than two ports to be interconnected. More particularly, each node interfaces with multiple and more than two, fabrics. Also, all fabrics are incomplete in that not every node interfaces with every fabric, and no fabric includes all the nodes, yet every pair of nodes appears together in at least one fabric. Nodes are used that appear together in a fabric as a class of nodes that exhibit similar interconnection properties. The present invention allows for scalable, high-performance and reliable interconnection of large numbers of end nodes while satisfying constraints on architecture of end nodes and networking equipment. Bounds for the number of fabrics and fabric size are disclosed for designing an optimized interconnection network.
1. A multi-fabric interconnection system, comprising:
k interconnection fabrics each comprising a plurality of routers and interconnection links, each having a vertex cardinality, m; and
n nodes each having p ports, wherein p is greater than two, and wherein every pair of nodes from among the n nodes is interconnected through at least one of the k interconnection fabrics,
where each of the k interconnection fabrics interconnects less than all of the n nodes, wherein the number k of interconnection fabrics is bounded above and below by the relationships
k
≤
(
p
+
1
2
)
and
k
≥
⌈
(
n
2
)
(
m
2
)
⌉
,
respectively
.
2. The interconnection system of claim 1 , wherein the k interconnection fabrics provide redundant interconnection paths between every pair of nodes from among the n nodes.
3. A multi-fabric interconnection system, comprising:
k interconnection fabrics each comprising a plurality of routers and interconnection links, each having a vertex cardinality, m; and
n nodes each having p ports, wherein p is greater than two, and wherein every pair of nodes from among the n nodes is interconnected through at least one of the k interconnection fabrics,
wherein each of the k interconnection fabrics interconnects less than all of the n nodes, wherein the vertex cardinality, m, is bounded above and below by the relationships
m
≤
2
⌈
n
p
+
1
⌉
and
m
≥
⌈
n
+
p
-
1
p
⌉
,
respectively
.
4. A multi-fabric interconnection system, comprising:
k interconnection fabrics, each having a vertex cardinality, m; and
n nodes each having p ports, wherein p is greater than two, and wherein every pair of nodes from among the n nodes is interconnected through at least one of the k interconnection fabrics,
wherein every pair from among the p ports is interconnected to at least one of k interconnection fabrics, and wherein each of the k interconnection fabrics interconnects less than all of the n nodes, wherein the number k of the interconnection fabrics is bounded above and below by the relationships
k
≤
(
p
+
1
2
)
and
k
≥
⌈
(
n
2
)
(
m
2
)
⌉
,
respectively
.
5. The interconnection system of claim 4 , wherein the vertex cardinality, m, is bounded above and below by the relationships
m
≤
2
⌈
n
p
+
1
⌉
and
m
≥
⌈
n
+
p
-
1
p
⌉
,
respectively
.
6. The interconnection system of claim 4 , wherein the k interconnection fabrics provide redundant interconnection paths between every pair of nodes from among the n nodes.
7. A multi-fabric interconnection system, comprising:
k interconnection fabrics each having a vertex cardinality, m; and
n nodes each having p ports, wherein p is greater than two, and wherein every pair of nodes from among then nodes is interconnected through at least one of the k interconnection fabrics, wherein the vertex cardinality, m, is bounded above and below by the relationships
m
≤
2
⌈
n
p
+
1
⌉
and
m
≥
⌈
n
+
p
-
1
p
⌉
,
respectively
.
8. The interconnection system of claim 7 , wherein the number k of interconnection fabrics is bounded above and below by the relationships
k
≤
(
p
+
1
2
)
and
k
≥
⌈
(
n
2
)
(
m
2
)
⌉
,
respectively
.
9. The interconnection system of claim 7 , wherein the k interconnection fabrics provide redundant interconnection paths between every pair of nodes from among the n nodes.
10. A multi-fabric interconnection system, comprising:
k incomplete interconnection fabrics each having a vertex cardinality, m; and
n nodes each having p ports, wherein p is greater than two, and wherein every pair of nodes from among the n nodes is interconnected through at least one of the k incomplete interconnection fabrics, wherein the vertex cardinality, m, is bounded above and below by the relationships
m
≤
2
⌈
n
p
+
1
⌉
and
m
≥
⌈
n
+
p
-
1
p
⌉
,
respectively
.
11. The interconnection system of claim 10 , wherein the number k of interconnection fabrics is bounded above and below by the relationships
k
≤
(
p
+
1
2
)
and
k
≥
⌈
(
n
2
)
(
m
2
)
⌉
,
respectively
.
12. The interconnection system of claim 10 , wherein the k interconnection fabrics provide redundant interconnection paths between every pair of nodes from among the n nodes.
13. A method for implementing a multi-fabric interconnection system, comprising:
providing k interconnection fabrics each having a vertex cardinality, m; and
providing n nodes each having p ports, wherein p is greater than two, and wherein every pair of nodes from among the n nodes is interconnected through at least one of the k interconnection fabrics,
wherein each of the k interconnection fabrics interconnects less than all of the n nodes, wherein the vertex cardinality, m, is bounded above and below by the relationships
m
≤
2
⌈
n
p
+
1
⌉
and
m
≥
⌈
n
+
p
-
1
p
⌉
,
respectively
.
14. The method of claim 13 , wherein the number k of interconnection fabrics is bounded above and below by the relationships
k
≤
(
p
+
1
2
)
and
k
≥
⌈
(
n
2
)
(
m
2
)
⌉
,
respectively
.
15. The method of claim 13 , wherein the k fabrics provide redundant interconnection paths between every pair of nodes from among the n nodes.
16. A method for implementing a multi-fabric interconnection system, comprising:
providing k interconnection fabrics, each having a vertex cardinality, m; and
providing n nodes each having p ports, wherein p is greater than two, and wherein every pair of nodes from among the n nodes is interconnected through at least one of the k interconnection fabrics,
wherein every pair from among the p ports is interconnected to at least one of k interconnection fabrics, and wherein each of the k interconnection fabrics interconnects less than all of the n nodes, wherein the number k of the interconnection fabrics is bounded above and below by the relationships
k
≤
(
p
+
1
2
)
and
k
≥
⌈
(
n
2
)
(
m
2
)
⌉
,
respectively
.
17. The method of claim 16 , wherein the vertex cardinality, m, is bounded above and below by the relationships
m
≤
2
⌈
n
p
+
1
⌉
and
m
≥
⌈
n
+
p
-
1
p
⌉
,
respectively
.
18. The method of claim 16 , wherein the k fabrics provide redundant interconnection paths between every pair of nodes from among the n nodes.
19. A method for implementing a multi-fabric interconnection system, comprising:
providing k interconnection fabrics each having a vertex cardinality, m; and
providing n nodes each having p ports, wherein p is greater than two, and wherein every pair of nodes from among the n nodes is interconnected through at least one of the k interconnection fabrics, wherein the vertex cardinality, m, is bounded above and below by the relationships
m
≤
2
⌈
n
p
+
1
⌉
and
m
≥
⌈
n
+
p
-
1
p
⌉
,
respectively
.
20. The method of claim 19 , wherein the number k of interconnection fabrics is bounded above and below by the relationships
k
≤
(
p
+
1
2
)
and
k
≥
⌈
(
n
2
)
(
m
2
)
⌉
,
respectively
.
21. The method of claim 19 , wherein the k fabrics provide redundant interconnection paths between every pair of nodes from among the n nodes.
22. A computer-readable medium embodying program code for implementing a multi-fabric interconnection system having instructions that cause a computer to perform steps, comprising:
interconnecting k fabrics each having a vertex cardinality, m; and
interconnecting n nodes each having p ports, wherein p is greater than two, and wherein every pair of nodes from among the n nodes is interconnected through at least one of the k interconnection fabrics,
wherein each of the k interconnection fabrics interconnects less than all of the n nodes wherein the number k of interconnection fabrics is bounded above and below by the relationships
k
≤
(
p
+
1
2
)
and
k
≥
⌈
(
n
2
)
(
m
2
)
⌉
,
respectively
.
23. The computer-readable medium of claim 22 , wherein the vertex cardinality, m, is bounded above and below by the relationships
m
≤
2
⌈
n
p
+
1
⌉
and
m
≥
⌈
n
+
p
-
1
p
⌉
,
respectively
.
24. The computer-readable medium of claim 22 , wherein the k fabrics provide redundant interconnection paths between every pair of nodes from among the n nodes.
25. A computer-readable medium embodying program code for implementing a multi-fabric interconnection system having instructions that cause a computer to perform steps, comprising:
interconnecting k fabrics each having a vertex cardinality, m; and
interconnecting n nodes each having p ports, wherein p is greater than two, and wherein every pair of nodes from among the n nodes is interconnected through at least one of the k interconnection fabrics,
wherein every pair from among the p ports is interconnected to at least one of k interconnection fabrics, and wherein each of the k interconnection fabrics interconnects less than all of the n nodes, wherein the vertex cardinality, m, is bounded above and below by the relationships
m
≤
2
⌈
n
p
+
1
⌉
and
m
≥
⌈
n
+
p
-
1
p
⌉
,
respectively
.
26. The computer-readable medium of claim 25 , wherein the number k of the interconnection fabrics is bounded above and below by the relationships
k
≤
(
p
+
1
2
)
and
k
≥
⌈
(
n
2
)
(
m
2
)
⌉
,
respectively
.
27. The computer-readable medium of claim 25 , wherein the k fabrics provide redundant interconnection paths between every pair of nodes from among the n nodes.
28. A computer-readable medium embodying program code for implementing a multi-fabric interconnection system having instructions that cause a computer to perform steps, comprising:
interconnecting k fabrics each having a vertex cardinality, m; and
interconnecting n nodes each having p ports, wherein p is greater than two, and wherein every pair of nodes from among the n nodes is interconnected through at least one of the k interconnection fabrics, wherein the number k of interconnection fabrics is bounded above and below by the relationships
k
≤
(
p
+
1
2
)
and
k
≥
⌈
(
n
2
)
(
m
2
)
⌉
,
respectively
.
29. The computer-readable medium of claim 28 , wherein the vertex cardinality, m, is bounded above and below by the relationships
m
≤
2
⌈
n
p
+
1
⌉
and
m
≥
⌈
n
+
p
-
1
p
⌉
,
respectively
.
30. The computer-readable medium of claim 28 , wherein the k fabrics provide redundant interconnection paths between every pair of nodes from among the n nodes.
31. A computer-readable medium embodying program code for implementing a multi-fabric interconnection system having instructions that cause a computer to perform steps, comprising:
interconnecting k incomplete fabrics each having a vertex cardinality, m; and
interconnecting n nodes each having p ports, wherein p is greater than two, and wherein every pair of nodes from among the n nodes is interconnected through at least one of the k incomplete interconnection fabrics, wherein the number k of interconnection fabrics is bounded above and below by the relationships
k
≤
(
p
+
1
2
)
and
k
≥
⌈
(
n
2
)
(
m
2
)
⌉
,
respectively
.
32. The computer-readable medium of claim 31 , wherein the vertex cardinality, m, is bounded above and below by the relationships
m
≤
2
⌈
n
p
+
1
⌉
and
m
≥
⌈
n
+
p
-
1
p
⌉
,
respectively
.
33. The computer-readable medium of claim 31 , wherein the k incomplete fabrics provide redundant interconnection paths between every pair of nodes from among the n nodes.