Mathematical Models of Cloud Computing with Absolute-relative Priorities of Providing of Computer Resources to Users in Conditions of Functioning Features and Failures

Abstract

Analytical models of cloud systems (СS) are developed as queueing systems with a mixed discipline of resource allocation. The models take into account failures and various functioning features and have arbitrary distribution laws for many stochastic processes. Such models for the СS are used for the first time. One of the main indicators of the effectiveness of the СS are indicators based on the evaluation of the time characteristics of these systems. Violation of the permissible time constraints, for example, the response time of the cloud system, adversely affects the efficiency of solving the target tasks of the user. This is particularly important for real-time systems and, first of all, for specific information systems built using private cloud systems. General description of the models is as follows. The input of the cloud system, which implements a mixed queuing discipline (with relative and absolute priorities), receives N Poisson flows of requests for resources with corresponding N priorities. The duration of requests queuing of various flows has their own arbitrary distribution laws. Are quest with relative priority interrupted by requests with absolute priority, returns to the queue. Two disciplines of the resumption of A and Bqueuing are considered. Within the same priority, requests are processed on a first-come, first-served basis. The СS fails according to the Poisson law, and is restored under an arbitrary law. During the recovery period, elements of adaptation to failures are used: requests of some flows to the queue are accepted and accumulated, while others are not accepted (the discipline of the queue replenishment, I and II, respectively,). The failure of service device can occur both during of its free state and during of the requests queuing. Two disciplines of queuing resumption after restoration C and D are considered. An interrupted request is processed from the point of its interruption. The combination of queuing resumption and replenishment of queue disciplines allows us to consider independent models of various types of systems that have the respective designation. Different functioning features consist of various combinations of disciplines A, B, C, D, I and II.

-

1

Introduction The development of mathematical models of cloud computing or information systems created using clouds is an important area for identifying and improving their characteristics [1], [3], [10]-[12]. Cloud computing (CC) is an object with a high level of uncertainty in the functioning process, the main factors of which are [1], [3]: -problem of the flow of requests for computing resources (CR); -presence of the required CR and the accidental time of their use by customers; -accidently failure of the infrastructure of the CC and the time of their elimination; -necessity to provide certain time characteristics for a number of clients, for example, the response time of the CC;

-necessity of optimal use of PR depending on the cost of time delay of customers ordered results of calculations and operating conditions;

-necessity of introduction of adaptation in the process of functioning CC in order to provide certain time characteristics for a number of clients and optimal use ОР.

One of the main indicators of the effectiveness of CC is the indicators based on the assessment of the time characteristics of these systems. Violation of permissible time constraints, for example, the response time of the CR, affects the effectiveness of the solution of user targets, which is of particular importance for real-time systems. First of all, it concerns special information systems, which are built using private CC.

The stochastic nature of the main factors and the necessity of quantification of mass processes on the basis of the theory of probability determines the use of the queueing theory. Then it is possible and appropriate to use the technology of the dynamic adaptive mixed discipline of providing CR (queuing) to users of the CC [1] as mechanisms of adaptation of the CS.

Analytical models for calculation of time characteristics are offered in the conditions of the features of the functioning of the CC using a mixed queuing discipline with absolutely relative priorities and taking into account failures. Models are based on works [2], [4] – [7], [9]. 2

Description of the Model of Cloud Infrastructure Operation with Mixed Queuing Discipline and Adaptation to Failures. Let the input of the CC system, in which the queuing discipline with a relatively absolute priority is implemented, arrive N Poisson flows of requests of intensity  (m, n) (m  1, M , n  1, Nm ) . These flows are aligned with N priorities [2].

The duration of the maintenance of requests of priority (m, n) is a random variable with a distribution function Bm, n (t) , the first b (m, n) and the second b( 2 ) (m, n) start point.

Are quests of priority (m, n) whose service is interrupted by requests from groups with 1, m  1, numbers is returned to the queue. Updating its service is possible either after servicing all interrupted requests (queuing discipline A), or after servicing all interrupted requests and all requests for accumulated flows, the m group with (m,1), (m, n 1) numbers (queuing discipline upgrade B) .

The service device (SD) fails in accordance with the Poisson law with the 0 parameter. The recovery period of the service device is a random variable that has an arbitrary distribution law Во(t) with the first b0 and second b02 initial moments.

During the restoration of the service device, requests of some streams in the queue are accepted, while others are not accepted. This condition is given by the matrix-row of coefficients ni ,i  1, N , , and in the case if requests of the ni  1 stream are accepted in the queue, and if requests ni  0 are denied.

