# Dynamic Scalable Stochastic Petri Net: A Novel Model for Designing and Analysis of Resource Scheduling in Cloud Computing

Authors: Hua He; Shanchen Pang; Zenghua Zhao
Journal: Scientific Programming
 (2016)

---

## Abstract

Performance evaluation of cloud computing systems studies the relationships among system configuration, system load, and performance indicators. However, such evaluation is not feasible by dint of measurement methods or simulation methods, due to the properties of cloud computing, such as large scale, diversity, and dynamics. To overcome those challenges, we present a novel Dynamic Scalable Stochastic Petri Net (DSSPN) to model and analyze the performance of cloud computing systems. DSSPN can not only clearly depict system dynamic behaviors in an intuitive and efficient way but also easily discover performance deficiencies and bottlenecks of systems. In this study, we further elaborate some properties of DSSPN. In addition, we improve fair scheduling taking into consideration job diversity and resource heterogeneity. To validate the improved algorithm and the applicability of DSSPN, we conduct extensive experiments through Stochastic Petri Net Package (SPNP). The performance results show that the improved algorithm is better than fair scheduling in some key performance indicators, such as average throughput, response time, and average completion time.


---

## Body

## 1. Introduction

Cloud computing provides shared configurable resources to users as services with pay-as-you-go scheme [1]. These services that consisted of set of components may be offered by different providers [2]. To meet the needs of customers, cloud service providers have to ensure that their profit and return on investment are not rapidly decreased due to increased costs, while maintaining a desirable level of the quality of service (QoS) of consumers, such as execution time, delay time, and budget restrictions [2–4]. To address this problem, most researches of cloud computing have focused on performance improvement and satisfaction of the QoS requirements and developed some efficient solutions. But for now, little work has been done about finding a convenient method of modeling, analyzing, and evaluating the performance of scheduling algorithms or systems in cloud environment without spending too much time on comparison and analysis [5, 6].Performance evaluation is important to cloud computing development. It is primarily aimed at selecting schemes that meet the requirements of consumers, finding out performance defects, predicting performance of the designed systems in future, and discovering better ways to achieve optimal resource allocation. In other words, performance evaluation is important in selecting, improving, and designing systems or scheduling algorithms in cloud computing environment [7]. The methods of performance evaluation are approximately divided into three types: measurement method, simulation method, and model method. However, measurement and simulation methods are only applicable to existing and running systems and might be time consuming. In addition, the two methods are incapable of finding out performance bottlenecks and analyzing large-scale and complicated cloud computing systems. In this study, we only focus on the model method.Model method is a kind of analysis method of performance evaluation by studying and describing the relationships among performance, system, and load based on mathematical theories. To facilitate mathematical descriptions and calculation, it usually requires simplification of the system model and making some rational assumptions about the status of the system. Compared to the other two methods, model method is based on a mature theoretical foundation and can clearly describe the relationship among all factors with a lower cost.Stochastic Petri Net (SPN) is a powerful tool of model method and can be applied to graphic modeling and mathematical analysis of many systems and areas, such as computer science, communication network, and multiprocessor system [8–13]. It can not only easily describe the properties of systems that have concurrency and synchronization characteristics but also clearly depict dynamic behaviors of systems in an intuitive and efficient way. In this way, it is easy to discover performance deficiencies and bottlenecks by using SPN in analysis.However, SPN is still not entirely suitable for modeling and performance evaluation of cloud computing systems: (i) cloud computing offers scalable infrastructures to consumers on demand by utilizing the virtualization technology. SPN is not capable of adjusting models dynamically when the infrastructure changes [13]. (ii) Different workloads submitted by users, which are simultaneously running on cloud clusters, might have different QoS requirements, such as response time, execution time, and data traffic [14]. However, SPN is incapable of representing the diversity of cloud computing. (iii) The configurable shared resources in cloud computing are usually heterogeneous and geographically distributed, so using SPN to build up models will increase the computational complexity and result in state explosion. Because of the problems mentioned above, SPN does not adequately model and analyze the performance of cloud computing in many situations.To overcome those challenges, we propose a novel extended form of SPN, which is called Dynamic Scalable Stochastic Petri Net (DSSPN), to conveniently model and analyze the performance of cloud computing systems. In order to support dynamic changes in cloud computing, three kinds of functions are introduced to enhance the dynamics of arcs, transitions, and places in DSSPN. In addition, many cloud service patterns under the same state can be compressed into a simple one by using DSSPN. Therefore, cloud computing systems can be easily modeled and analyzed by using DSSPN without changing the original graph structure. Consumers can easily evaluate performances only by setting the three functions of the DSSPN model without spending too much time on programming. According to the feature of SPN, system decomposition and model compression can be applied to reduce the complexity of the state space in DSSPN models.The main contributions of this paper include (1) proposing Dynamic Scalable Stochastic Petri Net (DSSPN) and then further demonstrating firing rules and some properties of DSSPN; (2) presenting classified fair scheduling (CFS) taking into consideration job diversity and resource heterogeneity, which can improve throughput and response time; (3) validating the proposed approach and algorithm, where we conduct and evaluate DSSPN models of fair scheduling and CFS algorithms by using Stochastic Petri Net Package (SPNP) [15, 16] analysis and simulation.The remainder of the paper is organized as follows. Section2 describes the related works of this study. Section 3 specifies the novel analytical model called DSSPN and elaborates its dynamics as well as some other properties. In Section 4, we construct a DSSPN model of resource scheduling of fair scheduler and propose the classified fair scheduling (CFS) algorithm taking into consideration the workload and resources diversity. In addition, in order to alleviate the problem of state explosion, we adopt the multiuser multiserver model [17] and analyze some parameters by using equivalent Markov model to refine our original models in Section 4. Section 5 demonstrates the experimental parameters setup and evaluates the system performance of the two scheduling algorithms by using SPNP. Finally, conclusions and future works are given in Section 6.


## 2. Related Works

Performance evaluation mainly focuses on relationships among system configuration, system load, and performance indicators and has drawn much research attention recently. Due to the complexity of the problem, most studies adopt measurement and simulation methods to quantitatively analyze system performance [18].By using some measuring devices or measuring programs, measurement and simulation methods can directly obtain the performance indicators of systems or closely related quantities and then work out performance indexes by the corresponding calculation. Ostermann et al. analyze the performance of the Amazon EC2 platform based on measurement at the background of scientific computing [19]. In addition, performance comparisons were made among EC2 and other platforms by using long-term traces of experimental data in some indicators, such as resource acquisition, release overheads, and system workload. Calheiros et al. propose extensible simulation toolkit CloudSim, which can model, simulate, and evaluate the performance of both cloud computing systems and application provisioning environments [20]. CloudSim supports single and internetworked cloud scenarios and is used by several organizations to investigate cloud resource allocation and energy efficiency management of data center resources. Bautista et al. present a performance measurement framework (PMF) for cloud computing systems with integration software quality concepts from ISO 25010 [21]. The PMF defines the requirements, data types, and evaluation criteria to measure “cluster behavior” performance. Mei et al. study performance measurement of network I/O applications in virtualized cloud [22]. This measurement is based on performance impact of coexisting applications in a virtualized cloud, such as throughput and resource sharing effectiveness. In addition, the measurement can quantify the performance gains and losses and reveal the importance of optimizing for application deployment.Measurement and simulation methods are the most direct and basic ones on performance evaluation, which the model method partly depends on. However, the two methods are only applicable to existing and running systems, and there are a lot of insufficiencies and abuses in evaluating the performance of cloud systems which are under dynamic environments and involve lots of parameters, such as time consuming, low degree of simulation, and quantitative difficulty. In addition, measurement and simulation methods are also incapable of finding out performance bottlenecks. Therefore, how to provide powerful mathematic tool, intuitional description method of models, effective analysis method, and available analysis software is the urgent problem for performance evaluation of cloud systems, which is just the core of analysis technology based on SPN. However, there have been few studies on the application of SPN in cloud computing.Cao et al. construct stochastic evaluation model based on Queuing Petri Net for “Chinese Cloud” of State Key Laboratory of High-End Server& Storage Technology [23]. They still present three kinds of cloud system architectures, distributed architecture, centralized architecture, and hybrid architecture, and then model the three architectures based on Queuing Petri Net. These models describe the relationships among network, CPU, I/O, and request queue. Finally, system throughputs of the three architectures are compared in different task types and workloads with QPME tool [24].Targeting the dynamic feature of cloud computing, Fan et al. propose a systematic method to describe the reliability, running time, and failure processing of resource scheduling [25]. In this study, resources scheduling process is abstracted as metaobject by using a reflection mechanism, and Petri Net is introduced to model its components, such as base layer, metalayer, and metaobject protocol. In addition, they present an adaptive resource scheduling strategy described by Computation Tree Logic (CTL) [26], which can realize dynamic reoptimization and distribution of system resources at runtime. Finally, Petri Net and its state space are used to verify the correctness and effectiveness of the proposed algorithm.In order to evaluate the performance of the Hadoop system, Ruiz et al. introduce Prioritised-Timed Coloured Petri Net (PTCPN) [27] to formally construct its stochastic model of MapReduce paradigm [28]. Tradeoffs are made between processing time and resource cost according to some performance evaluation parameters. In addition, state space and CPNTools [29] auxiliary software will execute the quantitative analysis of the system performance and the accuracy verification of the models.It is concluded that the above-mentioned methods of performance evaluation of cloud computing can well describe and model the various properties of cloud computing, but there are difficulties in comparative analysis. To overcome these challenges, we present a novel Dynamic Scalable Stochastic Petri Net (DSSPN) to better depict the important properties of cloud systems. Compared to other SPNs, DSSPN has the following advantages: (1) intuitive graphical representation and model easy to understand; (2) no requirements for strong mathematical background; (3) capability of flexibly depicting characteristics of cloud systems, such as the relationship between network topology and other components; and (4) automatically deriving the steady-state probability of state transitions by using auxiliary software, such as SPNP and SHLPNA.


