Methods and apparatus for performance management using self-adjusting model-based policies

[0002] The present invention relates generally to automating operations in accordance with performance management systems and, more specifically, to facilitating the specification of exceptional conditions in such systems.

[0003] Approximately 80% of the cost of networked systems can be attributed to management and operations. These costs are related to activities such as distributing and installing software, providing help desk support, and detecting performance and availability problems.

[0004] Generally, existing practice for detecting performance and availability problems consists of the following steps: (i) determining a set of metrics to monitor that indicate the presence of problems (e.g., CPU utilization, error rates, transaction request rates); (ii) establishing thresholds on the values of these metrics based on past experience; (iii) using management system software to detect threshold violations; and (iv) responding to threshold violations by taking actions (e.g., adjusting user priorities, restricting the admission of traffic into the network).

[0005] So fundamental are these steps to existing practice that the information that drives them is typically externalized as management.“policies.” A policy consists of a metric (or function of multiple metrics), a relational operator that specifies the direction of change in the metric that is undesirable, a threshold value, and an action to take when the threshold is violated.

[0006] Typically, policies are expressed as if-then rules. The if-part (or left-hand side, LHS, of the policy) contains a predicate expressed as a bound on one or more metrics. The then-part (or right-hand side, RHS, of the policy) contains the action to take. An example is: “If CPU utilization is greater than 90%, then alarm.” Here, “CPU utilization” is the metric, the relational operator is “greater than,” the threshold value is “90%,” and the action is “alarm” (e.g., send an urgent message to the operations console). The threshold value for alarms may be chosen so that it lies well beyond what is considered normal. We use the term “alarm threshold” for the metric value that, if exceeded, results in either the generation of an alarm or a management action (e.g., terminate a process). Existing approaches check for threshold violations and, when these violations occur, initiate the action specified in the right-hand side of the policy.

[0007] In practice, policies have another aspect as well. In order to eliminate transients, it is often the case that the right-hand side of a policy is executed only after the left-hand side of the policy has been satisfied for several successive time intervals. Thus, a common version of the foregoing example is: “If CPU utilization is greater than 90% for three successive time intervals, then alarm.” Thus, embedded within the left-hand side of policies in existing art are higher level policies that determine when the right-hand side should be executed. An example of such a higher level policy is “for three successive time intervals,” as in the foregoing example.

[0008] Existing art provides for policy authoring and execution. That is, administrators typically have a graphical user interface through which they specify policy metrics, threshold values, relational operators, and actions. The management system acquires the data necessary to test the left-hand side of a policy and to execute the right-hand side of a policy.

[0009] In order to author policies, administrators must specify one or more values for alarm thresholds (e.g., 90% CPU utilization). Doing so can be quite burdensome since the appropriate choice for an alarm threshold depends on factors such as configuration and workload. To complicate matters, workloads are time varying and so the appropriate choice of threshold values is time varying as well.

[0010] Researchers have tried to address these difficulties by: (i) computing threshold values from historical data (e.g., J. Buzen and A. Shum, “MASF-Multivariate Adaptive Statistical Filtering,” Proceedings of the Computer Measurement Group, pp. 1-10, 1995; and L. Ho et al., “Adaptive Network/Service Fault Detection in Transaction-Oriented Wide Area Networks,” Integrated Network Management VI, edited by M. Sloman et al., IEEE Publishing, 1999); and (b) developing multivariate tests for network-based problems (e.g., M. Thottan and C. Ji, “Fault Prediction at the Network Layer Using Intelligent Agents,” Integrated Network Management VI, edited by M. Sloman et al., IEEE Publishing, 1999), and automating the updates of threshold values (e.g., Ho et al. article).

[0011] Even so, existing art is deficient in two respects: (1) there is no mechanism for automated adaptation of alarm thresholds tested by agents on managed elements; and (2) higher level policies are embedded within the left-hand sides of the policies in existing art and hence changing these policies often requires extensive modifications to the management automation. Note that item (1) requires more than the distribution of new threshold values (e.g., as in Ho et al.). It also requires a means to determine when threshold values should be changed.

