JP2006526842A - Method and apparatus for system management using codebook correlation with symptom exclusion - Google Patents

Abstract

A method and apparatus are provided for correlating events in a system. Problems and other events can be detected, for example, in a system that generates signs or observable events. A computer-accessible codebook is provided that includes a mapping between each of a plurality of possible indications in a system and one of a plurality of likely exceptional events (eg, problems). The system is monitored and one or more known signs generated by the system are detected. Using a computer, each of the multiple groups of possible signs in the mapping and one or more known signs, ignoring the signs in the groups of possible signs that were not determined to be known The amount of mismatch is determined. One or more of a plurality of possible problems corresponding to one of the plurality of groups having the smallest amount of mismatch are selected.

Description

(Related application)
The present invention is based on patent document 1 filed on March 31, 2003, which is hereby incorporated by reference in its entirety, and claims priority from this application.

  This application relates generally to event correlation in complex systems that use codebook correlation techniques to relate events such as problems to observable events such as symptoms, and in particular some observable events are uncertain. It relates to using codebook correlation to determine the root problem or other event when it is or is unknown.

  Codebook correlation is a technique used to identify the root cause of problems or other events in the system. Examples of codebook correlation techniques are all described in Patent Document 2, Patent Document 3, and Patent Document 4 (herein referred to as “Yemi et al. Patents”) issued to Yekiam Yemini et al. The whole is incorporated here.

  Codebook correlation is applicable to virtually any system that generates events. Such systems include enterprise management systems, engineering systems, communication systems, networked information technology (IT) systems, distributed systems, application services, application servers, utility computing systems, automated control systems, grid computing systems, satellites, May include business processing systems, utility systems, power grids, biological systems, medical systems, weather systems, financial market systems, weapon systems, space vehicles, complex vehicles, medical diagnostics, and financial market analysis It is not limited.

  Briefly, codebook correlation correlates events using a data structure such as a mapping, eg, a table or graph that associates a particular event represented in a given column with other events represented in a given row. Deterministic or probabilistic approaches can be used. If a deterministic approach is used, the intersection of each row and column can be indicated as “1” if the event causes another event, and “0” otherwise. Alternatively, if a probabilistic approach is used, the intersection of each row “E2” and column “E1” can be denoted as “p”, assuming that the probability that E1 causes E2 is p.

  In one application, codebook correlation can be used to associate a particular event, such as a problem or other exceptional event, with an observable event, such as a symptom. Furthermore, any event that is exceptional or not can be associated with a symptom. In this case, the codebook table may have each row “S” corresponding to an indication and each column “P” corresponding to a problem. Using a deterministic approach, the intersection of each row and column can be indicated, for example, as “1” if the problem causes a symptom and “0” otherwise. Alternatively, the probability can be denoted as “p” for the intersection of each row S and column P, where P is the probability that P will cause S.

  Each column created in this way specifies a “signature” of the problem, ie it identifies a set of signs that the problem causes. Observers of operating system signs can use a sequence of codebooks to quickly identify each problem. Several extended and modified versions of these correlation techniques are described in the Yemini et al. Patent and are incorporated herein by reference.

  In some cases, the observed indications do not exactly match any of the signatures in the codebook problem (or other event). In such cases, the distance between the observed symptom and the problem signature can be determined to find a sufficiently close match. There are several possible ways to determine this distance. In the case of a deterministic codebook (with “1” and “0” in each column), one method is to count the number of inconsistencies between the signature and the observed indication. This number of inconsistencies defines the so-called Hamming distance between the observed indication and the signature. If the codebook sequence has probabilities, it involves finding the most likely combination of problems that produce the closest indication to the observed indication. For example, in this case, a specific definition of the distance between the observed indication and the signature can be used. David Alan Aussie Non-Patent Document 1 (hereinafter “Aussie Paper”), for example, in Section 5.2, shows the definition of such a distance and the observed signs and signatures according to this defined distance. It gives several algorithms (some of which use heuristics) that can find out how close they are.

  Indications generated by the system are usually detected by a subsystem, commonly referred to herein as a measurement means. Such instrumentation means detects events and relays them to the management system, but can also include, for example, hardware components associated with the elements of the system and software components (such as agents).