Adaptation to bounce will be that in the recovery period service device incoming requests can either accumulate in the queue (discipline of replenishment of queueI), or receive a refusal and leave the system (discipline of replenishment of queue II).

The failure of service device can occur both during of its free state and during of the requests queuing. In the latter case, the renewal of the service is carried out either from the interrupted request, if there are no requests interrupting its service, (the discipline of resumption of queuing C), or from requests of the senior relative priority of the corresponding group, if any (the discipline of resumption of queuing D).

In case of repeated receipt of the service device, the interrupted request shall be maintained from the place where it was interrupted. Within one priority, requests are served in the order of receipt.

The combination of queuing resumption and replenishment of queue disciplines allows to consider independent models of various types of systems that have the respective designation. Different functioning features consist of different combinations of disciplines A, B, C, D, I and II.

Let SD be in stationary mode, which RM  Kr condition is for systems of type I, M N and for systems of type II - RM  1. Here RM     (m, n) – total loading of the m1 n1 service device requests ( ( (m, n)   (m, n)b(m, n) - loading of the service device(m, n)-requests), and Kr  1 / (1  0 ) – the system readiness coefficient ( 0  0b0 – loading the service device with refusals).

It is necessary to determine the average v(m, n) time spent in the system of requests of each (m, n)-request, namely the response time of the system CC. 3

Definition of Time Characteristics of a Model of a System of Type AS-I.

To determine the average time of requests in the system (time response systems) type AS-I use the known direct method [2].

Let some request (j, k) be a priority in the system. The average duration of this request in the system v (j, k) consists of the average waiting time in the queue w (j, k) and the average service time b (j, k):

v( j, k)  w( j, k)  b( j, k) .

The average waiting time in the queue w( j, k) consists of the average waiting time before service and the average standby time in the interrupted state u( j, k) : w( j, k)  wН ( j, k)  u( j, k) .

The last term in this formula is due to the interruptions in the maintenance of the request (j, k)-request of requests from groups1, j 1 and denials, that is: ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) u( j, k)  uЗ ( j, k)  u0 ( j, k) .

( j, k)  b( j, k )  u( j, k) .

Average time from the beginning of service (j, k)-request to completion is the average full time of service:

Let's start with the calculation u( j, k) , for which we apply the approach described in [2].

During the queuing of (j, k) – request, b( j, k ) j1 interruptions will occur on averj1 Nm age, where  j1    (m, n) the intensity of the total flow of interrupted requests.

m1 n1

As a result of these interruptions, (j, k)-request returns to the queue and waits for the termination of service interruptions that will continue in b( j, k )R j1 average units of time where

j1 Nm Rj1    (m, n)b(m, n) .

m1 n1

During this time, requests from groups 1, j 1 will be received, which will lead to an increase in waiting time of (j, k)-requests for value b( j, k)R2j1 . In addition, the service of these requests will be accompanied by additional accumulation of requests of the same priorities, which are require of queuing of (j, k)-request before. This process is endless, with supplements to the waiting time of (j, k)-requests form a declining geometric progression with a denominator Rj1  1 . The sum of members of such geometric progression is the mean time of all interruptions of queuing of (j, k)request: Т ( 1 )  b( j, k) creases the waiting time (j, k)-request for value b( j, k )02 1RRj1j1 etc.

In the final analysis, we get: u0 ( j, k )  b( j, k )

K 

r 0 Kr  R j1 .

In the mean time Т ( 1 ) , the of service device will fail Т ( 1 )0 , resulting in it will be restored within Т ( 1 )0b0  Т ( 1 ) 0 units of time. Since in the system type AS-I during the recovery period the service device again receives requests that continue to accumulate in the queue, then after the service device is restored, the average waiting time (j, k) -supply in the interrupted state will increase by Т( 2 )  Т( 1 )

2 0 1RRj1j1  b( j, k )0 (1RRjj11 )2 .

During this time there may be a refusal of the service device, the restoration of which will be accompanied by the accumulation of new requests served before (j, k)requests, etc.

The total time of all interruptions of queuing of (j, k)-request of 1, j 1 request groups, taking into account refusals of service device uЗ ( j, k )  Т ( 1 )  Т ( 2 )    Т () . This expression represents the sum of two infinitely decreasing geometric progressions. After calculating the sum of the members of each of them and compiling the results, we get: uЗ ( j, k)  b( j, k)