[0012] In addition to the foregoing, existing art is deficient in the manner in which “warning policies” are handled. Warning policies provide advanced notice of alarm situations so that management staff can detect problems before they lead to widespread disruptions. In the existing art, warning policies are constructed manually by administrators. That is, administrators must specify a set of warning thresholds in addition to the alarm thresholds. Violating a warning threshold causes a message to be sent to the operations staff. Below is an example of a warning threshold for the previously introduced policy for CPU utilization: “If CPU utilization is greater than 80% for three successive time intervals, then warn.”

[0013] In existing practice, warning thresholds are specified in the same manner as alarm thresholds. Thus, there is no insight as to when or if the alarm threshold will be violated once a warning threshold is violated. Further, administrators are burdened with specifying still more thresholds.

[0014] The present invention provides methods and apparatus that reduce the burden on administrators for performance management. The methods and apparatus use models of metric values to construct and enforce: (1) alarm policies that adjust automatically to changes, for example, in configuration, topology, and workload; and (2) warning policies based on the probability of violating an alarm policy within a time horizon.

[0015] It is to be appreciated that a performance management system of the present invention preferably utilizes forecasting models (e.g., analysis of variance and time series models) to capture non-stationarities (e.g., time-of-day variations) and time-serial dependencies. For example, as described in J. Hellerstein, F. Zhang, and P. Shahabuddin, “An Approach to Predictive Detection for Service Level Management,” Integrated Network Management VI, edited by M. Sloman et al., IEEE Publishing, May 1999, the disclosure of which is incorporated herein by reference, a model in which S(i,j,k,l) is the value of a metric at time of day (i), day of week (j), month (k), and instance (l) may be employed in accordance with the invention. The model is: S(i,j,k,l)=mean+mean_tod(i)+mean_day-of-week(j)+mean_month(k)+e(i,j,k,l). Here, the terms beginning with “mean” are constants that are estimated from the data, and e(i,j,k,l) are the residuals of S. These constants may be estimated using standard statistical techniques such as analysis of variance and least square regression, which are well known in the art. The residuals are identically distributed (stationary), but time serial dependencies may remain. To remove time serial dependencies, a second model may be used: e(t)=a1*e(t−1)+a2*e(t−2)+y(t), where a1 and a2 are constants estimated from the data and the y(t) are independent and identically distributed normal random variables. The y(t) are the result of removing the time serial dependencies. Advantageously, with these two models, it is possible to forecast future values of metrics.

[0016] In addition to using models of metric behavior, the invention also utilizes the idea of separation of different kinds of information. Sometimes referred to as explicit knowledge representation, this technology has been used widely in the construction of expert systems. We use explicit knowledge representation to isolate the conditions for triggering right-hand sides from the other elements of a policy.

[0017] The present invention preferably deals with two kinds of policies. The first kind of policies, referred to as “control policies,” address the essence of the left-hand side of existing policies: identifying the metrics to be tested and the directional change in these metrics that constitutes an exceptional situation. The second kind of policies, referred to as “meta policies,” determine how control policies are interpreted. Meta policies address the following: (a) the acceptable level of false alarms; (b) the choice of alarm threshold (based on metric models and false alarm policies); (c) when models should be reconstructed; and (d) when warnings are generated.

[0018] We begin with control policies. These consist of three parts: (a) a simplified left-hand side; (b) a right-hand side having a similar form as in the existing art; and (c) a class (or label) that identifies the relevant meta policies. The left-hand side contains: (1) a metric to check; and (2) an indicator of directional change for the metric. An example of a control policy is:

[0019] CLASS_FILE.SERVER: If CPU utilization is too large, then alarm.

[0020] Here, CLASS_FILE.SERVER is a label that identifies the meta policies that apply to the control policy. The left-hand side of the policy specifies the metric to be tested, i.e., “CPU utilization,” and the directional change that is considered excessive, i.e., “too large.”

[0021] We consider four kinds of meta policies. For each, there is a class description that specifies the control policies for which the meta policy applies. This description can be expressed in many ways including, for instance, the use of scope hierarchies and wild cards. For example, the class description CLASS_*.SERVER matches the class CLASS_FILE.SERVER, where the symbol * denotes the wild card position.

