-

Analytical methods of nonstationary processes modeling?

0 ITMO University , Kronverkskiy pr., 49, lit. A, St. Petersburg, 197101 , Russia

Due to complex structure and a huge scale, cloud systems design and development requires a preliminary workload estimation. A typical solution for this design step is a workload upper-boundary estimation based on a sum of maximal intensities per cloud application. This solution is not well suitable for nonstationary functioning cloud computing systems, due to such an estimation would result in lots of hardware resources mostly unused during the worktime. Any workload can be represented as a combination of a probability density function and certain parameters for modeling purposes. For any stationary processes, a shape of the probability density function and the parameters would have constant values. On the contrary, nonstationary processes are characterized by changes of the values in time. The objective of the work is to develop an analytical method for the nonstationary processes modeling and representation. Completing the objective, the authors proposed a linearequation nonstationary processes representation form. Which allowed to carry out the estimation using standard mathematical transformations and operations. The proposed numerical method makes it possible to approximate periodic non-stationary distributions whose change in time is sinusoidal. The method is tested with di erent types of synthetic signals and in all cases demonstrates a high degree of compliance of the results with the original data.

Nonstationarity Mathematical modeling Cloud computing Computational resources scaling

Currently, computing is widespread in cloud systems that solve a wide range of tasks with small user requests processing time [ 1 ]. Examples of such systems include various Internet services for converting image formats and media les, services for performing mathematical calculations and services for collaborative work with o ce documents. Due to the fact that cloud systems, as a rule, have a web interface, there is no need in specialized software to work with them, ? Supported by ITMO University. therefore the number of their users is constantly increasing as well as the total workload. Therefore, these systems require continuous operation and high performance to ensure the high quality of the services provided.

A cloud system is a set of computing systems, as a rule, located in one data center, serviced by one sta and under the jurisdiction of one managing organization [ 2 ]. The management organization provides the services of renting a part of the cloud system computing power using virtualization technologies automatically or in a manual manner. For instance, there could be a special software for company administrators whis is capable of provisioning new computing resources for any software. Thus, the tenant receives a certain number of virtual nodes with the same con guration on which the cloud application can be launched. The cloud application has a single entry point for user requests and it is horizontally scalable, so the structure of the cloud application is hidden from users [ 3 ]. Cloud applications in contradiction to desktop apllications are characterized with a high level of horizontal scalability. Therefore, if a tenant has insu cient computing capacity at some point in time, he can rent additional virtual nodes and launch additional instances of it's cloud application, increasing the overall performance of his cloud application. 2

Problem formulation

