# US 8,751,867 B2 · Method and apparatus for root cause and critical pattern prediction using virtual directed graphs > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,751,867 B2 - Document ID: US8751867B2 - Status: Granted - Kind: B2 - Application number: 13/271,554 - Filed: 2011-10-12 - Published: 2013-04-18 - Granted: 2014-06-10 - Earliest claimed: 2011-10-12 - Assignees: VMware, Inc. - Applicants: Mazda A. Marvasti; Arnak Poghosyan; Ashot Harutyunyan; Naira Grigoryan - Inventors: Mazda A. Marvasti; Arnak Poghosyan; Ashot Harutyunyan; Naira Grigoryan - Web page: https://patentgrep.com/patent/US8751867B2 ## CPC - H04L 41/142: using statistical or mathematical methods - G06F 11/0706: {the processing taking place on a specific hardware platform or in a specific software environment} - G06F 11/079: {Root cause analysis, i.e. error or fault diagnosis (in a hardware test environment G06F11/22; in a software test environment G06F11/36)} - H04L 41/0631: using root cause analysis; using analysis of correlation between notifications, alarms or events based on decision criteria, e.g. hierarchy, tree or time analysis - H04L 41/065: {involving logical or physical relationship, e.g. grouping and hierarchies} - H04L 41/069: using logs of notifications; Post-processing of notifications - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract An approach to root cause determination in a complex systems based on monitoring and event data is disclosed. It includes a historical analysis of events with their probabilistic correlations. Applying information measures between the random variables which embody those events one can detect origins of problems and generate real-time recommendations for their locations in a hierarchical system. Estimation of system bottlenecks, as well as the risk of “black swan”-type events are also computed. The processes are based on a statistical processing of a virtual directed graph produced from historical events. ## Claims ### Claim 1 A method for determining a causative event in an information technology infrastructure comprising: collecting historical event data with a computer; generating an undirected graph, each node being an event and each edge being a joint probability of two events historically occurring simultaneously; generating a directed graph, each node being the event and each edge being a conditional probability of a second event occurring if a first event occurs; reducing the undirected graph by discarding edges based on mutual information calculated for each edge; reducing the directed graph by discarding edges that correspond to discarded edges of the undirected graph; and from the directed graph, creating and outputting an historical list of recommendations to a user, the historical list of recommendations comprising an at least one event deemed to be the most likely causative event. ### Claim 2 (depends on 1) The method of claim 1, further comprising comparing active events against the historical events of the directed graph; identifying current active events that correspond to events in the historical list of recommendations; and from the identified active events, creating and outputting a list of active mode recommendations comprising an at least one event deemed to be potentially a causative event. ### Claim 3 (depends on 1) The method of claim 1, wherein the creating and outputting of the historical list of recommendations comprises determining entropy for the nodes of the directed graph. ### Claim 4 (depends on 3) The method of claim 3, wherein the at least one event deemed to be the most likely causative event are the events having the lowest entropy. ### Claim 5 (depends on 3) The method of claim 3, wherein the creating and outputting of the historical list of recommendations further comprises determining a relative recommendation index. ### Claim 6 (depends on 5) The method of claim 5, wherein the at least one event deemed to be the most likely causative event are the events having the highest relative recommendation index. ### Claim 7 (depends on 5) The method of claim 5, wherein the creating and outputting of the historical list of recommendations further comprises: determining a list relative rank; wherein the at least one event deemed to be the most likely causative event are the events having the highest list relative ranks. ### Claim 8 (depends on 1) The method of claim 1, further comprising determining at least one of root nodes, critical nodes, critical paths, extreme paths, and critical sectors from at least one of the historical list of recommendations and the directed graph. ### Claim 9 (depends on 1) The method of claim 1, further comprising determining bottlenecks from at least one of the historical list of recommendations and the directed graph. ### Claim 10 (depends on 1) The method of claim 1, further comprising determining black swan events from at least one of the historical list of recommendations and the directed graph. ### Claim 11 A non-transitory machine readable medium with instructions stored thereon for determining a causative event in an information technology infrastructure comprising: collecting historical event data with a computer; generating an undirected graph, each node being an event and each edge being a joint probability of two events historically occurring simultaneously; generating a directed graph, each node being the event and each edge being a conditional probability of a second event occurring if a first event occurs; reducing the undirected graph by discarding edges based on mutual information calculated for each each edge; reducing the directed graph by discarding edges that correspond to discarded edges of the undirected graph; and from the directed graph, creating and outputting an historical list of recommendations to a user, the historical list of recommendations comprising an at least one event deemed to be the most likely causative event. ### Claim 12 (depends on 11) The machine readable medium of claim 11, further comprising comparing active events against the historical events of the directed graph; identifying current active events that correspond to events in the historical list of recommendations; and from the identified active events, creating and outputting a list of active mode recommendations comprising an at least one event deemed to be potentially a causative event. ### Claim 13 (depends on 11) The machine readable medium of claim 11, wherein the creating and outputting of the historical of recommendations comprises determining entropy for the nodes of the directed graph. ### Claim 14 (depends on 13) The machine readable medium of claim 13, wherein the at least one event deemed to be the most likely causative event are the events having the lowest entropy. ### Claim 15 (depends on 13) The machine readable medium of claim 13, wherein the creating and outputting of the historical list of recommendations further comprises determining a relative recommendation index. ### Claim 16 (depends on 15) The machine readable medium of claim 15, wherein the at least one event deemed to be the most likely causative event are the events having the highest relative recommendation index. ### Claim 17 (depends on 15) The machine readable medium of claim 15, wherein the creating and outputting of the historical list of recommendations further comprises: determining a list relative rank; wherein the at least one event deemed to be the most likely causative event are the events having the highest list relative ranks. ### Claim 18 (depends on 11) The machine readable medium of claim 11, further comprising determining at least one of root nodes, critical nodes, critical paths, extreme paths, and critical sectors from at least one of the historical list of recommendations and the directed graph. ### Claim 19 (depends on 11) The machine readable medium of claim 11, further comprising determining bottlenecks from at least one of the historical list of recommendations and the directed graph. ### Claim 20 (depends on 11) The machine readable medium of claim 11, further comprising determining black swan events from at least one of the historical list of recommendations and the directed graph.