=Paper=
{{Paper
|id=Vol-1689/paper6
|storemode=property
|title=On the Modeling and Performance Evaluation of Cloud Computing Centers Using M/G/c/c+r Queuing System
|pdfUrl=https://ceur-ws.org/Vol-1689/paper6.pdf
|volume=Vol-1689
|authors=Assia Outamazirt,Mohamed Escheikh,Djamil Aïssani,Kamel Barkaoui,Ouiza Lekadir
|dblpUrl=https://dblp.org/rec/conf/vecos/OutamazirtEABL16
}}
==On the Modeling and Performance Evaluation of Cloud Computing Centers Using M/G/c/c+r Queuing System ==
https://ceur-ws.org/Vol-1689/paper6.pdf
Stochastic Model for Cloud Dada Center with
M/G/c/c+r Queue
Assia Outamazirt Mohamed Escheikh
Research unit LaMOS University of Bejaia SYS’COM ENIT Tunis
Bejaia, Algeria Tunis, Tunisia
outamazirt.assia@gmail.com mohamed.escheikh@gmail.com
Djamil Aı̈ssani Kamel Barkaoui Ouiza Lekadir
Research unit LaMOS, University of Bejaia CEDRIC, CNAM Research unit LaMOS University of Bejaia
Bejaia, Algeria Paris, France Bejaia, Algeria
lamos bejaia@hotmail.com kamel.barkaoui@cnam.fr ouizalekadir@gmail.com
Analytical resolution of complex queuing systems remains nowadays an open and challenging issue and
may be extensively used in modeling and representing dynamic behavior of sophisticated systems. This is
particularly the case of M/G/c/c + r queue where exact analytical solution is difficult to reach. In this paper,
we propose a new approximate analytical model in order to evaluate the performance of cloud computing
center using M/G/c/c + r queuing system. The adopted modeling approach combines two models. The first
one is a transform-based analytical model whereas the second relies on an approximate Markov chain. This
combination enables to compute the one-step transition probabilities for the system M/G/c/c + r.
Cloud Computing, Performance Evaluation, M/G/c/c+r queue, Transition Matrix, Embedded Markov Chain
1. INTRODUCTION throughput, security, performance indicators (Wang
et al. (2010)).
The US National Institute of Standards and
Technology (NIST) has defined cloud computing Providing quality services require a solid model
as a model for enabling convenient, on-demand that provides detailed insights of computing centers.
network access to a shared pool of configurable Assessing the QoS offered by cloud providers
computing resources (e.g., networks, servers, necessitates the accurate performance evaluation of
storage, applications, and services) that can be the cloud center. Khazaei et al. (2012) adopted
rapidly provisioned and released with minimal M/G/c/c + r queuing system as the abstract model
management effort or service provider interaction for performance evaluation due to the characteristics
(Mell et al. (2009)). of cloud computing centers: having Poisson arrival
of task requests, generally distributed service time,
Cloud services are usually divided into main large number of servers and the finite capacity of
three categories. Software-as-a-Service (SaaS) is system.
a software delivery model in which software and
associated data are centrally hosted on the cloud. However analyzing of M/G/c/c + r queuing system
Platform-as-a Service (PaaS) provides a computing is not an easy task, an exact solution for this
platform like execution runtime, database, web model is only possible for special cases, such as
servers, development tools etc. In infrastructure-as- exponential service, a single server, or no waiting
a-Service (IaaS), cloud providers offer computers, queue at all. Consequently, an extensive research on
as physical or more often as virtual machines, performance evaluation of M/G/c queuing systems
servers, storage, load balancers, networks, etc. was described in the literature (Nozaki et al. (1978),
(Furht (2010)). Typically a service level agreement Yao (1985)). According to Khazaei et al. (2012),
(SLA) gives all the aspects of usage of cloud service the M/G/c approximation approaches that were
and the obligations of service providers and clients. It proposed in the literature (Kimura (1983), Tijms et
also includes various descriptors known as quality of al. (1981), Boxma et al. (1979)) are not suitable
service (QoS) which includes availability, reliability, for performance evaluation of cloud center. They
⃝
c The Authors. Published by BISL. 1
Proceedings of . . .
Stochastic Model for Cloud Dada Center
with M/G/c/c+r Queue
Outamazirt • Escheikh • Aı̈ssani • Barkaoui • Lekadir
cited three issues that make it difficult to apply these Ani Brown Mary et al. (2013) modeled a cloud center
approximations: as an [(M/G/1) : (∞/GD model)] queuing system
with a single task arrivals and a task request buffer
• a cloud center can have a large number of of infinite capacity. They used analytical methods to
facility (server) nodes (Amazon (2010)); evaluate the performance of queuing system and
solve it to obtain important performance factors
• the complex task service times and higher
like mean number of tasks, blocking probability
coefficient of variation (CoV) of service time
and probability of immediate service. Mean as well
distribution (Zhang et al. (2011), Reiss et al.
as standard deviation of the number of tasks is
(2012));
computed.
• due to the dynamic nature of cloud environ-
ments, diversity of users requests and time de- Analysis of queuing systems with multiple servers
pendency of load, cloud centers must provide and general distributed service time is more
expected quality of service at widely varying complex. For these queuing systems the steady
loads (Reiss et al. (2012), Xiong et al. (2009)). state probability, the distributions of response time
and the queue length cannot be obtained in
A new approximate approach used the combination closed form. Consequently, several researchers
of a transform-based analytical model and an have developed many methods for approximating its
embedded Markov chain model for the steady state solution.
probabilities of the M/G/c/c + r queueing system
was proposed by Khazaei et al. (2012). This new Kimura (1983) developed a diffusion approximation
approach is suitable for cases of large number model for the queue M/G/c. The main idea is to
of servers and when the distribution of service approximate formulas for the distributions of the
time has a coefficient of variation more than one. number of customers. Kimura (1996a) described
Improvements for this approach was proposed by an approximation for the steady state queue length
Chang et al. (2014). In these approaches, the distribution in M/G/c queue with finite waiting
instants of regeneration of the embedded Markov spaces.
chain were misinterpreted and the system state A similar approach in the context of M/G/c queues
transition behavior was not describe accurately. was described by Kimura (1996b), but extended so
This paper makes some progress towards a good as to approximate the blocking probability and, thus,
approximation for the computation of the one-step to determine the smallest buffer capacity such that
transition probabilities of the system M/G/c/c + r. the rate of lost tasks remains under predefined level.
This enables to enhance previous approximations.
Nozaki et al. (1978) proposed an approximation
The rest of the paper is organized as follows. for the average queuing delay in a M/G/c/c + r
Section 2 presents a brief overview of related work queue based on the relationship of joint distribution
on cloud performance evaluation and performance of remaining service time to the equilibrium service
characterization of queuing systems. In Section 3, distribution. Smith (2003) proposed a different
we present the analytical model in detail. In Section approximation for the blocking probability based on
4, we conclude by outlining same possible new the exact solution for finite capacity M/M/c/c + r
directions for future work. queues. The estimate of the blocking probability
is used to guide the allocation of buffers so that
the blocking probability remains below a specific
2. RELATED WORK threshold.
Xiong et al. (2009) modeled a cloud center as the However, the most of the approximations mentioned
classic open network, from which the distribution above are not directly applicable to performance
of response time was obtained by using Laplace analysis of cloud computing center due these
transformation. Using the distribution of response following limitations (Khazaei et al. (2012)):
time, the authors found the relationship between the
maximum number of customers, the minimal service • for example, approximations proposed by
resources and the highest level of services Kimura (1996a), Smith (2003) are reasonably
accurate when the number of servers is small,
Yang et al. (2009) proposed the M/M/c/c + r below 10 or so. They are not being suitable
queuing system for modeling the cloud center, which for the cloud computing centers with more than
indicates that both inter-arrival and service times are 100 servers;
exponential, the system has a finite buffer of size r
and its distribution of response time was obtained. • approximations proposed by Nozaki et al.
(1978), Yao (1985) are inaccurate when the
2
Stochastic Model for Cloud Dada Center
with M/G/c/c+r Queue
Outamazirt • Escheikh • Aı̈ssani • Barkaoui • Lekadir
coefficient of variation of the service time, CoV, The M/G/c/c + r queuing system is a non-
is above 1.0; markovian process and can be analyzing by using
the embedded Markov chain (EMC) technique
• approximation errors are particularly pro- Kleinrock (1975). This will be discussed below.
nounced when the traffic intensity ρ is small,
and/or when both the number of servers c Task request arrivals follow a Poisson process, which
and the CoV of the service time are large means that task inter-arrival time AX (x) , P [X ≤
(Kimura (1983), Tijms et al. (1981), Boxma x] is exponentially distributed with a rate of λ, its
et al. (1979)). probability density function (pdf) is a(x) = λe−λx and
its Laplace transform is
As these approximations mentioned above are
∫ ∞
not directly applicable to performance analysis of λ
cloud computing center, Khazaei et al. (2012) A∗ (s) = e−sx a(x)dx = .
0 λ + s
described a new approximate analytical model using
M/G/c/c + r queueing system. In order to evaluate
its performances, they used a combination of a Task service times are identically and independently
transform-based analytical model and an embedded distributed according to a general distribution
Markov chain model, which obtained a complete HY (y) , P [Y ≤ y] with a mean service time equal
probability distribution of response time and number to h = µ1 . its pdf is hY (y) and its Laplace transform is
of task in the system.
∫ ∞
∗
Chang et al. (2014) proposed an approximate H (s) = e−sx h(x)dy.
analytical model using M/G/c/c + r queueing 0
system for performance evaluation of cloud center The traffic intensity is ρ , cµ λ
. The Residual task
close to the proposed by Khazaei et al. (2012), service time, H+ , is the time interval from an
both divided the transition probabilities matrix of this arbitrary point (an arrival point) during a service time
system into four regions. The difference between to the end of the service time. This time is necessary
them lie in the approximation formula of the transition for our model since it represents time distribution
probabilities matrix in regions 3 and 4, because between a task arrival and departure of the task
according to these authors, the approximate formula which was in service when task arrival occurred.
proposed by Khazaei et al. (2012) is an inaccurate The Laplace transform of H+ is calculated by Takagi
approximation for the transition probabilities in these (1991) as:
regions. ∗ 1 − H ∗ (s)
H+ (s) = . (1)
sh
3. THE ANALYTICAL MODEL
3.2. Model Analysis
3.1. Model description
We use the same EMC technique adopted by
We consider a c-server queueing system with Khazaei et al. (2012) for analyzing the M/G/c/c + r
Poisson arrivals, general service times, and a queuing system. This EMC technique consists of
capacity limit of c + r for the number of tasks in selecting the Markov renewal points at the instant
the system, for modeling a cloud data center. In this of a new task arrival to the system. We choose two
model we assume that: consecutive arrivals to be the observation interval
for the EMC. The basic structure of the EMC is
• all c servers render service in order of task shown in Fig.1. Therefore, we model the number
request arrivals (FCFS); of the tasks in the system (both those in the
service and those in the waiting queue) at the
• each busy server is independent of the other moments immediately before the new task arrival,
busy serves; if we enumerate these instances as 0, 1, ..., c + r,
• if the waiting queue is empty and there is no we obtain a homogeneous Markov chain with state
new task request arrival, the server enters in space S = {0, 1, 2, ..., c + r}. This Markov chain is
the idle state; ergodic because it is irreducible, recurrent non-null,
and aperiodic (Khazaei et al. (2012)).
• if the task arrives while the system capacity
has already been attained, this task will depart Let tn and tn+1 the moments of nth and (n +
immediately without service; 1)th arrivals to the system respectively, while Xn
and Xn+1 indicate the number of tasks found in
• each task is serviced by a single server. the system immediately before these arrivals, Tn
denotes the inter-arrival time between tn and tn+1 ,
3
Stochastic Model for Cloud Dada Center
with M/G/c/c+r Queue
Outamazirt • Escheikh • Aı̈ssani • Barkaoui • Lekadir
Bn+1 indicates the number of tasks which depart • Px is the probability of completing the service
from the system between tn and tn+1 . of a task, which has already been in service
In the rest of this paper we use T to denote any inter- during the previous observation interval and is
arrival time. completed in the current interval.
We must calculate the transition probabilities • Py is the probability of completing the service
associated with EMC, and so we define of a task, which begins to be serviced in the
current interval and is finished within the same
pij , P (Xn+1 = j|Xn = i), (2) interval.
otherwise, we must calculate • If a server completes the service of a task
P (Bn+1 = i + 1 − j|Xn = i), (3) which has already been begun during the
previous observation interval, in the current
i.e., the probability that i − j + 1 tasks are serviced interval, this server will be idle. If the waiting
during T . It is clear that queue is nonempty, that server as well may
pij = 0, for j > i + 1. (4) complete a second service in the current
interval, and if the waiting queue is still
nonempty, a new service may be completed,
and so on until the waiting queue gets empty.
The probability of k services are completed by
a single server is given by Pz,k .
After defining the departure probabilities Px , Py and
Pz,k in the embedded Markov chain, we describe
the four different regions of the transition probability
matrix P . These regions are schematically shown
in Fig. 2, where the numbers on horizontal and
vertical axes correspond to the number of tasks in
the system immediately before a task request arrival
Figure 1: Embedded Markov points. (i) and immediately before the next task request
arrival (j), respectively.
Since the EMC is ergodic, an equilibrium probability
distribution π = [π0 , π1 , π2 , ..., πm+r ] exists for the
number of tasks present at the arrival instants with
πi = lim P (Xn = i) for 0 ≤ i ≤ m + r, and it is the
n→∞
solution of equation π = πP , where P is the matrix
whose elements are the transition probabilities pij .
3.2.1. Transition Probability Matrix
To find the elements of the transition probability
matrix P , we need to count the number of tasks
departing from the system in an observation interval.
Each server has zero or more departures in T . The
transition probability matrix P has four regions as
that defined by Khazaei et al. (2012) and Chang
et al. (2014). Before presenting pij in each region,
we first define the departure probabilities Px , Py and Figure 2: Range of validity for pij .
Pz,k as follows:
∗
Px , P (A > H+ ) = H+ (λ), (5) Region 1:
∗
Py , P (A > H) = H (λ), (6)
For i + 1 < j, pij = 0, since j cannot exceed i + 1
(Eq. 4).
[∏
k ]
Pz,k = P (A > H|A > (k − i)H + H+ ) · P (A > H+ ),
i=2
Region 2:
(7)
For i + 1 ≤ c, 0 ≤ j ≤ c, and i + 1 ≥ j, in this
region, all tasks are in the service (no waiting). The
where:
4
Stochastic Model for Cloud Dada Center
with M/G/c/c+r Queue
Outamazirt • Escheikh • Aı̈ssani • Barkaoui • Lekadir
probability that i − j + 1 tasks are served during T is:
i−j i−j
Ci Px j−1 (1 − Px )j Py + Cii−j+1 Pxi−j+1
(1 − Px ) (1 − Py ), if i + 1 > j;
Pij = (8) min(w,c) {
∑
M1 (i, j, w) = Cm Px (1 − Px )c−s1
s1 s1
(1 − Px )j , if i + 1 = j.
s1 =c−j
min(w−s1 ,i−c+1) [
∑
Region 3: Css12 Pz,2
s2
s2 =min(w−s1 ,c−j)
]}
For c ≤ i ≤ c + r, c ≤ j ≤ c + r, and i + 1 ≥ j, all (1 − Pz,2 )i−c+1−s2 , (14)
servers are busy during T . Let ω = i − j + 1 denotes
the number of departures in the system, with ω ≥ 0
and, we assume each single server completes no min(w,c) {
∑
more than three services of tasks in T . We define M2 (i, j, w) = Ccs1 Pxs1 (1 − Px )c−s1
the transition probabilities for this region by: s1 =c−j
∑
min(w−s1 ,s1 ) [
M (i, j, w) · χ, if i < c + r; Css12 Pz,2
s2
(1 − Pz,2 )s1 −s2
s2 =min(w−s1 ,c−j)
1 −s2 w−s1 −s2
pij = M (i, j, w − 1) · χ, if i = c + r; (9) Csw−s Pz,3
2
]}
(1 − Pz,3 )s2 −(w−s1 −s2 )
. (15)
0, if i > c + r,
where: 3.2.2. Discussion
{ Between two successive task arrivals (i.e. during T )
∑
min(w,c)
M (i, j, w) = Ccs1 Pxs1 (1 − Px )m−s1 there may be ω = i + 1 − j departures from the
s1 =min(w,1) system. In the region 2 there will be at most one
∑
min(w−s1 ,s1 ) [ departure from each server of the system, however,
s2
Css12 Pz,2 (1 − Pz,2 )s1 −s2 in regions 3 and 4, there can be more than one
s2 =min(w−s1 ,1) departure from any given server.
1 −s2 w−s1 −s2
Csw−s Pz,3
]}
2
Let us now examine in detail the equations of the
(1 − Pz,3 )s2 −(w−s1 −s2 ) , (10) transition probabilities for regions 2, 3 and 4 that we
propose and we compare these equations with those
proposed by Khazaei et al. (2012) and Chang et al.
and χ is the indicator function (2014).
1, if w − s1 − s2 ≤ s2 ; • Region 2 (i + 1 ≤ c, 0 ≤ j ≤ c, and i + 1 ≥ j):
χ= (11) In this region, the nth arrival finds the waiting
0, if w − s1 − s2 > s2 . queue empty and i servers busy (all i tasks in
the system are in service), then as i ≤ c−1 < c,
it will find an idle server and will immediately
Region 4:
enter into service. However, the (n+1)th arrival
For c ≤ i ≤ c + r, 0 ≤ j < c, and i + 1 ≥ j, all servers finds exactly j on arrival, i.e. there are i +
are busy at the beginning of T , and c − j servers 1 − j tasks leave the system between two
are idle at the end of T . In this region, the transition successive arrivals. We distinguish two cases:
probabilities are defined by: – Case 1: If among these i busy servers,
i − j of them completed the services of
M (i, j, w) · χ, if i < c + r; tasks and, the service of the nth arrival is
also completed before the (n+1)th arrival,
pij = M (i, j, w − 1) · χ, if i = c + r; (12) then the probability of having i + 1 − j
departures from the system in this case
0, if i > c + r,
is equal to:
where: Cii−j Pxi−j (1 − Px )j Py .
M1 (i, j, w), if s1 ≥ i − c + 1; – Case 2: If among these i busy servers,
M (i, j, w) = (13) i + 1 − j of them completed the services
M2 (i, j, w), if n1 < i − c + 1, of tasks and, the service of the nth arrival
5
Stochastic Model for Cloud Dada Center
with M/G/c/c+r Queue
Outamazirt • Escheikh • Aı̈ssani • Barkaoui • Lekadir
is not completed, then the probability of al. (2012), with the probability (1 − Pz,3 )s2 .
having i+1−j departures from the system According to this authors this equation is equal
in this case is equal to: to:
∑
min(w,c) {
Cii−j+1 Pxi−j+1 (1 − Px )j−1 (1 − Py ). pij = Ccs1 Pxs1 (1 − Px )m−s1
s1 =min(w,1)
In the two cases cited above, there are
∑
min(w−s1 ,s1 ) [
i + 1 − j tasks that leave the system
Css12 Pz,2
s2
(1 − Pz,2 )s1 −s2
between two successive arrivals, thus the
s2 =min(w−s1 ,1)
probability of having i + 1 − j departures
1 −s2 w−s1 −s2
from the system during T is equal to: Csw−s Pz,3
]}
2
Cii−j Pxi−j (1 − Px )j Py + (1 − Pz,3 )s2 . (17)
i−j+1 i−j+1
Ci Px (1 − Px )j−1 (1 − Py ). (16)
However, it is impossible to find exactly j tasks
This equation was proposed by Khazaei et al. in the system at the end of T in this equation
(2012) and Chang et al. (2014), but when we because the authors considered the number of
have i + 1 = j, i.e. there is the same number servers that are still busy processing the third
of tasks in the system at the beginning and service is set to s2 . Consequently, Chang et al.
at the end of T , Eq. 16 can not be used to (2014) proposed a new equation for this region,
compute the conditional probability P (Xn+1 = defined as:
i + 1|Xn = i). This probability can be obtained {
∑
min(w,c)
in the following manner: pij = Ccs1 Pxs1 (1 − Px )m−s1
s1 =min(w,1)
(1 − Px )j . ∑
min(w−s1 ,s1 ) [
s2
Css12 Pz,2 (1 − Pz,2 )s1 −s2
That is presents the probability of no having s2 =min(w−s1 ,1)
a departure between two successive arrivals. 1 −s2 w−s1 −s2
Csw−s Pz,3
]}
2
Consequently, the transition probabilities for
the region 2 defined in this paper is given by (1 − Pz,3 )s2 −(w−s1 −s2 ) . (18)
Eq. 8.
• Region 3 (c ≤ i ≤ c + r, c ≤ j ≤ c + r, and In this equation, the remaining ω − s1 − s2
i + 1 ≥ j): tasks that will must leave the system, can be
The nth arrival finds all c servers are busy serviced by the subset of s2 servers that have
and i − c tasks in the waiting queue. If the completed two services. When the number of
number of tasks in the system is strictly less s2 servers is small, then it can happen that
than c+r (system capacity), then the nth arrival the number of remaining tasks exceed this
will be allowed entry. Therefore, there should number, therefore, in order that the assumption
be i − c + 1 tasks in the waiting queue at the to have ”each single server completes no more
beginning of T . than three services of tasks in T ” can verify, an
In this region, there can be more than one indicator function must be used and it is equal
departure from any given server. Among the to 1 if the number of remaining tasks in the
c servers, s1 of them complete at least one system is less than the number of s2 servers,
service during T . Note that all these completed is equal to 0, otherwise (Eq. 11).
services must have already been in service at Also, in this region, if the nth arrival finds the
the beginning of T . Among these s1 servers,
system full (i = c + r), then it will be lost.
s2 of them will complete a second service
during T . As we assumed that each single Therefore, there will be i − j tasks that will
server completes no more than three services leave the system between the nth arrival and
of tasks in T , then the remaining ω − s1 − the (n + 1)th arrival instead of i + 1 − j tasks.
s2 services must be completed in T . These Accounting for the above analysis we propose
services will complete by a subset of these s2 in this paper a new approximate formula for
servers. The number of servers in the subset the computation of the element pc+r,j , for all
is ω − s1 − s2 , that is, there are ω − s1 − j. Consequently, a new accurate approximation
s2 servers, each of which completes exactly of the transition probabilities for the region 3 is
three services in T and, the number of servers defined in this paper by Eq. 9. This enables to
that are still busy processing the third service enhance previous approximations.
should be set to s2 − (ω − s1 − s2 ). This
number is set to s2 in the equation of the • Region 4 (c ≤ i ≤ c + r, 0 ≤ j < c, and
transition probabilities proposed by Khazaei et i + 1 ≥ j):
6
Stochastic Model for Cloud Dada Center
with M/G/c/c+r Queue
Outamazirt • Escheikh • Aı̈ssani • Barkaoui • Lekadir
In this region, at the beginning of T there are In the case where s1 ≥ i − c + 1, the Eq. 20 will
i − c + 1 tasks in the waiting queue and all c be equal to:
servers are busy, while at the end of T , the min(ω,c) {
∑
waiting queue is empty and there are c − j pij =
1
Ccs1 Pxs1 (1 − Px )c−s1
servers are idle. (1 − Pz,3 )c−j
s =c−j
1
The equation of the transition probabilities ∑
min(ω−s1 ,s1 ) [
proposed by Khazaei et al. (2012) for this s2
Ci−c+1 s2
Pz,2 (1 − Pz,2 )s1 −s2
region is given by: s2 =min(ω−s1 ,c−j)
ω−s1 −s2
min(ω,c) { Cmin(max(i−c+1−s P ω−s1 −s2
∑ 1 ,0),s2 ) z,3
]}
pij = Ccs1 Pxs1 (1 − Px )c−s1 (1 − Pz,3 )s2 −max(i−c+1−s1 −s2 ,0) , (21)
s1 =c−j
∑
min(w−s1 ,s1 ) [ therefore, the max(i − c + 1 − s1 , 0) = 0,
Css12 Pz,2
s2
(1 − Pz,2 )s1 −s2
min(max(i − c + 1 − s1 , 0), s2 ) = 0 and max(i −
s2 =min(ω−s1 ,c−j)
c + 1 − s1 − s2 , 0) = 0. As the waiting queue is
1 −s2 w−s1 −s2
Csω−s Pz,3 empty (all i − c + 1 tasks in waiting queue enter
]}
2
(1 − Pz,3 )s2 . (19) service because s1 ≥ i−c+1), then the number
of servers that will complete three services
during T is equal to 0 (i.e. ω − s1 − s2 =0).
In this equation, Khazaei et al. (2012) had not Therefore, the number of servers that will be
taken into account the number of tasks in the idle at the end of T is equal to s2 , i.e. c−j = s2 .
waiting queue at the beginning of T . However, Thus, Eq. 21 will be equal to:
in this region we distinguish two cases:
– case 1: If s1 ≥ i − c + 1, there are at most min(ω,c) {
∑
i−c+1 tasks that begin service at a subset pij = Ccs1 Pxs1 (1 − Px )c−s1
of the s1 servers that have completed one s1 =c−j
services in T and, there are s1 − (i − c + 1) ∑
min(ω−s1 ,s1 ) [
s2 s2
servers remain idle because the waiting Ci−c+1 Pz,2
s2 =min(ω−s1 ,c−j)
queue is empty. ]}
– case 2: If s1 < i − c + 1, there are s1 tasks (1 − Pz,2 )s1 −s2 . (22)
begin service at a subset of the s1 servers
that have completed one services in T .
In this equation, if the number of servers that
Chang et al. (2014) proposed a new equation
complete the second service is equal to i−c+1,
for the transition probabilities for this region:
then at the end of T , the number of servers
remain busy processing the second service is
min(ω,c) {
∑ equal to i − c + 1 − s2 , while in the Eq. 22,
1
pij = Ccs1 Pxs1 (1 − Px )c−s1 this number is equal to s1 − s2 , consequently,
(1 − Pz,3 )c−j
s =c−j
1 the number of tasks in the system at the
∑
min(ω−s1 ,s1 ) [ end of T exceeds j. Therefore, the coefficient
s2
P s2 (1 − Pz,2 )s1 −s2
(1−Pz,3 )c−j is not valid when s1 ≥ i − c + 1, but
Cmin(i−c+1,s 1
1 ) z,2
s2 =min(ω−s1 ,c−j)
it is valid just when s1 < i − c + 1.
ω−s1 −s2
Cmin(max(i−c+1−s P ω−s1 −s2
1 ,0),s2 ) z,3
]} Accounting for the above analysis for this
(1 − Pz,3 )s2 −max(i−c+1−s1 −s2 ,0) . (20) region we study the two cases cited above
separately and we propose in this paper a new
In this equation, the authors considered the approximate formula for each case (Eq. 14,
number of servers that are still busy processing Eq. 15 resp.). Consequently, a new accurate
the third service is equal to s2 − max(i − c + approximation of the transition probabilities for
1 − s1 − s2 , 0), because they assumed that all the region 4 is defined in this paper by Eq. 12.
servers that enter in the idle state during T they
do not complete the service, even though the
servers are idle. In order to correctly account 4. CONCLUSION
for the c − j idle servers at the end of T ,
In this paper we used the same analytical model,
they multiplied the equation of the transition
1 M/G/c/c + r queuing system, proposed by Khazaei
probabilities for this region by (1−Pz,3 )c−j . et al. (2012) for modeling the cloud computing
center. However, we focused on the one-step
transition matrix of this model because we constated
7
Stochastic Model for Cloud Dada Center
with M/G/c/c+r Queue
Outamazirt • Escheikh • Aı̈ssani • Barkaoui • Lekadir
that the analysis of this model differs from an Amazon (2010) Amazon Elastic Compute Cloud,
author to another (see the analysis of Khazaei User Guide, API Version ed., Amazon Web
et al. (2012), Chang et al. (2014)). So, we Service LLC or Its Affiliate. Available from
proposed a new approximation formulas for the http://aws.amazon.com/documentation/ec2.
one-step state-transition probabilities. Compared to
the existing approximation formulas for the one- Zhang Q., Hellerstein J. and Boutaba R. (2011)
step state-transition probabilities, our approximation Characterizing task usage shapes in Google’s
formulas improved the computation of the transition compute clusters, LADIS Workshop.
probabilities of the M/G/c/c + r transition matrix. Reiss C., Tumanov A., Ganger G. R., Katz R., and
Kozuch M. (2012) Heterogeneity and Dynamicity
Our future work, will be consecrate to the
of Clouds at Scale: Google Trace Analysis. Proc.
presentation of the numerical results. We also plan
ACM Symposium on Cloud Computing.
to extend the model M/G/c/c + r queuing system
with one-step transition matrix by considering the Xiong K. and Perros H. (2009) Service Performance
services with different priorities and batch-task and Analysis in Cloud Computing. proceedings of
arrivals. the 2009 Congress on Services. Los Angeles, CA,
6-10 July 2009. IEEE. 693-700.
REFERENCES Chang X., Wang B., Muppala J. K., Liu J. (2014)
Modeling active virtual machines on IaaS clouds
Mell P., and Grance T. (2009) The NIST using an M/G/m/m+K queue. IEEE Transactions
Definition of Cloud Computing. Available from on Services Computing, vol. PP. 1-1.
http://www.cloudbook.net/resources/stories/the-
nist-definition-of-cloud-computing Yang B., Tan F., Dai Y. and Guo S. (2009) Perfor-
mance Evaluation of Cloud Service Considering
Furht B. (2010) Cloud Computing Fundamentals. In: Fault Recovery. proceedings First International
Furht B. and Escalante A. (Eds.). Handbook of Conference, CloudCom 2009. Beijing, China, 1-4
Cloud Computing. Springer. 3-19. December 2009. Springer Berlin Heidelberg. 571-
Wang L., Von Laszewski G., Younge A. , He X., 576
Kunze M., Tao J., and Fu C. (2010) Cloud Ani Brown Mary N. and Saravanan K. (2013)
Computing: A Perspective Study. New Generation Performance Factors of Cloud Computing Data
Computing, vol. 28. 137-146. Centers Using [(M/G/1) : (∞/GD M ODEL)]
Khazaei H., Misic J. , and Vojislav B. M. (2012) Queuing Systems. International Journal of Grid
Performance analysis of cloud computing centers Computing & Applications IJGCA, Vol 4, 1-9.
using M/G/m/m + r queueing systems. IEEE Kimura T. (1996a) A Transform-Free Approximation
Transactions on Parallel and Distributed Systems, for the Finite Capacity M/G/s Queue. Operations
vol. 23. 936-943. Research, vol. 44, 984-988.
Nozaki S.A. and Ross S.M. (1978) Approximations in Kimura T. (1996b) Optimal Buffer Design of an
Finite-Capacity Multi-Server Queues with Poisson M/G/s Queue with Finite Capacity. Comm. in
Arrivals. Applied Probability, vol. 15, 826-834. Statistics Stochastic Models, vol. 12, 165-180.
Yao D.D. (1985) Refining the diffusion approximation Smith J.M. (2003) M/G/c/K Blocking Probability
for the M/G/m queue. Operations Research, vol. Models and System Performance. Performance
33, 1266-1277. Evaluation, vol. 52, 237-267.
Kimura T. (1983) Diffusion Approximation for an Kleinrock L. (1975) Queueing Systems vol. 1,
M/G/m Queue. Operations Research, vol. 31, Theory. Wiley-Interscience.
304-321.
Takagi H. (1991) Queueing Analysis. vol. 1, Vacation
Tijms H.C., Hoorn M.H.V. and, Federgru A. (1981) and Priority Systems. North-Holland.
Approximations for the Steady-State Probabilities
in the M/G/c Queue. Advances in Applied
Probability, vol. 13, 186-206.
Boxma O.J., Cohen J.W. , and, Huffel N. (1979)
Approximations of the Mean Waiting Time in an
M/G/s Queueing System. Operations Research,
vol. 27, 1115-1127.
8