Methods and apparatus for performing adaptive and robust prediction

• US 20040181370A1
• Filed: 03/10/2003
• Published: 09/16/2004
• Est. Priority Date: 03/10/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Surendra, Maheswaran, Froehlich, Steven E., Hellerstein, Joseph L., Mummert, Todd William, Lassettre, Edwin Richie
• Granted Patent: US 7,039,559 B2
• Time in Patent Office: Days
• US Class Current: 702/187
• CPC Class Codes: G06F 2209/5019 Workload prediction
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

Techniques for performing adaptive and robust prediction. Prediction techniques are adaptive in that they use a minimal amount of historical data to make predictions, the amount of data being selectable. The techniques are able to learn quickly about changes in the workload traffic pattern and make predictions, based on such learning, that are useful for proactive response to workload changes. To counter the increased variability in the prediction as a result of using minimal history, robustness is improved by checking model stability at every time interval and revising the model structure as needed to meet designated stability criteria. Furthermore, the short term prediction techniques can be used in conjunction with a long term forecaster.

Claims

1. An automated method of predicting a future attribute associated with an application, the method comprising the steps of:

obtaining a historical data set associated with the application for a given time interval; and

predicting the future attribute for the given time interval, based on the historical data set, using a prediction model, the prediction model being checked for stability in the given time interval and altered when determined to be unstable.

2. The method of claim 1, further comprising the step of adapting a size of the historical data set for a subsequent time interval based on a result of the predicting step for the given time interval.

3. The method of claim 2, wherein the size of the historical data set is also adapted based on at least one confidence value.

4. The method of claim 1, wherein the given time interval is approximately one of a second and a minute.

5. The method of claim 1, wherein the given time interval is relatively shorter than a time interval used by a seasonal forecasting model.

6. The method of claim 1, wherein the future attribute comprises a future workload level.

7. The method of claim 1, wherein the prediction model comprises an Auto-Regressive Integrated Moving Average (ARIMA) model.

8. The method of claim 1, wherein the prediction model is alterable by reducing an order of the model.

9. The method of claim 1, wherein the order of the model is iteratively reducible by an order of one.

10. The method of claim 1, wherein the predicting step further comprises the steps of:

estimating one or more model parameters of the prediction model;

checking the stability of the one or more model parameters;

altering a structure of the prediction model when the model is considered to be unstable; and

calculating the future attribute over a prediction horizon when the model is considered to be stable.

11. An automated method of predicting a future attribute associated with an application, the method comprising the steps of:

obtaining a historical data set associated with the application for a given time interval;

predicting the future attribute for the given time interval based on the historical data set; and

adapting a size of the historical data set for a subsequent time interval based on a result of the predicting step for the given time interval.

12. The method of claim 11, wherein the size of the historical data set is also adapted based on at least one confidence value.

13. An automated method of predicting a future attribute associated with an application, the method comprising the steps of:

obtaining a data set associated with the application;

providing forecasting capability for determining the future attribute based on at least a portion of the data set for a first time interval;

providing prediction capability for determining the future attribute based on at least a portion of the data set for a second time interval, wherein the second time interval is shorter than the first time interval; and

outputting a prediction result representative of the future attribute based on at least one of the forecasting capability and the prediction capability.

14. The method of claim 13, further comprising the step of checking the validity of data in the obtained data set.

15. The method of claim 13, wherein the forecasting capability comprises use of a seasonal forecasting model.

16. The method of claim 13, wherein the prediction capability comprises use of a prediction model.

17. The method of claim 16, wherein the prediction model comprises an Auto-Regressive Integrated Moving Average (ARIMA) model.

18. Apparatus for predicting a future attribute associated with an application, the apparatus comprising:

a memory; and

at least one processor coupled to the memory and operative to;

(i) obtain a historical data set associated with the application for a given time interval; and

(ii) predict the future attribute for the given time interval, based on the historical data set, using a prediction model, the prediction model being checked for stability in the given time interval and altered when determined to be unstable.

19. Apparatus for predicting a future attribute associated with an application, the apparatus comprising:

a memory; and

at least one processor coupled to the memory and operative to;

(i) obtain a historical data set associated with the application for a given time interval;

