Michel Fliess
email: michel.fliess@polytechnique.edu

Cédric Join
email: cedric.join@univ-lorraine.fr

Maria Bekcheva
email: maria.bekcheva@l2s.centralesupelec.fr

Alireza Moradi
email: alireza@inagral.com

Hugues Mounier
email: hugues.mounier@l2s.centralesupelec.fr

Easily implementable time series forecasting techniques for resource provisioning in cloud computing

Keywords: Cloud computing, computing resources, virtual machines, forecasting, time series, nonstandard analysis, trend, quick fluctuation, seasonality, estimation, machine learning

Workload predictions in cloud computing is obviously an important topic. Most of the existing publications employ various time series techniques, that might be difficult to implement. We suggest here another route, which has already been successfully used in financial engineering and photovoltaic energy. No mathematical modeling and machine learning procedures are needed. Our computer simulations via realistic data, which are quite convincing, show that a setting mixing algebraic estimation techniques and the daily seasonality behaves much better. An application to the computing resource allocation, via virtual machines, is sketched out.

I. INTRODUCTION

The fast development of cloud computing (see, e.g., [START_REF] Armbrust | A view on cloud computing[END_REF], [START_REF] Marinescu | Cloud Computing: Theory and Practice[END_REF]) is due to its tremendous benefits, which might be summarized by its pay-as-you-go (PAYG) feature. Providing adequate Quality-of-Service (QoS) and pricing necessitates obviously a good prediction of the workloads for a better resource provisioning. Several papers have already been written on this topic (see, e.g., [START_REF] Adegboyega | Time-series models for cloud workload prediction: A comparison[END_REF], [START_REF] Alkharif | Time-series analysis for price prediction of opportunistic cloud computing resources[END_REF], [START_REF] Amiri | Survey on prediction models of applications for resources provisioning in cloud[END_REF], [START_REF] Balaji | Non-linear analysis of bursty workloads using dual metrics for better Cloud Resource Management[END_REF], [START_REF] Calheiros | Workload predic-environments[END_REF], [START_REF] -K. Gueye | Coordinating self-sizing and self-repair managers for multi-tier systems[END_REF], [START_REF] Han | Analysing virtual machine usage in cloud computing[END_REF], [START_REF] Huang | Resource prediction based on double exponential smoothing in cloud computing[END_REF], [START_REF] Islam | Empirical prediction models for adaptive resource provisioning in the cloud[END_REF], [START_REF] Kaur | A resource elasticity framework for QoS-aware execution of cloud applications[END_REF], [START_REF] Kim | Evaluation of workload forecasting techniques for predictive cloud resource scaling[END_REF], [START_REF] Kumar | Workload prediction in cloud using artificial neural network and adaptive differential evolution[END_REF], [START_REF] Roumani | An empirical study on predicting cloud incidents[END_REF], [START_REF] Vazquez | Time series forecasting of cloud data center workloads for dynamic resource provisioning[END_REF], [START_REF] Ye | Long-term QoS-aware cloud service composition using multivariate time series analysis[END_REF], and the references therein). Various time series techniques prevail, especially those stemming from econometrics [START_REF] Mélard | Méthodes de prévision à court terme[END_REF], [START_REF] Tsay | Analysis of Financial Time Series[END_REF], artificial neural networks and deep learning [START_REF] Längkvist | A review of unsupervised feature learning and deep learning for time-series modeling[END_REF], [START_REF] Yan | Toward automatic time-series forecasting using neural networks[END_REF], or a mixture of both [START_REF] Zhang | Time series forecasting using a hybrid ARIMA and neural network model[END_REF]. They all need cumbersome mathematical modeling and/or machine learning procedures.

