Designing interconnect fabrics

• US 7,076,537 B2
• Filed: 12/19/2001
• Issued: 07/11/2006
• Est. Priority Date: 11/06/2000
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Wilkes, John, Ward, Julie A., Shahoumian, Troy A.
• Primary Examiner(s): Maung, Zarni
• Assistant Examiner(s): PHILLIPS, HASSAN A
• Application Number:
  US10/027,564
• Publication Number:
  US 20020083159A1
• Time in Patent Office: 1,665 Days
• Field of Search: 709220-222, 709/238, 709/239, 709/241
• US Class Current: 709/220
• CPC Class Codes: H04L 49/10 characterised by the switching fabric construction

Abstract

A technique for designing an interconnect fabric for communication between a set of source nodes and a set of terminal nodes. A design for an interconnect fabric is obtained having an interconnect device layer. The layer is adjacent to either the set of source nodes or the set of terminal nodes. Flow sets that traverse the layer of interconnect devices are identified. A pair of the flow sets are merged thereby alleviating at least one port violation. The technique may be implemented programmatically by a design tool.

Claims

1. A method of designing an interconnect fabric for communication between a set of source nodes and a set of terminal nodes, comprising:

obtaining a design for an interconnect fabric having an interconnect device layer adjacent to either the set of source nodes or the set of terminal nodes, the interconnect device layer comprising a first interconnect device;

identifying flow sets that traverse the interconnect device layer, each flow set specifying communication bandwidth between a source node of the set of source nodes and a terminal node of the set of terminal nodes and the flow sets including at least a first flow set that passes through the first interconnect device;

merging a pair of the flow sets, the pair including at least the first flow set and said merging comprising adding a second interconnect device to the design, the second interconnect device being linked to the first interconnect device, thereby alleviating at least one port violation and adding an additional interconnect device layer that includes the second interconnect device to the design; and

implementing the design.

2. The method according to claim 1, further comprising merging a pair of the flow sets that does not alleviate a port violation but results in cost savings.

3. The method according to claim 1, further comprising repeatedly performing, prior to said implementing, identifying an interconnect device layer adjacent to either the set of source nodes or the set of terminal nodes end said steps of identifying flow sets and merging a pair of the flow sets, until port violations are no longer present in the design, thereby adding one or more additional interconnect device layers to the design.

4. The method according to claim 1, wherein said obtaining comprises generating an arrangement of flow sets in response to a set of flow requirements for the source and terminal nodes and alleviating at least one port violation associated with the arrangement of flow sets by merging a pair of the flow sets in the arrangement.

5. The method according to claim 1, further comprising inserting a dummy node into the interconnect device layer for each link that traverses the interconnect device layer and that is not terminated in the interconnect device layer.

6. The method according to claim 1, further comprising determining for each source and terminal node one or more port violations including a number by which a set of ports for the corresponding flow sets exceed a set of available ports.

7. The method according to claim 6, wherein said merging a pair of the flow sets alleviates at least one port violation of a source or terminal node for which the number is highest.

8. The method according to claim 6, wherein said merging a pair of the flow sets alleviates at least one port violation of a source or terminal node for which the number is highest and also alleviates at least one port violation of a source or terminal for which the number is next highest.

9. The method according to claim 6, wherein said step of merging a pair of the flow sets alleviates at least one port violation of a source or terminal node for which the number is highest and for which the step of merging imposes a least cost or greatest cost savings.

10. The method according to claim 9, wherein cost is based on a cost of an interconnect device that carries the pair of flow sets.

11. The method according to claim 1, wherein said merging a pair of the flow sets comprises selecting pair by determining feasibility of merging the pair.

12. The method according to claim 11, wherein said determining feasibility comprises determining whether an available interconnect device has sufficient bandwidth to carry the pair of flow sets.

13. The method according to claim 11, wherein said determining feasibility comprises determining whether an available interconnect device has enough ports to carry the pair of flow sets.

