Integer programming technique for verifying and reprovisioning an interconnect fabric design

• US 7,237,020 B1
• Filed: 11/08/2002
• Issued: 06/26/2007
• Est. Priority Date: 01/25/2002
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Drew, Julie Ward
• Primary Examiner(s): LIN, WEN TAI
• Application Number:
  US10/290,643
• Time in Patent Office: 1,691 Days
• Field of Search: None
• US Class Current: 709/223
• 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 47/10 Flow control; Congestion control

Abstract

A technique for verifying and reprovisioning an interconnect fabric design using integer programming techniques. Requirements for the interconnect fabric design to be reprovisioned may be referred to as flow requirements. The flow requirements may include, for example, source and terminal nodes for communication flows and communication bandwidth required for the flows. An existing interconnect fabric design specifies an arrangement of elements of the fabric, such as links and interconnect devices. The invention programmatically verifies whether the existing design satisfies the flow requirements using integer programming techniques. If the existing design does not satisfy the flow requirements, the invention may also be used to reprovision the existing design to satisfy the flow requirements. If any flow(s) cannot be accommodated by the existing design, the integer programming techniques may also be used to identify links that can be added to accommodate the flow(s) Further, a new portion of interconnect fabric may be designed and added to the existing design to accommodate unassigned flows.

Claims

1. A computer implemented method for verifying and reprovisioning an initial design for an interconnect fabric, the method comprising:

initializing an integer programming problem with the initial design including an arrangement of interconnect elements for interconnecting a plurality of network nodes and with requirements for a plurality of flows among the network nodes, the interconnect elements including at least communication links and the integer programming problem being in terms of decision variables and constraints with at least one decision variable being an integer value that represents addition of a new link between a pair of the nodes;

solving the integer programming problem thereby forming a plurality of solutions, wherein in each solution, one or more of the flows is assigned to a path in the initial design, said solving comprising for at least one solution adding a new communication link to the initial design in a path for a flow, the adding of the new link being represented by the integer value; and

selecting a solution according to an objective of maximizing assignment of flows to paths in the initial design.

2. The method according to claim 1, wherein said interconnect elements further comprise interconnect devices wherein each path includes a contiguous set of one or more interconnect elements from a source node to a terminal node.

3. The method according to claim 1, further comprising determining whether any flows remain unassigned.

4. The method according to claim 1, further comprising removing communication links in said initial design for which no flow is assigned.

5. The method according to claim 1, wherein said adding the new communication link further comprises selecting a pair of available ports including an available port that is reachable from the source node for the flow and one of the available ports that is reachable from the terminal node for the flow, wherein said new communication link is added between the selected available ports.

6. The method according to claim 1, further comprising assigning a cost value to each new link added to the design.

7. The method according to claim 6, further comprising removing communication links in said initial design for which no flow is assigned.

8. The method according to claim 7, further comprising assigning a cost penalty to a link removed from the design.

9. The method according to claim 6, wherein said selecting a solution selects a solution according to a cost minimization objective.

10. The method according to claim 9, wherein said selecting a solution selects a solution according to a weighted combination of maximizing assignment of flows and minimizing cost.

11. The method according to claim 9, wherein said selecting a solution selects a least-cost solution from among a plurality of solutions selected according to the objective of maximizing assignment of flows to the initial design.

12. The method according to claim 1, further comprising designing a new portion of the interconnect fabric to be added to the initial design where one or more flows cannot be accommodated by said initial design.

13. The method according to claim 12, wherein said designing the new portion comprises assigning a cost to interconnect elements of the initial interconnect fabric design to which no flows are assigned that is lower than a cost assigned to elements of the new portion that are not included in the original interconnect fabric.

14. The method according to claim 12, wherein at least one flow is assigned partially to the initial fabric design and partially to the new portion.