Rj1 .

Similarly, the average waiting time of (j, k)-request is determined in the interrupted state due to service device refusals u0 ( j, k) . The only difference is the beginning of reasoning. During the queuing of (j, k)-request, the service device will fail on b( j, k)0 average, which will result in its restoration within b( j, k)0 units of time. Taking into account the possibility of accumulation in the period of service device renewal and priority service of requests with absolute priority from 1, j 1 group, the average waiting time of (j, k)-requests will increase by

R j1 .

b( j, k )0 1  Rj1 During this time, the service device can again be denied, which additionally in( 6 ) ( 7 ) ( 8 ) ( 9 ) Then the total average waiting time (j, k)-request in the interrupted state: and the total average service time (j, k)-request: 3) service requests from 2, j groups interrupted by requests from 1, j 1 groups; 4) service requests from 1, j groups interrupted by denials of the service device; 5) existing requests for streams with numbers ( 1,1 ), ( j, k ) are served; 6) service requests flowed with numbers ( 1,1 ), ( j, k 1) received during the waiting time (j, k)-request, taking into account service device refusals.

For the average duration of these events, we write the equation: wН ( j, k )   0  ( j, k )  ( j, k) 0 ( j, k ) 

j1 Nm k   wН (m, n) (m, n)   wН ( j, n) ( j, n)  .

m1 n1 n1 [ 0  zН ( j, k )]

Rj,k 1 Kr  R j,k1  zН ( j, k )

K 

r 0 Kr  R j,k 1 Here  0  K   – average time for updating the service device in the presence (j, k)r 0 0 request: Kr 0 – probability of resumption of the service device[2], 0  b0( 2 ) / 2b0 ; j Nm  ( j, k)     (m, n)(m, n) – average time for the maintenance of the request m1 n1 by the service device in the presence (j, k)-request: (m, n)  b( 2 ) (m, n) / 2b(m, n) ; ( 10 ) ( 11 ) ( 12 )

 (m, n)(m, n) – average time to receive requests from 2, j groups interrupted by requests from groups1, j 1:  (m, n) – probability of staying in queue (m, n)-requests, interrupted by requests from 1, m 1 groups. This probability is determined by the formula ( 8 ), taking into account the intensity  (m, n) of the flow (m, n)-requests;

Km1 Kr  Rm1 0 ( j, k)  j Nm Kr 0 m1 n1 Kr  Rm1

 (m, n)(m, n) – average time of subscription of requests from 1, j groups interrupted by service device refusals

K 

r 0  (m, n) – the probability that the queue has (m, n)-requests, interrupted Kr  Rm1 by the denial of the service device. This probability is determined on the basis of ( 9 ) with account  (m, n) ;

zН ( j, k) – average waiting time (j, k)-request, equal to the sum of the considered components without accounting 0 ;

j1 Nm k1 Rj,k1     (m, n)    ( j, n) .

m1 n1 n1

Note that in each queue there can be no more than one request interrupted by requests with absolute priority or denial.

After simple transformations from equation ( 12 ) we obtain the following recurrence relation: wН ( j, k )  1 Kr2 00  j Nm 1 

Kr  R j,k  m1 n1 Kr  Rm1

j1 Nm k 1  (m, n)(m, n)    wН (m, n) (m, n)  wН ( j, n) ( j, n ) m1 n1 n1 , (13) j1 Nm k where Rj,k     (m, n)    ( j, n) .

m1 n1 n1

To obtain a formula for explicit determination, we analyze the relation (13) for "pure" queueing disciplines with a relative and absolute priority.

For the queueing discipline with a relative priority we receive: - for the first flow wН ( 1,1 )  - for the second flow. wН ( 1, 2 ) 

N1 K 3     (1, n)(1, n) r 0 0

n1 Kr [Kr   ( 1,1 )]

,

N1 K 3     (1, n)(1, n) r 0 0

n1 [Kr   ( 1,1 )][Kr   ( 1,1 )   ( 1, 2 )]

These formulas allow us to assume a general solution in the form: wН (1, k ) 

N1 K 3     (1, n)(1, n) r 0 0

n1 (Kr  R1,k 1)(K r  R1,k )

, k1 where R1,k 1    (1, n), n1

k R1,k    (1, n) .

n1 wН ( 1,1 ) 

K 3    ( 1,1 )( 1,1 ) r 0 0

Kr [Kr   ( 1,1 )]

; • for the flow of the second group wН ( 2,1 ) 

