Identifying compatible system configurations

Patent metadata

Field	Value
Publication number	US-9716625-B2
Application number	US-201314049634-A
Country	US
Kind code	B2
Filing date	Oct 9, 2013
Priority date	Oct 9, 2013
Publication date	Jul 25, 2017
Grant date	Jul 25, 2017

Abstract

Methods, systems, and articles of manufacture for identifying compatible system configurations are provided herein. A method includes generating a second graph from a first graph of multiple devices in a network and 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 a sub-graph of two or more linked nodes in the second graph that is 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 are compatible based on the set of one or more network compatibility rules; and determining each of one or more changes needed to convert a current configuration in the network to a target configuration specified by the sub-graph.

First claim

What is claimed is:

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, whe

Assignees

• IBM

Inventors

• Song Yang
• Singh Aameek
• Griffin Thomas D
• Butler Eric
• Jadav Divyesh
• Mandagere Nagapramod
• Alatorre Gabriel

Classifications

• H04L47/829

  Topology based · CPC title

• H04L41/082 Primary

  the condition being updates or upgrades of network functionality · CPC title

• H04L41/12

  Discovery or management of network topologies · CPC title