## 3. Dynamic Scalable Stochastic Petri Net

Cloud computing is a service-oriented computing model, with the characteristics of large scale, complexity, resource heterogeneity, requirement of QoS diversity, and scalability. Those characteristics make the resource scheduling of cloud computing too complicated to be modeled and analyzed by the traditional Stochastic Petri Net. To overcome the problem, a novel Dynamic Scalable Stochastic Petri Net (DSSPN) is proposed in this study. DSSPN is generated from SPN [9, 30] and Stochastic Reward Net (SRN) [31]. In later sections, we will further introduce the feasibility and applicability in both modeling and performance evaluation of cloud computing systems. To easily understand the definition of DSSPN, we firstly present some notations. Let us suppose that S is a set and e is a number. |
S
| denotes the number of elements in S. S
^ represents the power set of S. [
e
] indicates the maximal integer that is not larger than e. N stands for the set of natural numbers, that is, N
=
0,1
,
2
,
…, while N
+ means the set of positive integers, that is, N
+
=
1,2
,
…. Let M
:
P
→
N denote a marking of DSSPN. R
(
M
) represents the set of reachable marking of the marking M. For all x
∈
P
∪
T, x
•
=
y
∣
(
y
,
x
)
∈
P
∪
T indicates the preset of x, while x
•
=
y
∣
(
x
,
y
)
∈
P
∪
T means the postset of x. Φ is an empty set, and ε represents an empty element.


### 3.1. Definitions of DSSPN

Definition 1.
A Dynamic Scalable Stochastic Petri Net is a 12-tuple(
P
,
T
,
F
,
K
,
W
,
λ
,
TS
,
G
,
E
,
f
,
g
,
M
0
), where (1)
P
=
p
1
,
p
2
,
…
,
p
n is a finite set of places, n
=
P;
(2)
T
=
T
I
∪
T
T is a finite set of transitions, T
I
=
t
I
1
,
t
I
2
,
…
,
t
I
m is a set of immediate transitions, and T
T
=
t
T
1
,
t
T
2
,
…
,
t
T
l is a set of timed transitions; m
=
T
I, l
=
T
T; note that T
I
∩
T
T
=
Φ;
(3)
P
∪
T
≠
Φ, and P
∩
T
=
Φ;
(4)
F
⊆
(
P
×
T
)
∪
(
T
×
P
) is a set of arcs;
(5)
K
:
P
→
N
+
∪
∞ is a capacity function where K
(
p
) denotes the capacity of the place p; let K
(
p
)
=
k
1 and T
1
=
p
•; if M
(
p
)
=
k
1, for all t
∈
T
1, t cannot be enabled;
(6)
letPr
⁡
(
M
(
P
^
)
) denote an expression of predicate logic related to the marking of the set P
^; P
^ means a subset of P;
(7)
W
:
F
→
N
∪
ε
∪
H
∪
{
Pr
⁡
(
M
(
P
^
)
→
N
)
} is a weighted function; W
(
p
,
t
) and W
(
t
,
p
) denote the weight of the a
r
c
(
p
,
t
) and (
t
,
p
), respectively. It may be a natural integer, or a function depending on the marking of the set P
^; if W
(
x
,
y
)
=
ε, it can be viewed as the weight of (
x
,
y
)
=
1; assume P
1 is a subset of P, and N
1 is a positive integer; if W
(
x
,
y
)
=
Pr
⁡
(
M
(
P
1
)
)
→
N
1, it means when Pr
⁡
(
M
(
P
1
)
)
= true, the weight of (
x
,
y
) is N
1;
(8)
H
:
M
(
P
^
)
→
R
+
∪
0 is a function which indicates the mapping from the marking of P
^ to a positive integer; let P
1
⊆
P and Z
=
M
p
∣
p
∈
P
1; then H
(
Z
)
∈
N;
(9)
λ
=
λ
1
,
λ
2
,
…
,
λ
l
∗
(
1
∨
H
) is a finite set of average transition enabling rates, where l
=
T
T;
(10)
TS
=
TS
1
,
TS
2
,
…
,
TS
n
1 is a finite set of types, where n
1
=
TS;
(11)
G
:
P
→
TS is a function denoting the type assigned to place p;
(12)
E
:
P
→
Pr
⁡
M
P
^
→
N
∪
H
⁎
N
∪
N is a function indicating the values of types; if G
(
p
)
=
TS
i, then E
(
TS
i
) stands for the value of tokens with type TS
i in place p; note that E
(
TS
i
) may be time-variant; it generally denotes the value of current period of time when a process is executed;
(13)
f
:
T
→
Pr
⁡
M
P
^
∪
ε is a function of enabling predicate, where f
(
t
) represents the enabling predicate of transition t. When f
(
t
)
=
ε, it means that the enabling condition of transition t is the same as in SPN;
(14)
g
:
(
T
→
{
ε
∪
R
+
∪
H
}
)
∪
(
P
→
N
+
) is a function of random switch, where g
(
t
) denotes the enabling priority of transition t, while g
(
p
) means the priority of place p; if there is a transition without a random switch, that is, g
(
t
)
=
ε, it represents that its enabling priority is 1 and g
(
p
)
=
ε has the same meaning of place p;
(15)
M
0
:
P
→
N is the initial marking which models the initial status of a system and satisfies: for all p
∈
P, M
0
(
p
)
≤
K
(
p
).
As described above, DSSPN is a novel extended form of SPN. The major differences lie in that the weight of an arc (or the transition enabling rate) not only is a constant but also is a function depending on the marking of a subset ofP. The weights of arcs and the transition enabling rates can be defined by customers. In addition, these values may actually change during the whole process. These features will increase the dynamic flexibility of SPN and allow the modeling process to automatically adjust.Definition 2.
The transition firing rule of DSSPN is elaborated as follows.
(1) For allt
∈
T, if ∀
p
∈
P,(1)
M
p
≥
W
p
,
t
,
if
p
∈
t
•
∧
true
,
ε
M
p
+
W
t
,
p
≥
W
p
,
t
,
if
p
∈
t
•
-
t
•
∧
f
t
∈
true
,
ε
M
p
+
W
t
,
p
-
W
p
,
t
≤
K
p
,
if
p
∈
t
•
∩
t
•
∧
f
t
∈
true
,
ε
M
p
,
otherwise
.
It is said that transitiont with the marking M is enabled, which is denoted as M
t.
(2) IfM
t and g
(
t
)
=
max
⁡
g
(
s
)
∣
s
b
e
l
o
n
g
s
t
o
P
a
n
d
s
a
t
i
s
f
i
e
s (1), then transition t can fire. After t fired, a new subsequent marking M
′ is generated from M, which is denoted as M
t
M
′ or M
→
t
M
′. For all p
∈
P,(2)
M
′
p
=
M
p
-
W
p
,
t
,
if
p
∈
t
•
∧
true
,
ε
M
p
+
W
t
,
p
,
if
p
∈
t
•
-
t
•
M
p
+
W
t
,
p
-
W
p
,
t
,
if
p
∈
t
•
∩
t
•
M
p
,
otherwise
.
In the markingM, there may be multiple transitions being enabled simultaneously. In this case, a transition is randomly chosen out from the set T
′ to be fired, where T
′
=
s
∣
g
(
s
)
=
max
⁡
{
g
(
t
)
,
t
∈
T
′
′
}, and T
′
′
=
t
∣
M
t
,
t
∈
T.
In order to formalize the dynamics of DSSPN, incidence matrix is introduced to depict its structure and behaviors.Definition 3.
The structure of a DSSPN can be expressed by using a matrix (called the incidence matrix of DSSPN) withn rows and m columns, where n
=
P and m
=
T:(3)
A
=
a
i
j
+
-
a
i
j
-
n
×
m
.
For1
≤
i
≤
n, 1
≤
j
≤
m,(4)
a
i
j
+
=
W
t
j
,
p
i
,
if
t
j
,
p
i
∈
F
∧
W
t
j
,
p
i
≠
ε
1
,
if
t
j
,
p
i
∈
F
∧
W
t
j
,
p
i
=
ε
0
,
otherwise
a
i
j
-
=
W
p
i
,
t
j
,
if
p
i
,
t
j
∈
F
∧
W
p
i
,
t
j
≠
ε
1
,
if
p
i
,
t
j
∈
F
∧
p
i
,
W
t
j
=
ε
0
,
otherwise
.
BecauseW
(
t
j
,
p
i
) or W
(
p
i
,
t
j
) can be a constant or a function depending on the marking of a subset of P, we firstly divide the set of transitions into two subsets: T
c and T
v. Consider (5)
T
c
=
t
∣
∀
p
∈
t
•
∪
t
•
,
M
p
is  related  to
a
i
j
T
v
=
T
-
T
c
.
That is, if any transition inT
c fired, the incidence matrix will be unchanged in current marking. Otherwise, a new marking will be generated and the value(s) of some element(s) will change. Suppose σ is a firing sequence of transitions. σ is firstly divided into two subsequences according to (6), σ
c and σ
v, where σ
c (or σ
v) only includes transitions in T
c (or T
v), and the orders of these transitions in σ
c and σ
v are the same as that in σ. Suppose C (an m-dimensional column vector) only counts the firing number of the transitions included in σ
c, and σ
=
t
1
t
2
⋯
t
k. Consider M
→
σ
c
M
1
→
t
1
M
2
⋯
M
k
→
t
k
M
k
+
1; then a fundamental equation [30] is obtained. The markings in the sequence change as follows: (6)
M
1
=
M
+
A
·
C
M
j
+
1
=
M
j
+
A
∗
j
,where 1
≤
j
≤
k. A
∗
j denotes the jth column vector of A. Note that if t
∈
T
v, the values of these elements in incidence matrix A, which are related to M
p
∣
p
∈
t
•
∪
t
•, should be updated after t fired.


