Generating interconnect fabric requirements

• US 9,009,004 B2
• Filed: 01/31/2002
• Issued: 04/14/2015
• Est. Priority Date: 01/31/2002
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Peh, Li-Shiuan, Wilkes, John, Ward, Julie Ann, O'Sullivan, Michael Justin
• Primary Examiner(s): Rivas, Omar Fernandez
• Assistant Examiner(s): KHAN, IFTEKHAR A
• Application Number:
  US10/066,051
• Publication Number:
  US 20030144822A1
• Time in Patent Office: 4,821 Days
• Field of Search: 703/1
• US Class Current: 703/1
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network

Abstract

A technique for generating interconnect fabric requirements. The technique programmatically generates an interconnect design problem based on criteria specified by a user. In one aspect, a computer implemented method is provided for generating an interconnect fabric design problem. The problem includes requirements for a plurality of flows among a set of network nodes. A source node and a terminal node are selected, from among the set of network nodes, for a flow to be added to the requirements. A maximum capacity available at the selected source node and the selected terminal node is determined. The flow is generated having a capacity less than or equal to the lower of the maximum capacity of the source node and the terminal node. Depending upon the input criteria, the invention may generate problems with greater flexibility than prior techniques.

Claims

1. A computer implemented method for generating an interconnected fabric design problem specification, the problem specification including requirements for a plurality of flows among a set of network nodes and the problem specification suitable for application of a design technique by which physical communication links and communication devices are arranged to meet the flow requirements, the method comprising:

selecting, from among the set of network nodes, a source node and terminal node for a flow to be added to the requirements;

determining a maximum capacity available at the selected source node;

determining a maximum capacity available at the selected terminal node;

determining which of the maximum capacity available at the selected source node and the maximum capacity available at the selected terminal node is smaller;

setting a maximum capacity requirement for a flow between the selected source node and the selected terminal node to a value less than or equal to the determined smaller maximum capacity; and

generating the flow between the selected source node and the selected terminal node.

2. The method according to claim 1, wherein determining the maximum capacity available at the selected source node comprises determining a capacity available at each port of the source node and selecting the highest available capacity for the source node ports, and

wherein determining the maximum capacity available at the selected terminal node comprises determining a capacity available at each port of the terminal node and selecting the highest available capacity for the terminal node ports.

3. The method according to claim 2, wherein determining the capacity at each port of the source or terminal node depends on a specified degree of port saturation and unused port capacity.

4. The method according to claim 1, wherein said selecting, said determining and said generating is repeated until a stop condition is reached.

5. The method according to claim 4, wherein the stop condition is reached when each node in the set has at least a specified number of flows.

6. The method according to claim 1, wherein said set of network nodes comprises a cluster of nodes and wherein the design problem specification includes a plurality of clusters.

7. The method according to claim 6, wherein the design problem specification includes at least one flow between a pair of clusters.

8. The method according to claim 7, wherein the design problem specification further comprises at least one node not in the clusters having a flow to a node in the clusters.

9. The method according to claim 1, further comprising generating an additional flow and determining whether to add the additional flow to the design problem specification according to a specified probability.

10. The method according to claim 9, further comprising repeating said steps of generating an additional flow and determining whether to add the additional flow to the design problem specification a number of times determined from a difference between a current number of flows and a specified maximum number of flows.

11. The method according to claim 1, wherein the flow is assigned to a single port at each of the source node and the terminal node.

12. The method according to claim 1, wherein the flow is split among multiple ports at one or both of the source node and the terminal node.

24. The method according to claim 1, wherein the maximum capacity requirement for the generated flow is randomly selected to be a value less than or equal to the lower of the maximum capacity of the source node and the terminal node.

25. The method according to claim 1 wherein the capacity available at a node is reduced by the capacity of each flow assigned to the node.

13. A system for generating an interconnect fabric design problem specification for communication among a set of nodes, the system comprising:

a set of design information including user-specified parameters for the design problem specification; and

a fabric design problem generation tool that generates the design problem specification for the interconnect fabric by adding flows to a set of flow requirements among the set of nodes in response to the design information,

wherein said fabric design problem generation tool is to;

select, from among the set of network nodes, a source node and a terminal node for a flow to be added to the flow requirements,

determine a maximum capacity available at the selected source node,

determine a maximum capacity available at the selected terminal node,

determine which of the maximum capacity available at the selected source node and the maximum capacity available at the selected terminal node is smaller,

set a maximum capacity requirement for a flow between the selected source node and the selected terminal node to a value less than or equal to the determined smaller maximum capacity, and

generate the flow between the source node and the terminal node.

14. The system according to claim 13, wherein said fabric design problem generation tool determines the maximum capacity available at the source node by determining a capacity available at each port of the source node and selecting the highest available capacity for the source node ports and wherein said fabric design tool determines the maximum capacity available at the terminal node by determining a capacity available at each port of the terminal node and selecting the highest available capacity for the terminal node ports.

15. The system according to claim 14, wherein said fabric design problem generation tool determines the capacity at each port of the source or terminal node based on a specified degree of port saturation and unused port capacity.

16. The system according to claim 13, wherein said fabric design problem generation tool adds flows to the set of flow requirements until a stop condition is reached.

17. The system according to claim 16, wherein the stop condition is reached when each node in the set has at least a specified number of flows.

18. The system according to claim 16, wherein the stop condition is based on bandwidth levels of the flow requirements.

19. The system according to claim 13, wherein said set of network nodes comprises a cluster of nodes and wherein the design problem includes a plurality of clusters.

20. The system according to claim 19, wherein the design problem specification includes at least one flow between a pair of the clusters.

21. The system according to claim 20, wherein the design problem specification further comprises at least one node not in the clusters having a flow to a node in the clusters.

22. The system according to claim 13, wherein the fabric design problem generation tool generates an additional flow and determines whether to add the additional flow to the design problem according to a specified probability.

23. The system according to claim 22, wherein the fabric design problem generation tool repeatedly generates an additional flow and determines whether to add the additional flow to the design problem a number of times determined from a difference between a current number of flows and a specified maximum number of flows.

26. The system according to claim 13, wherein the maximum capacity requirement for the generated flow is randomly selected to be a value less than or equal to the lower of the maximum capacity of the source node and the terminal node.

27. The system according to claim 13 wherein the capacity available at a node is reduced by the capacity of each flow assigned to the node.