17. The method according to claim 1, wherein said integer programming problem comprises a constraint that a flow can only be assigned to a path for the flow that starts at a source node for the flow, terminates at an end node for the flow and passes through a contiguous subset of the interconnect elements.

18. The method according to claim 17, wherein said integer programming problem comprises a further constraint that a flow can only be assigned to a path for which no bandwidth capacity is exceeded for the subset of interconnect elements.

15. A computer implemented method for verifying and reprovisioning an initial design for an interconnect fabric, the method comprising:

initializing an integer programming problem with the initial design including an arrangement of interconnect elements for interconnecting a plurality of network nodes and with requirements for a plurality of flows among the network nodes;

solving the integer programming problem thereby forming a plurality of solutions, wherein in each solution, one or more of the flows is assigned to a path in the initial design;

selecting a solution according to an objective of maximizing assignment of flows to paths in the initial design; and

designing a new portion of the interconnect fabric to be added to the initial design where one or more flows cannot be accommodated by said initial design, wherein said designing the new portion comprises recasting an interconnect device of the initial design as a source or terminal node for at least one of the flows that cannot be accommodated by said initial design.

16. The method according to claim 15, wherein said designing the new portion further comprises adding a dummy node wherein the dummy node serves as a source node when the recast interconnect device serves as a terminal node and the dummy node serves as a terminal node when the recast interconnect device serves as a source node.

19. A computer implemented method for reprovisioning an initial design for an interconnect fabric, the method comprising:

initializing an integer programming problem with the initial design including an arrangement of interconnect elements for interconnecting a plurality of network nodes and with requirements for a plurality of flows among the network nodes;

solving the integer programming problem thereby forming a plurality of solutions, wherein in each solution, one or more of the flows is assigned to a path in the initial design, and in at least one solution, one or more flows not assigned to a valid path in the initial design are assigned to a new portion of interconnect fabric and the at least one solution identifying entry and exit points for the one or more flows assigned to the new portion and routed between elements of the initial design and the new portion;

selecting a solution to the integer programming problem; and

designing the new portion of interconnect fabric for accommodating the flows not assigned to a valid path in the initial design.

20. The method according to claim 19, where said solving further comprises assigning any flow not assigned to a valid path in the initial design to a placeholder device and wherein said new portion replaces the placeholder device.

21. The method according to claim 20, wherein said assigned flows are assigned according to a cost objective.

22. The method according to claim 21, wherein said selecting a solution selects a least-cost solution from among a plurality of solutions selected according to an objective of maximizing assignment of flows to paths in the initial design.

23. The method according to claim 20, wherein said placeholder device is functionally equivalent to a switching device that has an unlimited port count and unlimited bandwidth.

24. The method according to claim 23, wherein said assigned flows are assigned according to a cost objective.

25. The method according to claim 20, wherein decision variables associated with the placeholder device identify all exit and entry points for flows assigned to the new portion of interconnect fabric.

26. The method according to claim 19, wherein a valid path begins and a source node for the flow, terminates at a terminal node for the flow and passes through a contiguous subset of interconnect devices for the flow.

27. The method according to claim 19, wherein said interconnect elements comprise communication links and wherein solving further comprises adding a new communication link to the initial design in a path for a flow.

28. The method according to claim 27, wherein said adding the new communication link further comprises selecting a pair of available ports including an available port that is reachable from the source node for the flow and one of the available ports that is reachable from the terminal node for the flow, wherein said new communication link is added between the selected available ports.

29. The method according to claim 19, wherein at least one flow is assigned partially to the initial fabric design and partially to the new portion.

30. The method according to claim 29, wherein said designing the new portion comprises recasting an interconnect device of the initial design as a source or terminal node for at least one of the partially assigned flows.

31. The method according to claim 30, wherein said designing the new portion further comprises adding a dummy node wherein the dummy node serves as a source node when the recast interconnect device serves as a terminal node and the dummy node serves as a terminal node when the recast interconnect device serves as a source node.