### 3.2. Properties of DSSPN

The major motivation to model systems or processes by DSSPN is the simplicity and dynamic expressions in representing systems with multiple users and dynamic environments. In some situations, there may be redundant transitions in DSSPN models. In order to precisely and concisely describe systems, we offer the following theorems.Theorem 4.
If there are some transitions with the same meaning in a DSSPN model, these transitions can be merged into one so that each transition is unique in a DSSPN model; that is, transition redundancy can be eliminated.Proof.
Assume transitionst
2 and t
2
′ have the same meaning. The preset and postset of t
2 are t
•
2 and t
2
•, respectively. Meanwhile the preset and postset of t
2
′ are t
2
′
• and t
2
′
•. Their enabling predicates and random switches are f
(
t
2
), f
(
t
2
′
), g
(
t
2
), and g
(
t
2
′
), respectively. Let us suppose t
1 is a forerunner transition of t
2 and t
1
′ is a forerunner transition of t
2
′. The two transitions can be merged as follows:(a)
Transitionst
2 and t
2
′ are merged into one transition t.
(b)
The preset oft is t
•
=
t
•
2
∪
t
2
′
•. For all p
,
s
∈
t
•
∪
t
•, p
≠
s; if their types and values are the same, that is, G
(
p
)
=
G
(
s
) and E
(
p
)
=
E
(
s
), then places p and s will be merged into one place, denoted by p
′. Moreover, the type and the corresponding value remain the same.
(c)
The enabling predicate isf
(
t
)
=
f
(
t
2
)
∨
f
(
t
2
′
), and the random switch is g
(
t
)
=
g
(
t
2
)
∧
g
(
t
2
′
).
(d)
Assumep and s will be merged; if p
∈
t
•
2 and s
∈
t
2
′
• or p
∈
t
2
• and s
∈
t
2
′
•, the weights of arcs relating to merged transition t and place p
′ are set as follows:(7)
W
p
′
,
t
=
f
t
2
⟶
W
p
,
t
2
f
t
2
′
⟶
W
s
,
t
2
′
or
W
t
,
p
′
=
f
t
2
⟶
W
t
2
,
p
f
t
2
′
⟶
W
t
2
′
,
s
.
Figure1 shows an example to merge transitions t
2 and t
3 with the same meaning. For places p
2, p
3, p
4, and p
5, assume G
(
p
2
)
=
G
(
p
3
), E
(
p
2
)
=
E
(
p
3
), G
(
p
4
)
=
G
(
p
5
), and E
(
p
4
)
=
E
(
p
5
). Note that the weights of some arcs relating to merged transitions and places will be changed, where(8)
w
1
′
=
f
t
2
⟶
w
1
f
t
3
⟶
w
2
w
2
′
=
f
t
2
⟶
w
3
f
t
3
⟶
w
4
w
3
′
=
f
t
3
⟶
w
5
0
.
As illustrated in Theorem4, a DSSPN model can eliminate redundant transitions. In DSSPN, each service or activity only corresponds to one transition that models a dynamic process or a system including multiple customers on a more convenient way.Figure 1
Equivalent transformation of merging two transitions with the same meaning.Theorem 5.
A DSSPN can be transformed into a simple net [17], such that, for all x
,
y
∈
P
∪
T, the preset of x is equal to that of y while the postset of x is equal to that of y only if x equals y; that is, (9)
x
•
=
y
•
∧
x
•
=
y
•
⟶
x
=
y
,
∀
x
,
y
∈
P
∪
T
.Proof.
First, we consider the case of two places with the same preset and postset, as shown in Figure2. If G
(
p
)
=
G
(
s
) and E
(
p
)
=
E
(
s
), we can easily transform it into a simple net just as illustrated in Theorem 4. Otherwise, we insert two new immediate transitions and two new places into the original model. Then the original net transforms into a simple one. Two things to note here are the settings of new arcs and places, that is, W
(
p
1
,
d
1
)
=
W
(
d
1
,
p
3
)
=
W
(
p
3
,
t
2
)
=
W
(
p
1
,
t
2
) and W
(
p
2
,
d
2
)
=
W
(
d
2
,
p
4
)
=
W
(
p
4
,
t
2
)
=
W
(
p
1
,
t
2
), while the settings of p
3 and p
4 are the same as those of p
1 and p
2. Similarly, the case of two transitions with the same preset and postset can be proven, just as shown in Figure 3.Figure 2
Equivalent transformation of two places with the same preset and postset.Figure 3
Equivalent transformation of two transitions with the same preset and postset.


## 3.1. Definitions of DSSPN

