=Paper=
{{Paper
|id=Vol-2318/paper13
|storemode=property
|title=Mathematical Models of Cloud Computing with Absolute-relative Priorities of Providing of Computer Resources to Users in Conditions of Functioning Features and Failures
|pdfUrl=https://ceur-ws.org/Vol-2318/paper13.pdf
|volume=Vol-2318
|authors=Aleksandr Matov
|dblpUrl=https://dblp.org/rec/conf/its2/Matov18
}}
==Mathematical Models of Cloud Computing with Absolute-relative Priorities of Providing of Computer Resources to Users in Conditions of Functioning Features and Failures==
https://ceur-ws.org/Vol-2318/paper13.pdf
Mathematical Models of Cloud Computing with
Absolute-relative Priorities of Providing of Computer
Resources to Users in Conditions of Functioning Features
and Failures
Aleksandr Matov1
1
Institute for Information Recording of National Academy of Sciences of Ukraine, Kyiv,
Ukraine
matov@ipri.kiev.ua
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 indica-
tors based on the evaluation of the time characteristics of these systems. Viola-
tion 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 sys-
tem, which implements a mixed queuing discipline (with relative and absolute
priorities), receives N Poisson flows of requests for resources with correspond-
ing 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 re-
sumption 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: re-
quests of some flows to the queue are accepted and accumulated, while others
are not accepted (the discipline of the queue replenishment, I and II, respective-
ly,). The failure of service device can occur both during of its free state and dur-
ing of the requests queuing. Two disciplines of queuing resumption after resto-
ration C and D are considered. An interrupted request is processed from the
point of its interruption. The combination of queuing resumption and reple-
nishment of queue disciplines allows us to consider independent models of var-
ious types of systems that have the respective designation.
Different functioning features consist of various combinations of disciplines
A, B, C, D, I and II.
151
Keywords: Сloud Computing, Mathematical Model, Interruption, Discipline of
Providing Computing Resources, Adaptation and Optimization of Queuing Dis-
ciplines, Efficiency of Adaptation, Mixed Queuing Discipline
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 characte-
ristics [1], [3], [10]-[12]. Cloud computing (CC) is an object with a high level of un-
certainty 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 exam-
ple, 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 dy-
namic 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 condi-
tions 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 abso-
lute priority is implemented, arrive N Poisson flows of requests of intensity
(m, n) (m 1, M , n 1, N m ) . 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.
152
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 para-
meter. The recovery period of the service device is a random variable that has an arbi-
trary 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 ac-
cepted 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 dis-
cipline 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 al-
lows to consider independent models of various types of systems that have the respec-
tive 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 K r 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 K r 1/ (1 0 ) – the system readiness coefficient ( 0 0 b0 – load-
ing the service device with refusals).
It is necessary to determine the average v (m, n) time spent in the system of re-
quests 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].
153
Let some request (j, k) be a priority in the system. The average duration of this re-
quest 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 ) . (1)
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 ) . (2)
The last term in this formula is due to the interruptions in the maintenance of the
request (j, k)-request of requests from groups 1, j 1 and denials, that is:
u ( j , k ) u З ( j , k ) u0 ( j , k ) . (3)
Average time from the beginning of service (j, k)-request to completion is the av-
erage full time of service:
( j , k ) b( j , k ) u ( j , k ) . (4)
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 aver-
j 1 N m
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
j 1 N m
where R j 1 (m, n)b(m, n) . (5)
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 ) R 2j 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 de-
clining geometric progression with a denominator R j 1 1 . The sum of members of
such geometric progression is the mean time of all interruptions of queuing of (j, k)-
request:
154
R j 1
Т (1) b( j , k ) . (6)
1 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 accu-
mulate in the queue, then after the service device is restored, the average waiting time
(j, k) -supply in the interrupted state will increase by
R j 1 R j21
Т (2) Т (1) 0 b( j, k ) 0 . (7)
1 R j 1 (1 R j 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 progres-
sions. After calculating the sum of the members of each of them and compiling the
results, we get:
R j 1
uЗ ( j, k ) b( j, k ) . (8)
K r R j 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 R j 1
During this time, the service device can again be denied, which additionally in-
R j 1
creases the waiting time (j, k)-request for value b ( j , k ) 02 etc.
1 R j 1
In the final analysis, we get:
K r 0
u0 ( j , k ) b( j , k ) . (9)
K r R j 1
155
Then the total average waiting time (j, k)-request in the interrupted state:
R j 1 K r 0
u ( j , k ) b( j , k ) . (10)
K r R j 1
and the total average service time (j, k)-request:
1
( j , k ) b ( j , k ) . (11)
K r R j 1
Now calculate wН ( j , k ) . Before (j, k)-request entered the system for the first time,
the following should be done:
1) the service device is restored
2) an request has been served from 1, j or groups of submissions of the served re-
quest from the j 1, M groups;
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 N m k
wН (m, n ) (m, n ) wН ( j , n ) ( j , n ) . (12)
m 1 n 1 n 1
R j , k 1 Kr 0
[ 0 z Н ( j , k )] zН ( j, k )
K r R j , k 1 K r R j ,k 1
Here
0 K r 0 0 – average time for updating the service device in the presence (j, k)-
request: K r 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) ;
156
j Nm
Rm 1
( j, k ) (m, n)(m, n) – average time to receive requests from
m 2 n 1 K r Rm 1
K m 1
2, j groups interrupted by requests from groups 1, j 1: (m, n) – probabili-
K r Rm 1
ty 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;
j Nm
K r 0
0 ( j , k ) (m, n)(m, n) – average time of subscription of re-
m 1 n 1 K r Rm 1
quests from 1, j groups interrupted by service device refusals
K r 0
(m, n) – the probability that the queue has (m, n)-requests, interrupted
K r 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 N m k 1
R j , 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 re-
quests with absolute priority or denial.
After simple transformations from equation (12) we obtain the following recur-
rence relation:
j Nm
1 2 1
wН ( j , k ) r 0 0
K
K r R j ,k m 1 n 1 K r Rm 1
, (13)
j 1 N m k 1
(m, n)(m, n) wН (m, n) (m, n) wН ( j , n) ( j , n )
m 1 n 1 n 1
j 1 N m k
where R j , 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:
157
N1
K r3 0 0 (1, n) (1, n)
n 1
- for the first flow wН (1,1) ,
K r [ K r (1,1)]
N1
K r3 0 0 (1, n) (1, n)
n 1
- for the second flow. wН (1, 2) .
[ K r (1,1)] [ K r (1,1) (1, 2)]
These formulas allow us to assume a general solution in the form:
N1
K r3 0 0 (1, n) (1, n)
n 1
wН (1, k ) , (14)
( K r R1, k 1 )( K r R1, k )
k 1 k
where R1,k 1 (1, n), R1, k (1, n) .
n 1 n 1
For the queueing discipline with absolute priority ( M N , N m 1 for all m 1, M )
of the expression (13) we obtain:
• for the flow of the first group
K r3 0 0 (1,1)(1,1)
wН (1,1) ;
K r [ K r (1,1)]
• for the flow of the second group
K r3 0 0 (1,1)(1,1) (2,1)(2,1)
wН (2,1) .
[ K r (1,1)][ K r (1,1) (2,1)]
Then on the basis of these equalities we get the general expression:
j
K r3 0 0 (m,1)(m,1)
m 1
wН ( j ,1) , (15)
( K r R j 1,1 )( K r R j ,1 )
j j
where R j 1,1 (m,1), R j ,1 (m,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:
158
j Nm
K r3 0 0 (m, n) (m, n)
m 1 n 1
wН ( j , k ) . (16)
( K r R j ,k 1 )( K r R j , k )
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 instantane-
ous 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 Ukrai-
nian), 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 servic-
ing”,Engineering Cybernetics, no. 10 (5), pp. 849-852, 1973.
6. A. Ya.Matov,“Two continuous queue disciplines for service-resumption period in a non-
preemptive-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]. Availa-
ble: https://cyberleninka.ru/article/n/model-sistemy-oblachnyh-vychisleniy-v-vide-
159
sistemy-massovogo-obsluzhivaniya-s-neskolkimi-ocheredyami-i-s-gruppovym-
postupleniem-zayavok. Last accessed: November 14, 2018.
11. J.M.Tsai, and S.W.Hung,“A novel model of technology diffusion:system dynamics pers-
pective 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 ap-
proach in cloud computing”,Knowledge and Information Systems, vol. 52, nol.1, 2017.
doi:10.1007/s10115-017-1044-2