This communication suggests that another rather efficient approach to workload forecasting exists where the computer burden is much less demanding. This new viewpoint on time series, that was introduced ten years ago in financial engineering [START_REF] Fliess | A mathematical proof of the existence of trends in financial time series[END_REF], [START_REF] Fliess | A-t-on vraiment besoin d'un modèle probabiliste en ingénierie financière ?[END_REF], rests on a profound result [12] which was obtained via the language of nonstandard analysis [START_REF] Robinson | Non-standard Analysis[END_REF]. It has been successfully employed for the prediction of traffic flow on highways [START_REF] Abouaïssa | On short-term traffic flow forecasting and its reliability[END_REF] and mainly of photovoltaic energy [START_REF] Fliess | Prediction bands for solar energy: New short-term time series forecasting techniques[END_REF]. It is worth mentioning that the signals corresponding to the workloads here and to the solar power in [START_REF] Fliess | Prediction bands for solar energy: New short-term time series forecasting techniques[END_REF] are quite similar including their sampling.

Contrarily to many publications,

• deterministic and probabilistic/statistical modelings become useless and therefore also parameter identification and/or machine learning, • we are not trying to employ time series for taking into account quick oscillations of the workload. Realistic computer experiments [START_REF] Bekcheva | Meilleure élasticité "nuagique" par commande sans modèle[END_REF] show that intelligent proportional controllers, or iPs, which are derived from the model-free control setting [START_REF] Fliess | Model-free control[END_REF], achieve this elasticity property (see, e.g., [START_REF] Al-Dhuraibi | Elasticity in cloud computing: State of the art and research challenges[END_REF], [START_REF] Coutinho | Elasticity in cloud computing: a survey[END_REF]) very well. Lack of space prevents us to detail the computer implementations. Note however that this implementation of our algebraic tools has already been fruitfully completed not only with respect to time series (see, e.g., [START_REF] Fliess | Prediction bands for solar energy: New short-term time series forecasting techniques[END_REF]), but also in control engineering and signal processing (see, e.g., [START_REF] Andréa-Novel | Model-free control of longitudinal and lateral dynamics for automated vehicles[END_REF], [START_REF] Bekcheva | Meilleure élasticité "nuagique" par commande sans modèle[END_REF], [START_REF] Beltran-Carbajal | On-line parametric estimation of damped multiple frequency oscillations[END_REF], [START_REF] Rampazzo | Modelling, simulation and real-time control of a laboratory tide generation system[END_REF], [START_REF] Sira-Ramírez | Algebraic Identification and Estimation Methods in Feedback Control Systems[END_REF], [START_REF] Sira-Ramírez | Active Disturbance Rejection Control of Dynamic Systems: A Flatness Based Approach[END_REF]).

Our paper is organized as follows. Our viewpoint on time series is developed in Section II, as well as three prediction techniques. Computer simulations are displayed and discussed in Section III. An application to the computing resource allocation, via virtual machines, is sketched out in Section IV. Section V presents some concluding remarks.

II. TIME SERIES

A. Time series and nonstandard analysis 1) Nonstandard analysis: Nonstandard analysis was invented by Robinson [42] almost sixty years ago in order to give a rigorous definition of "infinitely small" and "infinitely large" numbers. For more readable initiations, see, e.g., [START_REF] Diener | Tutorial[END_REF], [START_REF] Diener | Analyse non standard[END_REF]. Let us emphasize that this unconventional achievement has also been employed in applied sciences (see, e.g., [START_REF] Harthong | Le moiré[END_REF]).

2) A nonstandard definition of time series: Take the time interval [0, 1]. Introduce as often in nonstandard analysis the infinitesimal sampling

T = {0 = t 0 < t 1 < • • • < t ν = 1}
where t i+1 -t i , 0 ≤ i < ν, is infinitesimal, i.e., "very small." A time series X is a function T → R.

Remark 1: In practice a time lapse of 1 minute should be viewed as quite small when compared to 1 day.

3) Quick fluctuations: A time series X : T → R is said to be quickly fluctuating, or oscillating, around 0 [12], if, and only if, its integral A Xdm [12] is infinitesimal for any appreciable interval A, i.e., an interval which is neither infinitely small nor infinitely large.

