# Secure Partitioning of Cloud Applications, with Cost Look-Ahead
## 6 Partitioning with a Look Ahead on Migration Costs
### A Refined Probabilistic Cost Model
#### 6.1.4 Future Cost  
Fixing the maximum number of changes \(k\) and given a starting partitioning \(P_{0}\) that satisfies the initial labelling \(\mathcal{L}_{0}\), its cost is defined in Equation (18):  
\[Cost(P_{0})=\langle|P|,FutureCost(P_{0})\rangle\] \[FutureCost(P_{0})=\sum_{\mathcal{L}_{e}}P(\mathcal{L}_{0} \rightarrow_{k}\mathcal{L}_{e})\cdot C_{P_{0}P_{i}}\quad s.t.\quad P_{0} \rightarrow_{\mathcal{L}_{e}}P_{i} \tag{18}\]  
where \(FutureCost\) is the expected cost of migrating the partitioning \(P_{0}\) over all the possible labelling, considering the migration toward the partition \(P_{i}\) that satisfies the labelling as the best migration. The fact that the best migration is not unique does not bring a problem with the expected cost: only the value of the cost is considered and the partitioning with the best migration is not relevant.  
We give some intuitions for the complexity of calculating the \(FutureCost\) of all the partitioning that satisfy the initial labelling. The \(FutureCost\) search space of a single partitioning depends on  
\[\sum_{\mathcal{L}_{i}}\]  
and the number of labellings \(l\) is exponential in the number of data and characteristics:  
\[l=|L|^{dc}\]  
representing all the possible values that the labels of a labelling can assume.  
The number of partitionings satisfying the initial labelling depends on the application architecture. We consider the worst-case scenario where all the possible partitionings satisfythe initial labelling. The number of partitionings \(p\) is exponential in the number of software components \(n\) decreased by the partitioning dimension \(i\):  
\[p=\sum_{i=lb...n}\binom{n}{i}=\sum_{i=lb...n}\frac{n!}{i!(n-i)!}\]  
representing the sum of all the subsets of \(n\) with dimension \(i\) from \(lb\) (the lower bound of the number of domains needed) to \(n\) (every component is in a different domain).  
Thus, the overall search space is the combination of all the partitionings that satisfy the initial labelling and the number of possible labellings. To reduce this search space and be able to calculate the \(FutureCost\) of the partitioning of an application, we use two configurable parameters:  
* \(d\): the maximum number of domains admitted and
* \(k\): the number of possible changes admitted during the evolution of a labelling.  
The first element of the \(FutureCost\) pair is the number of domains of a partitioning. It does make sense to have an upper bound from the start to reduce the SK overhead. This upper bound is represented by \(d\). The search space of the number of partitionings \(p\) becomes  
\[p=\sum_{i=lb...d}\binom{n}{i}=\sum_{i=lb...d}\frac{n!}{i!(n-i)!}\]  
which is also exponential in the number of software components, but the decrease in the possible subsets is considerable. However, having a low value of \(d\) reduces the possibility of satisfying some of the labelling changes, increasing the probability of having a non-safely partitionable application.  
Concerning the limit to the number of label changes \(k\), it is straightforward that having a low value reduces exponentially the number of labellings reachable from the starting one, reducing the calculation of the \(FutureCost\). We emphasise a property of our probabilistic model. After fixing \(k\), the probability of reaching a specific labelling is guided by the single distribution of each label given by the variables \(X_{dc}\), i.e., the most probable reachable labelling is the one with the most probable values for each label.  
In Section 7 we assess how \(d\) and \(k\) impact the time to search safe partitionings and the probability of having a non-safely partitionable application.