# Popularity-Aware Service Provisioning Framework in Cloud Environment
## 4 Constrained MDP
### Transition Probability  
Since \(T\) denotes the remained contract time, only when \(T=0\) can allocated resource for the service \(i\) change based on the chosen action \(A_{i}\). That is, the transition of \(R_{i}\) is affected by \(T\) and \(A_{i}\). Meanwhile, the popularity of the service \(i\), \(P_{i}\), influences the incoming rate of the queue for the service \(i\). In addition, the allocated resources for the service \(i\), \(R_{i}\), affects the processing rate of the queue for that service. To sum up, the transition of \(Q_{i}\) is affected by \(P_{i}\) and \(R_{i}\). The other states transit independently with each other. Thus, the transition probability from the current state \(S\) to the next state \(S^{\prime}\) can be defined as  
\[P[S^{\prime}|S,A] = P[T^{\prime}|T]\times\prod_{i}P[R_{i}^{\prime}|R_{i},T,A_{i}] \times P[P_{i}^{\prime}|P_{i}]\times P[Q_{i}^{\prime}|Q_{i},P_{i},R_{i}] \tag{8}\]  
where \(T\) and \(T^{\prime}\) are the current and next states of the remaining contract time. In addition, \(R_{i}\), \(P_{i}\), and \(Q_{i}\) (or \(R_{i}^{\prime}\), \(P_{i}^{\prime}\), and \(Q_{i}^{\prime}\)) are the current (or next) states for the allocated resources, the popularity, and the queue length for the service \(i\), respectively. When the current contract time is over (i.e., \(T=0\)), the service provider requests the resources for the next contract period. Therefore, when \(T=0\), the next state for the remained contract time, \(T^{\prime}\), is always \(T_{D}\). \[P[T^{\prime}|T=0]=\left\{ \begin{array}{ll}1,&\text{if }T^{\prime}=T_{D}\\ 0,&\text{otherwise}.\end{array} \right. \tag{9}\]  
Meanwhile, when the current contract time is not over (i.e., \(T\
eq 0\)), the remained contract time decreases one by one. Thus, the corresponding transition probability can be represented as  
\[P[T^{\prime}|T\
eq 0]=\left\{ \begin{array}{ll}1,&\text{if }T^{\prime}=T-1\\ 0,&\text{otherwise}.\end{array} \right. \tag{10}\]  
The service provider periodically requests \(A_{i}\) resources for the provision of the service \(i\), and the request period is the contract time \(T_{D}\). That is, only when the current contract time is over (i.e., \(T=0\)) does the allocated resources for the service \(i\), \(R_{i}\), change according to the requested resources \(A_{i}\). Therefore, the corresponding transition probabilities can be described as  
\[P[R_{i}^{\prime}|R_{i},T=0,A_{i}]=\left\{ \begin{array}{ll}1,&\text{if }R_{i}^{ \prime}=A_{i}\\ 0,&\text{otherwise}\end{array} \right. \tag{11}\]  
and  
\[P[R_{i}^{\prime}|R_{i},T\
eq 0,A_{i}]=\left\{ \begin{array}{ll}1,&\text{if }R_{i}^{ \prime}=R_{i}\\ 0,&\text{otherwise}.\end{array} \right. \tag{12}\]  
It is assumed that the service processing rate for the service \(i\) with one resource unit follows an exponential distribution with the mean \(1/\mu_{i}\). Then, the probability that the service \(i\) is processed with the \(R_{i}\) resources within the time epoch \(\tau\) can be calculated as \(R_{i}\mu_{i}\tau\)[20]. Since the processing rate is proportional to the allocated resources \(R_{i}\), the probability that the service \(i\) is processed within the time epoch \(\tau\) is also proportional to the allocated resources \(R_{i}\). Meanwhile, the unit incoming rate \(\lambda\) is defined as the rate when the popularity of the service \(i\) is one. Then, the probability that the request for the service \(i\) with popularity \(P_{i}\) arrives at the corresponding queue within the time epoch \(\tau\) can be calculated as \(P_{i}\lambda\tau\)[20]. Based on these probabilities \(R_{i}\mu_{i}\tau\) and \(P_{i}\lambda\tau\), the corresponding transition probability can be defined as  
\[P[Q_{i}^{\prime}|Q_{i},P_{i},R_{i}]=\left\{ \begin{array}{ll}(1-P_{i}\lambda \tau)R_{i}\mu_{i}\tau,&\text{if }Q_{i}^{\prime}=Q_{i}-1\\ P_{i}\lambda\tau R_{i}\mu_{i}\tau+(1-P_{i}\lambda\tau)(1-R_{i}\mu_{i}\tau),& \text{if }Q_{i}^{\prime}=Q_{i}\\ P_{i}\lambda\tau(1-R_{i}\mu_{i}\tau),&\text{if }Q_{i}^{\prime}=Q_{i}+1\end{array} \right.