US Provisional Patent Application Serial No. 60 / 459,072 “System Management Using Codebook Correlation with Sign Exclusion” US Pat. No. 5,528,516 US Pat. No. 5,661,668 US Pat. No. 6,249,755 "Modeled Hypothetical Reasoning about Event Management and Correlation" (1998) Doctoral Dissertation, Columbia University

  The scheme used by instrumentation to detect symptoms may sometimes not poll all possible events in the system. In this case, there is no easy way to know if a sign has occurred or if the measuring means has failed to detect the sign. Therefore, it can be said that this symptom is in an “unknown” state, that is, it cannot be evaluated whether the symptom has occurred. This can lead to a false diagnosis of the root cause problem. An indication not in an “unknown” state is said to be in a “known” state.

  A method and apparatus are provided for correlating events in a system. In accordance with one or more embodiments of the present invention, problems and other exceptional events may be detected in a system that generates symptoms or observable events. Computer access including mapping between each of multiple groups of possible events (eg, indications) in the system and one of multiple other possible events, including but not limited to exceptional events (eg, problems) A possible codebook is provided. The system is monitored and one or more known symptoms generated by the system are detected. Using a computer, each of the plurality of possible signs in the mapping and one or more known signs as described above, ignoring the signs in the multiple groups of possible signs that were not determined to be known The amount of mismatch is determined. One or more of a plurality of possible problems corresponding to one of the plurality of groups having the smallest amount of mismatch are selected.

  These and other features will be readily apparent from the following detailed description, wherein embodiments of the invention are shown and described by way of illustration. As will be realized, the invention is capable of other and different embodiments, all without departing from the invention, some of which allow for modifications in various aspects. Accordingly, the drawings and description are to be regarded as illustrative in nature and not in a limiting or limiting sense for the scope of the application as set forth in the claims.

  The present application is generally directed to codebook correlation that allows accurate correlation to identify events (eg, problems) in the system even when there are unknown observable events or indications.

  Events may be lost due to loss or malfunction in the instrument or network. This case of a lost event can be distinguished from the case of an unknown event. An event may be unknown rather than a failure of the measuring means itself, for example because the measuring means may not be operating during a predetermined period of time when an event should be detected. For example, as described below, in the example network, the instrument may be a client to server query that can be determined to be successful or unsuccessful. The event may be lost in this case because the client may not have made any queries during a given period of time. The Yamini et al patent describes a process for handling lost events. Various embodiments of the present invention can handle both missing and unknown events.

  The various embodiments described herein refer primarily to two types of events: (1) observable events, particularly signs, and (2) exceptional events, particularly problems. However, it should be understood that embodiments of the present invention are applicable to various types of events that are not limited to signs and problems. For example, exceptional events can include a wide variety of events including normal operation of the system.

    Referring back to the original codebook scheme described in the Yemini et al patent, the presence of each unknown sign will typically increase the Hamming distance between the problem signature and the observed sign. . This result can be an inaccurate diagnosis of the problem. For example, FIG. 1 shows a graphical representation of an exemplary web-based application having several clients connected to a web server. These clients may detect problems in the system when an attempt to query the web server is unsuccessful. Therefore, each client inquiry also serves as a measuring means for detecting the indication “client inquiry failure”.

  FIG. 2 illustrates a possible way in which the codebook approach described in the Yemini et al. Patent can represent problems and symptoms associated with the system of FIG. Each row in the table of FIG. 2 identifies an observable symptom, whereas each column identifies a possible underlying problem. For example, the “client 1 query failure” indication may be due to a “web application down” problem or a “client 1 connection down” problem. On the other hand, the problem “Web Application Down” has the signature (1,1,1,1,1,1), that is, it produces all the observed signs (query from all clients 1-6) Will be diagnosed).

  Consider a situation where a web server crashes and brings down a web application. Assume that only clients 1 and 2 were accessing the web server. The signs seen by this system are depicted in FIG. Using the codebook of FIG. 2, the distance between the observed indication and the signature in question is 4 because 4 of the indications are missing. On the one hand, the distance between the signature and the combined problem of both the failure of the connection between the client 1 and the web server and the failure of the connection between the client 2 and the web server is simply zero. The system will therefore erroneously diagnose the root cause problem as a failure of both the connection between client 1 and the web server and the connection between client 2 and the web server.

  This diagnostic error occurred simply because some of the symptoms did not appear because the client was not accessing the web server. That is, the codebook correlation scheme in this case relied on the assumption that the instrumentation was accurate, i.e., the client was constantly accessing the server. Since this assumption did not hold, this codebook correlation scheme incorrectly concluded that the client connection was working when the client connection was actually in an unknown state. In fact, the connection between clients 3-6 and the web server should not have worked because the server was down.

  The approach according to one or more embodiments of the present invention can correctly identify the root problem even when some of the symptoms are unknown.

  A codebook correlation method according to one or more embodiments of the present invention is generally described with reference to FIG. A model of the system to be analyzed and a corresponding code book are given.

  In step 100, the system is monitored for signs and one or more signs are detected, for example, an event is detected indicating that the signs are being monitored. These signs are detected and are therefore shown as known signs. Signs that are indeterminate, ie unknown, are ignored. For example, in the web server / client example of FIG. 3, the indications for clients 3-6 would not be detected because clients 3-6 are not accessing the web server, and therefore clients 3-6 and web server An indication of the presence of communication between is indicated as unknown.

  In step 110, the known indication is applied to the codebook, ignoring entries in the codebook associated with the unknown indication. Since unknown signs are excluded from the problem signature, the method will diagnose the problem more accurately.

  An alternative method of codebook correlation according to one or more further embodiments of the present invention is generally described with reference to FIG. A model of the system to be analyzed and a corresponding code book are given. Every symptom in the system codebook model has an associated state attribute.

  At step 200, all state attributes are assigned an initial value of unknown to a state associated with a symptom.

  In step 210, when the value of the state attribute is unknown, the loss probability for the symptom is set to a high value, i.e., a value close to or equal to 100%.

  At step 220, the system is monitored for signs and one or more signs are detected, for example, an event is detected indicating that the signs are being monitored. These signs are detected and are therefore shown as known signs.

  In step 230, once an event is detected indicating that the symptom is being monitored and the attribute is set to a value other than unknown, the probability of loss for the system is reduced. The loss probability can be reduced to a low value, for example close to 0% or to 0%.

  At step 240, the signs are applied to the codebook taking into account their respective loss probabilities. This can be performed, for example, as follows. Let the loss probability set for sign S according to the previous steps be x. For each cell in the codebook that associates problem P with a symptom S having probability p, the new probability in the cell will be p × (1−x). Note that if an unknown sign has a loss probability x = 1, the cell will have 0. Some of the ways in which the codebook correlation technique can work with a probabilistic codebook are described in chapter 5 of the OH paper, particularly beginning at section 5.2. Since unknown signs are generally excluded from the problem signature, the method will more accurately diagnose the problem.

  Note that the probability p of the problem P that generates the symptom S may have been generated taking into account the probability of S missing or not observed. This may take into account the probability of S being a spurious sign. The Aussie paper, in particular in Chapter 5, explains how these probabilities can be taken into account to define the final probabilities in the codebook cell.

  According to one or more further embodiments of the present invention, the codebook may be “auto-tuned” based on event activity. If no events such as the client-web server query of FIG. 3 occur for clients 3-6, these corresponding symptoms are excluded from the affected problem signature. However, if the event occurs later, these corresponding symptoms can be restored to the problem signature.

  According to one or more further embodiments of the present invention, a time window can be specified that has a known associated state, each with a certain probability of being an indication. Periodically at the end of this window, all probabilities can be adjusted by increasing their uncertainties, i.e. the loss probability for all signs is high, e.g. close to or equal to 100%. Can be raised. This process can be used to adjust for any errors when detecting signs.

  For example, in the example of FIG. 3, an error in the system can create a false query between the client 4 and the web server that can result in observed symptoms. The time window embodiment will ultimately reduce the importance of such spurious events by reducing the probability of knowing the observed indication.