14. The method according to claim 1, wherein the interconnect fabric comprises a storage area network.

15. A system for designing an interconnect fabric for communication between a set of source nodes and a set of terminal nodes comprising:

a design for an interconnect fabric having at least one interconnect device layer that includes a first interconnect device; and

a fabric design tool that modifies the design for the interconnect fabric by identifying flow sets that traverse the layer of interconnect devices, each flow set specifying communication bandwidth between a source node of the set of source nodes and a terminal node of the set of terminal nodes and the flow sets including at least a first flow set that passes through the first interconnect device, and merging a pair of the flow sets, the pair including at least the first flow set and said merging comprising adding a second interconnect device to the design, the second interconnect device linked to the first interconnect device, thereby alleviating at least one port violation and adding an additional interconnect device layer that includes the second interconnect device to the design.

16. The system according to claim 15, wherein said fabric design tool merges a pair of the flow sets that does not alleviate a port violation but results in cost savings.

17. The system according to claim 15, wherein said fabric design tool repeatedly adds additional interconnect device layers to the design until port violations are no longer present in the design.

18. The system according to claim 15, wherein said design for the interconnect fabric is obtained by generating an arrangement of flow sets in response to a set of flow requirements for the source and terminal nodes and alleviating at least one port violation associated with the arrangement of flow sets by merging a pair of the flow sets in the arrangement.

19. The system according to claim 15, wherein the fabric design tool inserts a dummy node into the interconnect device layer for each link that traverses the interconnect device layer and that is not terminated in the interconnect device layer.

20. The system according to claim 15, wherein the fabric design tool determines for each source and terminal node one or more port violations including a number by which a set of ports for the corresponding flow sets exceed a set of available ports.

21. The system according to claim 20, wherein the fabric design tool alleviates at least one port violation of a source or terminal node for which the number is highest.

22. The system according to claim 20, wherein the fabric design tool alleviates at least one port violation of a source or terminal node for which the number is highest and also alleviates at least one port violation of a source or terminal for which the number is next highest.

23. The system according to claim 20, wherein the fabric design tool alleviates at least one port violation of a source or terminal node for which the number is highest and for which the step of merging imposes a least cost or greatest cost savings.

24. The system according to claim 23, wherein the fabric design tool determines the cost based on a cost of an interconnect device that carries the pair of flow sets.

25. The system according to claim 15, wherein said the fabric design tool selects a pair of the flow sets for merger by determining feasibility of merging the pair.

26. The system according to claim 25, wherein the fabric design tool determines the feasibility by determining whether an available interconnect device has sufficient bandwidth to carry the pair of flow sets.

27. The system according to claim 25, wherein the fabric design tool determines the feasibility by determining whether an available interconnect device has enough ports to carry the pair of flow sets.

28. The system according to claim 15, wherein the interconnect fabric comprises a storage area network.

29. A method of designing an interconnect fabric for communication between a set of source nodes and a set of terminal nodes, comprising:

obtaining a design for an interconnect fabric having a interconnect device layer adjacent to either the set of source nodes or the set of terminal nodes, the interconnect device layer comprising at least one interconnect device; and

repeatedly forming a next interconnect device layer adjacent to either the set of source nodes or terminal nodes by identifying flow sets that traverse an existing adjacent interconnect device layer and merging a pair of the flow sets thereby alleviating at least one port violation, each added interconnect device layer comprising at least one interconnect device linked to an interconnect device of the existing adjacent interconnect device layer, thereby adding interconnect device layers to the design, until the design satisfies a set of flow requirements between the source nodes and terminal nodes without port violations.

30. The method according to claim 29, wherein each added interconnect device layer reduces a number of port violations by at least one, thereby each added interconnect device layer progresses the design toward a condition of having no port violations.

31. The method according to claim 29, further comprising merging a pair of the flow sets that does not alleviate a port violation but results in cost savings.