Remark 2: Let us emphasize that the probabilistic and/or statistical nature of those quick fluctuations do not play any role.

4) The Cartier-Perrin theorem: The Cartier-Perrin theorem [12] states 1 for a time series X : T → R satisfying a rather weak integrability assumption the following additive decomposition

X(t) = E(X)(t) + X fluctuat (t) (1)
where

• the mean E(X)(t) is Lebesgue integrable, • X fluctuat (t)
is quickly fluctuating. The decomposition (1) is unique up to an additive infinitesimal quantity.

Remark 3: Replace the word "mean" by trend, which is perhaps more popular, in financial engineering for instance. Set therefore

E(X)(t) = X trend (t)
Note however that the meaning of "trend" in the time series literature is most often quite different (see, e.g., [START_REF] Tsay | Analysis of Financial Time Series[END_REF]). Remark 4: Our mean or trend should be understood as being quite close to the familiar notion of moving average [START_REF] Mélard | Méthodes de prévision à court terme[END_REF], [START_REF] Tsay | Analysis of Financial Time Series[END_REF].

B. Three forecasting techniques

According to the Cartier-Perrin theorem (1) it only makes sense to forecast E(X)(t), i.e., the mean or the trend.

1) Scaled persistence and seasonality 2 : The persistence assumption reads in our context

X trend (t + h) = X trend (t) (2)
where h > 0. Obviously Equation (2) will too often yield poor predictions. That is why we introduce scaled persistency via the most classic notion of seasonality in the time series literature [START_REF] Mélard | Méthodes de prévision à court terme[END_REF], [START_REF] Tsay | Analysis of Financial Time Series[END_REF]. Our data, where the sampling period is equal to 1 minute, exhibit here a self-evident daily pattern. Equation (2) should then be replaced by

X trend (t + h) = X trend (t -1440 + h) X trend (t -1440) X trend (t) (3)
where

• 0 < h ≤ 60min, • X trend (t-1440+h)
X trend (t-1440) is a correcting multiplicative term corresponding to the daily seasonality,

• 1440 = 60×24 is the number of minutes during a single day. 2) Forecasting via algebraic estimation techniques 3 : Start with a polynomial time function 1 The presentation in [START_REF] Lobry | Nonstandard analysis and representation of reality[END_REF] is less technical. We highly recommend this paper. It also includes a fruitful discussion on nonstandard analysis. 2 Persistence and scaled, or smart, persistence are quite often discussed elsewhere in the literature, essentially perhaps in meteorology (see, e.g., [START_REF] Voyant | Periodic autoregressive forecasting of global solar irradiation without knowledge-based model implementation[END_REF], [START_REF] Voyant | Time series modeling and large scale global solar radiation forecasting from geostationary satellites data[END_REF]) and climatology (see, e.g., [START_REF] Mudelsee | Climate Time Series Analysis: Classical Statistical and Bootstrap Methods[END_REF]). 3 For the estimation techniques, see also [START_REF] Fliess | Non-linear estimation is easy[END_REF], [START_REF] Sira-Ramírez | Algebraic Identification and Estimation Methods in Feedback Control Systems[END_REF], and [START_REF] Mboup | Numerical differentiation with annihilators in noisy environment[END_REF] for more mathematical details. of degree 1. Rewrite thanks to classic operational calculus (see, e.g., [START_REF] Yosida | Operational Calculus[END_REF]) p 1 as

p 1 (t) = a 0 + a 1 t, t ≥ 0, a 0 , a 1 ∈ R,
P 1 = a 0 s + a 1 s 2
Multiply both sides by s 2 :

s 2 P 1 = a 0 s + a 1 (4)
Take the derivative of both sides with respect to s, which corresponds in the time domain to the multiplication by -t:

s 2 dP 1 ds + 2sP 1 = a 0 (5)
The coefficients a 0 , a 1 are obtained via the triangular system of equations ( 4)- [START_REF] Amiri | Survey on prediction models of applications for resources provisioning in cloud[END_REF]. We get rid of the time derivatives, i.e., of sP 1 , s 2 P 1 , and s 2 dP1 ds , by multiplying both sides of Equations ( 4)-( 5) by s -n , n ≥ 2. The corresponding iterated time integrals are low pass filters. They attenuate the corrupting noises, which are viewed as highly fluctuating phenomena. A quite short time window is sufficient for obtaining accurate values of a 0 , a 1 .

The extension to polynomials of higher degree is obvious, and therefore also to truncated Taylor expansions.

Remark 5: In practice, the above integrals are of course replaced by straightforward linear digital filters.

Assume that the following rather weak assumption holds true: the mean E(X(t)) may be associated to a differentiable time function [0, 1] → R. Then, on a short time lapse, E(X(t)) is well approximated by a polynomial function of degree 1. The above calculations yield via sliding time windows numerical estimates X trend (t) and Ẋtrend (t) of the trend and of its derivative. Causality is taken into account via backward time calculations. In this setting ( [START_REF] Fliess | A mathematical proof of the existence of trends in financial time series[END_REF], [START_REF] Fliess | A-t-on vraiment besoin d'un modèle probabiliste en ingénierie financière ?[END_REF]), forecasting the time series X(t) boils down to an extrapolation of its mean E(X(t)). If h > 0 is not too "large", i.e., a few minutes in our context, a first order Taylor expansion yields the following estimate at time t + h

X trend (t + h) = X trend (t) + Ẋtrend (t)h (6)
3) Algebraic estimation and seasonality: Replace Equation (6) by

X trend (t + h) = X trend (t) + Ẋtrend (t -1440 + h)h (7)
where Ẋtrend (t-1440+h) is the derivative 1 day backwards. With such a choice the derivative estimation needs not to be causal and becomes more precise and much easier to compute [START_REF] Mboup | Numerical differentiation with annihilators in noisy environment[END_REF].

III. COMPUTER SIMULATIONS A. Data

The time series X (t) was provided by the Company Inagral to whom two authors, M. Bekcheva and A. Moradi, belong:

• it was recorded during a time lapse ∆ equal to 10 days, with a sampling period of 1 minute, • it represents the sum of processing times (CPU times) of the incoming user requests on a production Web Service, with a sampling rate of 1 minute.

Replace X (t) by (see Figure 1)

y(t) = X (t) max τ ∈∆ X (τ )
Thus 0 ≤ y(t) ≤ 1, ∀t ∈ ∆. This normalization procedure hides any sensitive information. The practical meaning of our computer simulations should nevertheless remain clear.

B. Comparison between the three different techniques

Predictions stemming from the three Equations ( 3), ( 6), ( 7) are now compared. In order to derive a sound comparability procedure let us assume the following property: Consider the three time series associated to the three forecasting techniques. In each case the quick fluctuations around the trend may be viewed [START_REF] Fliess | Analyse non standard du bruit[END_REF] as a noise like in engineering. It therefore yields a signal-to-noise ratio (SNR) [START_REF] Proakis | Digital Signal Processing[END_REF]. The three corresponding SNRs are assumed to be approximatively equal.

Three time horizons are considered: 5, 30, 60 minutes. The results are reported in the table below, where the first (resp. second, third) column corresponds to Formula (3) (resp. ( 6), ( 7)): The superiority of the approach from Section II-B.3, which is mixing the daily seasonality with our algebraic calculations, is indubitable. See Figure 1 for a view of the data and of the various trends according to the forecast horizons.

IV. FORECASTING COMPUTING CAPACITY NEEDS FOR RESOURCE PROVISIONING

Set z(t) = 5 × 106 y(t): it is the processing time in milliseconds defined in Section III-A. 4 Lack of space compels to a single forecast horizon of 30 minutes via the single Formula (7). See Figure 5 for z trend (t + 30).

