Reliability for interconnect fabrics

• US 7,233,983 B2
• Filed: 01/17/2002
• Issued: 06/19/2007
• Est. Priority Date: 11/06/2000
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Wilkes, John, Ward, Julie Ann, Shahoumian, Troy Alexander
• Primary Examiner(s): Harrell; Robert B.
• Application Number:
  US10/052,682
• Publication Number:
  US 20020091804A1
• Time in Patent Office: 1,979 Days
• Field of Search: 709238-239, 709223-224, 709473-474, 370/230, 370/236, 370/338, 714/4, 714/13
• US Class Current: 709/220
• CPC Class Codes: H04L 49/10 characterised by the switching fabric construction

Abstract

A technique for providing reliability to an interconnect fabric for communication among a set of nodes. The technique may be used to efficiently and programmatically produce a cost-effective interconnect fabric having a degree of reliability over a range of design problems. In one aspect, ports associated with each node are partitioned into a first set of ports and a second set of ports. A primary interconnect fabric is formed among the first set of ports in response to a set of flow requirements and a backup interconnect fabric is formed among the second set of ports. The backup interconnect fabric carries a portion of communications carried by the primary fabric so as to protect against a failure of an element in the primary fabric.

Claims

1. A method of providing reliability to an interconnect fabric for communication among a set of nodes, the method comprising:

partitioning ports associated with each node into a first set of ports and a second set of ports;

forming a primary interconnect fabric among the first set of ports in response to a set of flow requirements; and

forming a backup interconnect fabric among the second set of ports wherein the backup interconnect fabric carries a portion of communications carried by the primary fabric so as to protect against occurrence of a failure in the primary fabric, said forming the backup interconnect fabric comprising determining feasibility of merging candidate flow sets based on a sum of flow requirements in the candidate flow sets that are interrupted by a single failure in the primary interconnect fabric.

2. The method according to claim 1, wherein said forming the backup interconnect fabric further comprises generating arrangements of flow sets in response to the flow requirements, determining feasibility of merging pairs of candidate flow sets and merging a pair of the flow sets.

3. The method according to claim 2, wherein said merging the pair of the flow sets alleviates at least one port violation with respect to the second set of ports.

4. The method according to claim 1, said partitioning further comprising partitioning the ports associated with each node into a number of additional sets of ports.

5. The method according to claim 4, further comprising forming additional interconnect fabrics among the additional sets of ports.

6. The method according to claim 1, said partitioning further comprising partitioning the ports associated with each node into a number of additional sets of ports.

7. The method according to claim 6, further comprising forming additional interconnect fabrics among the additional sets of ports.

8. The method according to claim 1, wherein said set of nodes includes source nodes and terminal nodes.

9. The method according to claim 1, wherein each node is associated with at least two ports.

10. The method according to claim 1, wherein the second set of ports includes one port for each node.

11. A method of providing reliability to an interconnect fabric for communication among a set of nodes, the method comprising:

partitioning ports associated with each node into a first set of ports and a second set of ports;

forming a primary interconnect fabric among the first set of ports in response to a set of flow requirements; and

forming a backup interconnect fabric among the second set of ports wherein the backup interconnect fabric carries a portion of communications carried by the primary fabric so as to protect against occurrence of a failure in the primary fabric, wherein said forming the backup interconnect fabric comprises determining feasibility based on a highest sum of flow requirements in the candidate flow sets tat are interrupted by different failures in the primary interconnect fabric.

12. The method according to claim 11, wherein said forming the backup interconnect fabric further comprises generating arrangements of flow sets in response to the flow requirements, determining feasibility of merging pairs of candidate flow sets and merging a pair of the flow sets.

13. The method according to claim 12, wherein said merging the pair of the flow sets alleviates at least one port violation with respect to the second set of ports.

14. The method according to claim 11, wherein said set of nodes includes source nodes and terminal nodes.

15. The method according to claim 11, wherein each node is associated with at least two ports.

16. The method according to claim 11, wherein the second set of ports includes one port for each node.

17. A method of providing reliability to an interconnect fabric for communication among a set of nodes, the method comprising:

identifying one or more failure modes in a primary interconnect fabric, wherein the primary interconnect fabric carries communications among the set of nodes via a first set of ports of the nodes; and

forming a backup interconnect fabric among a second set of ports of the nodes for carrying a portion of the communications of the primary fabric so as to protect against occurrence of any single one of the failure modes of the primary fabric, wherein said forming the backup interconnect fabric comprises determining feasibility of merging candidate flow sets based on a sum of flow requirements in the candidate flow sets in the primary interconnect fabric that are interrupted by occurrence of a single failure mode in the primary interconnect fabric.