[0022] Considered first are false alarm policies. These policies are used in combination with the metric models to determine threshold values to test. False alarm policies are expressed as an upper limit on the probability of a false alarm. For example:

[0023] False alarm policy for CLASS_*.SERVER: Probability(false alarm)<0.05

[0024] False alarm policies are employed as follows. For each control policy that matches the class description CLASS_*.SERVER, the control policy's metric is identified, and the associated metric model is located. This model is used to determine the metric's 95th percentile for the time interval in which the control policy is being evaluated, which is used as the alarm threshold. The observed value of CPU utilization is then compared to this threshold.

[0025] Considered next are a trigger policies. A trigger policy specifies the circumstances under which a satisfied left-hand side of a policy will cause the right-hand side of the policy to execute. According to an embodiment of the invention, we specify the number of times that the left-hand side must be satisfied within a specified number of evaluations. For example:

[0026] Trigger policy for CLASS_*.SERVER: Execute right-hand side if the left-hand side is satisfied three times in three evaluations.

[0027] This trigger policy applies to all control polices with classes that have SERVER as the last component. The right-hand side of the policy will be executed if the left-hand side of the policy is satisfied three times in succession. A control policy is said to be “enabled” if it satisfies its trigger policy.

[0028] A third kind of meta policy addresses the conditions under which warnings are generated. There are two parts to this specification. The first indicates the time horizon in which a warning is desired. The second dictates how certain it must be that the alarm threshold will be violated. An example is:

[0029] Warning policy for CLASS_*.SERVER: Warn if the probability of violating the alarm threshold is greater than 0.7 in a 5 minute time horizon.

[0030] Note that there may be multiple warning policies for the same class of control policies, as long as the warning policies specify different time horizons. Further, observe that both warning and false alarm policies have a probability, although the semantics of this probability are different. Thus, from the point of view of information representation, a false alarm policy can be represented as a warning policy with a time horizon of zero.

[0031] The fourth meta policy dictates when the unknown constants in the metric model must be re-estimated based on the frequency of violation of alarm thresholds. This is specified in a manner similar to that used for trigger policies:

[0032] Model reconstruction policy for CLASS_*.SERVER: Reconstruct the model if the left-hand side is satisfied 8 times in 10 evaluations.

[0033] As will be illustrated in detail below, a performance management system of the invention may comprise a system manager to support the policies described herein which is responsible for one or more model-based policy agents that respectively reside on one or more managed elements. The system manager provides an interface for the administrator through which policies are authored and messages are reported. The model-based policy agent may preferably have the following components: an agent side policy controller, a model constructor, a threshold constructor, a control policy evaluator, and an action executor. In such an embodiment, the policy controller provides overall control of the agent. The model constructor estimates the unknown constants in the metric models that provide a way to predict future values and a method of determining the distribution of metric values for a particular system, e.g., time-of-day, etc. The threshold constructor uses the metric models and the false alarm policies to determine the value of alarm and warning thresholds. The control policy evaluator provides a mechanism for determining if the LHS of a policy is satisfied at a specific time. The action executor provides a means for executing the right-hand side of policies.

[0034] Specifically, an agent side policy controller according to the invention, may preferably perform the following operations: (i) invoke the model constructor for un-instantiated models; (ii) invoke the threshold constructor to determine metric thresholds in control policies based on policies for false alarms and warnings; (iii) invoke the control policy evaluator to determine which policies satisfy their left-hand sides; (iv) determine which control policies are enabled based on their trigger policies; (v) determine if model reconstruction is required based on model reconstruction policies; and (vi) invoke the action executor for enabled control policies.

[0035] The present invention provides many ways to reduce the burden of performance management. First, the invention eliminates the need for administrators to specify alarm thresholds. Instead, thresholds are computed dynamically based on historical data, metric models, and separately specified policies for false alarms and warnings.