Definition 1.
A Dynamic Scalable Stochastic Petri Net is a 12-tuple(
P
,
T
,
F
,
K
,
W
,
λ
,
TS
,
G
,
E
,
f
,
g
,
M
0
), where (1)
P
=
p
1
,
p
2
,
…
,
p
n is a finite set of places, n
=
P;
(2)
T
=
T
I
∪
T
T is a finite set of transitions, T
I
=
t
I
1
,
t
I
2
,
…
,
t
I
m is a set of immediate transitions, and T
T
=
t
T
1
,
t
T
2
,
…
,
t
T
l is a set of timed transitions; m
=
T
I, l
=
T
T; note that T
I
∩
T
T
=
Φ;
(3)
P
∪
T
≠
Φ, and P
∩
T
=
Φ;
(4)
F
⊆
(
P
×
T
)
∪
(
T
×
P
) is a set of arcs;
(5)
K
:
P
→
N
+
∪
∞ is a capacity function where K
(
p
) denotes the capacity of the place p; let K
(
p
)
=
k
1 and T
1
=
p
•; if M
(
p
)
=
k
1, for all t
∈
T
1, t cannot be enabled;
(6)
letPr
⁡
(
M
(
P
^
)
) denote an expression of predicate logic related to the marking of the set P
^; P
^ means a subset of P;
(7)
W
:
F
→
N
∪
ε
∪
H
∪
{
Pr
⁡
(
M
(
P
^
)
→
N
)
} is a weighted function; W
(
p
,
t
) and W
(
t
,
p
) denote the weight of the a
r
c
(
p
,
t
) and (
t
,
p
), respectively. It may be a natural integer, or a function depending on the marking of the set P
^; if W
(
x
,
y
)
=
ε, it can be viewed as the weight of (
x
,
y
)
=
1; assume P
1 is a subset of P, and N
1 is a positive integer; if W
(
x
,
y
)
=
Pr
⁡
(
M
(
P
1
)
)
→
N
1, it means when Pr
⁡
(
M
(
P
1
)
)
= true, the weight of (
x
,
y
) is N
1;
(8)
H
:
M
(
P
^
)
→
R
+
∪
0 is a function which indicates the mapping from the marking of P
^ to a positive integer; let P
1
⊆
P and Z
=
M
p
∣
p
∈
P
1; then H
(
Z
)
∈
N;
(9)
λ
=
λ
1
,
λ
2
,
…
,
λ
l
∗
(
1
∨
H
) is a finite set of average transition enabling rates, where l
=
T
T;
(10)
TS
=
TS
1
,
TS
2
,
…
,
TS
n
1 is a finite set of types, where n
1
=
TS;
(11)
G
:
P
→
TS is a function denoting the type assigned to place p;
(12)
E
:
P
→
Pr
⁡
M
P
^
→
N
∪
H
⁎
N
∪
N is a function indicating the values of types; if G
(
p
)
=
TS
i, then E
(
TS
i
) stands for the value of tokens with type TS
i in place p; note that E
(
TS
i
) may be time-variant; it generally denotes the value of current period of time when a process is executed;
(13)
f
:
T
→
Pr
⁡
M
P
^
∪
ε is a function of enabling predicate, where f
(
t
) represents the enabling predicate of transition t. When f
(
t
)
=
ε, it means that the enabling condition of transition t is the same as in SPN;
(14)
g
:
(
T
→
{
ε
∪
R
+
∪
H
}
)
∪
(
P
→
N
+
) is a function of random switch, where g
(
t
) denotes the enabling priority of transition t, while g
(
p
) means the priority of place p; if there is a transition without a random switch, that is, g
(
t
)
=
ε, it represents that its enabling priority is 1 and g
(
p
)
=
ε has the same meaning of place p;
(15)
M
0
:
P
→
N is the initial marking which models the initial status of a system and satisfies: for all p
∈
P, M
0
(
p
)
≤
K
(
p
).
As described above, DSSPN is a novel extended form of SPN. The major differences lie in that the weight of an arc (or the transition enabling rate) not only is a constant but also is a function depending on the marking of a subset ofP. The weights of arcs and the transition enabling rates can be defined by customers. In addition, these values may actually change during the whole process. These features will increase the dynamic flexibility of SPN and allow the modeling process to automatically adjust.Definition 2.
The transition firing rule of DSSPN is elaborated as follows.
(1) For allt
∈
T, if ∀
p
∈
P,(1)
M
p
≥
W
p
,
t
,
if
p
∈
t
•
∧
true
,
ε
M
p
+
W
t
,
p
≥
W
p
,
t
,
if
p
∈
t
•
-
t
•
∧
f
t
∈
true
,
ε
M
p
+
W
t
,
p
-
W
p
,
t
≤
K
p
,
if
p
∈
t
•
∩
t
•
∧
f
t
∈
true
,
ε
M
p
,
otherwise
.
It is said that transitiont with the marking M is enabled, which is denoted as M
t.
(2) IfM
t and g
(
t
)
=
max
⁡
g
(
s
)
∣
s
b
e
l
o
n
g
s
t
o
P
a
n
d
s
a
t
i
s
f
i
e
s (1), then transition t can fire. After t fired, a new subsequent marking M
′ is generated from M, which is denoted as M
t
M
′ or M
→
t
M
′. For all p
∈
P,(2)
M
′
p
=
M
p
-
W
p
,
t
,
if
p
∈
t
•
∧
true
,
ε
M
p
+
W
t
,
p
,
if
p
∈
t
•
-
t
•
M
p
+
W
t
,
p
-
W
p
,
t
,
if
p
∈
t
•
∩
t
•
M
p
,
otherwise
.
In the markingM, there may be multiple transitions being enabled simultaneously. In this case, a transition is randomly chosen out from the set T
′ to be fired, where T
′
=
s
∣
g
(
s
)
=
max
⁡
{
g
(
t
)
,
t
∈
T
′
′
}, and T
′
′
=
t
∣
M
t
,
t
∈
T.
In order to formalize the dynamics of DSSPN, incidence matrix is introduced to depict its structure and behaviors.Definition 3.
The structure of a DSSPN can be expressed by using a matrix (called the incidence matrix of DSSPN) withn rows and m columns, where n
=
P and m
=
T:(3)
A
=
a
i
j
+
-
a
i
j
-
n
×
m
.
For1
≤
i
≤
n, 1
≤
j
≤
m,(4)
a
i
j
+
=
W
t
j
,
p
i
,
if
t
j
,
p
i
∈
F
∧
W
t
j
,
p
i
≠
ε
1
,
if
t
j
,
p
i
∈
F
∧
W
t
j
,
p
i
=
ε
0
,
otherwise
a
i
j
-
=
W
p
i
,
t
j
,
if
p
i
,
t
j
∈
F
∧
W
p
i
,
t
j
≠
ε
1
,
if
p
i
,
t
j
∈
F
∧
p
i
,
W
t
j
=
ε
0
,
otherwise
.
BecauseW
(
t
j
,
p
i
) or W
(
p
i
,
t
j
) can be a constant or a function depending on the marking of a subset of P, we firstly divide the set of transitions into two subsets: T
c and T
v. Consider (5)
T
c
=
t
∣
∀
p
∈
t
•
∪
t
•
,
M
p
is  related  to
a
i
j
T
v
=
T
-
T
c
.
That is, if any transition inT
c fired, the incidence matrix will be unchanged in current marking. Otherwise, a new marking will be generated and the value(s) of some element(s) will change. Suppose σ is a firing sequence of transitions. σ is firstly divided into two subsequences according to (6), σ
c and σ
v, where σ
c (or σ
v) only includes transitions in T
c (or T
v), and the orders of these transitions in σ
c and σ
v are the same as that in σ. Suppose C (an m-dimensional column vector) only counts the firing number of the transitions included in σ
c, and σ
=
t
1
t
2
⋯
t
k. Consider M
→
σ
c
M
1
→
t
1
M
2
⋯
M
k
→
t
k
M
k
+
1; then a fundamental equation [30] is obtained. The markings in the sequence change as follows: (6)
M
1
=
M
+
A
·
C
M
j
+
1
=
M
j
+
A
∗
j
,where 1
≤
j
≤
k. A
∗
j denotes the jth column vector of A. Note that if t
∈
T
v, the values of these elements in incidence matrix A, which are related to M
p
∣
p
∈
t
•
∪
t
•, should be updated after t fired.


## 3.2. Properties of DSSPN

The major motivation to model systems or processes by DSSPN is the simplicity and dynamic expressions in representing systems with multiple users and dynamic environments. In some situations, there may be redundant transitions in DSSPN models. In order to precisely and concisely describe systems, we offer the following theorems.Theorem 4.
If there are some transitions with the same meaning in a DSSPN model, these transitions can be merged into one so that each transition is unique in a DSSPN model; that is, transition redundancy can be eliminated.Proof.
Assume transitionst
2 and t
2
′ have the same meaning. The preset and postset of t
2 are t
•
2 and t
2
•, respectively. Meanwhile the preset and postset of t
2
′ are t
2
′
• and t
2
′
•. Their enabling predicates and random switches are f
(
t
2
), f
(
t
2
′
), g
(
t
2
), and g
(
t
2
′
), respectively. Let us suppose t
1 is a forerunner transition of t
2 and t
1
′ is a forerunner transition of t
2
′. The two transitions can be merged as follows:(a)
Transitionst
2 and t
2
′ are merged into one transition t.
(b)
The preset oft is t
•
=
t
•
2
∪
t
2
′
•. For all p
,
s
∈
t
•
∪
t
•, p
≠
s; if their types and values are the same, that is, G
(
p
)
=
G
(
s
) and E
(
p
)
=
E
(
s
), then places p and s will be merged into one place, denoted by p
′. Moreover, the type and the corresponding value remain the same.
(c)
The enabling predicate isf
(
t
)
=
f
(
t
2
)
∨
f
(
t
2
′
), and the random switch is g
(
t
)
=
g
(
t
2
)
∧
g
(
t
2
′
).
(d)
Assumep and s will be merged; if p
∈
t
•
2 and s
∈
t
2
′
• or p
∈
t
2
• and s
∈
t
2
′
•, the weights of arcs relating to merged transition t and place p
′ are set as follows:(7)
W
p
′
,
t
=
f
t
2
⟶
W
p
,
t
2
f
t
2
′
⟶
W
s
,
t
2
′
or
W
t
,
p
′
=
f
t
2
⟶
W
t
2
,
p
f
t
2
′
⟶
W
t
2
′
,
s
.
Figure1 shows an example to merge transitions t
2 and t
3 with the same meaning. For places p
2, p
3, p
4, and p
5, assume G
(
p
2
)
=
G
(
p
3
), E
(
p
2
)
=
E
(
p
3
), G
(
p
4
)
=
G
(
p
5
), and E
(
p
4
)
=
E
(
p
5
). Note that the weights of some arcs relating to merged transitions and places will be changed, where(8)
w
1
′
=
f
t
2
⟶
w
1
f
t
3
⟶
w
2
w
2
′
=
f
t
2
⟶
w
3
f
t
3
⟶
w
4
w
3
′
=
f
t
3
⟶
w
5
0
.
As illustrated in Theorem4, a DSSPN model can eliminate redundant transitions. In DSSPN, each service or activity only corresponds to one transition that models a dynamic process or a system including multiple customers on a more convenient way.Figure 1
Equivalent transformation of merging two transitions with the same meaning.Theorem 5.
A DSSPN can be transformed into a simple net [17], such that, for all x
,
y
∈
P
∪
T, the preset of x is equal to that of y while the postset of x is equal to that of y only if x equals y; that is, (9)
x
•
=
y
•
∧
x
•
=
y
•
⟶
x
=
y
,
∀
x
,
y
∈
P
∪
T
.Proof.
First, we consider the case of two places with the same preset and postset, as shown in Figure2. If G
(
p
)
=
G
(
s
) and E
(
p
)
=
E
(
s
), we can easily transform it into a simple net just as illustrated in Theorem 4. Otherwise, we insert two new immediate transitions and two new places into the original model. Then the original net transforms into a simple one. Two things to note here are the settings of new arcs and places, that is, W
(
p
1
,
d
1
)
=
W
(
d
1
,
p
3
)
=
W
(
p
3
,
t
2
)
=
W
(
p
1
,
t
2
) and W
(
p
2
,
d
2
)
=
W
(
d
2
,
p
4
)
=
W
(
p
4
,
t
2
)
=
W
(
p
1
,
t
2
), while the settings of p
3 and p
4 are the same as those of p
1 and p
2. Similarly, the case of two transitions with the same preset and postset can be proven, just as shown in Figure 3.Figure 2
Equivalent transformation of two places with the same preset and postset.Figure 3
Equivalent transformation of two transitions with the same preset and postset.


## 4. System Model Based on DSSPN

