Preemptive cloud resource allocation modeling of processing jobs

Abstract

Cloud computing allows execution and deployment of different types of applications such as interactive databases or web-based services which require distinctive types of resources. These applications lease cloud resources for a considerably long period and usually occupy various resources to maintain a high quality of service (QoS) factor. On the other hand, general big data batch processing workloads are less QoS-sensitive and require massively parallel cloud resources for short period. Despite the elasticity feature of cloud computing, fine-scale characteristics of cloud-based applications may cause temporal low resource utilization in the cloud computing systems, while process-intensive highly utilized workload suffers from performance issues. Therefore, ability of utilization efficient scheduling of heterogeneous workload is one challenging issue for cloud owners. In this paper, addressing the heterogeneity issue impact on low utilization of cloud computing system, conjunct resource allocation scheme of cloud applications and processing jobs is presented to enhance the cloud utilization. The main idea behind this paper is to apply processing jobs and cloud applications jointly in a preemptive way. However, utilization efficient resource allocation requires exact modeling of workloads. So, first, a novel methodology to model the processing jobs and other cloud applications is proposed. Such jobs are modeled as a collection of parallel and sequential tasks in a Markovian process. This enables us to analyze and calculate the efficient resources required to serve the tasks. The next step makes use of the proposed model to develop a preemptive scheduling algorithm for the processing jobs in order to improve resource utilization and its associated costs in the cloud computing system. Accordingly, a preemption-based resource allocation architecture is proposed to effectively and efficiently utilize the idle reserved resources for the processing jobs in the cloud paradigms. Then, performance metrics such as service time for the processing jobs are investigated. The accuracy of the proposed analytical model and scheduling analysis is verified through simulations and experimental results. The simulation and experimental results also shed light on the achievable QoS level for the preemptively allocated processing jobs.

Appendices

Appendix A

Standard deviation of the ith workflow processing time is obtained by

$$\begin{aligned} \sigma _i =\left( {\left[ {\frac{\partial ^{2}\mathop {\prod }\nolimits _{r=1}^R \mathcal {P}\left( s \right) ^{N_r^i }}{\partial s^{2}}-\left( {\frac{\partial \mathop {\prod }\nolimits _{r=1}^R \mathcal {P}\left( s \right) ^{N_r^i }}{\partial s}} \right) ^{2}} \right] |_{s=0} } \right) ^{0.5} \end{aligned}$$

Proof

Parallel flow i delay is equal to,

$$\begin{aligned} d_T^i =\mathop {\sum }\limits _{r=1}^R \mathop {\sum }\limits _{j=1}^{N_r^i } T_{r\left( j \right) }^i \end{aligned}$$

where $N_r \left( i \right)$, $T_{r\left( j \right) }^i$ denote number of class r super-tasks of flow i and service time of the jth class r super-task of flow i. The probability distribution of service time of class r super-task, $p_{T_r } \left( t \right)$, is calculated in [30],

$$\begin{aligned} p_{(T_r )} (t)=r\mu e^{-\mu t}\mu (1-e^{-\mu t})^{r-1} \end{aligned}$$

Then, its associated Laplace transform is given by

$$\begin{aligned} \mathcal {P}\left( s \right) =\frac{s\varGamma \left( {r+1} \right) \varGamma \left( {\frac{s}{\mu }} \right) }{\mu \varGamma \left( {r+\frac{s}{\mu }+1} \right) }-1 \end{aligned}$$

where $\varGamma$ represents the gamma function. Then, Laplace transform of $d_T^i$ is l by

$$\begin{aligned} D_T^i \left( s \right) =\mathop {\prod }\limits _{r=1}^R \mathcal {P}\left( s \right) ^{N_r^i } \end{aligned}$$

Hence, the average of the $d_T^i$ is given by

$$\begin{aligned} E\left[ {d_T^i } \right] =-\frac{\partial D_T^i \left( s \right) }{\partial s}|_{s=0} =\mathop {\sum }\limits _{r=1}^R N_r^i \bar{T}_r \end{aligned}$$

Standard deviation of flow $i,\sigma _i$ also could be found by calculating

$$\begin{aligned} \sigma _i =\left( {\left[ {\frac{\partial ^{2}D_T \left( s \right) }{\partial s^{2}}-\left( {\frac{\partial D_T \left( s \right) }{\partial s}} \right) ^{2}} \right] |_{s=0} } \right) ^{0.5} \end{aligned}$$

Substituting $D_T \left( s \right)$ accomplishes the proof. $\square$

Appendix B

Lemma 1 Proof Average probability of task successful execution without failure is given by

$$\begin{aligned}&pr(task\,departure\,|\,no\,failure)pr\left( {no\,failure} \right) \\&\quad =\int pr(task\,departure\,|\,no\,failure)p_{x}(t)dt \end{aligned}$$

which id equal to

$$\begin{aligned} =\mathop {\int }\nolimits _0^{\infty } \mu e^{-\mu t}p_x (t)dt=\mathop {\int }\nolimits _0^{\infty } \mu e^{-\mu t}e^{-xt} dt=\frac{\mu }{\mu +x} \end{aligned}$$

$\square$

Proposition 1 Proof The average time that it takes for the failure to happen during time execution can be obtained through solving following integral,