K 3    ( 1,1 )( 1,1 )   ( 2,1 )( 2,1 ) r 0 0 [Kr   ( 1,1 )][Kr   ( 1,1 )   ( 2,1 )] .

Then on the basis of these equalities we get the general expression: wН ( j,1) 

j K 3     (m,1)(m,1) r 0 0

m1 (Kr  R j1,1 )(Kr  Rj,1 ) ,

For the queueing discipline with absolute priority ( M  N , Nm  1 for all m  1, M ) of the expression (13) we obtain: • for the flow of the first group

j where R j1,1    (m,1), m1

j Rj,1    (m,1) .

m1

Analyzing the expression (14) and (15), it is easy to assume the general form of the formula for determining wН ( j, k ) for a mixed queueing discipline: (14) (15) .

(16)

Substituting formula (16) in (13) and making simple transformations, we can verify the validity of this assumption.

By expressions ( 11 ) and (16) we calculate the required average time of stay (j, k) – request v( j, k) in the AS-I system

Similarly, as for the system type AC-I, formulas can be derived for determining the temporal characteristics for the remaining systems type AC-II, BD-I, BD-II.

The models take into account the physical properties of the CC, such as instantaneous elasticity (dynamic allocation and release of resources for fast scaling according to needs) and measuring service (management and optimization of resources with the help of measuring instruments).

References

1. A. Ya .Matov,“ Optimization of the provision of computing resources with adaptive cloud infrastructure”,Data recording, storage and processing ,vol. 20 , no. 3 , pp. 83 - 90 ,(in Ukrainian), 2018 .

2. A. Ya.Matov , V.N. Shpilev , A.D. Komov et al., Organization of computational processes in ACS. Ed. A.Ya.Matov . Kiev, Ukraine, (in Russian), 1989 .

3. A. Ya. Matov , I.O. Khramova , “ Problems of mathematics and mathematical modeling of old ones are counted for the integration of information and analysis of the system and power management”,Data recording, storage and processing , vol. 12 ,no. 2 , pp. 113 - 127 , (in Ukrainian), 2010 .

4. A. Ya .Matov,“ Two modes of continuous completion of a queue when the instrument is restored in a servicing system with a relative priority” , Avtomat. i Telemekh ., pp. 66 - 70 , 1974 .

5. A. Ya .Matov,“ Two priority system with an unreliable device and period of servicing” ,Engineering Cybernetics, no. 10 ( 5 ), pp. 849 - 852 , 1973 .

6. A. Ya .Matov,“ Two continuous queue disciplines for service-resumption period in a nonpreemptive-priority queuing system”,Automation and remote control , no. 35 ( 4 ), pp. 575 - 578 , 1974

7. A. Ya.Matov , N.F. Tishchenko ,“ Mathematical models of computing systems with priority denial of service”,Izv. Academy of Sciences of the USSR . Technical cybernetics , no. 3 , pp. 190 - 194 , (in Russian), 1980 .

8. A. Ya.Matov , V.N. Shpilev ,“ The use of combined priorities to improve the efficiency of computing processes in the ACS”,Mechanization and automation of management , no. 4 , pp. 58 - 60 , (in Russian), 1983 .

9. A Ya. Matov , V. I. Zhluktenko , K. A. Chernous , N. F. Tishchenko , “ Two continuous queuing disciplines in mixed priority systems”, Cybernetics and Systems Analysis , no. 14 ( 3 ), pp. 421 - 426 , 1978 .

10. E.V. Mokrov , K.E. Samuilov , “ Cloud computing system model in the form of a queuing system with multiple queues and with a group of requests”, (in Russian) . [Online]. Available: https://cyberleninka.ru/article/n/model -sistemy-oblachnyh-vychisleniy-v-videsistemy-massovogo-obsluzhivaniya-s-neskolkimi-ocheredyami-i-s-gruppovympostupleniem-zayavok . Last accessed: November 14 , 2018 .

11. J.M.Tsai , and S.W. Hung ,“ A novel model of technology diffusion:system dynamics perspective for cloud computing” , Journal of Engineering and Technology Management , vol. 33 , pp. 47 - 62 , 2014 .

doi:10 .1016/j.jengtecman. 2014 . 02 .003

12. P. Singh , M. Dutta , N.Aggarwal,“ A review of task scheduling based on meta-heuristics approach in cloud computing” , Knowledge and Information Systems , vol. 52 , nol .1, 2017 . doi: 10 .1007/s10115-017-1044-2