Task Admission Control and Boundary Analysis of Cognitive Cloud Data Centers

The cognitive DC center under investigation provides two services with service type (type-1: $T_{1}$) and batch type (type-2: $T_{2}$) of application task. $T_{1}$ is primary user (PU) and $T_{2}$ is secondary user (SU), each of which will require resources in the DC. A system work flow diagram is drawn in Fig. 1.

The other detailed assumptions for the cognitive DC are given as follows:

1. 1.

   There is a total number of C VMs defining the capacity of resources from the DCs, and two types of Tasks ($T_{1}$ and $T_{2}$) in the system will share those C VMs. $T_{1}$ is a type-$1$ task that is a time-sensitive service type task and needs a number of $b$ (here b is a given non-zero positive integer) VMs for service; $T_{2}$ is a type-$2$ task that is a specific application task and needs one VM for a sequence of operation steps. The $T_{1}$ task has a higher priority than the $T_{2}$ task as explained in the following items. Generally, since the system mainly provides service for $T_{1}$ tasks, it is always assumed that $C=bN_{1}$, where $N_{1}$ is a positive integer.

2. 2.

   The arriving process for tasks $T_{1}$ and $T_{2}$ are Poisson processes with rates $\lambda_{1}$ and $\lambda_{2}$, respectively. The task processing time for these tasks in one VM follows a negative exponential distribution with rates $\mu_{1}$ and $\mu_{2}$, respectively. If a $T_{1}$ task is processed with multiple $b$ VMs, the service rate would be $b\mu_{1}$ for that task.

3. 3.

   When a $T_{2}$ task comes to the system, the CSP will get it processed immediately when there is a VM available. However, if all VMs are busy, the CSP will decide whether to admit or reject the task based on the current number of type-1 and type-2 tasks in the system. The rejected tasks will leave the system. The admitted $T_{2}$ task will be put in a buffer waiting for the service whenever a VM is released for use. The waiting discipline in the buffer is ignored because the type-2 tasks in the buffer are indistinguishable. When a $T_{2}$ task completes the service, it will leave the system and the corresponding VM will be released for use by other tasks. When a $T_{2}$ task under processing is interrupted because of the arrival of a higher priority type-1 task, the interrupted $T_{2}$ task will be put in the buffer waiting for a new service whenever a VM is free to use.

4. 4.

   When a $T_{1}$ task comes to the system, let $n_{1}$ be the number of $T_{1}$ tasks currently in the system; the CSP will take different actions in the following two cases:

   1. (a)

      If $n_{1}<N_{1}$, provide the best service through allocating $b$ VMs for service, which includes the possibility of interrupting the service of several $T_{2}$ Tasks under processing;

   2. (b)

      If $n_{1}=N_{1}$, reject the $T_{1}$ task.

5. 5.

   In this paper, we focus on the admission control of a $T_{2}$ task. Admitting and then serving a $T_{2}$ task would contribute $R$ units of reward to the CSP. However, if a VM serving $T_{2}$ task is preempted by a higher priority $T_{1}$ task, there is a cost, say $r(r\geq 0)$, for that interruption. To hold the tasks in the system, the CSP needs to pay a holding price at a rate $f(n_{1},n_{2})$ to manage the VMs (resources) in the DCs when there are $n_{1}$ type-1 tasks in the process and $n_{2}$ type-2 tasks in the processing and in the buffer.

It is noteworthy to point put that some notations above, including $T_{1}$, $T_{2}$, $\lambda_{1}$ and $\lambda_{2}$, and $\mu_{1}$ and $\mu_{2}$, are used as the same as those in our recent work in [14] so that the audience may easily link up with our recent works in this area.

To better understanding all major given parameters in this paper, we summarize them in the Table I below:

Our objective in this research is to find the optimal policy such that the total expected discounted reward is maximized. In detail, if denote by $s_{t}$ the state at time $t$, $a_{t}$ the action to take at state $s_{t}$, and $r(s_{t},a_{t})$ for the reward obtained when action $a_{t}$ is selected at state $s_{t}$, our objective is to find an optimal policy $\pi_{\alpha}$ that can bring the maximum total expected discounted reward $v_{\alpha}^{\pi}(s)$ as defined below for every initial state $s$.

Here, a policy $\pi$ specifies the decision rule to be used at every decision epoch, $\alpha$ is the discount factor. It gives the decision maker a prescription for action selection for any possible future system state or history.

Based on the model description and above objective, we can now establish a Markov decision process as follows:

1. 1.

   Let’s define the state space of the system operating process as $S=\{s:s=(n_{1},n_{2})\}$, where integers $n_{1}$ and $n_{2}$ satisfy $N_{1}\geq n_{1}\geq 0$ and $n_{2}\geq 0$. The event space is defined by $E=\{D_{1},D_{2},A_{1},A_{2}\}$, where $D_{1}$ and $D_{2}$ means a $T_{1}$ and $T_{2}$ departure from the system after service, while $A_{1}$ means an arrival of a $T_{1}$ task, $A_{2}$ is an arrival of $T_{2}$ task. Since the states migration not only depends on the number of tasks in the system but also depends on the happening departure and arrival events, we will need to define a new state space as $\hat{S}=S\times E$. By doing so a state could be generally written as $\hat{s}=\langle s,e\rangle=\langle(n_{1},n_{2}),e\rangle$, where $n_{1}$ and $n_{2}$ are the numbers for $T_{1}$ and $T_{2}$ tasks, $e$ stands for the event which will probably happen on state $(n_{1},n_{2})$, $e\in\{D_{1},D_{2},A_{1},A_{2}\}$. Please be noticed that the specification of the event in this paper is one of major technical differences from that in paper [15], in which the event is assumed to happen before a state changes.

2. 2.

   Denote by $a_{C}$ as the action to continue, the action space for states $\langle(n_{1},n_{2}),D_{1}\rangle$ and $\langle(n_{1},n_{2}),D_{2}\rangle$ in the state space is then given by

   	$\displaystyle A_{\langle(n_{1},n_{2}),D_{1}\rangle}=\{a_{C}\},n_{1}>0;$
   	$\displaystyle A_{\langle(n_{1},n_{2}),D_{2}\rangle}=\{a_{C}\},n_{2}>0.$

   Similarly, in states $\langle(n_{1},n_{2}),A_{1}\rangle$ and $\langle(n_{1},n_{2}),A_{2}\rangle$, if denote by $a_{R}$ as the action to reject the request and $a_{A}$ as the action to admit, the action space will be

   	$\displaystyle A_{\langle(n_{1},n_{2}),A_{1}\rangle}=\{a_{R},a_{A}\};$
   	$\displaystyle A_{\langle(n_{1},n_{2}),A_{2}\rangle}=\{a_{R},a_{A}\}.$