$$\begin{aligned} \mathop {\int }\nolimits _0^\infty t\,pr (task\,execution\,|\,failure)pr\left( {failure} \right) dt \end{aligned}$$

By substituting $pr\left( {failure} \right) =xe^{-xt}$ and $pr(task\,execution\,|\,failure)=\mu e^{-\mu t}$, the average time for having a failure in the system is given by

$$\begin{aligned} \bar{\tau }_2 =\mathop {\int }\limits _0^\infty txe^{-xt}\mu e^{-\mu t}dt=\frac{x\mu }{\left( {x+\mu } \right) ^{2}} \end{aligned}$$

$\square$

Appendix C

Theorem 1 Proof PGF of the number of occupied CCRUs by stream tasks, $P\left( z \right)$ is given by

$$\begin{aligned} P\left( z \right) =e^{\int \frac{\varLambda \left( z \right) -\varLambda \left( 1 \right) }{\mu \left( {z-1} \right) }\partial z}=e^{\frac{-\sum \lambda _r \mathop {\sum }\nolimits _{i=1}^r \frac{1}{i}+\sum \lambda _r \mathop {\sum }\nolimits _{i=1}^r \frac{z^{i}}{i}}{\mu }} \end{aligned}$$

$\square$

Proof

Equilibrium equations in relation to Fig. 3, could be written as follows:

$$\begin{aligned} \left\{ \begin{array}{l@{\quad }l} \left( \mathop {\sum }\nolimits _{r=1}^R \lambda _r \right) p_0 =\mu p_1&{} k=0 \\ \left( {\mathop {\sum }\nolimits _{r=1}^R \lambda _r +k\mu } \right) p_k =\left( {k+1} \right) \mu p_{k+1} +\mathop {\sum }\nolimits _{r=1}^R p_{k-r} \lambda _r &{} k>0 \\ \end{array}\right. \end{aligned}$$

After multiplying to $z^{k}$ and summing over k, we have:

$$\begin{aligned}&\mathop {\sum }\limits _{k=1}^S \left( {\mathop {\sum }\limits _{r=1}^R \lambda _r +j\mu } \right) p_k z^{k}=\mathop {\sum }\limits _{k=1}^S \left( {k+1} \right) \mu p_{k+1} z^{k} +\mathop {\sum }\limits _{k=1}^\infty \mathop {\sum }\limits _{r=1}^R p_{k-r} \lambda _r z^{k} \end{aligned}$$

Taking out $z^{r}$ from the internal sigma leads to:

$$\begin{aligned}&\mathop {\sum }\limits _{k=1}^\infty \left( {\mathop {\sum }\limits _{r=1}^R \lambda _r +k\mu } \right) p_k z^{k}=\mathop {\sum }\limits _{k=1}^S \left( {k+1} \right) \mu p_{k+1}z^{k}+\left( {\mathop {\sum }\limits _{r=1}^R \lambda _r z^{r}\mathop {\sum }\limits _{k=r}^S p_{k-r} z^{k-r}} \right) \end{aligned}$$

Let us define $\varLambda \left( z \right) =\mathop {\sum }\nolimits _{r=1}^R \lambda _r z^{r}$ and $P\left( z \right) =\mathop {\sum }\nolimits _{k=0}^S p_k z^{k}$; then, with the substitution of the variable ${k}''$, we obtain:

$$\begin{aligned} \varLambda \left( 1 \right) \left( {P\left( z \right) -p_0 } \right) +z\mu p\left( z \right) =\mu \left( {P\left( z \right) -p_1 } \right) +\varLambda \left( z \right) P\left( z \right) \end{aligned}$$

(36)

(36) can be simplified to:

$$\begin{aligned} \left( {\varLambda \left( 1 \right) -\varLambda \left( z \right) } \right) P\left( z \right) +\left( {z-1} \right) \mu P\left( z \right) =\varLambda \left( 1 \right) p_0 -\mu p_1 \end{aligned}$$

(37)

From GBE it can be found that $\varLambda \left( 1 \right) p_0 -\mu p_1 =0$. Hence, after solving the first order differential equation,

$$\begin{aligned} P\left( z \right) =e^{\int \frac{\varLambda \left( z \right) -\varLambda \left( 1 \right) }{\mu \left( {z-1} \right) }\partial z} \end{aligned}$$

where $\frac{\varLambda \left( z \right) -\varLambda \left( 1 \right) }{z-1}=\frac{\mathop {\sum }\nolimits _{r=1}^R \lambda _r (z^{r}-1)}{z-1}=\mathop {\sum }\nolimits _{r=1}^R \lambda _r \left( {\mathop {\sum }\nolimits _{i=0}^{r-1} z^{i}} \right)$, the constant part of the PGF is obtained by applying the $P\left( z \right) |_{z=1} =1$ condition. Then we have,

$$\begin{aligned} P\left( z \right) =e^{\frac{\left( {-\mathop {\sum }\nolimits _{r=1}^R \lambda _r \mathop {\sum }\nolimits _{i=1}^r \frac{1}{i}} \right) +\left( {\mathop {\sum }\nolimits _{r=1}^R \lambda _r \mathop {\sum }\nolimits _{i=1}^r \frac{z^{i}}{i}} \right) }{\mu }} \end{aligned}$$

which completes the proof. $\square$