Nowadays, numerous cloud computing platforms are commercially available, such as Eucalyptus, Hadoop, and Amazon EC2 [31–33]. In this study, we take a typical cloud system by adopting fair scheduling algorithm as an example to construct a DSSPN model. Figure 4 illustrates the basic working process of tasks on a cloud platform in the light of the characteristics of a typical cloud system architecture. In the cloud system, jobs submitted by different customers may have different QoS requirements on computing time, memory space, data traffic, response time, and so forth. That is, a typical cloud platform can be viewed as a multiuser multitask system involving multiple data sets with different types of processing jobs at the same time [32]. In a cloud platform, tasks are the basic processing units in the executive process. Dispatchers firstly select tasks according to a certain rule from the waiting queues and then assign them to appropriate resources adopting some scheduling policies. However, the properties of cloud computing, such as large scale, dynamics, heterogeneity, and diversity, present a range of challenges for performance evaluation of cloud systems and cloud optimization problem [34]. In order to verify the applicability and feasibility of DSSPN, we will model and analyze the performance of a typical cloud system based on DSSPN in this section.Figure 4
Basic working process of tasks on a cloud platform.


### 4.1. Modeling Abstract

Without loss of generality, let us make the following assumptions for a typical cloud system:(1)
There aren clients, denoted by c
i. Client i submits jobs into a waiting queue (i.e., pool i) with a capacity of b
i.
(2)
The minimum share of pooli is denoted by ms
i.
(3)
In fair scheduling, the set of priorities of each pool is{
VERY_HIGH
,
HIGH
,
NORMAL
,
LOW
,
VERY_LOW
}. In order to facilitate the analysis, the set of priorities are set to 5,4
,
3,2
,
1.
(4)
The arrival process of tasks, submitted by clienti, obeys the Poisson distribution with rate of λ
i. When the number of tasks submitted by client i exceeds b
i, the job submission is rejected.
(5)
In each waiting queue, the scheduling discipline is First Come First Served (FCFS).
(6)
There arem servers (denoted by s
i), each of which has r
i virtual machines (VMs) shared by n clients.
(7)
The service rate of each VM ons
j is μ
j with exponent distribution. In addition, the service rates are generally independent of each other. Note that the sum of ms
i is equal to or smaller than the total number of resources; that is, ∑
i
=
1
n
≤
∑
j
=
1
m
r
j.


### 4.2. DSSPN Model of Fair Scheduling

Based on DSSPN, we model a typical cloud system adopting fair scheduling as a multiserver multiqueue system withn clients and m servers. The DSSPN model and involved notations are shown in Figure 5 and Notations. In order to simplify the description of the DSSPN model, we would not show the shared structures of servers.Figure 5
The refined DSSPN model of a typical cloud system adopting fair scheduling.All the places and transitions included in Figure5 are described as follows (1
≤
i
≤
n, 1
≤
j
≤
m):(1)c
j: a timed transition denotes client i submitting tasks with the firing rate of λ
i. The enabling predicate f
i of c
i is(10)
f
i
M
:
M
p
i
≤
b
i
,
1
≤
i
≤
n
.That is, client i can submit tasks when the number of tasks is smaller than its capacity.(2)p
i: a place indicates the pool storing these tasks submitted by client i, and K
(
p
i
)
=
b
i. In addition, G
(
p
i
)
=
MS, E
(
p
i
)
=
ms
i, and g
(
p
i
)
=
pl
i, where ms
i means the guaranteed minimum share of pool i, pl
i represents the priority of pool i, and pl
i
∈
5,4
,
3,2
,
1 (just as elaborated in previous section).(3)R
j: a place stands for the status of server j; for simplicity, it is not shown in Figure 5. M
(
R
j
) is the number of idle VMs of server j. K
(
R
j
)
=
r
j, which means the total number of VMs on server j.(4)d
i
j: an immediate transition indicates the execution of some scheduling or decision. The scheduling or decision is expressed by the enabling predicate f
i
j and random switch g
i
j associated with d
i
j:(11)
f
i
j
=
AR
i
<
E
p
i
∨
dem
i
≥
E
p
i
∧
∑
j
=
1
m
M
q
i
j
=
0
∧
SIDS
M
>
0
∨
dem
i
≥
E
p
i
∧
for
∀
h
≠
i
,
E
p
h
≤
E
p
i
∧
SIDS
M
>
0
g
i
j
=
5
×
1
UDLMS
M
,
if
i
∈
UDLMS
M
4
×
1
UDGMS
M
,
if
i
∈
UDGMS
M
3
×
1
ULMS
M
,
if
i
∈
DLMS
M
2
×
1
MMS
M
,
if
i
∈
MMS
M
0
,
otherwise
.In this scheme, the highest priority is firstly given to the unallocated pools whose demand is smaller than its minimum share. Secondly, a higher priority is assigned to the unallocated pools whose demands are equal to or greater than its minimum share. Then, a normal priority is given to allocated pools included inDLMS
(
M
). Finally, if there are any unallocated VMs, these idle resources will be assigned to the pools included in MMS
(
M
).(5)q
i
j: a place indicates the queue receiving tasks with the capacity of r
i
j; that is, K
(
q
i
j
)
=
r
i
j.(6)s
i
j: a timed transition stands for a VM on server j with the firing rate of μ
i
j. The server j is shared by VM s
i
j, where 1
≤
i
≤
n and 1
≤
j
≤
m.


### 4.3. DSSPN Model of Classified Fair Scheduling

Although fair scheduling can share a cluster among different users as fair as possible, it does not make good use of resources without considering various workload types or resource diversity. Various types of workload with different requirements of resources consequently launch different kinds of tasks, usually including CPU intensive tasks and I/O intensive tasks. Hence, it is beneficial for improving hardware utilization to distinguish types of tasks and resources. For example, the processing time of a CPU intensive task in resources with stronger computing power would be shorter than that in other resources. Letd
i
k denote the demand with type of k, and R
k represent the total number of VMs with type of k. Because of limited space, we only illustrate the improved part in classified fair scheduling (CFS) algorithm, shown in Algorithm 1. The remaining part of CFS is similar to that of fair scheduling presented by Zaharia et al. [35].Algorithm 1:The improved part of fair scheduling in CFS.
(1)   Initialize the classification of all available resources;
(2)   Initialize the classification of tasks when they are submitted to pools;
(3)   for each pool i whose demand ≤ its minimum share do
(3)    for each type k  do
(4)     if  d
i
k
≤
R
k  then
(5)      allocate the d
i
k resources with type of k;
(6)      R
k
-
=
d
i
k;
(6)     else
(7)      allocate the R
k resources with the type of k;
(8)      d
i
k
-
=
R
k;
(9)      allocate d
i
k resources with other types, while satisfying R
j
≥
d
i
k, j
∈
1,2
,
…
,
l;
(10)      end if
(11)   end for
(12) end for
(13) for (each pool i whose demand > its minimum share) ∧ (remaining idle unallocated VMs) do
(14) add the similar process as described above in light of the assigning decision of each pool;
(15) end forThe descriptions of places and transitions in Figure6 are similar to that in Figure 5. We will not reiterate them here. In order to facilitate understanding, we only emphasize the meaning of the subscripts for places and transitions. The subscript i denotes client i, the subscript k represents tasks with type k, and the subscript j describes server j. There are some differences on the values of some notations between Figures 5 and 6. The enabling rate of c
i
k is λ
i
k, and K
(
q
i
k
j
)
=
b
i
k
j, where ∑
i
=
1
n
‍
∑
k
=
1
l
‍
b
i
k
j
=
b
j. The enabling rate of s
i
k
j is μ
i
k
j, where ∑
i
=
1
n
‍
∑
k
=
1
l
‍
μ
i
k
j
=
μ
j. In addition, the servers are classified; that is, g
(
p
i
k
j
)
∈
1,2
,
…
,
l. The differences on the values between Figures 5 and 6 are described as follows:(12)
AR
i
=
∑
k
=
1
l
∑
j
=
1
m
M
q
i
k
j
×
Z
dem
i
=
∑
k
=
1
l
M
p
i
k
+
AR
i
SIDS
M
=
h
∣
∑
i
=
1
n
∑
k
=
1
l
M
q
i
k
h
≤
b
h
.Figure 6
The refined DSSPN model of a typical cloud system adopting CFS algorithm.Lety
i
k
j denote the service rate of s
i
k
j provided for the tasks in queue q
i
k
j:(13)
y
i
k
j
=
pl
×
μ
i
k
j
,
if
g
p
i
k
j
=
k
pl
′
×
μ
i
k
j
,
otherwise
.Note thatpl
>
pl
′. The scheme would ensure tasks whose types are the same as that of servers served at a higher priority.The major difference between fair scheduling (FS) and CFS is that tasks and resources diversity are taken into account. Without loss of generality, assume tasks and resources can be divided intol categories. The refined DSSPN model of CFS is shown in Figure 6. Note that Algorithm 1 only describes the improved part of FS [35], that is, the decision procedure to allocate resources with various types to different kinds of tasks.


### 4.4. Analysis and Solution of DSSPN Models

Although the problem of state explosion is improved to some extent in DSSPN compared to other forms of Petri Nets, it is still difficult to analyze the performance of large-scale cloud systems. Model refinement techniques elaborated by Lin [17] can develop compact models and expose the independence as well as the interdependent relations between submodels of an original model. Model refinement can lay a foundation for the decomposition and analysis of models. Consequently, the refinement of models has become a necessary step of the model design. The refinement methods have been applied to the performance evaluation of high speed network and shared resources systems [17, 36].


