Source: http://www.google.com/patents/US8112378?dq=5920316
Timestamp: 2014-12-28 01:00:01
Document Index: 731056445

Matched Legal Cases: ['art 311', 'art 311', 'art 312', 'art 312', 'art 311', 'art 311', 'art 311', 'art 312']

Patent US8112378 - Methods and systems for performing root cause analysis - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsA root cause analysis engine uses event durations and gradual deletion of events to improve analysis accuracy and reduce the number of required calculations. Matching ratios of relevant rules are recalculated every time notification of an event is received. The calculation results are held in a rule...http://www.google.com/patents/US8112378?utm_source=gb-gplus-sharePatent US8112378 - Methods and systems for performing root cause analysisAdvanced Patent SearchPublication numberUS8112378 B2Publication typeGrantApplication numberUS 12/213,257Publication dateFeb 7, 2012Filing dateJun 17, 2008Priority dateJun 17, 2008Also published asEP2291742A1, EP2341434A1, EP2341434A8, US8583581, US8732111, US20090313198, US20120117573, US20140025621, US20140229419, WO2009153901A1Publication number12213257, 213257, US 8112378 B2, US 8112378B2, US-B2-8112378, US8112378 B2, US8112378B2InventorsYutaka Kudo, Tetsuya Masuishi, Takahiro Fujita, Tomohiro MorimuraOriginal AssigneeHitachi, Ltd.Export CitationBiBTeX, EndNote, RefManPatent Citations (22), Non-Patent Citations (13), Referenced by (8), Classifications (15), Legal Events (1) External Links: USPTO, USPTO Assignment, EspacenetMethods and systems for performing root cause analysisUS 8112378 B2Abstract A root cause analysis engine uses event durations and gradual deletion of events to improve analysis accuracy and reduce the number of required calculations. Matching ratios of relevant rules are recalculated every time notification of an event is received. The calculation results are held in a rule memory in the analysis engine. Each event has a valid duration, and when the duration has expired, that event is deleted from the rule memory. Events held in the rule memory can be deleted without affecting other events held in the rule memory. The analysis engine can then re-calculate the matching ratio of each rule by only performing the re-calculation with respect to affected rules related to the deleted event. The calculation cost can be reduced because analysis engine processes events incrementally or decrementally. Analysis engine can determine the most possible conclusion even if one or more condition elements were not true.
BACKGROUND OF THE INVENTION According to recent trends, information technology (IT) systems of companies are becoming ever more large and complex. For example, in some businesses, the IT system is no longer just an infrastructure of the business, but needs to act in partnership with the business to increase the value and competitiveness of the business. Furthermore, the rapid growth of IT systems is not limited to very large companies, but even mid-sized companies can now have hundreds of servers. In addition, the rapid growth of server virtualization technology is causing an acceleration of this trend.
Typically, monitoring the health of an IT system and analyzing any problems that may arise is carried out using some form of availability and performance management software. This software usually includes the ability to discover devices in the IT system, identify their connections, and sometimes also identify locations where problems are occurring. Through use of such management software, administrators are relieved from a number of tedious operation tasks that they used to have to perform manually. However, as mentioned above, IT systems themselves are growing rapidly, while IT budgets are typically becoming more restricted. This has resulted in each administrator being responsible for managing a very large area of the IT system, and the size of these systems can make it difficult to determine the actual location and �root cause� of a problem that might occur. For example, some vendors provide root cause analysis products, but these products fail to provide any mechanisms for determining the time range of events to be inputted to the analysis engine. This means that calculation costs are inefficient and the accuracy of analysis is inadequate. Therefore, an on-going need exists for a solution to assist administrators in finding the root cause of failures, defects or other occurrences in an IT system environment.
The �Rete Matching Algorithm� is an example of the traditional expert system. This kind of expert system acts as a rule-based matching algorithm. As discussed by B. Schneier in �The Rete Matching Algorithm�, incorporated herein by reference below, the Rete algorithm was created in the late 1970s to speed up comparisons for pattern matching. Prior to the Rete algorithm, studies showed that older systems spent as much as 90% of their time performing pattern matching. These systems would iterate through the pattern matching process, taking each rule in turn, looking through the data memory to determine whether the conditions for a particular rule were satisfied, and then proceed to the next rule. Since then, methods have been found to index data elements and rule conditions for increasing efficiency, which speeds up program execution, but which still requires iterating through a series of rules and data elements. The Rete algorithm eliminates a large part of this iterative step, and hence, is a substantial improvement over competing algorithms.
Related art includes U.S. Pat. No. 4,727,487, entitled �Resource allocation method in a computer system�, to Masui et al.; U.S. Pat. No. 4,761,746, entitled �Dynamic reconstruction method for discrimination network�, to Tano et al.; U.S. Pat. No. 4,868,763, entitled �Knowledge-based system having plural processors�, to Masui et al.; U.S. Pat. No. 5,146,537, entitled �Method for judging whether conditions are satisfied by using a network having a plurality of nodes representing the conditions�, to Tano et al.; U.S. Pat. No. 5,353,385, entitled �Inference method and apparatus for use with knowledge base system and knowledge base system support method and apparatus using the inference method and apparatus�, to Tano et al.; U.S. Pat. No. 7,107,185, entitled �Apparatus and method for event correlation and problem reporting�, to Yemini et al.; U.S. Pat. No. 7,254,515, entitled �Method and apparatus for system management using codebook correlation with symptom exclusion�, to Ohsie et al.; Schneier, B., �The Rete Matching Algorithm�, Dr. Dobb's Journal, Dec. 5, 2002; and Forgy, C. L., �Rete: A fast algorithm for the many pattern/many object pattern matching problem�, ARTIFICIAL INTELLIGENCE, Vol. 19, no. 1, 1982, pp. 17-37, the entire disclosures of which are incorporated herein by reference.
BRIEF SUMMARY OF THE INVENTION Exemplary embodiments of the invention provide solutions which improve the accuracy and reduce the calculation costs associated with a root cause analysis. These and other features and advantages of the present invention will become apparent to those of ordinary skill in the art in view of the following detailed description of the preferred embodiments.
Furthermore, some portions of the detailed description that follow are presented in terms of algorithms and symbolic representations of operations within a computer. These algorithmic descriptions and symbolic representations are the means used by those skilled in the data processing arts to most effectively convey the essence of their innovations to others skilled in the art. An algorithm is a series of defined steps leading to a desired end state or result. In the present invention, the steps carried out require physical manipulations of tangible quantities for achieving a tangible result. Usually, though not necessarily, these quantities take the form of electrical or magnetic signals or instructions capable of being stored, transferred, combined, compared, and otherwise manipulated. It has proven convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers, instructions, or the like. It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise, as apparent from the following discussion, it is understood that throughout the description, discussions utilizing terms such as �processing�, �computing�, �calculating�, �determining�, �displaying�, or the like, can include the actions and processes of a computer system or other information processing device that manipulates and transforms data represented as physical (electronic quantities within the computer system's registers and memories into other data similarly represented as physical quantities within the computer system's memories or registers or other information storage, transmission or display devices.
FIG. 3 illustrates examples of Rules 301-305 which reside in the Rule Repository 131, and which are expanded rules propagated for the information system illustrated in FIG. 1. In general, a rule can be divided into two parts, a first part 311, which may be referred to as the �IF� part 311, and a second part 312, which may be referred to as the �THEN� part 312. The IF part 311 can comprise one or more condition elements. For example, Rule 301 has four conditions in the IF part 311, namely, �<ServerA iSCSI_Comm_Err>�, �<ServerB iSCSI_Comm_Err>�, �<ServerC iSCSI_Comm_Err>� and �<Storage1 Controller_Err>�. Accordingly, when an error event such as �iSCSI_Comm_Err� is received from �ServerA�, the condition �<ServerA iSCSI_Comm_Err>� becomes true. When all the conditions in the IF part 311 are true, then the conclusion element in the THEN part 312 is presumed to be true according to the particular rule. For example, Rule 311 has a conclusion element �<Storage1 Controller_Err>�. Thus, according to rule 301, ServerA, ServerB and ServerC report communication errors and Storage1 reports a controller error, rule 301 indicates that the root cause is a controller error at Storage1. In addition, there may occur a case in which a rule has more than one conclusion (i.e., the THEN part points to occurrences at more than one node, or the like). For example, the THEN portion of a rule may have more than one conclusion when it is preferred to define multiple rules that have the same conditions in each IF part, but different conclusions in each THEN part. For instance, when there are two rules such as �IF A B C THEN X� and �IF A B C THEN Y�, these rules can be combined and defined as one rule �IF A B C THEN X Y�.
FIG. 4 illustrates an exemplary diagram of rule memory associations for an object model stored in Rule Memory 121. In FIG. 4, there are three types of objects illustrated, namely, Condition Objects 401, Operator Objects 402 and Conclusion Objects 403. These objects and their connections are created by Rule Loader Program 122. Condition Object 401 includes four attributes, �Node Name�, which is the name of the node, �Event Type�, which is the type of event, �Received Time�, which is the time at which the event was received, and �Weight�, which is an assigned weighting value for the condition. The Operator Object 402 has an attribute, �Not�, which may be True or False. For example, if the condition element written in the rule is specified �NOT� unary operator, such as �<NOT Storage1 Volume_Err>�, the value of this attribute will be set as �True�; otherwise, the value will be set as �False�. Conclusion Object 403 has four attributes, namely, �Rule Name�, which specifies an identifier for the particular rule, �Node Name�, which specifies the nodes which are rules applied, �Cause�, which identifies the cause of the error, and �Matching Ratio� (MR), which indicates a probability of correctness, or in other words, MR value indicates the certainty that this conclusion as a root cause of an event. This object model is formed without duplication of the condition element. Rule Loader Program 122 omits the duplication when it creates Condition Object 401 according to the condition element defined in rules. By doing so, Event Writer Program 124 does not need to write event many times for one received event. Rules are represented by connecting Conclusion Object 403 and Operator Object 402. For example, Conclusion Object 403 a has four connections to Operator Objects 402 a, 402 b, 402 c and 402 d. Each Operator Object 402 is connected to exactly one Condition Object 401. So the IF part of �Rule1� consists of four conditions. Conclusion Object 403 b also has four connections to Operator Objects 402 a, 402 b, 402 c and 402 d. Operator Object 402 a is shared by Conclusion Object 403 a, 403 b and 403 c. �Matching Ratio� in exemplary embodiments of the invention is a certainty factor calculated at a rate according to which elements become true among the elements which constitute the total number of condition elements for a rule. The formula for calculating the matching ratio may be expressed as follows:
FIG. 5 illustrates an exemplary data structure of an Event Message 505 that is received by Event Receiver Program 123, such as from a monitoring agent on one of the monitored nodes. Event Message 505 includes three kinds of information, namely, �Node Type� 501, �Node Name� 502 and �Event Type� 503. Node Type 501 is the type of node that the event message relates to, such as server, network switch or storage. Node Name 502 is a unique name in the information system environment which can identify the particular IT node. Event Type 503 indicates the type of event that has taken place.
FIG. 8 illustrates an exemplary data structure of the Event Erase Task Table 134 that resides in the Monitoring Computer 101. Event Erase Task Table 134 is used for managing the valid duration of each received event. Event Erase Task Table 134 is filled-in by Event Writer Program 124 as events are received, and is used by Event Eraser Program 127 for determining when to begin erasing an event, and includes a Start Time 801, a Node Name 802, an Event Type 803 and an Attrition Rate 804. Start Time 801 is the date and time when an event erase task should start. Start Time 801 is calculated according to the formula: �Received Time 604+Valid Duration 703�. Node Name 802 is the internal node name and Event Type 803 is the type of event that caused the event message. Event Eraser Program 127 identifies the target Condition Object 401 by these two values (Node Name 802 and Event Type 803). Therefore, Node Name 802 and Event Type 803 are copied from Node Name 602 and Event Type 603 in Event Queue table 132. Attrition Rate 804 is copied from Event Erase Setting table 133.
In step 1314, Event Writer Program 124 sets the current date and time to �Received� attribute of the Condition Object 401 determined in step 1313.
In step 1315, Event Writer Program 124 sets �1.0� to �Weight� attribute of the Condition Object 401 retrieved in step 1313.
In step 1317, Event Writer Program 124 creates a task entry on Event Erase Task table 134 so that Event Eraser Program can execute the event erase task on the time specified in Event Erase Setting table 133. For example, if the entry in Event Queue Table 132 to be processed is entry 611 in FIG. 6, then the node type is a server, and the event type is an iSCSI communication error. Next, by referring to Event Erase Setting Table 133, at entry 711, for a server having an iSCSI communication error, the Valid Duration 701 is 10 minutes and the Attrition Rate 704 is 0.3 per minute. Accordingly, the task entry created Event Erase Task Table 134 in step 1317 in this example would be: Start Time 801=�Current Date and Time�+10 min.; Node Name 802=�ServerA�; Event Type 803=�iSCSI_Comm_Err�; and Attrition Rate 805=0.3.
In step 1406, Matching Ratio Evaluator Program 125 calculates the value of matching ratio (MR) according to the formula: �Total Weight/Number of Condition Objects� and sets the result to MR attribute of the corresponding Conclusion Object 403. For example, as illustrated in FIG. 4, the MR of Conclusion Object 403 a would be equal to 1.0 (i.e., 4.0/4).
In step 1605, Event Eraser Program 127 gets the Weight value from the Condition Object 401 retrieved in step 1604 and sets the Weight value of the retrieved Condition Object 401 to the result of �Weight minus Attrition Rate�. For example, if the weight value is equal to 1.0, and the attrition rate is equal to 0.3 points/minute, the new weight value for the Condition Object 401 would be equal to 0.7 for any matching ratio calculations made over the next minute. After a minute has passed, the weight value would again be decreased by 0.3 points down to 0.4 for matching ratios calculated in the following minute.
In step 1607, since the weight value is still greater than zero, Event Eraser Program 127 updates the Start Time 801 of this task entry on Event Erase Task table 134 as �Start Time 801+1 minute�.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4727487Jul 31, 1985Feb 23, 1988Hitachi, Ltd.Resource allocation method in a computer systemUS4761746Aug 19, 1986Aug 2, 1988Hitachi, Ltd.Dynamic reconstruction method for discrimination networkUS4868763Feb 17, 1987Sep 19, 1989Hitachi, Ltd.Knowledge-based system having plural processorsUS5146537Jun 13, 1989Sep 8, 1992Hitachi, Ltd.Method for judging whether conditions are satisfied by using a network having a plurality of nodes representing the conditionsUS5214653Oct 22, 1990May 25, 1993Harris CorporationFault finder expert systemUS5261086Oct 19, 1992Nov 9, 1993Nec CorporationPerformance analyzing and diagnosing system for computer systemsUS5353385Mar 29, 1991Oct 4, 1994Hitachi, Ltd.Inference method and apparatus for use with knowledge base system and knowledge base system support method and apparatus using the inference method and apparatusUS6938021 *Oct 18, 2002Aug 30, 2005Intertrust Technologies CorporationMethods for matching, selecting, narrowcasting, and/or classifying based on rights management and/or other informationUS7092914 *Feb 4, 2000Aug 15, 2006Intertrust Technologies CorporationMethods for matching, selecting, narrowcasting, and/or classifying based on rights management and/or other informationUS7107185Nov 1, 2005Sep 12, 2006Emc CorporationApparatus and method for event correlation and problem reportingUS7110983 *Oct 18, 2002Sep 19, 2006Intertrust Technologies CorporationMethods for matching, selecting, narrowcasting, and/or classifying based on rights management and/or other informationUS7143066 *Oct 18, 2002Nov 28, 2006Intertrust Technologies Corp.Systems and methods for matching, selecting, narrowcasting, and/or classifying based on rights management and/or other informationUS7254515Jan 20, 2006Aug 7, 2007Emc CorporationMethod and apparatus for system management using codebook correlation with symptom exclusionUS7299244 *Dec 10, 2002Nov 20, 2007Hewlett-Packard Development Company, L.P.System and method for dynamic sequencing of a requirements-based workflowUS7430610 *Sep 4, 2001Sep 30, 2008Opyo, Inc.System and method for adjusting the distribution of an asset over a multi-tiered networkUS7447667 *Dec 11, 2002Nov 4, 2008International Business Machines CorporationMethod and knowledge structures for reasoning about concepts, relations, and rulesUS7752214 *Sep 4, 2001Jul 6, 2010Op40, Inc.Extended environment data structure for distributed digital assets over a multi-tier computer networkUS7769706 *Jun 22, 2009Aug 3, 2010International Business Machines CorporationMethod and system for obtaining a combination of faulty parts from a dispersed parts treeUS20060112061Nov 22, 2005May 25, 2006Masurkar Vijay BRule based engines for diagnosing grid-based computing systemsUS20060123278Oct 13, 2004Jun 8, 2006Petre DiniMethod and apparatus for generating diagnoses of network problemsWO2002078262A1Mar 21, 2002Oct 3, 2002Micromuse IncMethod and system for reducing false alarms in network fault management systemsWO2003005200A1Jul 8, 2002Jan 16, 2003Associates International Inc CMethod and system for correlating and determining root causes of system and enterprise events* Cited by examinerNon-Patent CitationsReference1 *A filtering algorithm of no backtracking key phrase set for real-time information monitoring, Huang Jian; Lu Jun; Ren Liyong; Hou Mengshu; Apperceiving Computing and Intelligence Analysis, 2009. ICACIA 2009. International Conference on Digital Object Identifier: 10.1109/ICACIA.2009.5361132 Publication Year: 2009 , pp. 144-147.2A. Hanemann, et al., Assured Service Quality by Improved Fault Management, Service-Oriented Event Correlation, 10 pp., Nov. 2004, USA.3 *An Edge Nodes Energy Efficient Hole Modeling in Wireless Sensor Networks, Fucai Yu; Younghwan Choi; Soochang Park; Euisin Lee; Ye Tian; Sang-Ha Kim; Global Telecommunications Conference, 2007. GLOBECOM '07. IEEE Digital Object Identifier: 10.1109/GLOCOM.2007.896 Publication Year: 2007 , pp. 4724-4728.4Charles L. Forgy, Dept. of Computer Science, Carnegie-Mellon Univeristy, Pittsburgh, PA 15213, USA, "Rete A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problems*", 1982-North-Holland, pp. 17-37.5Charles L. Forgy, Dept. of Computer Science, Carnegie-Mellon Univeristy, Pittsburgh, PA 15213, USA, "Rete A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problems*", 1982�North�Holland, pp. 17-37.6Dr. Dobb's, "The Rete Matching Algorithm", Dec. 5, 2002, http://www.ddj.com/article/printableArticle.jhtml;jsessionid=5Y4I0RVLH5ANMQSN. . . pp. 1-4.7J.M. Gupta et al., Preprocessor Algorithm for Network Management Codebook, Proceedings of the Workshop on Intrusion Detection and Network Monitoring, Apr. 1999, 11 pp., Santa Clara, CA, USA.8M. Hasan et al., A Conceptual Framework for Network Management Event Correlation and Filtering Systems, IEEE International Symposium on Integrated Management, May 1999, 14 pp., USA.9 *Remote monitoring of building structural integrity by a smart wireless sensor network, Morello, R.; De Capua, C.; Meduri, A.; Instrumentation and Measurement Technology Conference (I2MTC), 2010 IEEE Digital Object Identifier: 10.1109/IMTC.2010.5488136 Publication Year: 2010 , pp. 1150-1154.10S. Tano et al., Fast Pattern Match Algorithm for Knowledge Based Systems, Building Tool-EUREKA, Information Processing Society of Japan, Dec. 1987, 58 pp., vol. 28, No. 12, Japan.11S. Tano et al., St-Net Generation Algorithm for Fast Bidirectional Inference, Information Processing Society of Japan, Sep. 1989, 48 pp., vol. 30, No. 9, Japan.12S.A. Yemini et al., High Speed and Robust Event Correlation, IEEE Communications Magazine, May 1996, 9 pp., USA.13 *Syntax and semantics in a distributed speech understanding system, Hayes-Roth, F.; Mostow, D.; Acoustics, Speech, and Signal Processing, IEEE International Conference on ICASSP '76. vol. 1 Digital Object Identifier: 10.1109/ICASSP.1976.1170046 Publication Year: 1976 , pp. 421-424.* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS8429453 *Jul 16, 2009Apr 23, 2013Hitachi, Ltd.Management system for outputting information denoting recovery method corresponding to root cause of failureUS8429455 *Jul 28, 2010Apr 23, 2013Hitachi, Ltd.Computer system management method and management systemUS8583581 *Jan 10, 2012Nov 12, 2013Hitachi, Ltd.Method and system for performing root cause analysisUS8732111 *Sep 27, 2013May 20, 2014Hitachi, Ltd.Method and system for performing root cause analysisUS20110264956 *Jul 16, 2009Oct 27, 2011Hitachi, Ltd.Management system for outputting information denoting recovery method corresponding to root cause of failureUS20120017127 *Jul 28, 2010Jan 19, 2012Hitachi, Ltd.Computer system management method and management systemUS20120030346 *Jul 29, 2010Feb 2, 2012Hitachi, Ltd.Method for inferring extent of impact of configuration change event on system failureUS20120117573 *Jan 10, 2012May 10, 2012Hitachi, Ltd.Method and system for performing root cause analysis* Cited by examinerClassifications U.S. Classification706/47International ClassificationG06N5/02, G06F17/00Cooperative ClassificationH04L41/16, H04L41/12, H04L41/0681, G06F11/079, H04L41/046, H04L41/069, G06F11/0709, G06N5/025European ClassificationG06F11/07P6, G06F11/07P1A, H04L41/06E, H04L41/06GLegal EventsDateCodeEventDescriptionJul 28, 2008ASAssignmentOwner name: HITACHI, LTD.,JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:KUDO, YUTAKA;MASUISHI, TETSUYA;FUJITA, TAKAHIRO AND OTHERS;REEL/FRAME:21304/310Effective date: 20080725Owner name: HITACHI, LTD., JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:KUDO, YUTAKA;MASUISHI, TETSUYA;FUJITA, TAKAHIRO;AND OTHERS;REEL/FRAME:021304/0310RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google