Any workload can be represented as a combination of a probability density function and certain parameters for modeling purposes [ 5 ]. For any stationary processes, a shape of the probability density function and the parameters would have constant values. On the contrary, nonstationary processes are characterized by changes of the values in time. Thus nonstationarity in any systems could be delimited in three classes: with constant probability distribution, with constant parameters (mean, variation, etc.), and total non-constant [ 6 ]. Each of those nonstationarity classes is typical for speci c environmental conditions. Mostly, nonstationarity may occur due to natural workload behavior. There are number of nonstationarity reasons that could be converged in three classes: periodic, aperiodic (e.g. damped oscillations) and chaotic { without any visible structure or reproducibility. Figure 1 represents a workload of the biggest Internet data exchange point of the Russian Federation { MSK-IX. It's shown that a network tra c tends to be a periodic nonstationary process, due to number of Internet users at a speci c point: much more active users during an evening. development of the software package for cloud system resources automatic provisioning based on a system states simple approximation; cloud systems process types identification; developing an analytical method for the nonstationary processes modelling and representation; synthetic tests; integration of the obtained numerical and analytical methods into the caler

Analytical methods of nonstationary processes modeling

MSK-IX weekly traffic 3 3500 3000 s it/2500 b G , ic2000 f f a r t ed1500 r u s ae1000 M 500 0 0 3 : 5 1 9 c e D 0 3 : 6 0 0 1 c e D 0 3 : 1 2 0 1 c e D Absolutely the same workload class { periodic nonstationary process { was discovered iyn a course of numerous cloud systems studies. In spite this fact, typical approach of cloud systems design and real-time management consists of an estimation on maximum intensity values [ 7 ]. Such an approach leads to nonoptimal workload distribution due to big amount of unused hardware resources. Therefore, the objective of the work is to develop an analytical method for the nonstationary processes modeling and representation.

t0 ti t 3

t0 + x

Period estimation

ti - x For the nonT-ystpaitciaolncalroyudprpolcaetsfosersminauvetost-isgcaatliionng dsuervinicgemoergaasunrizemateionnts on a real system, it is necessary to take not only the numerical characteristics of the distribution into account, which a ect the absolute values of the measurands, but also the periodic component describing distribution characteristics changing with time. There is a need to automatically estimate the period length based on a sample of measured values in order to present the observed process in an analytical form. Below we propose a method for such processes period length estimating to ensure their analytical description and research.

Existing methods for such problems solving are usually associated with the sound signals analysis or have a di erent, narrow eld of application, which makes it di cult to use them in network computing systems [ 8 ]. In addition, curreWntolryklouasded methods are not suitable for the investigation of non-stationary processes occurring in cloud computing systems, since the function describing changes in such processes does not always have a sinusoidal form. Methods such as, for example, the fast Fourier transform (FFT) are not suitable for the period estimation of signals with a missing fundamental [ 9 ]. In particular, the fast

Contributors and references

Caler

Typica AnyLogic mod Representation and c Process 1 Sum Composition

Fourier transform has a fairly good algorithmic complexity, but it requires a large number of oating point operations, including the results post-processing, which eliminates the algorithmic complexity advantage over the method described below. Also, despite the fact that the fast Fourier transform works well on signals having a natural nature, its applicability is not always relevant for the \arti cial" signals observed in computer science [ 10 ]. In particular, the number of terms required for the FFT calculating in gap functions processing rushes to in nity, which makes the calculation impossible [ 11 ]. Therefore, it became necessary to develop a method for the period T length estimating, satisfying the following requirements. 1. The method should evaluate the period on an incomplete set of input data.

Since the load created by users changes over time [ 12 ], to manage the cloud system, it is necessary to estimate the length of the requests arrival process period in "real time". 2. The method must have a polynomial or constant algorithmic complexity. It is clear that during long-term high frequency measurements, a su ciently large number of measured values will be obtained, which will lead to a large processing time using existing algorithms with the exponential complexity [ 13 ]. 3. The main memory usage should linearly dependent on the amount of input data, since it is assumed to use the developed method to manage the cloud system with a limited memory capacity [ 14 ]. 4. The method should be resistant to measurement errors and obtain reliable results (in real environment as well) characterized by a non-ideal input signal form [ 15 ]. 5. Calculation results should not depend on the quality of a periodic input data, due to real systems discreteness and therefore function holes presence.

Let there be some periodic value Y , depending on time Y = y(t). Obviously, there exists a moment of time ti for which the interval (0; ti) is an integer number of the y(t) function periods. However, in practice, measurements of the Y values can be made with a variable time step, often skipping i-th samples. This makes it impossible to iteratively pass through all points in time at an equal step to analyze the y(t) function behavior, so it becomes necessary to obtain the missing values of Y , that is, to move from the Y values to the Y 0 values pending at regular time intervals.

A linear interpolation could be used for y0(t) missing values estimation. Having computational complexity of O(1), it provides more precise period estimation [ 16 ].

Since the period T includes an integer number of intervals t (provided that T > t and T mod t = 0), at time ti the y0(ti) = y0(ti T ) equality is true.

Thus, two arbitrary adjacent equal intervals in which the y0(t) function will have the same behavior can be found to search for a period in the sample.

In the proposed method, an iterative passage through the normalized sample of a given value is used, starting from the moment of t0, that is, the moment of its rst measurement. At every second moment of time ti the interval t = ti t0 is divided into two equal segments t0 : : : ti=2 and ti=2 : : : ti respectively. If the y0(t) behaves identically on the obtained segments, then the segment ti=2 is the desired y0(t) function period.

Considered many ways to assess the functions characters similarity. In the proposed method, as a measure of the y0(t) function behavior similarity degree on time intervals t0 : : : ti=2 and ti=2 : : : ti Pearson correlation coe cient r is used, which is calculated according to the formula (1).

r = cov(t0 : : : ti=2; ti=2 : : : ti) [t0 : : : ti=2] [ti=2 : : : ti] (1) Here, the correlation moment cov(t0 : : : ti=2; ti=2 : : : ti) is de ned as cov(X; Y ) = M [(X M [X]) (Y M [Y ])], where M is the mean value de ned for the series of values analyzing task as the arithmetic average. The standard deviation is de ned as = pM [X2] M [X]2.

Due to the limitation on the method computational complexity, for calculating M and values, required for the r coe cient determination, it is proposed to also store PN j=0 y0(tj )2 sums for each value of the y0(ti) func

j=0 y0(tj ) and PN tion. This makes it possible to reduce the mean value determination time of the sample to the time of calculating the di erence between two values and the quotient, and the operation computational complexity is O(1), while the r coe cient calculating computational complexity decreases to O(N ).

Thus, for each second sample of the y0(t) function, the similarity degree of the two functions describing both halves of a known values series is calculated, respectively. If the correlation r exceeds a certain threshold value R, the t0 = ti=2 value is assumed to be a multiple of the function period T . In this case, the t0 value s placed in the table of the y0(t) function expected periods. This table is a correspondence of a supposed period Ti0 and the number of times n, which this period was recorded among the y0(t) function values y0(t) with a high degree of similarity. Therefore, it is necessary not only to estimate the y0(t) function halfsegments similarity degree of the half-segments of the function when processing the next incoming samples of the y0(t) function, but also to evaluate the added samples similarity of the function with all multiple expected periods.

To increase the accuracy of the obtained results, the n value can be considered not the number of periods occurrences in the set of the function known values, but the calculated correlation coe cients sum. In this case, for r > R the n value will increase by the n = R 6 n 6 1 value. Such an approach does not decrease the proposed method algorithmic complexity, however, it will require slightly more oating-point calculations, which may be undesirable, for example, in embedded systems.

In the course of numerous experiments it was found that for ideal functions (sinusoidal, meander, sawtooth and triangular) the suitable value of R is 0; 999.

On data received from Russia's largest tra c exchange point [ 17 ], high estimation accuracy is achieved at R = 0; 9. In the general case, it is proposed to estimate R using preparatory simulation experiments or use R = 0; 8.

CALER A cross-platform utility for cloud backend systems

autoscaling optimization y Project status: Current Caler architecture deficiencies identifying in autoscaling services of6modern cloudSseyrsgteemis;Zhmylev, Ilya Martynchuk, Valeriy Kireev, and Tau k Aliev development of the software package for cloud system resources automatic provisioning based on a system states simple approximation; cloud systems process types identification; developing an analytical method for the nonstatio4nary proCcesosemsposition modelling and representation; synthetic tests; integration of the obtained numerical and analytical methods into the caler To solve the problem of designing cloud systems [ 18 ] with non-stationary proMSK-IX weekly traffic cesses it is important to identify the properties of the nonstationary distributions composition. Let two non-stationary processes are given by non-stationary distributions (2) and (4). 3500 3000 ii,ffttrr/sscaaeedbuGM1212005500000000 (f f(x(t;)t)==c(at() f (t); x)Caler (2) <>8>:suhm(t)(bx(=; tgc)((t=t)); +xa()d(ft()t); x) (3) 500 8>comp(x; t) = (a( f (t); x)+ 0 :ce91350D :ce100630D :ce102130D :ce111230D P:ce120330Derio:ce121830Dd es:ce130930Dtim:ce140300Datio:ce141530Dn :ce150360D :ce152310D T:ce161230Do(:ce170330Dcga(:ce171830Dglxc(ut;:ce109803D)tla)=t=edtb(ht(e) gs(utm); xo)f thesT(ey4pip)carloauctoe>:<-ssscaelihsn+g(=a3lbg)o(c,r(iitthtgm)(it+s)a;dxs(s)tu))=m2ed that the pro(b5a)bility ; density function can be represented as a convolution of the original probabilty density functions [ 19 ], and to calculate their composition (5), the probability density function can be calculated as the half-sum.

To estimate an average and maximum queries intensity one can just sum the relevant values: (t) = c(t) + d(t) and max(t) = cmax(t) + dmax(t). All of those t0 hypothesisti htave been successfully tested with a following model in AnyLogic t0 + x Pti -rxofessional 7.0.1 simulation environment: Typical cloud platform auto-scaling service organization

AnyLogic model of a cloud computing system Workload

Representation and composition of nonstationary processes Process 1 Fig. 2P.roAcenssy2Logic mo–dperolbability density functions

– queries intensity functions

Analyticapl amrodaemleters: The model (Figure 2) has Stuhme following Average i(t) { input streams intensity; b { application processing time; A1( ) and A2( ) { input stream probability density functions; B( ) { application processing time probability distribution

Contributors and referencefsunction; characteristic Coomfptohsiteionmodel: { loadMaaxivmeumr aingteen.sity

Zhmylev Sergei, Martynchuk Ilia, The in-development autoscaling service is Kireev Valeriy, Aliev Taufik, Turkov Nikita completely open source andAavsailabale orneGistHuubl:t of modeling the following property was identi ed: if the sum of https://github.com/zhmylove/caler/ average values of intensity does not exceed intensity of service [ 20 ], then, regardless of the sum of maximum values of intensities, the system will not pass to constantly overloaded state [ 21 ]. Thus, with su cient storage capacities in such systems, mass losses do not occur. The revealed property allows to draw conclusions about the expediency of redistribution of non-stationary load in cloud systems to solve the problem of automatic scaling of the cloud [ 22 ]. However, the question of choosing suitable storage capacities remains open, so that the system functions correctly, without mass loss of applications [ 23 ].

Taking into account the con dence intervals with a con dence probability of 95% and the generally accepted error of simulation modeling of 5% [ 24 ], it can be concluded that at constant average intensities of incoming ows the total intensity is their sum. 5

Approximation

Let there be a series of non-stationary distributed data X = (x0; x1; :::; xN ), the distribution intensity of which varies according to some time depinding periodic law: (t), meanwhile the probability distribution function does not change.

Let (t) be a periodic function, having the form of a sinusoid with a period T . Then the following function can be found (6), where A { the sin amplitude, 0 { the initial phase, C { the shift on the y-axis, which will most closely match the original (t).

0 (t) = A sin(!(t) + 0) + C (6) At the same time, the Pearson correlation coe cient r can be chosen as a measure of compliance [ 24 ].

That is, the task of the X set approximation is reduced to the selection of such values A, 0, ! and C, for which (t) and 0 (t) have the highest correlation coe cient r value.

At the rst stage of the method, it is proposed to obtain a set of averaged values i (i 2 (0::mT ); m 2 N) with a length of one or several (t) function periods by averaging the measured X values at i + kT points, where k = (0; 1; 2; :::; mNT 1).

Since R02k (A sin(t) + C)dt = 2k C, C is the (t) function's average [ 25 ].

PiN=0 i , given number of

N Thus, C can be obtained as C = values N is multiple of the period [ 26 ].

The sine amplitude A can be calculated using the mean square of i values: A = q 2 PNiN=0 i2 . Or, given the value of C, A = q 2 PiN=0N( i C)2 .

Having A and C values, the initial phase 0 could be estimated as follows, resulting in 0 (t) estimation. Consider 0 at point t = 0: (0) = 0 = A sin( 0) + C. There are only two potential values of 0: 0(1) = arcsin( 0A C ) and 0(2) = arcsin( 0A C ). To choose the correct one, Pearson correlation coe cient [ 27 ] could be used again, and the function with proper 0 value would have higher coe cient value.

The proposed numerical method makes it possible to approximate periodic non-stationary distributions whose change in time is sinusoidal [ 28 ] and represent it in a form of (6). The method is tested with di erent types of synthetic signals and in all cases demonstrates a high degree of compliance of the results with the original data. The results of experiments with con dence intervals are presented in the table below. We can conclude that for the case of low coe cient of variation [ 28 ] ( = p15 , the Erlang distribution with k = 5), the method as a result sets the function 0 (t), strongly correlating with the initial (t) for the sine and triangular wave and, in general, acceptable results in all other cases.

This fact con rms the possibility of using the method in practice for systems having a similar workload. 6

Putting results into practice

The results obtained in the work can be applied in algorithms for automatic scaling of cloud computing systems. For example, let the cloud system have two nodes that run instances of the cloud application, shown on Figure 3. A workload from two users (User 1 and User 2) is distributed between the nodes, which is shown by solid and intermittent lines, respectively. Suppose each user creates a sinusoidal antiphase workload on the compute nodes. If we sum up the maximum values of the users workload intensities, we can make the erroneous conclusion that at least two nodes are needed to work simultaneously to ensure the required performance. At the same time, if we take into account the information about the nonstationarity of the load created by users and take advantage of the results obtained in the work, there will be no overload state with just one computing node. In this situation, the load balancer can send all user requests to one node, and the second node can be turned o to increase the energy e ciency of the cloud system.

Such an approach can signi cantly decrease energy consumption of large datacenters, in which cloud systems could use thousands and thousands of physical servers. Which is resulting in a huge economic cost reduce for the datacenter owners, who can farther reduce rent costs for end-users and increase their commerce income. 7

Conclusion

In this paper we proposed an analytical method for the nonstationary processes modeling and representation. This method includes the following: numerical parameterized method that allows to estimate a period length of non-stationary processes; a linear-equation nonstationary processes representation form, which allowed to carry out the estimation using standard mathematical transformations and operations; a numerical approximation method of periodic nonstationary distributions whose change in time is sinusoidal. This method helps to solve the problem of designing cloud systems with non-stationary processes.

1. Bogatyrev , Vladimir A., and

A. V.

Bogatyrev . "Functional reliability of a realtime redundant computational process in cluster architecture systems . " Automatic Control and Computer Sciences 49.1 ( 2015 ): 46 - 56 .

2. Park , K. , Willinger , W. ( 2000 ). Self-similar network tra c and performance evaluation . John Wiley and Sons, Inc..

3. Bogatyrev , Vladimir A. "Fault tolerance of clusters con gurations with direct connection of storage devices." Automatic Control and Computer Sciences 45.6 ( 2011 ): 330 - 337 .

4. Aliev , T. I. ,

M. I.

Rebezova , and

A. A.

Russ . "Statistical methods for monitoring travel agencies in the settlement system . " Automatic Control and Computer Sciences 49.6 ( 2015 ): 321 - 327 .

5. Chhibber , Anju, and Sunil Batra . "Security analysis of cloud computing." International Journal of Advanced Research in Engineering and Applied Sciences 2.3 ( 2013 ): 2278 - 6252 .

6. Mahon , Edward. Transitioning the Enterprise to the Cloud: A Business Approach . Cloudworks Publishing Company, 2015 .

7. Kavis , Michael J. Architecting the cloud: design decisions for cloud computing service models (SaaS, PaaS , and IaaS). John Wiley and Sons, 2014 .

8. Rafaels , Ray J. Cloud Computing: From Beginning to End . CreateSpace Independent Publishing Platform , 2015 .

9. Buzzetto-More , Nicole A ., ed. Advanced principles of e ective e-learning. Informing Science , 2007 .

10.

Matthew

Portnoy . Virtualization Essentials, 2nd Edition . New York: Wiley / Sybex, 2016

11. Jiang , Qiqi, Jianjun

Qin , and Lele

Kang . "A literature review for open source software studies." International Conference on HCI in Business . Springer, Cham, 2015 .

12. Bogatyrev , Vladimir A., S. V.

Bogatyrev , and I. Yu

Golubev . "Optimization and the process of task distribution between computer system clusters . " Automatic Control and Computer Sciences 46.3 ( 2012 ): 103 - 111 .

13. V. A. Bogatyrev

M.S.

Vinokurova . "Control and Safety of Operation of Duplicated Computer Systems" Communications in Computer and Information Science , vol. 700 , pp. 331 - 342 2017.

14. Grossman , Robert L. "The case for cloud computing . " IT professional 11.2 ( 2009 ): 23 - 27 .

15. Lee , Gillam. "Cloud Computing: Principles, Systems and Applications/Nick Antonopoulos,

Lee

Gillam ." L.: Springer ( 2010 ).

16. Park , Kihong, and Walter Willinger . Self-similar network tra c and performance evaluation . John Wiley and Sons, Inc., 2000 .

17. Marston , Sean , et al. "Cloud computing|The business perspective." Decision support systems 51.1 ( 2011 ): 176 - 189 .

18. Mao , Ming, and Marty Humphrey . "A performance study on the vm startup time in the cloud . " 2012 IEEE Fifth International Conference on Cloud Computing. IEEE , 2012 .

19. Boniface , Michael , et al. "Platform-as-a-service architecture for real-time quality of service management in clouds." Internet and Web Applications and Services (ICIW) , 2010 Fifth International Conference on. IEEE , 2010 .

20. Cover , Thomas

and Joy A.

Thomas . "Elements of information theory 2nd edition." Willey-Interscience: NJ ( 2006 ).

21. He , Sijin , et al. "Elastic application container: A lightweight approach for cloud resource provisioning." Advanced information networking and applications (aina ), 2012 ieee 26th international conference on. IEEE , 2012 .

22. Rashvand , Habib F., ed. Using cross-layer techniques for communication systems . IGI Global , 2012 .

23. Gogouvitis , Spyridon , et al. "Work ow management for soft real-time interactive applications in virtualized environments." Future Generation Computer Systems 28.1 ( 2012 ): 193 - 209 .

24. Gogouvitis , Spyridon , et al. "Work ow management for soft real-time interactive applications in virtualized environments." Future Generation Computer Systems 28.1 ( 2012 ): 193 - 209 .

25. Gogouvitis , Spyridon , et al. "Work ow management for soft real-time interactive applications in virtualized environments." Future Generation Computer Systems 28.1 ( 2012 ): 193 - 209 .

26. Gogouvitis , Spyridon , et al. "Work ow management for soft real-time interactive applications in virtualized environments." Future Generation Computer Systems 28.1 ( 2012 ): 193 - 209 .

27. Gogouvitis , Spyridon , et al. "Work ow management for soft real-time interactive applications in virtualized environments." Future Generation Computer Systems 28.1 ( 2012 ): 193 - 209 .

28. Bogatyrev , V. A. "Protocols for dynamic distribution of requests through a bus with variable logic ring for reception authority transfer." Automatic control and computer sciences 33.1 ( 1999 ): 57 - 63 .