#### 4.4.1. Equivalent Refinement Model and Markov Model

In this section, we will make further use of enabling predicates and random switches of transitions to refine the model proposed above. Figure7 shows the equivalent model for models in Figures 5 and 6, while Figure 8 describes the equivalent Markov model of Figure 7.Figure 7
The refined DSSPN model of Figures5 and 6.Figure 8
The equivalent Markov model of Figure7.Comparing Figure7 with Figures 5 and 6, it can be found that the refined model is easier to understand and significantly reduces the state space by deleting any unnecessary vanishing states. In addition, refined model greatly decreases the complexity in performance evaluation because of structural similarities of submodels.In Figure7, immediate transitions and place p
i (or p
i
k) and related arcs are removed from Figure 5 (or Figure 6), where 1
≤
i
≤
n and 1
≤
k
≤
l. The enabling predicates and random switches associated with d
i
j and c
i
j (or d
i
k
j and c
i
k
j) have changed, while others are remaining the same. The random switch of transition c
i
j is defined as follows:(14)
g
i
j
M
:
λ
i
×
g
i
j
M
.The enabling switch of transitionc
i
k
j is(15)
g
i
k
j
M
:
λ
i
k
×
g
i
k
j
M
.


#### 4.4.2. Parameters Analysis

In order to obtain the steady-state probabilities of all states, a state transition matrix can be constructed based on the state transition rate and Markov chain illustrated in Figure8. Then, the performance parameters of the modeled cloud system can be discussed. Let P
[
M
] denote the steady-state probability of M.The throughput of transitiont is denoted as T
t:(16)
T
t
=
∑
M
∈
H
P
M
×
λ
t
,where H is a set of all markings under which transition t is enabled with the enabling rate of λ
t in marking M.The average number of tokens in placep is denoted as N
p:(17)
N
p
=
∑
j
×
P
M
p
=
j
.The throughput is a crucial indicator of the system performance. LetT
i
j (or T
i
k
j) indicate the throughput of subsystem A
i
j (or A
i
k
j). According to the illustration in [16], the throughput of the model can be calculated as follows:(18)
T
=
∑
i
=
1
n
∑
j
=
1
m
T
s
i
j
or
T
=
∑
i
=
1
n
∑
k
=
1
l
∑
j
=
1
m
T
s
i
k
j
.Another important indicator is response time.R
i
j (or R
i
k
j), R
i, and R denote the response time of subsystem A
i
j (or A
i
k
j), client i, and the system, respectively:(19)
R
i
j
=
D
q
i
j
T
s
i
j
R
i
=
∑
j
=
1
m
T
s
i
j
×
R
i
j
∖
∑
h
=
1
m
T
s
i
h
R
=
∑
i
=
1
n
R
i
×
∑
h
=
1
m
T
s
i
h
T
R
i
k
j
=
D
q
i
k
j
T
s
i
k
j
R
i
k
=
∑
j
=
1
m
T
s
i
k
j
×
R
i
k
j
∖
∑
h
=
1
m
T
s
i
k
h
R
i
=
∑
k
=
1
l
T
s
i
k
×
R
i
k
∖
∑
h
=
1
l
T
s
i
h
R
=
∑
i
=
1
n
R
i
×
∑
h
=
1
l
T
s
i
h
T
.The average rejection rate of tasks in the cloud system with FS at timet is expressed by AER
(
t
):(20)
AER
t
=
∑
i
=
1
n
∑
j
=
1
m
P
M
p
i
j
>
b
i
n
×
t
.The average rejection rate of tasks in the cloud system with CFS at timet is expressed by AER
′
(
t
):(21)
AER
′
t
=
∑
i
=
1
n
∑
k
=
1
l
∑
j
=
1
m
P
M
p
i
k
j
>
b
i
n
×
t
.The average idle rate of servers in the cloud system with FS at timet is expressed by AUR
(
t
):(22)
AUR
t
=
∑
j
=
1
m
∑
i
=
1
n
∑
y
=
0
t
1
-
P
enabled
s
i
j
y
m
×
t
,where P
enabled
s
i
j
y means the probability that transition s
i
j
(
y
) can fire at time y.The average idle rate of servers in the cloud system with CFS at timet is expressed by AUR
′
(
t
):(23)
AUR
′
t
=
∑
j
=
1
m
∑
i
=
1
n
∑
k
=
1
l
∑
y
=
0
t
1
-
P
enabled
s
i
k
j
y
m
×
t
,where P
(
enabled
(
s
i
k
j
(
y
)
)
) means the probability that transition s
i
k
j
(
y
) can fire at time y.In a multiuser multiserver cloud system, the performance parameters include the state changes of waiting queues and the service rates of shared servers. The improvement of throughput and the decrease of response time can be realized by furthest parallelizing the operations ofn servers. In other words, load balance should be maintained.


## 4.1. Modeling Abstract

Without loss of generality, let us make the following assumptions for a typical cloud system:(1)
There aren clients, denoted by c
i. Client i submits jobs into a waiting queue (i.e., pool i) with a capacity of b
i.
(2)
The minimum share of pooli is denoted by ms
i.
(3)
In fair scheduling, the set of priorities of each pool is{
VERY_HIGH
,
HIGH
,
NORMAL
,
LOW
,
VERY_LOW
}. In order to facilitate the analysis, the set of priorities are set to 5,4
,
3,2
,
1.
(4)
The arrival process of tasks, submitted by clienti, obeys the Poisson distribution with rate of λ
i. When the number of tasks submitted by client i exceeds b
i, the job submission is rejected.
(5)
In each waiting queue, the scheduling discipline is First Come First Served (FCFS).
(6)
There arem servers (denoted by s
i), each of which has r
i virtual machines (VMs) shared by n clients.
(7)
The service rate of each VM ons
j is μ
j with exponent distribution. In addition, the service rates are generally independent of each other. Note that the sum of ms
i is equal to or smaller than the total number of resources; that is, ∑
i
=
1
n
≤
∑
j
=
1
m
r
j.


## 4.2. DSSPN Model of Fair Scheduling

Based on DSSPN, we model a typical cloud system adopting fair scheduling as a multiserver multiqueue system withn clients and m servers. The DSSPN model and involved notations are shown in Figure 5 and Notations. In order to simplify the description of the DSSPN model, we would not show the shared structures of servers.Figure 5
The refined DSSPN model of a typical cloud system adopting fair scheduling.All the places and transitions included in Figure5 are described as follows (1
≤
i
≤
n, 1
≤
j
≤
m):(1)c
j: a timed transition denotes client i submitting tasks with the firing rate of λ
i. The enabling predicate f
i of c
i is(10)
f
i
M
:
M
p
i
≤
b
i
,
1
≤
i
≤
n
.That is, client i can submit tasks when the number of tasks is smaller than its capacity.(2)p
i: a place indicates the pool storing these tasks submitted by client i, and K
(
p
i
)
=
b
i. In addition, G
(
p
i
)
=
MS, E
(
p
i
)
=
ms
i, and g
(
p
i
)
=
pl
i, where ms
i means the guaranteed minimum share of pool i, pl
i represents the priority of pool i, and pl
i
∈
5,4
,
3,2
,
1 (just as elaborated in previous section).(3)R
j: a place stands for the status of server j; for simplicity, it is not shown in Figure 5. M
(
R
j
) is the number of idle VMs of server j. K
(
R
j
)
=
r
j, which means the total number of VMs on server j.(4)d
i
j: an immediate transition indicates the execution of some scheduling or decision. The scheduling or decision is expressed by the enabling predicate f
i
j and random switch g
i
j associated with d
i
j:(11)
f
i
j
=
AR
i
<
E
p
i
∨
dem
i
≥
E
p
i
∧
∑
j
=
1
m
M
q
i
j
=
0
∧
SIDS
M
>
0
∨
dem
i
≥
E
p
i
∧
for
∀
h
≠
i
,
E
p
h
≤
E
p
i
∧
SIDS
M
>
0
g
i
j
=
5
×
1
UDLMS
M
,
if
i
∈
UDLMS
M
4
×
1
UDGMS
M
,
if
i
∈
UDGMS
M
3
×
1
ULMS
M
,
if
i
∈
DLMS
M
2
×
1
MMS
M
,
if
i
∈
MMS
M
0
,
otherwise
.In this scheme, the highest priority is firstly given to the unallocated pools whose demand is smaller than its minimum share. Secondly, a higher priority is assigned to the unallocated pools whose demands are equal to or greater than its minimum share. Then, a normal priority is given to allocated pools included inDLMS
(
M
). Finally, if there are any unallocated VMs, these idle resources will be assigned to the pools included in MMS
(
M
).(5)q
i
j: a place indicates the queue receiving tasks with the capacity of r
i
j; that is, K
(
q
i
j
)
=
r
i
j.(6)s
i
j: a timed transition stands for a VM on server j with the firing rate of μ
i
j. The server j is shared by VM s
i
j, where 1
≤
i
≤
n and 1
≤
j
≤
m.


## 4.3. DSSPN Model of Classified Fair Scheduling