The following are non-limiting examples of codebook correlation applications according to one or more embodiments of the present invention.
(Web application failure)
Referring to FIG. 3, unknown signs coming from clients 3-6 will be removed or ignored from the codebook signature of FIG. In this case, the root cause is correctly detected as a web application failure because the distance between the observed indication and the signature in the adjusted codebook is zero. Note that the distance between the observed signature and the signature in the adjusted codebook for other candidate problems is at least 1.
(Client-server connection failure)
The example of FIG. 6 shows a client accessing a web server similar to the example of FIG. However, in the example of FIG. 6, the two transactions relating to the clients 1 and 2 are not responding, while the other clients 3 to 6 give correct responses.

  In this case, there is no unknown state, so the problem signature for web server down will not match the available indications. The system will correctly identify the root problem as the connection with clients 1 and 2 is down.

  Although the above examples and applications are generally network related, various embodiments of the present invention can be applied to enterprise management systems, engineering systems, communication systems, networked information technology (IT) systems, distributed systems, application services, applications. Server, utility computing system, automatic control system, grid computing system, satellite, business processing system, utility system, power grid, biological system, medical system, weather system, financial market system, weapon system, spacecraft It is widely applicable to a wide variety of systems including, but not limited to, simple transportation means, medical diagnosis, and financial market analysis.

  These codebook correlation methods described herein are preferably implemented on one or more general purpose or other computers. Typical computers are, for example, Intel Pentium (registered trademark), PowerPC (registered trademark), or RISC-based, and also include Windows (registered trademark), OS / 2 (registered trademark), Unix (registered trademark), etc. A personal computer or workstation platform that includes an operating system. As is well known, such machines include a display interface (graphical user interface or “GUI”) and associated input devices (eg, keyboard or mouse).

  The codebook correlation method is preferably implemented in software, so one preferred embodiment of the present invention is as a set of instructions (program code) in a code module that resides in a random access memory of a computer. Realized. This set of instructions, until requested by the computer, is stored in another computer memory, for example on a hard disk drive, or on an optical disk (for final use on a CD-ROM) or floppy disk ( It can be stored in removable memory (for end use in a floppy disk device) or downloaded over the Internet or some other computer network. Moreover, although the various methods described are conveniently implemented in a general purpose computer that is selectively activated or reconfigured by software, those skilled in the art will perform the specified method steps. It will also be appreciated that it may be implemented in hardware configured in such a way, in firmware, or even in a dedicated device.

  While the preferred embodiment of the invention has been described, it will be apparent that modifications can be made without departing from the spirit and scope of the invention.

  Any numbered steps in the attached method claims should not be construed as limiting the specific order in which the claimed steps are performed.

FIG. 2 is a graphical illustration of an exemplary web-based application having multiple clients connected to a web server. 2 is an exemplary table of codebooks showing possible mappings of problems and symptoms for the system shown in FIG. FIG. 2 is a graphical illustration of possible indications in the example web application of FIG. 1 regarding web server failure. 6 is a flow diagram illustrating a method for codebook correlation according to one or more embodiments of the invention. 6 is a flow diagram illustrating a method for codebook correlation according to one or more further embodiments of the present invention. FIG. 2 is a graphical illustration of possible indications in the example web application of FIG. 1 regarding client-server connection failures.

Claims (21)

(A) providing a mapping between each of a plurality of possible observable events of a plurality of groups in the system and one of a plurality of like corresponding events;
(B) monitoring the observable event to detect one or more known observable events generated by the system;
(C) possible observation of the plurality of groups in the mapping using a computer while ignoring observable events of the plurality of possible observable events that have not been determined to be known Determining a mismatch amount between each of the possible events and the one or more known observable events;
(D) selecting one or more of the plurality of likely events corresponding to one of the plurality of groups having a minimum mismatch amount; A way to detect.   The method of claim 1, wherein the likely corresponding event includes a problem.   The method of claim 1, wherein the computer accessible mapping includes a codebook.   The method of claim 1, wherein the mapping is deterministic.   The method of claim 1, wherein the mapping is probabilistic.   The method of claim 1, wherein the mismatch amount includes a Hamming distance.   The method of claim 1, wherein the mapping is computer accessible. (A) providing a mapping between each of a plurality of possible indications of a group in the system and one of a plurality of likely events;
(B) assigning an unknown value to all of the possible indications in the mapping;
(C) monitoring the indications to detect one or more known indications generated by the system;
(D) assigning a known value to the possible indications in the mapping corresponding to the one or more known indications;
(E) each of the possible indications of the plurality of groups having a known value in the mapping using a computer, ignoring the indications in the plurality of groups of possible indications having the value of unknown, and Determining an amount of mismatch between one or more known indications;
(F) selecting one or more of the plurality of likely events corresponding to one of the plurality of groups having the smallest mismatch amount, A way to detect.   The method of claim 8, further comprising the step of periodically repeating steps (c)-(f).   The method of claim 8, further comprising the step of periodically repeating steps (b)-(f).   The method of claim 8, wherein step (b) comprises assigning a high loss probability value to the indication.   The method of claim 8, wherein step (d) includes assigning a low loss probability value to the indication.   The method of claim 8, wherein the likely event includes a problem.   The method of claim 8, wherein the computer accessible mapping comprises a codebook.   The method of claim 8, wherein the mapping is deterministic.   The method of claim 8, wherein the mapping is probabilistic.   The method of claim 8, wherein the mismatch amount includes a Hamming distance.   The method of claim 8, wherein the mapping is computer accessible. (A) a computer-accessible codebook in which each value includes a matrix of values corresponding to a mapping between one of a plurality of possible known and unknown indications and one of a plurality of likely events in the system; Preparing steps;
(B) associating an approximately 100% loss probability with all unknown signs in the codebook;
(C) monitoring a plurality of indication data values representing a plurality of known indications generated by the system over time;
(D) reducing the loss probability for indications in the received codebook;
(E) an inconsistent amount between each of the plurality of groups of values in the codebook and the plurality of known symptom data values through the use of a computer, taking into account the probability of losing signs; Determining the amount of alignment;
(F) selecting one of the plurality of likely events corresponding to one of the plurality of groups having a minimum mismatch amount, and generating a plurality of indications A method for detecting problems in the system. A storage device for storing a computer accessible mapping between each of a plurality of possible observable events of a plurality of groups in the system and one of a plurality of likely corresponding events;
Means for monitoring the observable event and detecting one or more known observable events generated by the system;
Ignoring observable events in the plurality of groups of possible observable events that have not been determined to be known, while using a computer to identify possible observable events of the plurality of groups in the mapping Means for determining a mismatch amount between each and the one or more known observable events;
Detecting an event in the system comprising: means for selecting one or more of the plurality of likely events corresponding to one of the plurality of groups having a minimum mismatch amount Device to do. A computer for detecting an event in a system using a computer accessible mapping between each of a plurality of possible observable events of a plurality of groups in the system and one of a plurality of likely corresponding events A computer program product in a readable medium, the computer program product comprising:
Monitoring the observable event to detect one or more known observable events generated by the system;
Ignoring observable events in the plurality of groups of possible observable events that have not been determined to be known, while using a computer to identify possible observable events of the plurality of groups in the mapping Determining the amount of inconsistency between each and the one or more known observable events;
A computer program comprising instructions for causing a computer to select one or more of the plurality of likely events corresponding to one of the plurality of groups having a minimum mismatch amount. Product.

Images