[0036] Second, the present invention separates trigger policies from control policies. In existing practice, trigger policies are embedded within the left-hand side of policy rules. Thus, changing a trigger policy may require administrators to modify many policy rules. By separating trigger and control policies, we simplify the control policies and provide an easy way for administrators to adjust the manner in which transient problems are addressed.

[0037] Third, our invention provides a systematic way to provide warnings. In existing practice, warnings are provided in an ad hoc and cumbersome way in that additional policies must be constructed and the relationship between warnings and alarms is unclear. In contrast, the present invention provides a method for constructing warning policies automatically, without specifying metric thresholds. This is done by having warning policies that express the minimum probability of a threshold violation for which administrators want to be notified of a possible alarm at a future time. Through our invention, the burden imposed on administrators is greatly reduced, and the semantics of warnings are more clear.

[0038] Fourth, our invention employs model reconstruction policies that determine when metric models should be reconstructed automatically (e.g., due to changes in workload, configuration, or other factors). Such policies provide a means for automated adaptation of the model-based approach to performance management.

[0039] These and other objects, features and advantages of the present invention will become apparent from the following detailed description of illustrative embodiments thereof, which is to be read in connection with the accompanying drawings.

[0040] FIG. 1 is a block diagram illustrating a performance management system according to an exemplary embodiment of the present invention;

[0041] FIG. 2 is a block diagram illustrating a model-based policy agent according to an exemplary embodiment of the present invention;

[0042] FIG. 3 is a block diagram illustrating a hardware implementation of components of a performance management system according to an exemplary embodiment of the present invention;

[0043] FIG. 4 is a flow diagram illustrating a first portion of a method for interpreting model-based policies according to an exemplary embodiment of the present invention; and

[0044] FIG. 5 is a flow diagram illustrating a second portion of a method for interpreting model-based policies according to an exemplary embodiment of the present invention.

[0045] The present invention will be described below in the context of an exemplary system architecture. However, it is to be understood that the invention is not limited to a particular system architecture but is rather more generally applicable to use in systems in which it is desirable to reduce the burden on an system administrator with respect to system performance management functions.

[0046] Referring now to FIG. 1, a block diagram illustrating a performance management system according to an exemplary embodiment of the present invention is shown. In the system as shown, one or more business users 150 (150-1 through 150-N) respectively interact with one or more managed elements 100 (100-1 through 100-N). The number of business users may also differ from the number of managed elements. Each managed element may have one or more business applications 130 (130-1 through 130-K) that utilize platform services 110.

[0047] It is to be understood that the invention is not limited to any particular application, or business application for that matter. However, some examples of business applications 130 with which the invention may be employed are enterprise resource planning, inventory management, billing, payroll. Also, the invention is not limited to any particular platform services. However, examples of platform services 110 are memory management, file system access, network access, and name resolution.

[0048] On each managed element is also a model-based policy agent 120 that enforces performance management policies, as will be explained in detail below. The managed elements communicate with a manager 140 that is controlled by an administrative user 160 who is responsible for authoring and ensuring the distribution of management policies through the policy authoring, distribution, and reporting component 145. In particular, the manager 140 provides an administrator 160 a place to enter information into the following repositories: model reconstruction policies 205, alarm policies 225, control policies 210, and action trigger policies 220. Policy authoring, distribution, and reporting is well understood in the art. It involves, for example: entering information in a graphical user interface to be stored in a database, distributing databases to other machines, and reporting the results of events that take place on remote machines. Platform services 110 similar to the services provided for in the managed elements 100 may be provided in the manager 140. However, other services specific to the manager may be provided. One or more of these platform services allow the manager to communicate with the managed elements.

[0049] To elaborate on the contents of the policy repositories, the model reconstruction policies specify a class description and the number of times the policy must be satisfied for a specified number of evaluations of the policy. Alarm policies provide the means to construct alarm and warning thresholds. As such, each contains a class description, time horizon, and probability. The latter is interpreted as a probability of a false alarm in the case of alarm thresholds, and the probability of exceeding the alarm threshold in the case of warning thresholds. Control policies specify: a control policy identifier or CPID (a unique identifier for each control policy), policy class, metric, directional change of the metric that is considered undesirable, and action to take. Note that there may be multiple entries for a single CPID to provide for AND/OR logic that combines multiple individual thresholds. Action trigger policies include the class description and the number of times that the LHS of a control policy must be satisfied for a number of evaluations of the LHS.