Although fair scheduling can share a cluster among different users as fair as possible, it does not make good use of resources without considering various workload types or resource diversity. Various types of workload with different requirements of resources consequently launch different kinds of tasks, usually including CPU intensive tasks and I/O intensive tasks. Hence, it is beneficial for improving hardware utilization to distinguish types of tasks and resources. For example, the processing time of a CPU intensive task in resources with stronger computing power would be shorter than that in other resources. Letd
i
k denote the demand with type of k, and R
k represent the total number of VMs with type of k. Because of limited space, we only illustrate the improved part in classified fair scheduling (CFS) algorithm, shown in Algorithm 1. The remaining part of CFS is similar to that of fair scheduling presented by Zaharia et al. [35].Algorithm 1:The improved part of fair scheduling in CFS.
(1)   Initialize the classification of all available resources;
(2)   Initialize the classification of tasks when they are submitted to pools;
(3)   for each pool i whose demand ≤ its minimum share do
(3)    for each type k  do
(4)     if  d
i
k
≤
R
k  then
(5)      allocate the d
i
k resources with type of k;
(6)      R
k
-
=
d
i
k;
(6)     else
(7)      allocate the R
k resources with the type of k;
(8)      d
i
k
-
=
R
k;
(9)      allocate d
i
k resources with other types, while satisfying R
j
≥
d
i
k, j
∈
1,2
,
…
,
l;
(10)      end if
(11)   end for
(12) end for
(13) for (each pool i whose demand > its minimum share) ∧ (remaining idle unallocated VMs) do
(14) add the similar process as described above in light of the assigning decision of each pool;
(15) end forThe descriptions of places and transitions in Figure6 are similar to that in Figure 5. We will not reiterate them here. In order to facilitate understanding, we only emphasize the meaning of the subscripts for places and transitions. The subscript i denotes client i, the subscript k represents tasks with type k, and the subscript j describes server j. There are some differences on the values of some notations between Figures 5 and 6. The enabling rate of c
i
k is λ
i
k, and K
(
q
i
k
j
)
=
b
i
k
j, where ∑
i
=
1
n
‍
∑
k
=
1
l
‍
b
i
k
j
=
b
j. The enabling rate of s
i
k
j is μ
i
k
j, where ∑
i
=
1
n
‍
∑
k
=
1
l
‍
μ
i
k
j
=
μ
j. In addition, the servers are classified; that is, g
(
p
i
k
j
)
∈
1,2
,
…
,
l. The differences on the values between Figures 5 and 6 are described as follows:(12)
AR
i
=
∑
k
=
1
l
∑
j
=
1
m
M
q
i
k
j
×
Z
dem
i
=
∑
k
=
1
l
M
p
i
k
+
AR
i
SIDS
M
=
h
∣
∑
i
=
1
n
∑
k
=
1
l
M
q
i
k
h
≤
b
h
.Figure 6
The refined DSSPN model of a typical cloud system adopting CFS algorithm.Lety
i
k
j denote the service rate of s
i
k
j provided for the tasks in queue q
i
k
j:(13)
y
i
k
j
=
pl
×
μ
i
k
j
,
if
g
p
i
k
j
=
k
pl
′
×
μ
i
k
j
,
otherwise
.Note thatpl
>
pl
′. The scheme would ensure tasks whose types are the same as that of servers served at a higher priority.The major difference between fair scheduling (FS) and CFS is that tasks and resources diversity are taken into account. Without loss of generality, assume tasks and resources can be divided intol categories. The refined DSSPN model of CFS is shown in Figure 6. Note that Algorithm 1 only describes the improved part of FS [35], that is, the decision procedure to allocate resources with various types to different kinds of tasks.


## 4.4. Analysis and Solution of DSSPN Models

Although the problem of state explosion is improved to some extent in DSSPN compared to other forms of Petri Nets, it is still difficult to analyze the performance of large-scale cloud systems. Model refinement techniques elaborated by Lin [17] can develop compact models and expose the independence as well as the interdependent relations between submodels of an original model. Model refinement can lay a foundation for the decomposition and analysis of models. Consequently, the refinement of models has become a necessary step of the model design. The refinement methods have been applied to the performance evaluation of high speed network and shared resources systems [17, 36].


### 4.4.1. Equivalent Refinement Model and Markov Model

In this section, we will make further use of enabling predicates and random switches of transitions to refine the model proposed above. Figure7 shows the equivalent model for models in Figures 5 and 6, while Figure 8 describes the equivalent Markov model of Figure 7.Figure 7
The refined DSSPN model of Figures5 and 6.Figure 8
The equivalent Markov model of Figure7.Comparing Figure7 with Figures 5 and 6, it can be found that the refined model is easier to understand and significantly reduces the state space by deleting any unnecessary vanishing states. In addition, refined model greatly decreases the complexity in performance evaluation because of structural similarities of submodels.In Figure7, immediate transitions and place p
i (or p
i
k) and related arcs are removed from Figure 5 (or Figure 6), where 1
≤
i
≤
n and 1
≤
k
≤
l. The enabling predicates and random switches associated with d
i
j and c
i
j (or d
i
k
j and c
i
k
j) have changed, while others are remaining the same. The random switch of transition c
i
j is defined as follows:(14)
g
i
j
M
:
λ
i
×
g
i
j
M
.The enabling switch of transitionc
i
k
j is(15)
g
i
k
j
M
:
λ
i
k
×
g
i
k
j
M
.


### 4.4.2. Parameters Analysis

In order to obtain the steady-state probabilities of all states, a state transition matrix can be constructed based on the state transition rate and Markov chain illustrated in Figure8. Then, the performance parameters of the modeled cloud system can be discussed. Let P
[
M
] denote the steady-state probability of M.The throughput of transitiont is denoted as T
t:(16)
T
t
=
∑
M
∈
H
P
M
×
λ
t
,where H is a set of all markings under which transition t is enabled with the enabling rate of λ
t in marking M.The average number of tokens in placep is denoted as N
p:(17)
N
p
=
∑
j
×
P
M
p
=
j
.The throughput is a crucial indicator of the system performance. LetT
i
j (or T
i
k
j) indicate the throughput of subsystem A
i
j (or A
i
k
j). According to the illustration in [16], the throughput of the model can be calculated as follows:(18)
T
=
∑
i
=
1
n
∑
j
=
1
m
T
s
i
j
or
T
=
∑
i
=
1
n
∑
k
=
1
l
∑
j
=
1
m
T
s
i
k
j
.Another important indicator is response time.R
i
j (or R
i
k
j), R
i, and R denote the response time of subsystem A
i
j (or A
i
k
j), client i, and the system, respectively:(19)
R
i
j
=
D
q
i
j
T
s
i
j
R
i
=
∑
j
=
1
m
T
s
i
j
×
R
i
j
∖
∑
h
=
1
m
T
s
i
h
R
=
∑
i
=
1
n
R
i
×
∑
h
=
1
m
T
s
i
h
T
R
i
k
j
=
D
q
i
k
j
T
s
i
k
j
R
i
k
=
∑
j
=
1
m
T
s
i
k
j
×
R
i
k
j
∖
∑
h
=
1
m
T
s
i
k
h
R
i
=
∑
k
=
1
l
T
s
i
k
×
R
i
k
∖
∑
h
=
1
l
T
s
i
h
R
=
∑
i
=
1
n
R
i
×
∑
h
=
1
l
T
s
i
h
T
.The average rejection rate of tasks in the cloud system with FS at timet is expressed by AER
(
t
):(20)
AER
t
=
∑
i
=
1
n
∑
j
=
1
m
P
M
p
i
j
>
b
i
n
×
t
.The average rejection rate of tasks in the cloud system with CFS at timet is expressed by AER
′
(
t
):(21)
AER
′
t
=
∑
i
=
1
n
∑
k
=
1
l
∑
j
=
1
m
P
M
p
i
k
j
>
b
i
n
×
t
.The average idle rate of servers in the cloud system with FS at timet is expressed by AUR
(
t
):(22)
AUR
t
=
∑
j
=
1
m
∑
i
=
1
n
∑
y
=
0
t
1
-
P
enabled
s
i
j
y
m
×
t
,where P
enabled
s
i
j
y means the probability that transition s
i
j
(
y
) can fire at time y.The average idle rate of servers in the cloud system with CFS at timet is expressed by AUR
′
(
t
):(23)
AUR
′
t
=
∑
j
=
1
m
∑
i
=
1
n
∑
k
=
1
l
∑
y
=
0
t
1
-
P
enabled
s
i
k
j
y
m
×
t
,where P
(
enabled
(
s
i
k
j
(
y
)
)
) means the probability that transition s
i
k
j
(
y
) can fire at time y.In a multiuser multiserver cloud system, the performance parameters include the state changes of waiting queues and the service rates of shared servers. The improvement of throughput and the decrease of response time can be realized by furthest parallelizing the operations ofn servers. In other words, load balance should be maintained.


## 4.4.1. Equivalent Refinement Model and Markov Model

In this section, we will make further use of enabling predicates and random switches of transitions to refine the model proposed above. Figure7 shows the equivalent model for models in Figures 5 and 6, while Figure 8 describes the equivalent Markov model of Figure 7.Figure 7
The refined DSSPN model of Figures5 and 6.Figure 8
The equivalent Markov model of Figure7.Comparing Figure7 with Figures 5 and 6, it can be found that the refined model is easier to understand and significantly reduces the state space by deleting any unnecessary vanishing states. In addition, refined model greatly decreases the complexity in performance evaluation because of structural similarities of submodels.In Figure7, immediate transitions and place p
i (or p
i
k) and related arcs are removed from Figure 5 (or Figure 6), where 1
≤
i
≤
n and 1
≤
k
≤
l. The enabling predicates and random switches associated with d
i
j and c
i
j (or d
i
k
j and c
i
k
j) have changed, while others are remaining the same. The random switch of transition c
i
j is defined as follows:(14)
g
i
j
M
:
λ
i
×
g
i
j
M
.The enabling switch of transitionc
i
k
j is(15)
g
i
k
j
M
:
λ
i
k
×
g
i
k
j
M
.


