Hierarchical Forecasting of Web Server Workload Using Sequential Monte Carlo Training

摘要

Internet service utilities host multiple server applications on a shared server cluster (server farm). One of the essential tasks of the hosting service provider is to allocate servers to each of the websites to maintain a certain level of quality of service for different classes of incoming requests at each point of time, and optimize the use of server resources, while maximizing its profits. Such a proactive management of resources requires accurate prediction of workload, which is generally measured as the amount of service requests per unit time. As a time series, the workload exhibits not only short time random fluctuations but also prominent periodic (daily) patterns that evolve randomly from one period to another. We propose a solution to the Web server load prediction problem based on a hierarchical framework with multiple time scales. This framework leads to adaptive procedures that provide both long-term (in days) and short-term (in minutes) predictions with simultaneous confidence bands which accommodate not only serial correlation but also heavy-tailedness, and nonstationarity of the data. The long-term load is modeled as a dynamic harmonic regression (DHR), the coefficients of which evolve according to a random walk, and are tracked using sequential Monte Carlo (SMC) algorithms; whereas the short-term load is predicted using an autoregressive model, whose parameters are also estimated using SMC techniques. We evaluate our method using real-world Web workload data