Designing interconnect fabrics

• US 20020083159A1
• Filed: 12/19/2001
• Published: 06/27/2002
• Est. Priority Date: 11/06/2000
• Status: Active Grant

• 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.
• Granted Patent: US 7,076,537 B2
• Time in Patent Office: Days
• 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;

identifying flow sets that traverse the interconnect device layer;

merging a pair of the flow sets thereby alleviating at least one port violation; and

implementing the design.

2. The method according to claim 1, wherein said merging adds an additional interconnect device layer to the design.

3. The method according to claim 2, 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 and 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.

16. The system according to claim 15, wherein said fabric design tool adds an additional interconnect device layer to the design by merging a pair of the flow sets.

17. The system according to claim 16, 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.

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, wherein said step of forming comprises identifying flow sets that traverse the interconnect device layer and merging a pair of the flow sets thereby alleviating at least one port violation.

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; and

a fabric design tool that modifies the design for the interconnect fabric by identifying flow sets that traverse the layer of interconnect devices and merging a pair of the flow sets, thereby alleviating at least one port violation.

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; and

repeatedly forming a next interconnect device layer adjacent to either the set of source nodes or terminal nodes, 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.