(ii) predict the future attribute for the given time interval based on the historical data set; and

(iii) adapt a size of the historical data set for a subsequent time interval based on a result of the predicting step for the given time interval.

20. Apparatus for predicting a future attribute associated with an application, the apparatus comprising:

a memory; and

at least one processor coupled to the memory and operative to;

(i) obtain a data set associated with the application;

(ii) provide forecasting capability for determining the future attribute based on at least a portion of the data set for a first time interval;

(iii) provide prediction capability for determining the future attribute based on at least a portion of the data set for a second time interval, wherein the second time interval is shorter than the first time interval; and

(iv) output a prediction result representative of the future attribute based on at least one of the forecasting capability and the prediction capability.

21. An article of manufacture for predicting a future attribute associated with an application, comprising a machine readable medium containing one or more programs which when executed implement the steps of:

obtaining a historical data set associated with the application for a given time interval; and

predicting the future attribute for the given time interval, based on the historical data set, using a prediction model, the prediction model being checked for stability in the given time interval and altered when determined to be unstable.

22. An article of manufacture for predicting a future attribute associated with an application, comprising a machine readable medium containing one or more programs which when executed implement the steps of:

obtaining a historical data set associated with the application for a given time interval;

predicting the future attribute for the given time interval based on the historical data set; and

adapting a size of the historical data set for a subsequent time interval based on a result of the predicting step for the given time interval.

23. An article of manufacture for predicting a future attribute associated with an application, comprising a machine readable medium containing one or more programs which when executed implement the steps of:

obtaining a data set associated with the application;

providing forecasting capability for determining the future attribute based on at least a portion of the data set for a first time interval;

providing prediction capability for determining the future attribute based on at least a portion of the data set for a second time interval, wherein the second time interval is shorter than the first time interval; and

outputting a prediction result representative of the future attribute based on at least one of the forecasting capability and the prediction capability.

24. A method of attempting to ensure satisfaction of one or more service objectives associated with the execution of an application, the method comprising the steps of:

contracting a service provider to host the application in accordance with the one or more service objectives; and

contracting the service provider to implement an automated system for predicting a future workload level associated with the application, the system being operative to;

(i) obtain a historical data set associated with the application for a given time interval; and

(ii) predict the future workload level for the given time interval, based on the historical data set, using a prediction model, the prediction model being checked for stability in the given time interval and altered when determined to be unstable.

25. A method of attempting to ensure satisfaction of one or more service objectives associated with the execution of an application, the method comprising the steps of:

contracting a service provider to host the application in accordance with the one or more service objectives; and

contracting the service provider to implement an automated system for predicting a future workload level associated with the application, the system being operative to;

(i) obtain a historical data set associated with the application for a given time interval;

(ii) predict the future workload level for the given time interval based on the historical data set; and

(iii) adapt a size of the historical data set for a subsequent time interval based on a result of the predicting step for the given time interval.

26. A method of attempting to ensure satisfaction of one or more service objectives associated with the execution of an application, the method comprising the steps of:

contracting a service provider to host the application in accordance with the one or more service objectives; and

contracting the service provider to implement an automated system for predicting a future workload level associated with the application, the system being operative to;

(i) obtain a data set associated with the application;

(ii) provide forecasting capability for determining the future workload level based on at least a portion of the data set for a first time interval;

(iii) provide prediction capability for determining the future workload level based on at least a portion of the data set for a second time interval, wherein the second time interval is shorter than the first time interval; and

(iv) output a prediction result representative of the future attribute based on at least on of the forecasting capability and the prediction capability.

27. An automated system for predicting a future attribute associated with a measurement source, the system comprising:

a long term forecaster for determining the future attribute based on a long term time interval and at least a portion of an input data set associated with the measurement source; and

a short term predictor for determining the future attribute based on a short term time interval and at least a portion of an input data set associated with the measurement source;

wherein a prediction result is output representative of the future attribute based on at least on of the long term forecaster and the short term predictor.

28. The system of claim 27, wherein the measurement source comprises one or more resources associated with an application.

29. The system of claim 28, wherein the future attribute comprises a workload level associated with the application.

30. The system of claim 27, wherein the short term predictor comprises an Auto-Regressive Integrated Moving Average (ARIMA) model.