Identifying compatible system configurations

1. A method comprising:

generating a second graph from (i) a first graph of multiple devices in a network and (ii) a set of one or more network compatibility rules, wherein said generating comprises dividing each device in the first graph into multiple nodes in the second graph, and wherein each node in the second graph represents a valid configuration of a device in the first graph;

identifying multiple sub-graphs of two or more linked nodes in the second graph that are each isomorphic to at least a portion of the first graph, wherein the two or more linked nodes in the second graph represent two or more configurations that (i) are compatible based on the set of one or more network compatibility rules, and (ii) satisfy one or more constraints pertaining to device upgrades;

identifying each of the multiple sub-graphs in the second graph that corresponds to a valid upgrade plan, wherein said identifying comprises (i) verifying that each device has only one configuration in each of the multiple sub-graphs, and (ii) filtering out each of said sub-graphs that (a) is isomorphic but (b) does not satisfy a target configuration based on said verifying;

creating an upgrade plan arising from each of the remaining sub-graphs, wherein each upgrade plan is based on a determination of each of one or more changes needed to convert a current configuration in the network to said target configuration specified by the sub-graph from which the upgrade plan arises;

computing a cost associated with each of the upgrade plans via a cost function comprising at least the number of devices in the network requiring at least one configuration change under each of the upgrade plans; and

outputting a sub-set of the multiple upgrade plans that satisfy one or more pre-defined specifications based on the computed cost associated with each of the upgrade plans;

wherein the steps are carried out by at least one computing device.

2. The method of claim 1 , wherein said second graph comprises a compatibility graph.

3. The method of claim 1 , wherein said first graph comprises a network connectivity graph of multiple devices in the network.

4. The method of claim 1 , comprising:

repeating said dividing step for all devices in the first graph.

5. The method of claim 1 , wherein said identifying the multiple sub-graphs of two or more linked nodes in the second graph that are each isomorphic to at least a portion of the first graph comprises applying a graph matching algorithm to the first graph and the second graph.

6. The method of claim 1 , wherein said cost function further comprises the number of upgrade steps specified in the upgrade plan.

7. The method of claim 1 , wherein said cost function further comprises an estimated upgrade time required to execute the upgrade plan.

8. The method of claim 1 , comprising:

determining, for each pair of nodes in the second graph that are derived from two devices in the first graph, whether the pair is compatible based on the set of one or more network compatibility rules.

9. The method of claim 8 , comprising:

repeating said step of determining whether the pair is compatible, for each pair of nodes derived from two devices in the first graph.

10. The method of claim 1 , wherein said identifying each of the multiple sub-graphs in the second graph that corresponds to a valid upgrade plan comprises verifying that pair-wise compatibility is achieved for each pair of interconnected devices in the first graph.

11. An article of manufacture comprising a non-transitory computer readable storage medium having computer readable instructions tangibly embodied thereon which, when implemented, cause a computer to carry out a plurality of method steps comprising:

generating a second graph from (i) a first graph of multiple devices in a network and (ii) a set of one or more network compatibility rules, wherein said generating comprises dividing each device in the first graph into multiple nodes in the second graph, and wherein each node in the second graph represents a valid configuration of a device in the first graph;

identifying multiple sub-graphs of two or more linked nodes in the second graph that are each isomorphic to at least a portion of the first graph, wherein the two or more linked nodes in the second graph represent two or more configurations that (i) are compatible based on the set of one or more network compatibility rules and (ii) satisfy one or more constraints pertaining to device upgrades;

identifying each of the multiple sub-graphs in the second graph that corresponds to a valid upgrade plan, wherein said identifying comprises (i) verifying that each device has only one configuration in each of the multiple sub-graphs, and (ii) filtering out each of said sub-graphs that (a) is isomorphic but (b) does not satisfy a target configuration based on said verifying;

creating an upgrade plan arising from each of the remaining sub-graphs, wherein each upgrade plan is based on a determination of each of one or more changes needed to convert a current configuration in the network to said target configuration specified by the sub-graph from which the upgrade plan arises;

computing a cost associated with each of the upgrade plans via a cost function comprising at least the number of devices in the network requiring at least one configuration change under each of the upgrade plans; and

outputting a sub-set of the multiple upgrade plans that satisfy one or more pre-defined specifications based on the computed cost associated with each of the upgrade plans.

12. A system comprising:

a memory; and

at least one processor coupled to the memory and configured for:

generating a second graph from (i) a first graph of multiple devices in a network and (ii) a set of one or more network compatibility rules, wherein said generating comprises dividing each device in the first graph into multiple nodes in the second graph, and wherein each node in the second graph represents a valid configuration of a device in the first graph;

identifying multiple sub-graphs of two or more linked nodes in the second graph that are each isomorphic to at least a portion of the first graph, wherein the two or more linked nodes in the second graph represent two or more configurations that (i) are compatible based on the set of one or more network compatibility rules and (ii) satisfy one or more constraints pertaining to device upgrades;

identifying each of the multiple sub-graphs in the second graph that corresponds to a valid upgrade plan, wherein said identifying comprises (i) verifying that each device has only one configuration in each of the multiple sub-graphs, and (ii) filtering out each of said sub-graphs that (a) is isomorphic but (b) does not satisfy a target configuration based on said verifying;

creating an upgrade plan arising from each of the remaining sub-graphs, wherein each upgrade plan is based on a determination of each of one or more changes needed to convert a current configuration in the network to said target configuration specified by the sub-graph from which the upgrade plan arises;

computing a cost associated with each of the upgrade plans via a cost function comprising at least the number of devices in the network requiring at least one configuration change under each of the upgrade plans; and

outputting a sub-set of the multiple upgrade plans that satisfy one or more pre-defined specifications based on the computed cost associated with each of the upgrade plans.

13. A method comprising:

generating a second graph from (i) a first graph of multiple devices in a network and (ii) a set of one or more network compatibility rules, wherein said generating comprises dividing each device in the first graph into multiple nodes in the second graph, and wherein each node in the second graph represents a valid configuration of a device in the first graph;

identifying multiple sub-graphs of two or more linked nodes in the second graph that are each isomorphic to one or more portions of the first graph, wherein the linked nodes in the second graph represent two or more configurations that (i) are compatible based on the set of one or more network compatibility rules and (ii) satisfy one or more constraints pertaining to device upgrades;

identifying each of the multiple sub-graphs in the second graph that corresponds to a valid upgrade plan, wherein said identifying comprises (i) verifying that each device has only one configuration in each of the multiple sub-graphs, and (ii) filtering out each of said sub-graphs that (a) is isomorphic but (b) does not satisfy a target configuration based on said verifying;

generating an upgrade plan corresponding to each of the remaining sub-graphs, wherein each upgrade plan is based on each of one or more changes needed to convert a current configuration in the network to said target configuration specified by the corresponding sub-graph in the second graph;

computing a cost associated with each upgrade plan via a cost function comprising at least the number of devices in the network requiring at least one configuration change under each of the upgrade plans;

selecting one or more of the upgrade plans based on the computed cost associated with each upgrade plan; and

outputting the one or more selected upgrade plans;

wherein the steps are carried out by at least one computing device.