Method for automatic partitioning of node-weighted, edge-constrained graphs

• US 6,437,804 B1
• Filed: 10/23/1997
• Issued: 08/20/2002
• Est. Priority Date: 10/23/1997
• Status: Expired due to Term

• Current Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Original Assignee: Aprisma Management Technologies Incorporated (Broadcom, Inc.)
• Inventors: Vaishnavi, Vick, Dev, Roger, Ibe, Oliver
• Primary Examiner(s): Bayerl, Raymond J.
• Assistant Examiner(s): Hailu, Tadesse
• Application Number:
  US08/956,831
• Time in Patent Office: 1,762 Days
• Field of Search: 345/340, 345/345, 345/334, 345/435, 345/969, 345/348, 345/356, 345/765, 345/744, 345/804, 345/734, 345/736, 345/853, 345/854, 709/223, 709/224
• US Class Current: 715/736
• CPC Class Codes: G06F 2111/04 Constraint-based CAD
• CPC Class Codes: G06F 2111/12 Symbolic schematics
• 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

Abstract

According to an embodiment of the present invention, a method is provided for partitioning a network, comprising modeling the network as a graph comprising nodes which represent network devices, and edges which represent links between the devices, and automatically partitioning the graph into domains. One embodiment of the method includes identifying a number of anchor nodes in the graph and partitioning the domains around the anchor nodes such that each domain contains only one anchor node. Another embodiment of the method includes partitioning a graph without anchor nodes into a number of domains, and assigning controllers to each of the domains. Preferably, the method further includes assigning a weight to each node in the graph, and balancing the partitions as a function of the weight of each node in a respective partition.

Claims

1. A method for partitioning a communication network into partitions, the method comprising:

modeling the network as a graph comprising nodes which represent network devices and edges which represent links between the devices; and

automatically partitioning the graph;

and wherein the partitioning step includes a step of generating partitions such that links identified as weak links are not included within any one partition.

2. The method of claim 1, further comprising assigning domain controllers to each of said partitions.

3. A method for partitioning a communication network into partitions, the method comprising:

modeling the network as a graph comprising nodes which represent network devices and edges which represent links between the devices;

automatically partitioning the graph; and

assigning a weight to each node in the graph;

and wherein the partitioning step includes a step of balancing the combined weights of the nodes in each partition.

4. The method of claim 3, wherein the generating step includes the step of determining a range of acceptable weights for each partition.

5. The method of claim 4, wherein the determining step includes the step of determining a total of the weights of all nodes in the graph divided by a number of possible domains for the graph, plus and minus a smallest weight of all of the nodes.

6. A method for partitioning a communication network, the method comprising:

modeling the network as a graph comprising nodes which represent network devices and edges which represent links between the devices;

automatically partitioning the graph;

wherein the partitioning step comprises;

a step of identifying supernodes in the graph; and

a step of combining supernodes which have at least two nodes in common into a cluster.

7. The method of claim 6, wherein each identified supernode comprises three fully connected nodes.

8. The method of claim 7, wherein the network is partitioned into domains and the partitioning step further comprises a step of generating the domains from the clusters.

9. The method of claim 8, wherein the domains are generated around anchor nodes such that each domain includes only one anchor node.

10. A domain partitioning engine comprising:

means for receiving, a representation of a graph comprising nodes and edges;

means for identifying a plurality of supernodes; and

means, responsive to the means for identifying, for automatically partitioning the graph into a number of domains, at least one of which comprises one or more of the plurality of supernodes.

11. The domain partitioning engine of claim 10, further comprising means for assigning a weight to each node in the graph;

and wherein the means for partitioning includes means for to balancing the combined weights of the nodes in each respective partition.

12. The method of claim 11, wherein the means for generating includes means for determining a range of acceptable weights for each partition.

13. The domain partitioning engine of claim 10, wherein the means for identifying identifies supernodes consisting of three fully connected nodes.

14. The domain partitioning engine of claim 10, further comprising:

means for identifying a number of anchor nodes;

means for combining the supernodes into a number of clusters;

means for generating each of the number of clusters around each of said number of anchor nodes, such that each cluster includes only one anchor node; and

means for generating the number of domains from the clusters.

15. The domain partitioning engine of claim 14, further comprising means for balancing a weight of the graph between the number of domains.

16. The domain partitioning engine of claim 10, wherein the nodes represent switches in a computer network and the edges represent links between the switches.

17. The domain partitioning engine of claim 10, wherein the nodes represent components of a VLSI chip and the edges represent interconnections among the components.

18. The domain partitioning engine of claim 10, wherein the nodes represent tasks to be performed on a computer in a distributed computing system and the edges represent data dependencies among the tasks.

19. A method for using a computer to automatically partition a graph comprising a plurality of nodes interconnected by edges, the method comprising:

(a) identifying a plurality of supernodes, each supernode comprising one or more plurality of nodes;

(b) forming clusters including one or more of the identified supernodes; and

(c) forming partitions from the clusters.

20. The method of claim 19, wherein the forming partitions step includes a step of forming partitions such that links identified as weak links are not included within any one partition.

21. The method of claim 19, wherein the step (b) comprises the steps of:

combining supernodes having two or more nodes in common into a cluster, wherein a cluster is a set of nodes in which each node in the set is linked to at least two other nodes in the set;

absorbing supernodes which share two or more nodes with a cluster into the cluster; and

separating clusters having a node in common by removing the common node from one of the clusters.

22. The method of claim 19, wherein each of the nodes includes a quantifiable characteristic, the method further comprising the steps of:

(d) determining a sum of the quantifiable characteristic for each cluster; and

(e) manipulating the clusters such that the sum of the quantifiable characteristic for each cluster falls within a range.

23. The method of claim 22, wherein, if the sum of a particular domain falls above the range, step (e) comprises steps of:

detecting an adjacent domain having a smaller sum; and

transferring a node from the particular domain to the domain having a smaller sum.

24. The method of claim 22, wherein, if the sum of a particular domain falls below the range, step (e) comprises the steps of:

detecting an adjacent domain having a greater sum; and

transferring a node from the domain having a greater sum to the particular domain.

25. The method of claim 19, wherein the nodes represent switches in a computer network and the edges represent links between the switches.

26. The method of claim 25, wherein each of the nodes includes a number of ports, the method further comprising the steps of:

(d) determining a sum of the number of ports in each cluster; and

(e) manipulating the clusters such that the sum of the ports of each cluster falls within a range.

27. The method of claim 19, wherein the nodes represent tasks to be performed on a computer in a distributed computing system and the edges represent dependencies among the tasks.

28. The method of claim 19, wherein the nodes represent components on a VLSI chip and the edges represent interconnections among the components.

29. A method of automatically partitioning a graph into domains, the graph having a plurality of nodes interconnected by a plurality of edges, the method comprising:

identifying a number of anchor nodes in the graph; and

combining the nodes into a number of control groups, which number is the same as the number of domains, such that each control group includes only one anchor node.