[0050] Referring now to FIG. 2, a block diagram illustrating a model-based policy agent 120 according to an exemplary embodiment of the present invention is shown. In the model-based policy agent, an agent side policy controller 200 provides overall control and interacts with the platform services to update local copies of policy repositories and to report alarms and warnings to the manager 140. The agent side policy controller 200 invokes a model constructor 230 to estimate the values of unknown constants in models based on historical values of measurement data 215. The model constructor 230 produces values of metric models 250 for each control policy (or CPID). The operation of component 230 is well understood, as disclosed in the literature on time series forecasting, e.g., G.E.P. Box and G. M. Jenkins, “Time Series Analysis,” Prentice Hall, 1977. The agent 120 also includes a threshold constructor 235 which uses the metric models 250, metric history 215, and alarm policies 220 to compute values of alarm and warning thresholds in the model-based threshold repository 255. For example, such components and models which may be used to forecast future values of particular metrics are described above with regard to the above-referenced Hellerstein et al. article (“An Approach to Predictive Detection for Service Level Management,” Integrated Network Management VI, edited by M. Sloman et al., IEEE Publishing, May 1999), e.g., the forecasting or predictive models, S(i,j,k,l) and e(t). However, it is to be appreciated that other forecasting or predictive models may be used.

[0051] Control policies are evaluated using a CP (control policy) evaluator 240, which outputs control policy state information 260 by CPID, time horizon, and evaluation history. The CP evaluator evaluates threshold-based policies, except that threshold values are in the CP state repository 260 instead of being embedded within the policy itself. Indexing from the policy to the threshold in the repository is done in a straightforward way by using the CPID.

[0052] The CP state repository is used by the agent side policy controller to interpret action trigger policies and model reconstruction policies. The actions of enabled policies are written to the repository 265. An action executor 245 reads repository 265 and executes each action in turn.

[0053] Referring now to FIG. 3, a block diagram is shown of an illustrative hardware implementation for both a managed element (e.g., 100-1 through 100-N) and a manager 140 according to the invention. In one embodiment, a managed element 100 and a manager 140 may be respectively implemented in individual computer systems. Each computer system may include a processor 300 coupled to a memory 310 and I/O device(s) 320, as shown in FIG. 3.

[0054] It is to be appreciated that the term “processor” as used herein is intended to include any processing device, such as, for example, one that includes a CPU (central processing unit). The term “memory” as used herein is intended to include memory associated with a processor or CPU, such as, for example, RAM, ROM, a fixed memory device (e.g., hard drive), a removable memory device (e.g., diskette), flash memory, etc. In addition, the term “input/output devices” or “I/O devices” as used herein is intended to include, for example, one or more input devices, e.g., keyboard, mouse, etc., for inputting data to the processing unit, and/or one or more output devices, e.g., CRT display, printer, etc., for providing results associated with the processing unit. It is also to be understood that various elements associated with a processor may be shared by other processors. Accordingly, software components including instructions or code for performing the methodologies of the invention, as described herein, may be stored in one or more of the associated memory devices (e.g., ROM, fixed or removable memory, etc.) and, when ready to be utilized, loaded in part or in whole (e.g., into RAM) and executed by a CPU.

[0055] For example, in the case of a managed element, the processor 300 performs the functions associated with the various components running therein, e.g., the model-based policy agent 120. The memory 310 may be used by the processor for performing such functions and for storing data associated with the various repositories and results of the processes. The I/O devices may include one or more data input devices for inputting data, e.g., to be used in by the policy agent. The I/O devices may also include one or more data output devices for presenting a user with results associated with the functions performed in accordance with the various components, e.g., presenting a business user with an alarm or warning. By way of example, a display may present a user with a graphical user interface for viewing such results.

