Impact Propagation in a Directed Acyclic Graph

• US 20090157723A1
• Filed: 12/14/2007
• Published: 06/18/2009
• Est. Priority Date: 12/14/2007
• Status: Active Grant

• Current Assignee: BMC Software Incorporated (KKR & Co., Inc.)
• Original Assignee: BMC Software Incorporated (KKR & Co., Inc.)
• Inventors: De Peuter, Geert, Bonnell, David
• Granted Patent: US 8,301,755 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06Q 10/10 Office automation; Time management

Abstract

A method, system and medium for efficiently propagating service impact data in a directed acyclic graph. One or more service components, impact rules and business rules will be grouped together into a directed acyclic graph and a related metadata array. Impact propagation uses related metadata array to minimize traversal of the graph. As nodes of the graph are updated to propagate impact data a determination is made as to when no further impact propagation is required and calculations are terminated without having to traverse the entire graph. This method will allow a system or business administrator to maintain real-time notification and visualization of, the impacted state of all objects in the graph.

Claims

1. A service model impact propagation method, comprising:

creating a data structure of a service impact model, the data structure having nodes representing components of the service impact model and having impact relationships between at least some of the nodes, each of the nodes having one of at least two states;

associating counts with at least some of the nodes, the count for a given one of the nodes tracking at least one of the two states for the nodes having impact relationships with the given node;

changing the state of a first of the nodes;

propagating impact of the change to the counts associated with one or more second of nodes having impact relationships with the first node; and

determining the state of the one or more second nodes with the counts.

2. The method of claim 1, wherein the data structure comprises a directed acyclic graph having the nodes for the components and having directed edges for the impact relationships.

3. The method of claim 1, wherein associating counts with at least some of the nodes comprises dynamically allocating storage for the counts when needed.

4. The method of claim 1, wherein associating the count for a given one of the nodes is performed only when at least one of the nodes having an impact relationship with the given node has one of the states designated as being tracked.

5. The method of claim 1, wherein the at least two states for the nodes are selected from the group consisting of—

at least two of a warning status, an alarm status, and an OK status for the components represented by the nodes;

at least two ranges of percentage availability for the components represented by the nodes; and

at least two ranges of throughput levels for the components represented by the nodes.

6. The method of claim 1, wherein propagating impact of the change terminates along the impact relationships at a given one of the second nodes when the state determined for the given node remains unchanged.

7. The method of claim 1, wherein propagating impact of the change to the counts comprises counting, for a given one of the second nodes, a number of other nodes having a given state and having an impact relationship with the given node.

8. The method of claim 1, wherein determining the state of the one or more second nodes with the counts comprises determining the state for a given one of the second nodes from the associated count tracking the state having a highest value.

9. The method of claim 1, wherein determining the state of the one or more second nodes with the counts comprises determining the state for a given one of the second nodes from the associated count tracking the state representing a worst of the at least two states.

10. The method of claim 1, wherein propagating impact of the change comprises generating one or more tasks, each of the tasks based on a depth of the one or more second nodes in the data structure.

11. The method of claim 10, further comprising:

collecting the tasks into a work list by depth; and

processing each depth in the work list in prioritized order.

12. A program storage device, readable by a programmable control device, comprising instructions stored on the program storage device for causing the programmable control device to implement the method of claim 1.

13. A service model impact propagation method, comprising:

creating a directed acyclic graph having nodes and directed edges, the nodes representing components of a service impact model, the directed edges representing impact relationships between at least some the components, each of the nodes having one of at least two states;

associating counts with at least some of the nodes, the count for a given one of the nodes tracking at least one of the states for the nodes having impact relationships with the given node;

receiving information about a change in one or more first of the nodes;

propagating impact of the change to one or more second of the nodes along the directed edges with the one or more first nodes by—

updating the counts associated with the one or more second nodes, and

determining the state for the one or more second nodes from the updated counts.

14. The method of claim 13, wherein associating the count for a given one of the nodes is performed only when at least one of the nodes having an impact relationship with the given node has one of the states designated as being tracked.

15. The method of claim 13, wherein the at least two states for the nodes are selected from the group consisting of—

at least two of a warning status, an alarm status, and an OK status for the components represented by the nodes;

at least two ranges of percentage availability for the components represented by the nodes; and

at least two ranges of throughput levels for the components represented by the nodes.

16. The method of claim 13, wherein propagating impact of the change terminates along the directed edges at a given one of the second nodes when the state determined for the given node remains unchanged.

17. The method of claim 13, wherein updating the counts associated with the one or more second nodes comprises counting, for a given one of the second nodes, a number of other nodes having a given state and having an impact relationship with the given node.

18. The method of claim 13, wherein determining the state for the one or more second nodes from the updated counts comprises determining the state for a given one of the second nodes from the associated count tracking the state having a highest value.

19. The method of claim 13, wherein determining the state for the one or more second nodes from the updated counts comprises determining the state for a given one of the second nodes from the associated count tracking the state representing a worst of the at least two states for the given node.

20. The method of claim 13, wherein propagating impact of the change comprises generating one or more tasks, each of the tasks based on a depth of the one or more second nodes in the directed acyclic graph.

21. The method of claim 20, further comprising:

collecting the tasks into a work list based on depth; and

processing each of the depths in the work list in prioritized order.

22. The method of claim 13, further comprising reducing storage requirements for the counts by using a technique selected from the group consisting of sparse arrays, hash tables, and hash tables keyed on state.

23. The method of claim 22, wherein propagating impact of the change comprises buffering state changes to the one or more first nodes in a batch window.

24. The method of claim 23, wherein buffering the state changes in the batch window comprises grouping the state changes together, and processing the state changes in a single pass of propagation through the directed acyclic graph.

25. A program storage device, readable by a programmable control device, comprising instructions stored on the program storage device for causing the programmable control device to implement the method of claim 13.