## 4.4.2. Parameters Analysis

In order to obtain the steady-state probabilities of all states, a state transition matrix can be constructed based on the state transition rate and Markov chain illustrated in Figure8. Then, the performance parameters of the modeled cloud system can be discussed. Let P
[
M
] denote the steady-state probability of M.The throughput of transitiont is denoted as T
t:(16)
T
t
=
∑
M
∈
H
P
M
×
λ
t
,where H is a set of all markings under which transition t is enabled with the enabling rate of λ
t in marking M.The average number of tokens in placep is denoted as N
p:(17)
N
p
=
∑
j
×
P
M
p
=
j
.The throughput is a crucial indicator of the system performance. LetT
i
j (or T
i
k
j) indicate the throughput of subsystem A
i
j (or A
i
k
j). According to the illustration in [16], the throughput of the model can be calculated as follows:(18)
T
=
∑
i
=
1
n
∑
j
=
1
m
T
s
i
j
or
T
=
∑
i
=
1
n
∑
k
=
1
l
∑
j
=
1
m
T
s
i
k
j
.Another important indicator is response time.R
i
j (or R
i
k
j), R
i, and R denote the response time of subsystem A
i
j (or A
i
k
j), client i, and the system, respectively:(19)
R
i
j
=
D
q
i
j
T
s
i
j
R
i
=
∑
j
=
1
m
T
s
i
j
×
R
i
j
∖
∑
h
=
1
m
T
s
i
h
R
=
∑
i
=
1
n
R
i
×
∑
h
=
1
m
T
s
i
h
T
R
i
k
j
=
D
q
i
k
j
T
s
i
k
j
R
i
k
=
∑
j
=
1
m
T
s
i
k
j
×
R
i
k
j
∖
∑
h
=
1
m
T
s
i
k
h
R
i
=
∑
k
=
1
l
T
s
i
k
×
R
i
k
∖
∑
h
=
1
l
T
s
i
h
R
=
∑
i
=
1
n
R
i
×
∑
h
=
1
l
T
s
i
h
T
.The average rejection rate of tasks in the cloud system with FS at timet is expressed by AER
(
t
):(20)
AER
t
=
∑
i
=
1
n
∑
j
=
1
m
P
M
p
i
j
>
b
i
n
×
t
.The average rejection rate of tasks in the cloud system with CFS at timet is expressed by AER
′
(
t
):(21)
AER
′
t
=
∑
i
=
1
n
∑
k
=
1
l
∑
j
=
1
m
P
M
p
i
k
j
>
b
i
n
×
t
.The average idle rate of servers in the cloud system with FS at timet is expressed by AUR
(
t
):(22)
AUR
t
=
∑
j
=
1
m
∑
i
=
1
n
∑
y
=
0
t
1
-
P
enabled
s
i
j
y
m
×
t
,where P
enabled
s
i
j
y means the probability that transition s
i
j
(
y
) can fire at time y.The average idle rate of servers in the cloud system with CFS at timet is expressed by AUR
′
(
t
):(23)
AUR
′
t
=
∑
j
=
1
m
∑
i
=
1
n
∑
k
=
1
l
∑
y
=
0
t
1
-
P
enabled
s
i
k
j
y
m
×
t
,where P
(
enabled
(
s
i
k
j
(
y
)
)
) means the probability that transition s
i
k
j
(
y
) can fire at time y.In a multiuser multiserver cloud system, the performance parameters include the state changes of waiting queues and the service rates of shared servers. The improvement of throughput and the decrease of response time can be realized by furthest parallelizing the operations ofn servers. In other words, load balance should be maintained.


## 5. Case Study and Evaluation

In this section, we provide a case to study the performance of the DSSPN model based on steady-state probabilities. To verify the applicability and feasibility of DSSPN, we only study some performance indicators of FS and CFS by means of the above method. In addition, Stochastic Petri Net Package (SPNP) is applied to automatically derive the analytic solution of performance for the DSSPN model. This is beneficial in modeling and evaluating the performance of cloud systems, because the number of states might reach thousands even only including few machines, shown in Table1.Table 2 describes the parameter settings in the simulation.Table 1
Number of states and fired transitions.
1 machine
2 machines
3 machines
4 machines
Reachable states
283
569
1088
1594
Fired transitions
923
1977
3928
5842Table 2
Parameter settings in simulation.
Algorithm
λ
2
/
λ
1
m
s
1
m
s
2
b
1
j
b
2
j
b
1
k
j
b
2
k
j
μ
1
j
μ
2
j
μ
1
k
j
μ
2
k
j
p
l
p
l
′
b
FS
2
/
3
3
4
10
8
3
2
30
CFS
2
/
3
3
4
10
8
3
2
2
1
30The simulation was conducted to the cloud system consisting of 3 servers, 2 customers, and 2 categories. That is, there are 4 waiting queues in FS, while 8 waiting queues are existing in CFS. Assumeg
(
s
1
)
=
1 and g
(
s
2
)
=
2. The task submitted by each client can be classified into 2 groups. In the simulation scenario, there are 4 VMs that can be running on server 1 simultaneously, while 5 VMs are running on server 2.As shown in Figure9, when the configuration parameters are identical, the values of system average throughput in steady state of CFS are significantly greater than that of fair scheduling. Figure 10 describes the average delay, which is depicted by average response time in DSSPN models, in steady state of CFS and FS. Apparently, the average delay of CFS is prominently smaller than that of fair scheduling. That is, CFS is a powerful way to decrease waiting time for users. As can be seen from Figure 9, the difference of average throughput between CFS and FS can reach 14.8 when λ
1
=
6
/
s
e
c, while the maximal difference of average delay between CFS and FS is 5.75 sec when λ
1
=
6
/
s
e
c.Figure 9
Average throughput whenλ
1
=
3,4
,
5,6
,
7.Figure 10
Average response time whenλ
1
=
3,4
,
5,6
,
7.Figure11 illustrates that average completion time of CFS is significantly better than that of FS. The simulation results present that the novel scheme (CFS) can efficiently increase the average system throughput and thus can improve utilization of resources. This means that it can realize economic benefits in the commercial cloud services.Figure 11
Average completion time whenλ
1
=
3,4
,
5,6
,
7.Moreover, Figures9, 10, and 11 also show that the performance of CFS is generally better than that of fair scheduling across all circumstances, especially at heavy load. However, queues cannot be simulated efficiently, because these schemes are only based on the current state of queues but ignore the dynamics of task in the queues. The simulation results are different by setting different input rates due to incapability of predicting the future state of the waiting queues.Figure12 shows how the average rejection rate of the cloud system changes as service time goes on. When the task request in one waiting pool is up to 30, the system will reject new requests submitted by the corresponding user. When 1
≤
t
≤
10, the average rejection rate of FS is higher than that of CFS. The differences between FS and CFS in the average rejection rate are up to 40.08% at service time of 5 seconds. In addition, Figure 12 also illustrates that, along with the operation of the cloud system, the average reject rate increases with the accumulation of backlogs in waiting queues.Figure 12
Average rejection rate at different service timet.Figure13 illustrates how the scheduling strategies affect the average resource utilization of the system. When 0
≤
t
≤
10, the average idle rate of servers in FS is lower than that in CFS. The maximal differences between FS and CFS in the average idle rate of servers at different service times are 4%. It means that there is potential to achieve higher utilization rate with CFS algorithm by increasing the system throughput.Figure 13
Average idle rate of servers at different service timet.


## 6. Conclusion

In this paper, we propose the definition of DSSPN that can easily describe the multiple clients systems based on cloud services, such as a typical cloud platform. The major motivation to model systems or processes by DSSPN is its simplicity and dynamic expressions to represent systems with multiple users and dynamic environments. Moreover, we further elaborate dynamic property of DSSPN and analyze some properties of DSSPN. In the following section, for some shortcomings of fair scheduling, the classified fair scheduling (CFS) algorithm is proposed taking into consideration jobs and resources diversity.In the real world, a typical cloud system is shared by multiple applications including production applications, batch jobs, and interactive jobs. Meanwhile, different applications have different requirements on hardware resources and QoS parameters. Therefore, we adopt the multiuser multiserver model to analyze the performance analysis and design DSSPN models for FS and CFS. In order to avoid the state space explosion, the analysis techniques and model refinement techniques are applied to performance evaluation of their DSSPN models. Finally, SPNP is used to obtain some key indicators of QoS; that is, system average throughput, response time, and average completion time are compared between the two schemes. Just as shown from Figures9–11, the performance of CFS is generally better than that of fair scheduling across all circumstances, especially at heavy load.The following topics are of high interest for future work:(1)
Other quality metrics, such as energy consumption and cost, should be analyzed.
(2)
The proposed model is without considering local task migrations among servers in the same data center.
(3)
The theoretical derivations between simulation results and actual cloud systems will be studied.



---

*Source: 9259248-2016-08-18.xml*