In our case, the QoS and the Web Service stability are ensured with 50% of processing usage on each single virtual CPU (vCPU) core. It yields the following predicted number of virtual machines:

n VM (t + 30min) = z trend (t + 30min) 30000 (8)
where

• VM is the well-known acronym of virtual machine,

• 30000 is the number of milliseconds in a minute (in CPU time) for achieving the 50% use. The computer results derived from Formula (8) are provided in Figure 6.

Remark 6: Being able to estimate the required amount of computing resources in advance, one can easily acquire the necessary resources via Cloud provider's spare available capacity at a bargained price. For example, in the case of Amazon Web Services (AWS), the use of Spot Instances can reduce the compute price up to 90%. 5Remark 7: As already stated in our Introduction, the unavoidable quick oscillations around n VM (t) and occasional uncertain load fluctuations are most efficiently taken into account [START_REF] Bekcheva | Meilleure élasticité "nuagique" par commande sans modèle[END_REF] by iPs from model-free control.

V. CONCLUSION

We hope to have convinced the reader that easily implementable time series approaches yield convincing prediction results in cloud computing. If seasonality patterns are available, they should be exploited. They lead to notable simplifications and improvements.

This introductory communication should nevertheless be completed in several ways:

• Comparisons with other viewpoints on time series and, more generally, on forecasting should be investigated. Suitable metrics will be proposed. • How would behave our setting with respect to different time lapses and samplings? • The inevitable uncertainty of any forecasting technique plays obviously a critical role. It will be examined as in [START_REF] Fliess | Prediction bands for solar energy: New short-term time series forecasting techniques[END_REF]. Let us conclude by mentioning that some works have suggested to use time series for detecting anomalies (see, e.g., [START_REF] Huang | Time series anomaly detection for trustworthy services in cloud computing systems[END_REF], [START_REF] Vallis | A novel technique for longterm anomaly detection in the cloud[END_REF]) and enhencing privacy protection (see, e.g., [START_REF] Pawar | Review on privacy preserving in cloud using time series pattern based noise generation[END_REF], [START_REF] Zhang | Time-series pattern based effective noise generation for privacy protection on cloud[END_REF]). Our algebraic techniques [START_REF] Fliess | Algebraic change-point detection[END_REF], [START_REF] Fliess | Prediction bands for solar energy: New short-term time series forecasting techniques[END_REF] might also be helpful there. [13] J. Chen, K. Lia, H. Ronga, K. Bilald, K. Lia, P.S. Yub, "A periodicitybased parallel time series prediction algorithm in cloud computing

Figure 2 (

 2 resp. 3, 4) displays forecasts according to Section II-B.1 (resp. II-B.2, II-B.3).

Fig. 1 :Fig. 2 :

 12 Fig. 1: Time series and its trend

Fig. 3 :

 3 Fig. 3: Zoom2: Scaled persistence (-), Algebraic techniques (-) and Algebraic techniques & seasonality (-).

Fig. 4 :

 4 Fig. 4: Zoom3: Scaled persistence (-), Algebraic techniques (-) and Algebraic techniques & seasonality (-).

Fig. 5 :

 5 Fig. 5: Predicted workload via Section II-B.3: z trend (t + 30min)

Fig. 6 :

 6 Fig. 6: Predicted need of virtual machines via Section II-B.3: n VM (t + 30min)

TABLE I :

 I Error 2

	Prediction horizons	Pe	Al [gain in %]	Mi [gain in %]
	t + 5min	15.12	12.47 [21.21%]	10.49 [44.17%]
	t + 30min	32.23 65.68 [-50.862%] 27.89 [15.56%]
	t + 60min	53.49 153.79 [-65.21%]	49.04 [9.08%]

The multiplicative factor

× 10

is "inspired" by the real data which are not made public in this paper.