[0056] As indicated, both the managed elements and the manager may have such a hardware architecture as shown in FIG. 3. As such, the processor 300, memory 310 and I/O devices 320 in a computer system embodying a manager 140 permit an administrator to perform the functions and methodologies of the manager as are known and/or described herein.

[0057] Also, it is to be appreciated that the computer systems of the managed elements and the manager may be in communication with each other via conventional communication links, e.g., local area network, wide area network, etc. Further, as mentioned, more than one computer system may be employed to implement the components illustrated in a managed element or a manager.

[0058] Referring now to FIG. 4, a flow diagram is shown illustrating a first portion of a method for interpreting model-based policies according to an exemplary embodiment of the present invention. It is to be appreciated that a model-based policy agent such as illustrated in FIG. 2 may be employed to perform this methodology. As such, reference will be made to various components of the policy agent 120 in FIG. 2.

[0059] In step 400, metric data is updated. In step 410, an iteration loop is begun in which each control policy is examined. The control policy currently under consideration is denoted by CPID. Step 420 is reached if there is an unexamined control policy. This step consults repository 250 to determine if all of its entries for the current CPID have a variable referred to as “Instantiated?” equal to true. If this is not the case, step 430 is invoked to determine if there is sufficient data to estimate the unknown constants in the model(s) of the metric(s). in CPID. If this is not the case, control returns to step 410. If it is the case, then the model constructor 230 is invoked in step 440, and the metric models in repository 250 are updated. In step 450, thresholds are constructed for the metrics of CPID and written to repository 255. In step 460, the CP evaluator 240 is invoked for CPID and the repository 260 is updated. When all CPIDs have been processed, control passes to step 500 of FIG. 5 to be explained below.

[0060] FIG. 5 is a flow diagram illustrating a second portion of a method for interpreting model-based policies according to an exemplary embodiment of the present invention. Again, a model-based policy agent such as illustrated in FIG. 2 may be employed to perform this methodology and, as such, reference will be made to various components of the policy agent 120 in FIG. 2.

[0061] Step 500 selects the next control policy state from the CP state repository 260. In step 510, an “EvalHist” field of this entry is consulted to determine if it satisfies the appropriate action trigger policy in repository 225. If this is the case, then the action of the control policy is appended to the Enabled Actions (EA) repository 265. When the loop in step 500 terminates, control resumes at step 530, where a loop begins for each enabled action in the repository 265. The current entry is denoted by EA. In step 540, the EA is read and deleted from the enabled actions repository. In step 550, the action executor 245 is invoked for the action in entry EA. Once all entries in repository 265 have been processed, the method terminates.

[0062] To illustrate our invention, consider the management of routers, hubs, domain name servers and other elements in a network infrastructure. Each device has metrics it exposes, such as CPU utilization, bytes sent, and length of the run queue. Based on these metrics, the operations staff hopes to detect and isolate problems before they lead to performance degradations. Such exception checking requires control policies such as those outlined in our invention. However, workloads are time varying due to variations in user work schedules, business needs, and other factors. Further, the workloads vary from device to device depending on topology and department activities. Thus, providing exception checking in practice means establishing a large number of thresholds for different devices for their operation at different times of the day. This is quite burdensome if performed in the conventional manner.

[0063] Our invention provides a means to reduce the demands on the operations staff for performance management. Instead of specifying detailed policies for individual metrics, the staff provides higher level policies, such as “alarm if CPU utilization is too large.” Doing so only requires specifying one threshold instead of many. Further, the same policy can be used for multiple, disparate devices.

[0064] To provide this capability, our invention has a means for authoring policies, both control policies and meta policies. The enactment system of our invention provides a means for constructing models of metrics that determine the normal variation of metric values. The threshold constructor then combines the calculations in the model with the control policy specifications stated by the analyst. These compiled policies are evaluated dynamically by the CP evaluator, which determines if an exceptional situation exists.

[0065] Although illustrative embodiments of the present invention have been described herein with reference to the accompanying drawings, it is to be understood that the invention is not limited to those precise embodiments, and that various other changes and modifications may be affected therein by one skilled in the art without departing from the scope or spirit of the invention.