18. The method according to claim 17, wherein said forming the backup interconnect fabric comprises generating arrangements of flow sets in response to the flow requirements, determining feasibility of merging pairs of candidate flow sets and merging a pair of the flow sets.

19. The method according to claim 18, wherein said merging the pair of the flow sets alleviates at least one port violation with respect to the second set of ports.

20. The method according to claim 17, said partitioning further comprising partitioning the ports associated with each node into a number of additional sets of ports.

21. The method according to claim 20, further comprising forming additional interconnect fabrics among the additional sets of ports.

22. The method according to claim 17, wherein said set of nodes includes source nodes and terminal nodes.

23. The method according to claim 17, wherein each node is associated with at least two ports.

24. The method according to claim 17, wherein the second set of ports includes one port for each node.

25. A method of providing reliability to an interconnect fabric for communication among a set of nodes, the method comprising:

identifying one or more failure modes in a primary interconnect fabric, wherein the primary interconnect fabric carries communications among the set of nodes via a first set of ports of the nodes; and

forming a backup interconnect fabric among a second set of ports of the nodes carrying a portion of the communications of the primary fabric so as to protect against occurrence of any single one of the failure modes of the primary fabric, wherein said forming the backup interconnect fabric comprises determining feasibility of merging candidate flow sets based on a highest sum of flow requirements in the candidate flow sets in the primary interconnect fabric that are interrupted by occurrence of different failure modes in the primary interconnect fabric.

26. The method according to claim 25, wherein said forming the backup interconnect fabric comprises generating arrangements of flow sets in response to the flow requirements, determining feasibility of merging pairs of candidate flow sets and merging a pair of the flow sets.

27. The method according to claim 26, wherein said merging the pair of the flow sets alleviates at least one port violation with respect to the second set of ports.

28. The method according to claim 25, wherein said set of nodes includes source nodes and terminal nodes.

29. The method according to claim 25, wherein each node is associated with at least two ports.

30. The method according to claim 25, said partitioning further comprising partitioning the ports associated with each node into a number of additional sets of ports.

31. The method according to claim 30, further comprising forming additional interconnect fabrics among the additional sets of ports.

32. The method according to claim 25, wherein the second set of ports includes one port for each node.

33. A system for generating an interconnect fabric design comprising:

means for partitioning ports associated with each node into a first set of ports and a second set of ports;

means for generating a design for a primary interconnect fabric among the first set of ports in response to a set of flow requirements; and

means for generating a design for a backup interconnect fabric among the second set of ports wherein the backup interconnect fabric carries a portion of communications carried by the primary interconnect fabric so as to protect against occurrence of a failure in the primary interconnect fabric, wherein the means for generating the design for the backup interconnect fabric determines feasibility of merging candidate flow sets based on a sum of flow requirements in the candidate flow sets that are interrupted by a single failure in the primary interconnect fabric.

34. A system for generating an interconnect fabric design comprising:

means for partitioning ports associated with each node into a first set of ports and a second set of ports;

means for generating a design for a primary interconnect fabric among the first set of ports in response to a set of flow requirements; and

means for generating a design for a backup interconnect fabric among the second set of ports wherein the backup interconnect fabric carries a portion of communications carried by the primary interconnect fabric so as to protect against occurrence of a failure in the primary interconnect fabric, wherein the means for generating the design for the backup interconnect fabric determines feasibility based on a highest sum of flow requirements in the candidate flow sets that are interrupted by different failures in the primary interconnect fabric.

35. A system for generating an interconnect fabric design comprising:

means for identifying one or more failure modes in a primary interconnect fabric, wherein the primary interconnect fabric carries communications among the set of nodes via a first set of ports of the nodes; and

means for generating a design for a backup interconnect fabric among a second set of ports of the nodes for carrying a portion of the communications of the primary interconnect fabric so as to protect against occurrence of any single one of the failure modes of the primary interconnect fabric, wherein the means for generating the design for the backup interconnect fabric determines feasibility of merging candidate flow sets based on a sum of flow requirements in the candidate flow sets in the primary interconnect fabric that are interrupted by occurrence of a single failure mode in the primary interconnect fabric.

36. A system for generating an interconnect fabric design comprising:

means for identifying one or more failure modes in a primary interconnect fabric, wherein the primary interconnect fabric carries communications among the set of nodes via a first set of ports of the nodes; and

means for generating a design for a backup interconnect fabric among a second set of ports of the nodes for carrying a portion of the communications of the primary interconnect fabric so as to protect against occurrence of any single one of the failure modes of the primary interconnect fabric, wherein the means for generating the design for the backup interconnect fabric determines feasibility of merging candidate flow sets based on a highest sum of flow requirements in the candidate flow sets in the primary interconnect fabric that are interrupted by occurrence of different failure modes in the primary interconnect fabric.