3. 3.

   Let $C_{1}(n_{1})$ be the number of VMs occupied by $T_{1}$ tasks, $C_{2}(n_{1},n_{2})$ be the number of VMs occupied by $T_{2}$ tasks, $C_{v}(n_{1},n_{2})$ be the number of VMs serving $T_{2}$ tasks that will be pre-empted if admitting a $T_{1}$ task, sometimes simplified as $C_{1}$, $C_{2}$ and $C_{v}$ in this paper. From these definitions, it is easy to know that

   	$\displaystyle C_{1}(n_{1})$	$\displaystyle=$	$\displaystyle bn_{1},n_{1}\leq N_{1},$
   	$\displaystyle C_{2}(n_{1},n_{2})$	$\displaystyle=$	$\displaystyle\min{(C-C_{1}(n_{1}),n_{2})},$
   	$\displaystyle C_{v}(n_{1},n_{2})$	$\displaystyle=$	$\displaystyle\max{(C_{1}+C_{2}+b-C,0)},n_{1}<N_{1},$
   	$\displaystyle C_{v}(n_{1},n_{2})$	$\displaystyle=$	$\displaystyle 0,n_{1}=N_{1}.$

   The decision epochs are those time points when a call arriving or leaving the system. Based on our assumption, it is not too hard to know that the distribution of time between two epochs is

   $$F(t|\hat{s},a)=1-e^{-\beta(\hat{s},a)t},t\geq 0,$$

   where $\hat{s}=\langle((n_{1},n_{2})),b\rangle$. Denote by $s=(n_{1},n_{2})$ and $\beta_{0}(s)=\lambda_{1}+\lambda_{2}+C_{1}\mu_{1}+C_{2}\mu_{2}.$ Since a departure event only happens when there is a task in the system, the $\beta(\hat{s},a)$ will be represented for an action $a$ as

   $\displaystyle\left\{\begin{array}[]{ll}\beta_{0}(s)-b\mu_{1},&e=D_{1},a=a_{C},n_{1}>0,C_{2}=n_{2}\\ \beta_{0}(s)-b\mu_{1}+&e=D_{1},a=a_{C},n_{1}>0,n_{2}>C_{2},\\ \min{(n_{2}-C_{2},b)}\mu_{2},&\\ \beta_{0}(s)-\mu_{2},&e=D_{2},a=a_{C},C_{2}=n_{2}>0,\\ \beta_{0}(s),&e=D_{2},a=a_{C},n_{2}>C_{2},\\ \beta_{0}(s)+b\mu_{1},&e=A_{1},a=a_{A},C_{1}+C_{2}\leq C-b,\\ \beta_{0}(s)+b\mu_{1}-&e=A_{1},a=a_{A},\\ C_{v}\mu_{2},&C_{1}+C_{2}>C-b,n_{1}<N_{1}-1,\\ \lambda_{1}+\lambda_{2}+C\mu_{1},&e=A_{1},a=a_{A},n_{1}=N_{1}-1,\\ \beta_{0}(s)+\mu_{2},&e=A_{2},a=a_{A},C_{1}+C_{2}<C,\\ \beta_{0}(s),&e=A_{2},a=a_{A},C_{1}+C_{2}=C,\\ \beta_{0}(s),&e=\{A_{1},A_{2}\},a=a_{R}.\end{array}\right.$

4. 4.

   Let $q(j|\hat{s},a)$ denote the probability that the system occupies state $j$ in the next epoch, if at the current epoch the system is at state $\hat{s}$ and the decision maker takes action $a\in A_{\hat{s}}$. For the cases of departure events, e.g. for a departure event of $D_{1}$ under the condition of ($n_{1}>0$), $(\hat{s},a)=(\langle(n_{1},n_{2}),D_{1}\rangle,a_{C})$, if denote by $s_{n_{1}}=(n_{1}-1,n_{2})$, then we will have $q(j|\hat{s},a)$ as

   $\displaystyle\left\{\begin{array}[]{ll}\lambda_{1}/\beta_{0}(s_{n_{1}}),&j=\langle(n_{1}-1,n_{2}),A_{1}\rangle,\\ \lambda_{2}/\beta_{0}(s_{n_{1}}),&j=\langle(n_{1}-1,n_{2}),A_{2}\rangle,\\ C_{1}(n_{1}-1)\mu_{1}/\beta_{0}(s_{n_{1}}),&j=\langle(n_{1}-1,n_{2}),D_{1}\rangle,\\ C_{2}(n_{1}-1,n_{2})\mu_{2}/\beta_{0}(s_{n_{1}}),&j=\langle(n_{1}-1,n_{2}),D_{2}\rangle.\\ \end{array}\right.$

   Similar equations can be derived for case when $(\hat{s},a)=(\langle(n_{1},n_{2}),D_{2}\rangle,a_{C})$. If denote by $s_{n_{2}}=(n_{1},n_{2}-1)$ at the condition of $n_{2}>0$, we have $q(j|\hat{s},a)$ as

   $\displaystyle\left\{\begin{array}[]{ll}\lambda_{1}/\beta_{0}(s_{n_{2}}),&j=\langle(n_{1},n_{2}-1),A_{1}\rangle,\\ \lambda_{2}/\beta_{0}(s_{n_{2}}),&j=\langle(n_{1},n_{2}-1),A_{2}\rangle,\\ C_{1}(n_{1})\mu_{1}/\beta_{0}(s_{n_{2}}),&j=\langle(n_{1},n_{2}-1),D_{1}\rangle,\\ C_{2}(n_{1},n_{2}-1)\mu_{2}/\beta_{0}(s_{n_{2}}),&j=\langle(n_{1},n_{2}-1),D_{2}\rangle.\\ \end{array}\right.$

   For the cases of arrival events, such as $(\hat{s},a)=(\langle(n_{1},n_{2}),A_{1}\rangle,a_{A})$, and $(\hat{s},a)=(\langle(n_{1},n_{2}),A_{2}\rangle,a_{A})$, since admitting an incoming call migrates the system state immediately (adding one user or not), we will get $q(j|\hat{s},a)$ as

   $\displaystyle\left\{\begin{array}[]{ll}q(j|\langle(n_{1}+2,n_{2}),D_{1}\rangle,a_{C}),&e=A_{1},a=a_{A},\\ q(j|\langle(n_{1}+1,n_{2}),D_{1}\rangle,a_{C}),&e=A_{1},a=a_{R},\\ q(j|\langle(n_{1},n_{2}+2),D_{2}\rangle,a_{C}),&e=A_{2},a=a_{A},\\ q(j|\langle(n_{1},n_{2}+1),D_{2}\rangle,a_{C}),&e=A_{2},a=a_{R}.\end{array}\right.$

5. 5.

   Because the system state does not change between decision epochs, from Chp 11.5.2  [16] and our assumptions, the expected discounted reward between epochs satisfies

   	$\displaystyle r(\hat{s},a)$	$\displaystyle=$	$\displaystyle k(\hat{s},a)+c(\hat{s},a)E_{\hat{s}}^{a}\left\{\int_{0}^{\tau_{1}}e^{-\alpha t}dt\right\}$
   		$\displaystyle=$	$\displaystyle k(\hat{s},a)+c(\hat{s},a)E_{\hat{s}}^{a}\left\{[1-e^{-\alpha\tau_{1}}]/\alpha\right\}$
   		$\displaystyle=$	$\displaystyle k(\hat{s},a)+\frac{c(\hat{s},a)}{\alpha+\beta(\hat{s},a)},$

   where

   $\displaystyle k(\hat{s},a)=\left\{\begin{array}[]{cc}0,&e=\{D_{1},D_{2}\},a=a_{C},\\ 0,&e=\{A_{1},A_{2}\},a=a_{R},\\ -C_{v}r,&e=A_{1},a=a_{A},\\ R,&e=A_{2},a=a_{A}.\end{array}\right.$

   Also, we have the cost function $c(\hat{s},a)$ as

   $\displaystyle\left\{\begin{array}[]{cl}-f(n_{1}-1,n_{2}),&e=D_{1},a=a_{C},n_{1}>0,\\ -f(n_{1},n_{2}-1),&e=D_{2},a=a_{C},n_{2}>0,\\ -f(n_{1}+1,n_{2}),&e=A_{1},a=a_{A},n_{1}<N_{1},\\ -f(n_{1},n_{2}+1),&e=A_{2},a=a_{A},\\ -f(n_{1},n_{2}),&e=\{A_{1},A_{2}\},a=a_{R}.\end{array}\right.$

In the next section we will prove that there exists a state-related threshold for accepting the tasks if the cost function has some special properties.

Denote by a constant $c=\lambda_{1}+\lambda_{2}+C*\max(\mu_{1},\mu_{2})$, which is bigger than $[1-q(\hat{s}|\hat{s},a)]\beta(\hat{s},a)$. From Chp 11.5.2  [16], we know that there is a unique optimal solution of our model and this solution is also a stationary state-related control limit policy satisfying

By using above equation and also the uniformization technique described in  [16], we have

This means that

Similarly, it is easily found that

which shows the equality between different departure events. This leads us to define a new function $X(n_{1},n_{2})$ as below:

for any $n_{1}\geq 0$ and $n_{2}\geq 0$.

It is noticed that $X(n_{1},n_{2})$, is only related to the state, but not with the happening event. This observation will greatly simplify the needed proof processes in next several sections.

Similar as above results for a departure event, we can consider an arrival event and will get the following results:

and

From above equations, we can easily get

In fact, these two inequalities will be the equalities when the corresponding action $a_{A}$ or $a_{R}$ is the best action, respectively. From these analysis, it is not too hard to verify that

For the $T_{1}$ tasks, as the system always accepts them until all VMs are being used, we have

Before providing our major optimal result, we need to introduce a general result as below.

Lemma 1: Let $h(i)$ ($i\geq 0$) be an integer concave function, and denote by

for a given constant $R$. Then, $g(i)$ is also an integer concave function for $i\geq 0$.

Proof: Denote by $\Delta h(i)=h(i+1)-h(i)$ for any integer $i\geq 0$, we will prove this Lemma by considering the following three cases:

Case 1: If for any $i\geq 0$ , $\Delta h(i)\leq-R$. Thus, $g(i)\equiv h(i)$ and $g(i)$ is then concave.

Case 2: If for any $i\geq 0$, $\Delta h(i)\geq-R$. Thus, $g(i)\equiv R+h(i+1)$ and $g(i)$ is then concave.

Case 3: We now consider the case when both of above cases would not be true. In this case, we can first know that $\Delta h(1)\geq-R$. In fact, if it is not sure, i.e., if $\Delta h(1)\leq-R$, we can inductively verify that $\Delta h(i)\leq-R$ for any $i\geq 0$ by noting the assumption that $h(i)$ is an integer concave function.

Since $\Delta h(1)\geq-R$, $\Delta h(i)$ is decreasing because of the concavity of $h(i)$, and the Case 2 will not hold for all $i$ in this Case 3, there then must exist an integer $k\geq 1$ such that

From this analysis, we will know that for any $i\geq 0$,

The concavity of $g(i)$, i.e., $\Delta g(i)\leq 0$, is then verified by the concavity of $h(i)$, of a constant $-R$, and the following further notification for any $i\geq 1$:

Remark 1: It is worthy to point out that there is no condition for the given constant in the Lemma 1. This constant could be either negative or positive. In fact, we introduced this result in paper [17] for the case when the constant is non-positive, and in paper [14] for the case when the constant is non-negative. However, it is the first time in this paper that we point out this general result without any condition on the constant $R$ and also provide the mathematical verification.

Based on above Lemma 1 and the expression developed before Lemma 1, we can now provide and then verify the following major optimal result:

Theorem 1: If $f(n_{1},n_{2})$ is convex and increasing function on $n_{2}$ for any given $n_{1}$, the optimal policy is then a control limit policy. That means, for any state $(n_{1},n_{2})$, there must exist an integer, say $N_{2}$, such that decision

Proof: If all VMs are busy when an SU arrives at state $(n_{1},n_{2})$, we know that $C_{1}(n_{1})+n_{2}\geq C$ and then

Therefore

which is independent of $n_{2}$. Further, by using the notation of $X((n_{1},n_{2}))$, we can rewrite the equation (13) as below:

For any two-dimensional integer function $g(n_{1},n_{2})$ ($n_{1}\geq 0,n_{2}\geq 0$), we introduce the following definitions for $n_{1}$ and $n_{2}$, respectively:

From the observation in equation (27) and the equation (28), we will have

Next, by noting

and equation (21), we will have