Impact propagation in a directed acyclic graph

• US 8,301,755 B2
• Filed: 12/14/2007
• Issued: 10/30/2012
• 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
• Primary Examiner(s): Chankong, Dohm
• Assistant Examiner(s): UTREJA, NEERAJ K
• Application Number:
  US11/956,507
• Publication Number:
  US 20090157723A1
• Time in Patent Office: 1,782 Days
• Field of Search: 709/224
• US Class Current: 709/224
• 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, wherein the at least two states are respectively indicative of at least two operational statuses for their respective node;

associating one or more counts with at least some of the nodes, each count of the one or more counts for a given one of the nodes representing a number of the nodes having impact relationships with the given node with a respective one of the at least two states, wherein each state of the at least two states comprises one of a respective discrete operational status, a respective range of percentage availability or a respective range of throughput levels;

changing a state of a first of the nodes;

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

determining a 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 each discrete operational status is selected from the group consisting of a warning status, an alarm status, and an OK status.

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, wherein the at least two states are respectively indicative of at least two operational statuses for their respective node;

associating one or more counts with at least some of the nodes, each count of the one or more counts for a given one of the nodes representing a number of the nodes having impact relationships with the given node with a respective one of the at least two states, wherein each state of the at least two states comprises one of a respective discrete operational status, a respective range of percentage availability or a respective range of throughput levels;

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

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

updating counts associated with the one or more second nodes to reflect the state change in the one or more first nodes, and determining a 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 each discrete operational status is selected from the group consisting of a warning status, an alarm status, and an OK status.

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.